[curves] Unifying public key formats

[Robert Ransom]

On 1/21/15, Trevor Perrin <trevp at trevp.net> wrote:
> On Wed, Jan 21, 2015 at 3:07 PM, Robert Ransom <rransom.8774 at gmail.com>
> wrote:
>> On 1/21/15, Trevor Perrin <trevp at trevp.net> wrote:
>>
>>> C) Full-format keys everywhere
>>> All public keys include the sign bit, so this is a true "unified
>>> format".  [...] Montgomery-ladder-only implementation will require
>>> an extra inversion, so key generation would be slowed by ~10%.
>>
>> It's not an extra inversion -- remember that inversions can easily be
>> batched using 'Montgomery's trick'.
>
> Good point, and Jivsov also described this [1].
>
> So the Montgomery ladder function could be modified to recover the
> Edwards x sign bit at very low cost.

Having to implement the formulas to recover a second coordinate is not
a 'very low' cost.

> Would you prefer this for a unified format, instead of using a
> single-coordinate format with the sign bit implied as zero (Jivsov) or
> encoded into signatures (your idea)?

If Mike Hamburg's single-coordinate point formats are ruled out for
whatever reason (backwards compatibility with an existing system or
existing keypairs, incompatibility of the sgn(y)/sqrt(x) format with
5mod8 fields, etc.), the best point format depends on the system in
which it will be used.

Since TextSecure had already deployed Curve25519 ECDH and its users
had already published public keys without the sign bit, the choice was
between adjusting each existing private key (as Jivsov suggested, but
done every time the private key is used for signing) and transmitting
the sign bit in some location other than the existing public-key
strings (either in each signature, where there is room for it, or in a
copy of the public key which accompanies the signature).

Tor provides two other examples of how to choose a point format well:

* Each Tor relay currently publishes a medium-term Curve25519 ECDH
public key in the 'ntor-onion-key' field of its relay descriptor.  If
Tor ever switches to a new circuit-extension protocol which relies on
the sign bit of a Curve25519 public key, the simplest way to transmit
that sign bit is for each relay which supports that new protocol to
begin including the sign bit of its key in the high bit of that same
field.  There would be no disadvantage to making relay implementations
which include that high bit distinguishable from others (since the
protocol would identify those relays in other ways), and there is no
need to support use of an ECDH public key published by an old
implementation with the new protocol.

* Tor's future hidden service protocol will need to contain enough of
an ECC public key in each HS address that a client can perform a
scalar multiplication on that public key; accordingly, it must at
least contain something from which a Montgomery-form x coordinate can
be computed.  Each HS descriptor must contain a full blinded public
key sufficient to verify a signature, as well as a signature of the
descriptor.  For Curve25519, I suggested using the Montgomery-form x
coordinate *only* as the HS address, since (a) that coordinate can be
represented in only 51 base32 characters, and including another bit in
the address would have increased that to 52 characters; (b) there is
existing software to perform scalar multiplication on a
Montgomery-form x coordinate, much of which is faster than anything I
could have written for the purpose; and (c) the HS address, and the
blinded address sent to the server in order to request the HS's
current descriptor, only need to be sufficient to recognize the HS's
full blinded public key.  (My advice was ignored.)


I hope that Mike Hamburg's new point format will eliminate the need
for this level of careful design, at least for new systems.


Robert Ransom