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@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves