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

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: Many typos, inaccuracies, and imprecisions are fixed. More explanatory texts and clarifications are added.

Available format(s)
Secret-key cryptography
Publication info
Class groupsHash functionsBinary Quadratic formsVerifiable delay functionsTimed commitments
Contact author(s)
seresistvanandras @ gmail com
bupe @ inf elte hu
p kutas @ bham ac uk
2024-05-17: last of 3 revisions
2024-01-09: received
See all versions
Short URL
No rights reserved


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.