[curves] qDSA signatures

[Joost Renes]

Hi all,

Yesterday Ben Smith and I have published a draft of our recent research
on an x-only signature scheme, which we named qDSA (short for quotient
Digital Signature Algorithm). It can be found here:

http://eprint.iacr.org/2017/518.pdf,

with accompanying code at http://www.cs.ru.nl/~jrenes/.

One of the main benefits is that it removes the need to switch between
DH keys (eg. Curve25519 keys) and EdDSA keys (eg. Ed25519 keys). This
can be done by only minor modifications to the EdDSA scheme, essentially
by doing verification "up to sign". We provide a relatively standard
proof of security to gain confidence in its security.

Initially, this was motivated by the goal of reducing stack usage in the
genus 2 signature scheme by CCS [A], which we implemented on
microcontrollers [B]. In this case, converting between the Kummer
surface and the Jacobian is particularly expensive, so we want to avoid
this. We define qDSA by altering EdDSA in such a way that such
conversions are completely unnecessary, and dedicate much of the paper
to showing how one could implement this efficiently. The main
complication to overcome is signature verification, where seemingly a
group operation would be necessary.

Perhaps more interestingly, qDSA can also be instantiated with
Curve25519 (\S3 of the paper). The result is a signature scheme for
which key pairs are equal to X25519 key pairs, and where any conversion
to the (twisted) Edwards form is obsolete. Unsurprisingly, it ends up
being quite close to Mike Hamburg's Strobe [C] implementation, but with
the added benefit of having a proof of security.

Since almost all arithmetic needed in qDSA is identical to that used in
X25519, this allows for especially compact and memory-friendly
implementations. On the other hand, a small loss of efficiency in
verification is expected. Its main use would be for memory-constraint
environments, but it may extend beyond that.

We would be very interested and happy to hear any comments, feedback, or
questions that you might have.

Kind regards,
Joost

[A] Chung et al., http://eprint.iacr.org/2016/777.pdf

[B] R. et al., http://eprint.iacr.org/2016/366.pdf

[C] Hamburg, http://eprint.iacr.org/2017/003.pdf