[curves] Another try at point compression

[Michael Hamburg]

> On Dec 22, 2014, at 6:44 PM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> 
> On 12/22/14, Michael Hamburg <mike at shiftleft.org> wrote:
>> 
>>> On Dec 22, 2014, at 5:07 PM, Robert Ransom <rransom.8774 at gmail.com>
>>> 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".)

>>> 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
> 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?  In the Curve25519 case it’s about the curve’s cofactor being larger than the twist’s cofactor.

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.

> If the field order is congruent to 1 mod 4, then curve cofactor 4
> implies twist cofactor 8 (at least), so strong twist security with
> this format requires that secret-key scalars be divisible by 2 (or
> more) rather than 1.
> 
> 
> I'm assuming that strong twist security remains necessary with this
> point format.  If twist security isn't necessary -- in the sense that
> the output step after a Montgomery-ladder scalarmult is *guaranteed*
> to fail for inputs on the twist, even if the ladder's output is zero,
> infinite, or invalid ((0 : 0)) -- then I think my objections can be
> eliminated by choosing the curve well.

I think you can guarantee this — at least for some encodings, if not the one I suggested earlier — but I haven’t worked it out yet.  And it will probably add complexity, so that’s a downside.  Maybe sometime this vacation.

Cheers,
— Mike

>>> Any implementation of signing
>>> would already need to reduce scalars modulo the group order (in order
>>> to compute s), so that bit of extra complexity won't hurt signature
>>> software, but it sucks for ECDH.  Curve25519 remains better for ECDH.
>> 
>> I also don’t understand this statement.  Is this assuming that the fancy
>> point format is only odd-ladderable with the Montgomery ladder?  (Which it
>> might be…)
> 
> I'm strictly talking about the key-generation annoyances.  And I guess
> I mean “Curve25519 remains better for ECDH-only implementations.”; if
> you're already implementing signing, ECDH won't be any worse.
> 
> 
> Robert Ransom