Paper 2023/1389

Cuckoo Commitments: Registration-Based Encryption and Key-Value Map Commitments for Large Spaces

Dario Fiore, IMDEA Software Institute
Dimitris Kolonelos, IMDEA Software Institute, Universidad Politécnica de Madrid
Paola de Perthuis, École Normale Supérieure - PSL, Cosmian

Registration-Based Encryption (RBE) [Garg et al. TCC'18] is a public-key encryption mechanism in which users generate their own public and secret keys, and register their public keys with a central authority called the key curator. Similarly to Identity-Based Encryption (IBE), in RBE users can encrypt by only knowing the public parameters and the public identity of the recipient. Unlike IBE, though, RBE does not suffer the key escrow problem — one of the main obstacles of IBE's adoption in practice — since the key curator holds no secret. In this work, we put forward a new methodology to construct RBE schemes that support large users identities (i.e., arbitrary strings). Our main result is the first efficient pairing-based RBE for large identities. Prior to our work, the most efficient RBE is that of [Glaeser et al. ePrint'22] which only supports small identities. The only known RBE schemes with large identities are realized either through expensive non-black-box techniques (ciphertexts of 3.6 TB for 1000 users), or via a specialized lattice-based construction [Döttling et al. Eurocrypt'23] (ciphertexts of 2.4 GB), or through the more complex notion of Registered Attribute-Based Encryption [Hohenberger et al. Eurocrypt’23]. By unlocking the use of pairings for RBE with large identity space, we enable a further improvement of three orders of magnitude, as our ciphertexts for a system with 1000 users are 1.7 MB. The core technique of our approach is a novel use of cuckoo hashing in cryptography that can be of independent interest. We give two main applications. The first one is the aforementioned RBE methodology, where we use cuckoo hashing to compile an RBE with small identities into one for large identities. The second one is a way to convert any vector commitment scheme into a key-value map commitment. For instance, this leads to the first algebraic pairing-based key-value map commitments.

Note: Added a reference to related work.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Registration-Based EncryptionIdentity-Based EncryptionVector CommitmentsCuckoo HashingKey-Value Maps
Contact author(s)
dario fiore @ imdea org
dimitris kolonelos @ imdea org
paola de perthuis @ ens fr
2023-10-19: last of 4 revisions
2023-09-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dario Fiore and Dimitris Kolonelos and Paola de Perthuis},
      title = {Cuckoo Commitments: Registration-Based Encryption and Key-Value Map Commitments for Large Spaces},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1389},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.