Paper 2020/431

x-only point addition formula and faster compressed SIKE

Geovandro Pereira, Javad Doliskani, and David Jao

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. and Zanon et al. The combination of the techniques in previous works 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. 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 1,300 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 vs decapsulation speed and storage is introduced and achieves a 1.7 times faster decapsulation.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. MINOR revision.Journal of Cryptographic Engineering
DOI
10.1007/s13389-020-00245-4
Keywords
Post-quantum cryptographySupersingular elliptic curvesPublic-key compressionDiffie-Hellman key exchange
Contact author(s)
geovandro pereira @ uwaterloo ca
History
2021-04-08: last of 2 revisions
2020-04-15: received
See all versions
Short URL
https://ia.cr/2020/431
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/431,
      author = {Geovandro Pereira and Javad Doliskani and David Jao},
      title = {x-only point addition formula and faster compressed SIKE},
      howpublished = {Cryptology ePrint Archive, Paper 2020/431},
      year = {2020},
      doi = {10.1007/s13389-020-00245-4},
      note = {\url{https://eprint.iacr.org/2020/431}},
      url = {https://eprint.iacr.org/2020/431}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.