Paper 2017/518

qDSA: Small and Secure Digital Signatures with Curve-based Diffie-Hellman Key Pairs

Joost Renes and Benjamin Smith

Abstract

qDSA is a high-speed, high-security signature scheme that facilitates implementations with a very small memory footprint, a crucial requirement for embedded systems and IoT devices, and that uses the same public keys as modern Diffie--Hellman schemes based on Montgomery curves (such as Curve25519) or Kummer surfaces. qDSA resembles an adaptation of EdDSA to the world of Kummer varieties, which are quotients of algebraic groups by \(\pm1\). Interestingly, qDSA does not require any full group operations or point recovery: all computations, including signature verification, occur on the quotient where there is no group law. We include details on four implementations of qDSA, using Montgomery and fast Kummer surface arithmetic on the 8-bit AVR {ATmega} and 32-bit ARM Cortex~M0 platforms. We find that qDSA significantly outperforms state-of-the-art signature implementations in terms of stack usage and code size. We also include an efficient compression algorithm for points on fast Kummer surfaces, reducing them to the same size as compressed elliptic curve points for the same security level.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2017
Keywords
SignaturesKummerCurve25519Diffie--Hellmanelliptic curvehyperelliptic curve
Contact author(s)
j renes @ cs ru nl
History
2018-01-08: last of 2 revisions
2017-06-05: received
See all versions
Short URL
https://ia.cr/2017/518
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/518,
      author = {Joost Renes and Benjamin Smith},
      title = {qDSA: Small and Secure Digital Signatures with Curve-based Diffie-Hellman Key Pairs},
      howpublished = {Cryptology ePrint Archive, Paper 2017/518},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/518}},
      url = {https://eprint.iacr.org/2017/518}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.