QDSA: Small and secure digital signatures with curve-based diffie–hellman key pairs

Joost Renes; Benjamin Smith

doi:10.1007/978-3-319-70697-9_10

QDSA: Small and secure digital signatures with curve-based diffie–hellman key pairs

Joost Renes
, Benjamin Smith

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 ± 1. 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.

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings
Editors	Tsuyoshi Takagi, Thomas Peyrin
Publisher	Springer Verlag
Pages	273-302
Number of pages	30
ISBN (Print)	9783319706962
DOIs	https://doi.org/10.1007/978-3-319-70697-9_10
Publication status	Published - 1 Jan 2017
Externally published	Yes
Event	23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017 - Hong Kong, Hong Kong Duration: 3 Dec 2017 → 7 Dec 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10625 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017
Country/Territory	Hong Kong
City	Hong Kong
Period	3/12/17 → 7/12/17

Keywords

Curve25519
Diffie–Hellman
Elliptic curve
Hyperelliptic curve
Kummer
Signatures

Access to Document

10.1007/978-3-319-70697-9_10

Cite this

Renes, J., & Smith, B. (2017). QDSA: Small and secure digital signatures with curve-based diffie–hellman key pairs. In T. Takagi, & T. Peyrin (Eds.), Advances in Cryptology – ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings (pp. 273-302). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10625 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-70697-9_10

Renes, Joost ; Smith, Benjamin. / QDSA : Small and secure digital signatures with curve-based diffie–hellman key pairs. Advances in Cryptology – ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings. editor / Tsuyoshi Takagi ; Thomas Peyrin. Springer Verlag, 2017. pp. 273-302 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{bf2bcd08099c4dfbb1d7a7cd1e3c9c9a,

title = "QDSA: Small and secure digital signatures with curve-based diffie–hellman key pairs",

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 ± 1. 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.",

keywords = "Curve25519, Diffie–Hellman, Elliptic curve, Hyperelliptic curve, Kummer, Signatures",

author = "Joost Renes and Benjamin Smith",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2017.; 23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017 ; Conference date: 03-12-2017 Through 07-12-2017",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/978-3-319-70697-9\_10",

language = "English",

isbn = "9783319706962",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "273--302",

editor = "Tsuyoshi Takagi and Thomas Peyrin",

booktitle = "Advances in Cryptology – ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings",

}

Renes, J & Smith, B 2017, QDSA: Small and secure digital signatures with curve-based diffie–hellman key pairs. in T Takagi & T Peyrin (eds), Advances in Cryptology – ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10625 LNCS, Springer Verlag, pp. 273-302, 23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017, Hong Kong, Hong Kong, 3/12/17. https://doi.org/10.1007/978-3-319-70697-9_10

QDSA: Small and secure digital signatures with curve-based diffie–hellman key pairs. / Renes, Joost; Smith, Benjamin.
Advances in Cryptology – ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings. ed. / Tsuyoshi Takagi; Thomas Peyrin. Springer Verlag, 2017. p. 273-302 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10625 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - QDSA

T2 - 23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017

AU - Renes, Joost

AU - Smith, Benjamin

N1 - Publisher Copyright: © International Association for Cryptologic Research 2017.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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 ± 1. 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.

AB - 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 ± 1. 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.

KW - Curve25519

KW - Diffie–Hellman

KW - Elliptic curve

KW - Hyperelliptic curve

KW - Kummer

KW - Signatures

U2 - 10.1007/978-3-319-70697-9_10

DO - 10.1007/978-3-319-70697-9_10

M3 - Conference contribution

AN - SCOPUS:85037830701

SN - 9783319706962

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 273

EP - 302

BT - Advances in Cryptology – ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings

A2 - Takagi, Tsuyoshi

A2 - Peyrin, Thomas

PB - Springer Verlag

Y2 - 3 December 2017 through 7 December 2017

ER -

Renes J, Smith B. QDSA: Small and secure digital signatures with curve-based diffie–hellman key pairs. In Takagi T, Peyrin T, editors, Advances in Cryptology – ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings. Springer Verlag. 2017. p. 273-302. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-70697-9_10

QDSA: Small and secure digital signatures with curve-based diffie–hellman key pairs

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this