1. Efficient compression of SIDH public keys 2017 Diffie-Hellman EllipticCurves Eurocrypt Isogenies PQC
    Craig Costello, David Jao, Patrick Longa, Michael Naehrig, Joost Renes, and David Urbanik
    [View PDF on eprint.iacr.org]
    [Show BibTex Citation]

    @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, Report 2016/963},
    year = {2016},
    note = {\url{https://eprint.iacr.org/2016/963}},
    }

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.

  1.