Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2019
Keywords
Post-quantum cryptographypublic-key compressionsupersingular elliptic curvesdual isogeniesreduced Tate pairings
Contact author(s)
j renes @ cs ru nl
History
2019-10-02: last of 2 revisions
2019-05-20: received
See all versions
Short URL
https://ia.cr/2019/499
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/499,
      author = {Michael Naehrig and Joost Renes},
      title = {Dual Isogenies and Their Application to Public-key Compression for Isogeny-based Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2019/499},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/499}},
      url = {https://eprint.iacr.org/2019/499}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.