International Association
for Cryptologic Research

This work investigates zero-knowledge protocols in subverted RSA groups where the prover can choose the modulus and where the verifier does not know the group order. We introduce a novel technique for extracting the witness from a general homomorphism over a group of unknown order that does not require parallel repetitions. We then present a NIZK range proof for general homomorphisms as Paillier encryptions in the designated verifier model that works under a subverted setup. The key ingredient of our proof is a constant sized NIZK proof of knowledge for a plaintext. Security is proven in the ROM assuming an IND-CPA additively homomorphic encryption scheme. The verifier's public key can be maliciously generated and is reusable and linear in the number of proofs to be verified.

Laconic cryptography is an emerging paradigm that enables cryptographic primitives with sublinear communication complexity in just two messages. In particular, a two-message protocol between Alice and Bob is called \emph{laconic} if its communication and computation complexity are essentially independent of the size of Alice's input. This can be thought of as a dual notion of fully-homomorphic encryption, as it enables ``Bob-optimized'' protocols. This paradigm has led to tremendous progress in recent years. However, all existing constructions of laconic primitives are considered only of \emph{theoretical interest}: They all rely on non-black-box cryptographic techniques, which are highly impractical. This work shows that non-black-box techniques are not necessary for basic laconic cryptography primitives. We propose a \emph{completely algebraic} construction of laconic encryption, a notion that we introduce in this work, which serves as the cornerstone of our framework. We prove that the scheme is secure under the standard Learning With Errors assumption (with polynomial modulus-to-noise ratio). We provide proof-of-concept implementations for the first time for laconic primitives, demonstrating the construction is indeed practical: For a database size of $2^{50}$, encryption and decryption are in the order of single digit \emph{milliseconds}. Laconic encryption can be used as a black box to construct other laconic primitives. Specifically, we show how to construct: \begin{itemize} \item Laconic oblivious transfer \item Registration-based encryption scheme \item Laconic private-set intersection protocol \end{itemize} All of the above have essentially optimal parameters and similar practical efficiency. Furthermore, our laconic encryption can be preprocessed such that the online encryption step is entirely combinatorial and therefore much more efficient. Using similar techniques, we also obtain identity-based encryption with an unbounded identity space and tight security proof (in the standard model).

Distributed broadcast encryption (DBE) improves on the traditional notion of broadcast encryption by eliminating the key-escrow problem: In a DBE system, users generate their own secret keys non- interactively without the help of a trusted party. Then anyone can broad- cast a message for a subset S of the users, in such a way that the resulting ciphertext size is sublinear in (and, ideally, independent of) |S|. Unfor- tunately, the only known constructions of DBE requires heavy crypto- graphic machinery, such as general-purpose indistinguishability obfusca- tion, or come without a security proof. In this work, we formally show that obfuscation is not necessary for DBE, and we present two practical DBE schemes from standard assumptions in prime-order bilinear groups. Our constructions are conceptually simple, satisfy the strong notion of adaptive security, and are concretely efficient. In fact, their performance, in terms of number of group elements and efficiency of the algorithms, is comparable with that of traditional (non distributed) broadcast encryption schemes from bilinear groups.

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 au- thority 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), 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 im- provement 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 ap- plications. 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 com- mitment scheme into a key-value map commitment. For instance, this leads to the first algebraic pairing-based key-value map commitments.

Vector commitments with subvector openings (SVC) [Lai-Malavolta, Boneh-Bunz-Fisch; CRYPTO'19] allow one to open a committed vector at a set of positions with an opening of size independent of both the vector's length and the number of opened positions. We continue the study of SVC with two goals in mind: improving their efficiency and making them more suitable to decentralized settings. We address both problems by proposing a new notion for VC that we call \emph{incremental aggregation} and that allows one to merge openings in a succinct way an \emph{unbounded} number of times. We show two applications of this property. The first one is immediate and is a method to generate openings in a distributed way. The second application is an algorithm for faster generation of openings via preprocessing. We then proceed to realize SVC with incremental aggregation. We provide two constructions in groups of unknown order that, similarly to that of Boneh et al. (which supports aggregating only once), have constant-size public parameters, commitments and openings. As an additional feature, for the first construction we propose efficient arguments of knowledge of subvector openings which immediately yields a keyless proof of storage with compact proofs. Finally, we address a problem closely related to that of SVC: storing a file efficiently in completely decentralized networks. We introduce and construct \emph{verifiable decentralized storage} (VDS), a cryptographic primitive that allows to check the integrity of a file stored by a network of nodes in a distributed and decentralized way. Our VDS constructions rely on our new vector commitment techniques.