[curves] Another try at point compression

[Robert Ransom]

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.


>> 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.

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.


>> 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