The Existence of Cycles in the Supersingular Isogeny Graphs Used in SIKE

Hiroshi Onuki; Yusuke Aikawa; Tsuyoshi Takagi

Paper 2020/439

The Existence of Cycles in the Supersingular Isogeny Graphs Used in SIKE

Hiroshi Onuki, Yusuke Aikawa, and Tsuyoshi Takagi

Abstract

In this paper, we consider the structure of isogeny graphs in SIDH, that is an isogeny-based key-exchange protocol. SIDH is the underlying protocol of SIKE, which is one of the candidates for NIST post quantum cryptography standardization. Since the security of SIDH is based on the hardness of the path-finding problem in isogeny graphs, it is important to study those structure. The existence of cycles in isogeny graph is related to the path-finding problem, so we investigate cycles in the graphs used in SIKE. In particular, we focus on SIKEp434 and SIKEp503, which are the parameter sets of SIKE claimed to satisfy the NIST security level 1 and 2, respectively. We show that there are two cycles in the 3-isogeny graph in SIKEp434, and there is no cycles in the other graphs in SIKEp434 and SIKEp503.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Supersingular isogeny graphs post quantum cryptography SIDH SIKE
Contact author(s): onuki @ mist i u-tokyo ac jp
History: 2020-08-25: last of 2 revisions; 2020-04-19: received; See all versions
Short URL: https://ia.cr/2020/439
License: CC BY

BibTeX

@misc{cryptoeprint:2020/439,
      author = {Hiroshi Onuki and Yusuke Aikawa and Tsuyoshi Takagi},
      title = {The Existence of Cycles in the Supersingular Isogeny Graphs Used in {SIKE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/439},
      year = {2020},
      url = {https://eprint.iacr.org/2020/439}
}