x -only point addition formula and faster compressed SIKE
- PDF / 426,894 Bytes
- 13 Pages / 595.276 x 790.866 pts Page_size
- 15 Downloads / 138 Views
REGULAR PAPER
x-only point addition formula and faster compressed SIKE Geovandro Pereira1
· Javad Doliskani2 · David Jao1
Received: 8 August 2019 / Accepted: 7 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract The optimization of the main key compression bottlenecks of the supersingular isogeny key encapsulation mechanism (SIKE) has been a target of research in the last few years. Significant improvements were introduced in the recent works of Costello et al. (EUROCRYPT’2017) and Zanon et al. (PQCrypto’2018; IEEE ToC’2018). The combination of the techniques in Zanon et al. (PQCrypto’2018; IEEE ToC’2018) reduced the running time of binary torsion basis generation in decompression by a factor of 29 compared to previous work. On the other hand, generating such a basis still takes almost a million cycles on an Intel Core i5-6267U Skylake. In this paper, we continue the work of Zanon et al. (IEEE ToC’2018) and introduce a technique that drops the complexity of binary torsion basis generation by a factor log p in the number of underlying field multiplications. In particular, our experimental results show that a basis can be generated in about 1300 cycles, attaining an improvement by a factor more than 600. Although this result eliminates one of the key compression bottlenecks, many other bottlenecks remain. In addition, we give further improvements for the ternary torsion generation with significant impact on the related decompression procedure. Moreover, a new trade-off between ciphertext sizes versus decapsulation speed and storage is introduced and achieves a 1.7 times faster decapsulation. Keywords Post-quantum cryptography · Supersingular elliptic curves · Public-key compression · Diffie–Hellman key exchange
1 Introduction Public-key cryptosystems based on elliptic curve isogenies are conjectured to be secure against quantum attacks and as a result have attracted some interest in the post-quantum cryptography community. One particular such cryptosystem, supersingular isogeny key encapsulation (SIKE) [17], has been proposed as a candidate for the NIST post-quantum standardization process [15]. SIKE is based on the supersingular isogeny Diffie–Hellman (SIDH) construction of Jao and De Feo [11], whose security relies on the hardness of the supersingular isogeny graph path-finding problem introduced by Charles et al. [5].
This work is supported in part by NSERC, CryptoWorks21, Canada First Research Excellence Fund, Public Works and Government Services Canada, and the Royal Bank of Canada.
B
Geovandro Pereira [email protected]
1
University of Waterloo, Waterloo, Canada
2
Ryerson University, Toronto, Canada
An especially attractive feature of SIKE is its small public key size. Of all the public-key cryptosystems submitted to the NIST standardization process in the first round, SIKE has the smallest proposed public keys at each of its supported security levels. Furthermore, the public keys can actually be made even smaller: in 2016, Azarderakhsh et. al. [2] introdu
Data Loading...
