Paper 2016/229

Key Compression for Isogeny-Based Cryptosystems

Reza Azarderakhsh, David Jao, Kassem Kalach, Brian Koziel, and Christopher Leonardi

Abstract

We present a method for key compression in quantum-resistant isogeny-based cryptosystems, which allows a reduction in and transmission costs of per-party public information by a factor of two, with no effect on security. We achieve this reduction by associating a canonical choice of elliptic curve to each $j$-invariant, and representing elements on the curve as linear combinations with respect to a canonical choice of basis. This method of compressing public information can be applied to numerous isogeny-based protocols, such as key exchange, zero-knowledge identification, and public-key encryption. We performed personal computer and ARM implementations of the key exchange with compression and decompression in C and provided timing results, showing the computational cost of key compression and decompression at various security levels. Our results show that isogeny-based cryptosystems achieve by far the smallest possible key sizes among all existing families of post-quantum cryptosystems at practical security levels; e.g. 3073-bit public keys at the quantum 128-bit security level, comparable to (non-quantum) RSA key sizes.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. AsiaPKC2016
Keywords
elliptic curvesisogenieskey compressionpost-quantum cryptography
Contact author(s)
rxaeec @ rit edu
History
2016-04-15: last of 3 revisions
2016-03-01: received
See all versions
Short URL
https://ia.cr/2016/229
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/229,
      author = {Reza Azarderakhsh and David Jao and Kassem Kalach and Brian Koziel and Christopher Leonardi},
      title = {Key Compression for Isogeny-Based Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2016/229},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/229}},
      url = {https://eprint.iacr.org/2016/229}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.