[curves] XEd25519

[Pelayo Bernedo Azpiri]

The XEd25519 signature method creates signatures compatible with Ed25519
using X25519 keys. If the sign bit of the public key is negative then the
private scalar used for signing is negated in order to obtain a positive
public key. The Ed25519 specification requires that the private scalars
have bit 254 set and the lower 3 bits cleared. This makes the private
scalar a multiple of the cofactor. Private scalars obtained by negating a
private X25519 key that already includes the bit masking do not conform to
this Ed25519 requirement. From my very limited understanding it seems that
this is not a problem for the single signature verification as defined in
XEd25519. Ed25519 also defines batch signature verification. Batch
verification is 3 times faster than single signature verification (at least
in the ed25519-donna implementation). Therefore there is an incentive for
an Ed25519 implementation to use batch verification whenever applicable.
Given that XEd25519 signatures are compatible with Ed25519, can they be
used with Ed25519 batch verification? What are the security considerations
of not conforming to the bit masking required by Ed25519?

The specification for the XEd25519 verification states that the X25519
public key shall be converted to an Ed25519 public key (the convert_mont
routine). Instead of this conversion, it could mention the direct
decompression from Montgomery u to Edwards as shown in
https://moderncrypto.org/mail-archive/curves/2015/000376.html (also by the
same author as the XEdDSA specification). I have implemented this based on
ed25519-donna and there is no measurable difference in the time required
for verification of signatures using compressed Montgomery or compressed
Edwards points.

XEd25519 signatures are fully compatible with Ed25519 signatures. If the
requirement of Ed25519 compatibility is dropped and the only goal is to be
able to use X25519 keys for signing and verifying, then the computation of
the hash(R || A || M) can be done with the X25519 public key instead of the
Ed25519 public key. This still ties the message to the public key as
explained in
https://www.ietf.org/mail-archive/web/cfrg/current/msg07335.html. Using the
public X25519 key would avoid the need to keep the public Ed25519 key for
signing and would also eliminate the need for caching it. Using the X25519
public key in hash(R || A || M) together with the direct decompression from
Montgomery coordinates would remove all mentions of the Ed25519 public
keys, simplifying key management.

An alternative method for generating signatures with X25519 keys was
proposed in https://moderncrypto.org/mail-archive/curves/2014/000293.html
(by the same author as the XEdDSA specification). In this proposal the sign
bit is stored in the signature. The method is otherwise identical to
Ed25519, except that it allows the attacker to choose the sign bit. In this
proposal all private scalars comply with the bit masking requirements of
Ed25519. How does this scheme compare to XEd25519? It would allow batch
verification but it is not clear to me if allowing an attacker to choose
the sign bit would somehow offer a practical attack.

Pelayo.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161120/6d44f75b/attachment.html>