Cryptology ePrint Archive: Report 2016/963

Efficient compression of SIDH public keys

Craig Costello and David Jao and Patrick Longa and Michael Naehrig and 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.

Category / Keywords: Post-quantum cryptography, Diffie-Hellman key exchange, supersingular elliptic curves, isogenies, SIDH, public-key compression, Pohlig-Hellman algorithm

Date: received 4 Oct 2016, last revised 24 Mar 2017

Contact author: j renes at cs ru nl; dburbani@uwaterloo ca

Available format(s): PDF | BibTeX Citation

Version: 20170324:071944 (All versions of this report)

Short URL: ia.cr/2016/963

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]