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: The ePrint 2023/013 is the full version of this paper. We merged this paper with the ePrint 2022/1054 and revised some security analyses in the ePrint 2023/013.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
SIDHisogeny-based cryptographymasked-degree SIDH
Contact author(s)
tomoki_moriya @ mist i u-tokyo ac jp
History
2023-02-22: last of 2 revisions
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.