On Collisions Related to an Ideal Class of Order 3 in CSIDH
| Autor: | Tsuyoshi Takagi, Hiroshi Onuki |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
Isogeny Class (set theory) Post-quantum cryptography Ideal (set theory) Mathematics::Commutative Algebra Computer science Ideal class group Order (ring theory) 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Supersingular elliptic curve Integer 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering |
| Zdroj: | Advances in Information and Computer Security ISBN: 9783030582074 IWSEC |
| DOI: | 10.1007/978-3-030-58208-1_8 |
| Popis: | 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 \(\mathbb {F}_{p}\)-isomorphism 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 determines 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, \dots , 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|