GeezerVison

GeezerVison is showing eprint.iacr.org — Efficient compression of SIDH public keys

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 cryptography Diffie-Hellman key exchange supersingular elliptic curves isogenies SIDH public-key compression Pohlig-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: 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},
      url = {https://eprint.iacr.org/2016/963}
}