International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Dual Isogenies and Their Application to Public-Key Compression for Isogeny-Based Cryptography

Authors:
Michael Naehrig
Joost Renes
Download:
DOI: 10.1007/978-3-030-34621-8_9
Search ePrint
Search Google
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.
BibTeX
@article{asiacrypt-2019-30040,
  title={Dual Isogenies and Their Application to Public-Key Compression for Isogeny-Based Cryptography},
  booktitle={Advances in Cryptology – ASIACRYPT 2019},
  series={Advances in Cryptology – ASIACRYPT 2019},
  publisher={Springer},
  volume={11922},
  pages={243-272},
  doi={10.1007/978-3-030-34621-8_9},
  author={Michael Naehrig and Joost Renes},
  year=2019
}