You are looking at a specific version 20200604:105338 of this paper. See the latest version.

Paper 2019/1209

On collisions related to an ideal class of order 3 in CSIDH

Hiroshi Onuki and Tsuyoshi Takagi

Abstract

CSIDH is an isogeny-based key exchange, which is a candidate for post quantum cryptography. It uses the action of an ideal class group on Fp-isomorphic classes of supersingular elliptic curves. In CSIDH, the ideal classes are represented by vectors with integer coefficients. The number of ideal classes represented by these vectors de- termines the security level of CSIDH. Therefore, it is important to investigate the correspondence between the vectors and the ideal classes. Heuristics show that integer vectors in a certain range represent “almost” uniformly all of the ideal classes. However, the precise correspondence between the integer vectors and the ideal classes is still unclear. In this paper, we investigate the correspondence between the ideal classes and the integer vectors and show that the vector (1, . . . , 1) corresponds to an ideal class of order 3. Consequently, the integer vectors in CSIDH have collisions related to this ideal class. Here, we use the word “collision” in the sense of distinct vectors belonging to the same ideal class, i.e., distinct secret keys that correspond to the same public key in CSIDH. We further propose a new ideal representation in CSIDH that does not include these collisions and give formulae for efficiently computing the action of the new representation.

Note: To appear at IWSEC 2020.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
CISDHpost-quantum cryptographyisogeny-based cryptographyideal class groupssupersingular elliptic curve isogenies
Contact author(s)
onuki @ mist i u-tokyo ac jp
History
2020-06-04: revised
2019-10-16: received
See all versions
Short URL
https://ia.cr/2019/1209
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.