Hash functions from superspecial genus-2 curves using Richelot isogenies
In 2018 Takashima proposed a version of Charles, Goren and Lauter’s hash function using Richelot isogenies, starting from a genus-2 curve that allows for all subsequent arithmetic to be performed over a quadratic finite field 𝔽p2. In 2019 Flynn and Ti pointed out that Takashima’s hash function is in...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2020-08-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2019-0021 |
| _version_ | 1817997671031373824 |
|---|---|
| author | Castryck Wouter Decru Thomas Smith Benjamin |
| author_facet | Castryck Wouter Decru Thomas Smith Benjamin |
| author_sort | Castryck Wouter |
| collection | DOAJ |
| description | In 2018 Takashima proposed a version of Charles, Goren and Lauter’s hash function using Richelot isogenies, starting from a genus-2 curve that allows for all subsequent arithmetic to be performed over a quadratic finite field 𝔽p2. In 2019 Flynn and Ti pointed out that Takashima’s hash function is insecure due to the existence of small isogeny cycles. We revisit the construction and show that it can be repaired by imposing a simple restriction, which moreover clarifies the security analysis. The runtime of the resulting hash function is dominated by the extraction of 3 square roots for every block of 3 bits of the message, as compared to one square root per bit in the elliptic curve case; however in our setting the extractions can be parallelized and are done in a finite field whose bit size is reduced by a factor 3. Along the way we argue that the full supersingular isogeny graph is the wrong context in which to study higher-dimensional analogues of Charles, Goren and Lauter’s hash function, and advocate the use of the superspecial subgraph, which is the natural framework in which to view Takashima’s 𝔽p2-friendly starting curve. |
| first_indexed | 2024-04-14T02:41:50Z |
| format | Article |
| id | doaj.art-ed924e12d50e4c92a843c5be2e4c19c0 |
| institution | Directory Open Access Journal |
| issn | 1862-2976 1862-2984 |
| language | English |
| last_indexed | 2024-04-14T02:41:50Z |
| publishDate | 2020-08-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-ed924e12d50e4c92a843c5be2e4c19c02022-12-22T02:17:02ZengDe GruyterJournal of Mathematical Cryptology1862-29761862-29842020-08-0114126829210.1515/jmc-2019-0021jmc-2019-0021Hash functions from superspecial genus-2 curves using Richelot isogeniesCastryck Wouter0Decru Thomas1Smith Benjamin2imec-COSIC, Department of Electrical Engineering, KU Leuven, Franceimec-COSIC, Department of Electrical Engineering, KU Leuven, FranceInria and École Polytechnique, Institut Polytechnique de Paris, Palaiseau, FranceIn 2018 Takashima proposed a version of Charles, Goren and Lauter’s hash function using Richelot isogenies, starting from a genus-2 curve that allows for all subsequent arithmetic to be performed over a quadratic finite field 𝔽p2. In 2019 Flynn and Ti pointed out that Takashima’s hash function is insecure due to the existence of small isogeny cycles. We revisit the construction and show that it can be repaired by imposing a simple restriction, which moreover clarifies the security analysis. The runtime of the resulting hash function is dominated by the extraction of 3 square roots for every block of 3 bits of the message, as compared to one square root per bit in the elliptic curve case; however in our setting the extractions can be parallelized and are done in a finite field whose bit size is reduced by a factor 3. Along the way we argue that the full supersingular isogeny graph is the wrong context in which to study higher-dimensional analogues of Charles, Goren and Lauter’s hash function, and advocate the use of the superspecial subgraph, which is the natural framework in which to view Takashima’s 𝔽p2-friendly starting curve.https://doi.org/10.1515/jmc-2019-0021isogenycryptography14k0214g5094a60 |
| spellingShingle | Castryck Wouter Decru Thomas Smith Benjamin Hash functions from superspecial genus-2 curves using Richelot isogenies Journal of Mathematical Cryptology isogeny cryptography 14k02 14g50 94a60 |
| title | Hash functions from superspecial genus-2 curves using Richelot isogenies |
| title_full | Hash functions from superspecial genus-2 curves using Richelot isogenies |
| title_fullStr | Hash functions from superspecial genus-2 curves using Richelot isogenies |
| title_full_unstemmed | Hash functions from superspecial genus-2 curves using Richelot isogenies |
| title_short | Hash functions from superspecial genus-2 curves using Richelot isogenies |
| title_sort | hash functions from superspecial genus 2 curves using richelot isogenies |
| topic | isogeny cryptography 14k02 14g50 94a60 |
| url | https://doi.org/10.1515/jmc-2019-0021 |
| work_keys_str_mv | AT castryckwouter hashfunctionsfromsuperspecialgenus2curvesusingrichelotisogenies AT decruthomas hashfunctionsfromsuperspecialgenus2curvesusingrichelotisogenies AT smithbenjamin hashfunctionsfromsuperspecialgenus2curvesusingrichelotisogenies |