Paper 2024/034

How (not) to hash into class groups of imaginary quadratic fields?

István András Seres, Eötvös Loránd University
Péter Burcsi, Eötvös Loránd University
Péter Kutas, Eötvös Loránd University, University of Birmingham
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)
PDF
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
No rights reserved
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.