International Association
for Cryptologic Research

We present a pairing-based traitor tracing scheme for N users with |pk| = |ct| = O(N^(1/3)), |sk| = O(1). This is the first pairing-based scheme to achieve |pk| * |sk| * |ct| = o(N). Our construction relies on the (bilateral) k-Lin assumption, and achieves private tracing and full collusion resistance. Our result simultaneously improves upon the sizes of pk, ct in Boneh--Sahai--Waters [Eurocrypt '06] and the size of sk in Zhandry [Crypto '20], while further eliminating the reliance on the generic group model in the latter work.

We investigate the best-possible (asymptotic) efficiency of functional encryption (FE) and attribute-based encryption (ABE) by proving inherent space-time trade-offs and constructing nearly optimal schemes. We consider the general notion of partially hiding functional encryption (PHFE), capturing both FE and ABE, and the most efficient computation model of random-access machine (RAM). In PHFE, a secret key sk_f is associated with a function f, whereas a ciphertext ct_x(y) is tied to a public input x and encrypts a private input y. Decryption reveals f(x,y) and nothing else about y. We present the first PHFE for RAM solely based on the necessary assumption of FE for circuits. Significantly improving upon the efficiency of prior schemes, our construction achieves nearly optimal succinctness and computation time: - Its secret key sk_f is of *constant size* (optimal), independent of the function description length |f|, i.e., |sk_f| = poly(lambda). - Its ciphertext ct_x(y) is *rate-2* in the private input length |y| (nearly optimal) and *independent* of the public input length |x| (optimal), i.e., |ct_x(y)| = 2|y| + poly(lambda). - Decryption time is *linear* in the *instance* running time T of the RAM computation, plus the function and public/private input lengths, i.e., T_Dec = (T + |f| + |x| + |y|)poly(lambda). As a corollary, we obtain the first ABE with both keys and ciphertexts being constant-size, while enjoying the best-possible decryption time matching the lower bound by Luo [ePrint '22]. We also separately achieve several other optimal ABE subject to the known lower bound. We study the barriers to further efficiency improvements. We prove the first unconditional space-time trade-offs for (PH-)FE: - *No* secure (PH-)FE can have |sk_f| and T_Dec *both* sublinear in |f|. - *No* secure PHFE can have |ct_x(y)| and T_Dec *both* sublinear in |x|. Our lower bounds apply even to the weakest secret-key 1-key 1-ciphertext selective schemes. Furthermore, we show a conditional barrier towards the optimal decryption time T_Dec = T poly(lambda) while keeping linear size dependency --- any such (PH-)FE scheme implies doubly efficient private information retrieval (DE-PIR) with linear-size preprocessed database, for which so far there is no candidate.

We introduce a new idealized model of hash functions, which we refer to as the *pseudorandom oracle* (PrO) model. Intuitively, it allows us to model cryptosystems that use the code of an ideal hash function in a non-black-box way. Formally, we model hash functions via a combination of a pseudorandom function (PRF) family and an ideal oracle. A user can initialize the hash function by choosing a PRF key $k$ and mapping it to a public handle $h$ using the oracle. Given the handle $h$ and some input $x$, the oracle can also be called to evaluate the PRF at $x$ with the corresponding key $k$. A user who chooses the PRF key $k$ therefore has a complete description of the hash function and can use its code in non-black-box constructions, while an adversary, who just gets the handle $h$, only has black-box access to the hash function via the oracle. As our main result, we show how to construct ideal obfuscation in the PrO model, starting from functional encryption (FE), which in turn can be based on well-studied polynomial hardness assumptions. In contrast, we know that ideal obfuscation cannot be instantiated in the basic random oracle model under any assumptions. We believe our result provides heuristic justification for the following: (1) most natural security goals implied by ideal obfuscation can be achieved in the real world; (2) obfuscation can be constructed from FE at polynomial security loss. We also discuss how to interpret our result in the PrO model as a construction of ideal obfuscation using simple hardware tokens or as a way to bootstrap ideal obfuscation for PRFs to that for all functions.

An important theme in the research on attribute-based encryption (ABE) is minimizing the sizes of secret keys and ciphertexts. In this work, we present two new ABE schemes with *constant-size* secret keys, i.e., the key size is independent of the sizes of policies or attributes and dependent only on the security parameter $\lambda$. - We construct the first key-policy ABE scheme for circuits with constant-size secret keys, ${|\mathsf{sk}_f|=\mathrm{poly}(\lambda)}$, which concretely consist of only three group elements. The previous state-of-the-art scheme by [Boneh et al., Eurocrypt '14] has key size polynomial in the maximum depth $d$ of the policy circuits, ${|\mathsf{sk}_f|=\mathrm{poly}(d,\lambda)}$. Our new scheme removes this dependency of key size on $d$ while keeping the ciphertext size the same, which grows linearly in the attribute length and polynomially in the maximal depth, ${|\mathsf{ct}_{\mathbf{x}}|=|\mathbf{x}|\mathrm{poly}(d,\lambda)}$. - We present the first ciphertext-policy ABE scheme for Boolean formulae that simultaneously has constant-size keys and succinct ciphertexts of size independent of the policy formulae, namely, ${|\mathsf{sk}_f|=\mathrm{poly}(\lambda)}$ and ${|\mathsf{ct}_{\mathbf{x}}|=\mathrm{poly}(|\mathbf{x}|,\lambda)}$. Concretely, each secret key consists of only two group elements. Previous ciphertext-policy ABE schemes either have succinct ciphertexts but non-constant-size keys [Agrawal--Yamada, Eurocrypt '20, Agrawal--Wichs--Yamada, TCC '20], or constant-size keys but large ciphertexts that grow with the policy size as well as the attribute length. Our second construction is the first ABE scheme achieving *double succinctness*, where both keys and ciphertexts are smaller than the corresponding attributes and policies tied to them. Our constructions feature new ways of combining lattices with pairing groups for building ABE and are proven selectively secure based on LWE and in the generic (pairing) group model. We further show that when replacing the LWE assumption with its adaptive variant introduced in [Quach--Wee--Wichs FOCS '18], the constructions become adaptively secure.

We present a new general framework for constructing compact and adaptively secure attribute-based encryption (ABE) schemes from k-Lin in asymmetric bilinear pairing groups. Previously, the only construction [Kowalczyk and Wee, Eurocrypt '19] that simultaneously achieves compactness and adaptive security from static assumptions supports policies represented by Boolean formulae. Our framework enables supporting more expressive policies represented by arithmetic branching programs. Our framework extends to ABE for policies represented by uniform models of computation such as Turing machines. Such policies enjoy the feature of being applicable to attributes of arbitrary lengths. We obtain the first compact adaptively secure ABE for deterministic and non-deterministic finite automata (DFA and NFA) from k-Lin, previously unknown from any static assumptions. Beyond finite automata, we obtain the first ABE for large classes of uniform computation, captured by deterministic and non-deterministic logspace Turing machines (the complexity classes L and NL) based on k-Lin. Our ABE scheme has compact secret keys of size linear in the description size of the Turing machine M. The ciphertext size grows linearly in the input length, but also linearly in the time complexity, and exponentially in the space complexity. Irrespective of compactness, we stress that our scheme is the first that supports large classes of Turing machines based solely on standard assumptions. In comparison, previous ABE for general Turing machines all rely on strong primitives related to indistinguishability obfuscation.

We present succinct and adaptively secure attribute-based encryption (ABE) schemes for arithmetic branching programs, based on k-Lin in pairing groups. Our key-policy ABE scheme have ciphertexts of constant size, independent of the length of the attributes, and our ciphertext-policy ABE scheme have secret keys of constant size. Our schemes improve upon the recent succinct ABE schemes in [Tomida and Attrapadung, ePrint '20], which only handles Boolean formulae. All other prior succinct ABE schemes either achieve only selective security or rely on q-type assumptions. Our schemes are obtained through a general and modular approach that combines a public-key inner product functional encryption satisfying a new security notion called gradual simulation security and an information-theoretic randomized encoding scheme called arithmetic key garbling scheme.

We introduce a new technique that allows to give a zero-knowledge proof that a committed vector has Hamming weight bounded by a given constant. The proof has unconditional soundness and is very compact: It has size independent of the length of the committed string, and for large fields, it has size corresponding to a constant number of commitments. We show five applications of the technique that play on a common theme, namely that our proof allows us to get malicious security at small overhead compared to semi-honest security: (1) actively secure k-out-of-n OT from black-box use of 1-out-of-2 OT, (2) separable accountable ring signatures, (3) more efficient preprocessing for the TinyTable secure two-party computation protocol, (4) mixing with public verifiability, and (5) PIR with security against a malicious client.