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
-
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},
url = {https://eprint.iacr.org/2019/499}
}
