Joost Renes

2017-06-06 15:46:36 UTC

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

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