[curves] Isogeny patterns among Edwards curves

[Robert Ransom]

On 1/30/14, Michael Hamburg <mike at shiftleft.org> wrote:
>
>
> On Jan 30, 2014, at 11:38 AM, Watson Ladd <watsonbladd at gmail.com> wrote:
>
>> On Thu, Jan 30, 2014 at 9:08 AM, Robert Ransom <rransom.8774 at gmail.com>
>> wrote:

Just to clarify: the following paragraph is Watson Ladd's.  (You
didn't quote anything that I wrote in this message.)

>> There is also a bigger problem: each encoding and decoding doubles the
>> point. This is fine for ECDH, but makes signatures ugly.




> Compare this to a coordinate+signbit encoding, where to check the sign bit
> (not suuuuuper necessary, but a good idea for strictness) you have to do a
> division at the end.  Or if the sign bit is a Legendre symbol, you have to
> compute that symbol.  So in total, signature checking is not much more
> complicated or expensive with the x/y encoding than it is with
> coordinate+signbit.

That's an important point.


> Likewise, in the Elligator PAKE, you have to compute wire+elligator, and
> eventually serialize to wire again, which (as things stand) costs at least 1
> square root, 1 Legendre and 1 inversion in addition to the elligator and the
> scalarmul.  This is compared to just a square root and an inversion for a
> coordinate+signbit representation.
>
> So, maybe it's not good enough *yet*, because it adds moderate slowdowns to
> batch-verify and Elligator PAKE.  But it doesn’t really slow down ECDH,
> signing or single-verify, which is pretty good for a trick I’ve been working
> on since yesterday.

* Anyone who is using the Elligator trick (by which I specifically
mean generation of keypairs for which the public key can be
represented in a form indistinguishable from a uniform random
bitstring, and not use of the Elligator maps in hash-to-group-element
functions) in a protocol doesn't care that darn much about backwards,
or even sideways, compatibility.

* Anyone who wants to use the Elligator trick and doesn't care about
being compatible with other protocols can specify that the
shared-secret point is a Montgomery-form x coordinate only (as with
current Curve25519 ECDH implementations), so the existence and use of
this point format in other contexts doesn't hurt them.


>> I think any encoding should be able to represent the entire curve,
>> without nasty problems like this.
>
> Aside from performance concerns, do you think it’s actually a problem if the
> encoding fails to faithfully convey points, by destroying the difference
> between P and P+(point of order 2)?

It destroys the difference between P and Phi+P, where Phi is a
non-rational point and can't be represented in any other format that
has been discussed.

Using Montgomery-form x instead of Edwards-form y already smashes the
distinction between the identity and a (different) point of order 2.
There was serious discussion about adding that rational point of order
2 in order to save the extra bit; this proposal is cleaner.


>> Yes, it's surmountable, but what
>> does this idea have over a regularly compressed Edwards point?

> What this has vs a coordinate+signbit compressed Edwards point is that you
> can use the Montgomery ladder without destroying the sign bit, and without
> paying more than a few muls extra to compute it.  This is nice for a
> protocol which wants to do a scalar mul but cares about the sign that comes
> out afterwards.  Dragonfly does exactly this.  I know that neither of us
> loves Dragonfly, but there may be other protocols that care about this sort
> of thing.

This benefit seems relevant to SPAKE2 as well.


> What’s more, this is the first suggestion for a unified point format which
> might reduce complexity instead of increasing it.  But only if I can work
> out a nice decompression algorithm.

You've probably noticed this already, but someone should say it
anyway: this is exactly the same format as your earlier proposal to
send 1/sqrt(u), but now you've found out how to avoid computing a
square root during encoding (as well as other clear benefits).


> Also, it might dodge patents, but that probably doesn’t matter if the
> patents are expiring in July anyway.

The patent on point compression was never valid.

It would be nice to escape the cloud of FUD around point compression,
but it's not necessary.



Robert Ransom