CryptoDB
Constraint-Friendly Map-to-Elliptic-Curve-Group Relations and Their Applications
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2025 |
| Abstract: | Hashing to elliptic curve groups is a fundamental primitive underlying numerous cryptographic applications, including multiset hashing and BLS signatures. With the recent rise of zero-knowledge applications, these primitives are increasingly used in constraint programming settings. For example, multiset hashing enables memory consistency checks in zkVMs, while BLS signatures are widely used in zkPoS protocols. In such cases, it becomes critical for hash-to-elliptic-curve-group constructions to be constraint-friendly. However, existing constructions rely on cryptographic hash functions that are expensive to represent in arithmetic constraint systems, resulting in high proving costs in these applications. We propose a constraint-efficient alternative: a map-to-elliptic-curve-group relation that bypasses the need for cryptographic hash functions and can serve as a drop-in replacement for hash-to-curve constructions in practical settings, including the aforementioned applications. Our relation naturally supports witness-based instantiations within constraint programming frameworks, enabling efficient integration into zero-knowledge circuits. We formally analyze the security of our approach in the elliptic curve generic group model (EC-GGM). Our implementation in Noir/Barretenberg demonstrates the efficiency of our construction in constraint programming: it achieves over 60x fewer constraints than the best hash-to-elliptic-curve-group alternatives, and enables 50-100x faster proving times at scale. |
BibTeX
@inproceedings{asiacrypt-2025-36115,
title={Constraint-Friendly Map-to-Elliptic-Curve-Group Relations and Their Applications},
publisher={Springer-Verlag},
author={Jens Groth and Harjasleen Malvai and Andrew Miller and Yi-Nuo Zhang},
year=2025
}