Key Compression for Isogeny-Based Cryptosystems
Authors:
Open Access
- 30 May 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 2016, 1-10
Abstract
We present a method for key compression in quantumresistant isogeny-based cryptosystems, which allows a reduction in and transmission costs of per-party public information by a factor of two, with no e ect 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 identi cation, 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.Keywords
Funding Information
- National Science Foundation (1464118)
This publication has 12 references indexed in Scilit:
- A Panorama of Post-quantum Cryptography2014
- A Quantum Algorithm for Computing Isogenies between Supersingular Elliptic Curves2014
- Towards quantum-resistant cryptosystems from supersingular elliptic curve isogeniesJournal of Mathematical Cryptology, 2014
- Constructing elliptic curve isogenies in quantum subexponential timeJournal of Mathematical Cryptology, 2013
- Claw finding algorithms using quantum walkTheoretical Computer Science, 2009
- Choosing NTRUEncrypt Parameters in Light of Combined Lattice Reduction and MITM Approaches2009
- Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications2000
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- The Arithmetic of Elliptic Curves1986
- An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)IEEE Transactions on Information Theory, 1978