CryptoDB
On the Optimal Succinctness and Efficiency of Functional Encryption and Attribute-Based Encryption
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | EUROCRYPT 2023 |
| 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. |
BibTeX
@inproceedings{eurocrypt-2023-32999,
title={On the Optimal Succinctness and Efficiency of Functional Encryption and Attribute-Based Encryption},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-30620-4_16},
author={Aayush Jain and Huijia Lin and Ji Luo},
year=2023
}