Paper 2024/295

An Efficient Hash Function for Imaginary Class Groups

Kostas Kryptos Chalkias, Mysten Labs
Jonas Lindstrøm, Mysten Labs
Arnab Roy, Mysten Labs

This paper presents a new efficient hash function for imaginary class groups. Many class group based protocols, such as verifiable delay functions, timed commitments and accumulators, rely on the existence of an efficient and secure hash function, but there are not many concrete constructions available in the literature, and existing constructions are too inefficient for practical use cases. Our novel approach, building on Wesolowski's initial scheme, achieves a staggering 500-fold increase in computation speed, making it exceptionally practical for real-world applications. This optimisation is achieved at the cost of a smaller image of the hash function, but we show that the image is still sufficiently large for the hash function to be secure. Additionally, our construction is almost linear in its ability to be parallelized, which significantly enhances its computational efficiency on multi-processor systems, making it highly suitable for modern computing environments.

Available format(s)
Publication info
Imaginary class groupsClass group cryptographyHash functionsVerifiable delay functionsTimed commitments
Contact author(s)
kostas @ mystenlabs com
jonas @ mystenlabs com
arnab @ mystenlabs com
2024-02-23: approved
2024-02-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kostas Kryptos Chalkias and Jonas Lindstrøm and Arnab Roy},
      title = {An Efficient Hash Function for Imaginary Class Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2024/295},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.