Cryptology ePrint Archive: Report 2019/499

Dual Isogenies and Their Application to Public-key Compression for Isogeny-based Cryptography

Michael Naehrig and Joost Renes

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.

Category / Keywords: public-key cryptography / Post-quantum cryptography, public-key compression, supersingular elliptic curves, dual isogenies, reduced Tate pairings

Original Publication (with minor differences): IACR-ASIACRYPT-2019

Date: received 14 May 2019, last revised 2 Oct 2019

Contact author: j renes at cs ru nl

Available format(s): PDF | BibTeX Citation

Version: 20191002:064737 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]