Using torsion safe scalars for ed25519.

[durgesh-pandey]

Added new method for torsion safe scalar from big int and Checks for torsion safe properties and test.

[survived]

Hi @durgesh-pandey, thanks for contribution!

Correct me if I'm wrong - from what I understood from the thread you pointed out in the code, the purpose of safe representation is to protect against accident multiplication by torsion point. More formally, if a' is Torsion-safe representation of a, then a = a' (mod l) and a G = a' G, but a' T = 0 so multiplication at T doesn't leak any information.

curv library is protected against accident multiplication at T, more specifically any Point is guaranteed to have no T component (see guarantees section).

Is there any other reason to have conversion to Torsion-safe representation?

[durgesh-pandey]

Hey @survived , thanks for having a look at this.

You are right on the points you mentioned about torsion-safe representatives. Apart from this, using a torsion-safe representative as a scalar for ed25519 may remove some of the bit clamping requirements along with having properly defined arithmetic operations that bit clamping may not have. This also helps in HKD. Even though HKD can be implemented on bit clamped scalars in BIP32 style, there have been some concerns about its security. For more details, have a looks at this issue from ed25519 and links in discussion: https://github.com/ZenGo-X/multi-party-eddsa/issues/4

[survived]

I see the point — you need safe representation to replace bit clamping. The only property that safe representation may provide is protection against multiplication at Torsion base. We covered this case in the lib. Why not just remove bit clamping?

[durgesh-pandey]

I think main problem arises in HD key derivation. As mentioned at 1 & 2 (not accessible right now), when you allow Long path key derivation (following methods similar to BIP32 ED25519 3), overflow may occur, at that point either you choose to stop deriving new keys in that path (this check should be properly added in key derivation logic, still it limits the key which can be derived in a path) or choose to do mod l or mod 2^256 operations, both of which leads to some form of key recovery attacks. Doing mod 8l is properly defined and torsion safety essentially implements that allowing proper HD key derivation in a given path.

[survived]

Sounds good, but all the operations are still mod \ell, not mod 8\ell — ie. any arithmetic operation with torsion safe scalar produces scalar mod \ell. Do I correctly understand that we need to enable arithmetic mod 8\ell to have profit from torsion safe scalars?

[survived]

Currently torsion safe scalars contradict with the design of the library. Specifically, ECScalar must be mod group_order (ie. mod \ell), that's stated in the documentation. In order to add torison safe scalars, we need to redesign scalars, properly define arithmetic, comparison, etc.

Having scalars mod 8\ell is tricky, eg. consider comparison: since scalars are mod 8\ell, it's possible to construct 8 different representation of the same scalar, they behave similarly in arithmetic, but they are actually different. Currently, in order to test equality of two scalars, we just compare their memory representation. With scalars mod 8*\ell, we will have to take both scalars mod \ell first (assuming that arithmetic&comparison remains to be mod \ell).

[durgesh-pandey]

Yes, you are right. That's why when we use the torsion safety property, it is recommended to choose only torsion safe scalar every time we choose an ed25519 scalar, i.e. when a scalar is given or need to be chosen or resulted from an operation, it is required to convert it to torsion safe representative and then use it. We added torsion safe property in our internal code which is forked from the very old version of your curv lib and that's why I created this PR for you guys' convenience after the discussion in the issue thread for the ed25519 crate I mentioned above. It's your decision to merge it in lib or keep it for later or simply discard it if no torsion safety feature is going to be added in this lib.