[curves] qDSA signatures

[Mike Hamburg]

Hello Joost and Ben,

This is cool work!  I like that you did hyperelliptic Kummer surfaces too.
I have a few questions about it.

Do you run into any problems where x:z = 0:0 in any of the formulas?  That
would make Check always return true, but maybe it can’t happen?

Likewise, do you run into any problems if one of the points is on the twist?
It might be that eg Q is on the twist but [c]Q = small torsion point is on both the
curve and the twist, and so the verification goes through.  But maybe it’s hard
to cause this so the proof works anyway.

Do you know a good way to make the signature nonmalleable?  I settled for
malleable ones in STROBE, but it would be neat if there were a way to make
it nonmalleable.

Finally, are you sure that your trick of setting c <- Z_N+ is necessary?  It
seems to me that the probability that c1 = -c2 is negligible anyway, so the
proof would work just as well without this modification.  In that case, your
proof would probably cover STROBE’s implementation as well, except
that STROBE depends on the hash’s collision resistance.

Cheers,
— Mike

> On Jun 6, 2017, at 8:46 AM, Joost Renes <j.renes at cs.ru.nl> wrote:
> 
> 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
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3571 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170606/8585d634/attachment.bin>