Paper 2016/963

Efficient compression of SIDH public keys

Craig Costello, David Jao, Patrick Longa, Michael Naehrig, Joost Renes, and David Urbanik

Abstract

Supersingular isogeny Diffie-Hellman (SIDH) is an attractive candidate for post-quantum key exchange, in large part due to its relatively small public key sizes. A recent paper by Azarderakhsh, Jao, Kalach, Koziel and Leonardi showed that the public keys defined in Jao and De Feo's original SIDH scheme can be further compressed by around a factor of two, but reported that the performance penalty in utilizing this compression blew the overall SIDH runtime out by more than an order of magnitude. Given that the runtime of SIDH key exchange is currently its main drawback in relation to its lattice- and code-based post-quantum alternatives, an order of magnitude performance penalty for a factor of two improvement in bandwidth presents a trade-off that is unlikely to favor public-key compression in many scenarios. In this paper, we propose a range of new algorithms and techniques that accelerate SIDH public-key compression by more than an order of magnitude, making it roughly as fast as a round of standalone SIDH key exchange, while further reducing the size of the compressed public keys by approximately 12.5%. These improvements enable the practical use of compression, achieving public keys of only 330 bytes for the concrete parameters used to target 128 bits of quantum security and further strengthens SIDH as a promising post-quantum primitive.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Post-quantum cryptographyDiffie-Hellman key exchangesupersingular elliptic curvesisogeniesSIDHpublic-key compressionPohlig-Hellman algorithm
Contact author(s)
j renes @ cs ru nl
dburbani @ uwaterloo ca
History
2017-08-03: last of 3 revisions
2016-10-05: received
See all versions
Short URL
https://ia.cr/2016/963
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/963,
      author = {Craig Costello and David Jao and Patrick Longa and Michael Naehrig and Joost Renes and David Urbanik},
      title = {Efficient compression of SIDH public keys},
      howpublished = {Cryptology ePrint Archive, Paper 2016/963},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/963}},
      url = {https://eprint.iacr.org/2016/963}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.