Paper 2022/1019

Masked-degree SIDH

Tomoki Moriya, Department of Mathematical Informatics, The University of Tokyo
Abstract

Isogeny-based cryptography is one of the candidates for post-quantum cryptography. SIDH is a compact and efficient isogeny-based key exchange, and SIKE, which is the SIDH-based key encapsulation mechanism, remains the NIST PQC Round 4. However, by the brilliant attack provided by Castryck and Decru, the original SIDH is broken in polynomial time (with heuristics). To break the original SIDH, there are three important pieces of information in the public key: information about the endomorphism ring of a starting curve, some image points under a cyclic hidden isogeny, and the degree of the isogeny. In this paper, we proposed the new isogeny-based scheme named \textit{masked-degree SIDH}. This scheme is the variant of SIDH that masks most information about degrees of hidden isogenies, and the first trial against Castryck--Decru attack. The main idea to cover degrees is to use many primes to compute isogenies that allow the degree to be more flexible. Though the size of the prime $p$ for this scheme is slightly larger than that of SIDH, this scheme resists current attacks using degrees of isogenies like the attack of Castryck and Decru. The most effective attack for masked-degree SIDH has $\tilde{O}(p^{1/(8\log_2{(\log_2{p})})})$ time complexity with classical computers and $\tilde{O}(p^{1/(16\log_2{(\log_2{p})})})$ time complexity with quantum computers in our analysis.

Note: I apologize there are some errors in the security analysis. I will fix them as soon as possible.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
SIDH isogeny-based cryptography masked-degree SIDH
Contact author(s)
tomoki_moriya @ mist i u-tokyo ac jp
History
2022-08-09: revised
2022-08-07: received
See all versions
Short URL
https://ia.cr/2022/1019
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1019,
      author = {Tomoki Moriya},
      title = {Masked-degree SIDH},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1019},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1019}},
      url = {https://eprint.iacr.org/2022/1019}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.