Paper 2022/1019

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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Contact author(s)
tomoki_moriya @ mist i u-tokyo ac jp
History
2022-08-09: revised
See all versions
Short URL
https://ia.cr/2022/1019

CC BY

BibTeX

@misc{cryptoeprint:2022/1019,
author = {Tomoki Moriya},