Paper 2024/034
How (not) to hash into class groups of imaginary quadratic fields?
Abstract
Class groups of imaginary quadratic fields (class groups for short) have seen a resurgence in cryptography as transparent groups of unknown order. They are a prime candidate for being a trustless alternative to RSA groups because class groups do not need a (distributed) trusted setup to sample a cryptographically secure group of unknown order. Class groups have recently found many applications in verifiable secret sharing, secure multiparty computation, transparent polynomial commitments, and perhaps most importantly, in time-based cryptography, i.e., verifiable delay functions, (homomorphic) time-lock puzzles, timed commitments, etc. However, there are various roadblocks to making class groups widespread in practical cryptographic deployments. We initiate the rigorous study of hashing into class groups. Specifically, we want to sample a uniformly distributed group element in a class group such that nobody knows its discrete logarithm with respect to any public parameter. We point out several flawed algorithms in numerous publicly available class group libraries. We further illustrate the insecurity of these hash functions by showing concrete attacks against cryptographic protocols, i.e., verifiable delay functions, if they were deployed with one of those broken hash-to-class group functions. We propose two families of cryptographically secure hash functions into class groups. We implement these constructions and evaluate their performance. We release our implementation as an open-source library.
Note: Clarifications and more proofs were added. Figures are made visible on black and white prints.
Metadata
- Available format(s)
- Category
- Secret-key cryptography
- Publication info
- Preprint.
- Keywords
- Class groupsHash functionsBinary Quadratic formsVerifiable delay functionsTimed commitments
- Contact author(s)
-
seresistvanandras @ gmail com
bupe @ inf elte hu
p kutas @ bham ac uk - History
- 2024-10-01: last of 4 revisions
- 2024-01-09: received
- See all versions
- Short URL
- https://ia.cr/2024/034
- License
-
CC0
BibTeX
@misc{cryptoeprint:2024/034, author = {István András Seres and Péter Burcsi and Péter Kutas}, title = {How (not) to hash into class groups of imaginary quadratic fields?}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/034}, year = {2024}, url = {https://eprint.iacr.org/2024/034} }