CryptoDB
Ji Luo
Publications
Year
Venue
Title
2023
EUROCRYPT
Traitor Tracing with N^(1/3)-size Ciphertext and O(1)-size Keys from k-Lin
Abstract
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.
2023
EUROCRYPT
On the Optimal Succinctness and Efficiency of Functional Encryption and Attribute-Based Encryption
Abstract
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.
2022
TCC
ABE for Circuits with Constant-Size Secret Keys and Adaptive Security
Abstract
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.
2020
EUROCRYPT
Compact Adaptively Secure ABE from k-Lin: Beyond NC1 and towards NL
📺
Abstract
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.
2020
ASIACRYPT
Succinct and Adaptively Secure ABE for Arithmetic Branching Programs from k-Lin
📺
Abstract
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.
2018
PKC
Compact Zero-Knowledge Proofs of Small Hamming Weight
Abstract
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.
Coauthors
- Ivan Damgård (1)
- Junqing Gong (1)
- Aayush Jain (1)
- Hanjun Li (1)
- Huijia Lin (4)
- Sabine Oechsner (1)
- Peter Scholl (1)
- Mark Simkin (1)
- Hoeteck Wee (1)