On 12/24/14, Michael Hamburg <[email protected]> wrote: > >> On Dec 22, 2014, at 6:44 PM, Robert Ransom <[email protected]> >> wrote: >> >> On 12/22/14, Michael Hamburg <[email protected]> wrote: >>> >>>> On Dec 22, 2014, at 5:07 PM, Robert Ransom <[email protected]> >>>> wrote: >>>> >>>> No, this is the same sort of ‘hazard elimination’ that Dr. Bernstein >>>> has been advocating (and implementing), e.g. with Curve25519 ECDH. >>> >>> That’s the idea, though obviously the added complexity hurts. >> >> Having to compute a square root for every point encoded is the real >> drawback -- with the ‘simple’ point formats, one can batch the final >> inversion over multiple keygen/signing operations. I consider >> complexity of the ‘use these formulas, and if you don't do them right >> your software won't work at all’ sort to be much less problematic. > > Ah, this is true. There are batchable variants, notably “Edwards y such > that x and y are even”, but I don’t know of a batchable variant which also > makes the twisted curve safe everywhere. > > Maybe a compromise would be “preimage under some 2-isogeny such that x and y > are even”. This might allow batched signing where you scalarmul by nonce/2 > and then apply the isogeny, which avoids the square root, even though you > can’t always batch encoding. Furthermore, using “even” instead of “square" > might avoid some problems with the Montgomery ladder, at the cost of making > Edwards serialization more complicated. (For example, it might allow cheap > twist rejection in the Montgomery ladder, which would complete the design > goal of “accept no inputs which cannot be outputs".)
On further thought, the formulas you posted at the beginning of this thread should allow nearly batched encoding (one Legendre symbol per encoding plus one inversion), which is close to good enough. >>>> It's too bad that this point format will require cofactor 4 (although >>>> there are good mathematical reasons for that) -- that either makes key >>>> generation more complicated or decreases the secret key length by an >>>> extra bit (regardless of the field). >>> >>> I don’t understand this point. Why does cofactor 4 make key generation >>> more >>> complicated? >> >> If the field order is congruent to 3 mod 4, then curve cofactor 4 >> implies twist cofactor 4, so ‘twist security’ (in the strong sense >> that every scalar which acts as non-zero on the curve also acts as >> non-zero on the twist, not necessarily in the more general sense that >> Dr. Bernstein has also used) requires that the curve cofactor be Oops. I meant “curve order”, not “curve cofactor”, here. >> slightly less than the field order (and thus slightly less than a >> power of 2 with every form of special prime currently being >> considered). (I'll call this version of twist security “strong twist >> security” in this message; I don't know whether that's a good term to >> use for this property in general.) That requires that key generators >> either (a) compare against and/or reduce modulo the curve subgroup >> order, or (b) generate keys one bit shorter than the curve subgroup >> order (to use Curve1174 as an example, the curve subgroup order is >> 2^249-something; keys could be generated as 2^247 + 247-bit number). >> One could stop setting the high bit of a scalar to compensate for this >> somewhat, although then there's the faint possibility of generating >> zero itself as a secret key. > > What attacks does your strong twist-security prevent? Surely an attack > which depends on the secret key being exactly the order of the twist has > negligible probability of success anyway? I don't know of any specific attacks, but keep in mind that not all scalars are secret keys, and not all non-secret-key scalars are completely public either. I mainly don't want to have to think about the possibility of some non-zero scalar acting on a non-zero point (in the Montgomery ladder) to produce a zero result -- that's an undesirable property which a protocol designer shouldn't have to think about. > In the Curve25519 case it’s about > the curve’s cofactor being larger than the twist’s cofactor. That's the other case I considered (field congruent to 1 mod 4). > However, designers often spec the curve's order as being smaller than the > twist’s order or at least smaller than a power of 2 — I did this for > Ed480-Ridinghood — because that way you don’t need one extra bit for the > scalars. Yes. (Strong twist security requires that the curve subgroup order be less than the twist subgroup order, and a golden trinomial field makes it likely (but doesn't guarantee) that both curve and twist orders will be less than the smallest power of 2 greater than the field order.) I think my objections here are invalid after all -- in both Curve1174 and Curve25519, if one wants to (a) generate secret keys solely by masking a sequence of random bits, (b) ensure that the high bit is in a fixed location, and (c) ensure that all secret-key scalars act as non-zero on all input points, there are n-4 secret scalar bits, over an n-bit field. I would prefer to use n-3 secret bits on Curve1174, but that requires a more complicated secret key generation process which someone will screw up (e.g. by using memcmp). Robert Ransom _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
