@InProceedings{NR19,
    author="Naehrig, Michael
    and Renes, Joost",
    editor="Galbraith, Steven D.
    and Moriai, Shiho",
    title="Dual Isogenies and Their Application to Public-Key Compression for Isogeny-Based Cryptography",
    booktitle="Advances in Cryptology -- ASIACRYPT 2019",
    year="2019",
    publisher="Springer International Publishing",
    address="Cham",
    pages="243--272",
    abstract="The isogeny-based protocols SIDH and SIKE have received much attention for being post-quantum key agreement candidates that retain relatively small keys. A recent line of work has proposed and further improved compression of public keys, leading to the inclusion of public-key compression in the SIKE proposal for Round 2 of the NIST Post-Quantum Cryptography Standardization effort. We show how to employ the dual isogeny to significantly increase performance of compression techniques, reducing their overhead from 160--182{\%} to 77--86{\%} for Alice's key generation and from 98--104{\%} to 59--61{\%} for Bob's across different SIDH parameter sets. For SIKE, we reduce the overhead of (1) key generation from 140--153{\%} to 61--74{\%}, (2) key encapsulation from 67--90{\%} to 38--57{\%}, and (3) decapsulation from 59--65{\%} to 34--39{\%}. This is mostly achieved by speeding up the pairing computations, which has until now been the main bottleneck, but we also improve (deterministic) basis generation.",
    isbn="978-3-030-34621-8"
}