International Association
for Cryptologic Research

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.

We present CanDID, a platform for practical, user-friendly realization of {\em decentralized identity}, the idea of empowering end users with management of their own credentials. While decentralized identity promises to give users greater control over their private data, it burdens users with management of private keys, creating a significant risk of key loss. Existing and proposed approaches also presume the spontaneous availability of a credential-issuance ecosystem, creating a bootstrapping problem. They also omit essential functionality, like resistance to Sybil attacks and the ability to detect misbehaving or sanctioned users while preserving user privacy. CanDID addresses these challenges by issuing credentials in a user-friendly way that draws securely and privately on data from existing, unmodified web service providers. Such legacy compatibility similarly enables CanDID users to leverage their existing online accounts for recovery of lost keys. Using a decentralized committee of nodes, CanDID provides strong confidentiality for user's keys, real-world identities, and data, yet prevents users from spawning multiple identities and allows identification (and blacklisting) of sanctioned users. We present the CanDID architecture and its technical innovations and report on experiments demonstrating its practical performance.