[curves] Another try at point compression

[Robert Ransom]

On 12/24/14, Michael Hamburg <mike at shiftleft.org> wrote:
>
>> 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".)

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