Welcome to the resource topic for 2022/1317
Title:
On the Optimal Succinctness and Efficiency of Functional Encryption and Attribute-Based Encryption
Authors: Aayush Jain, Huijia Lin, Ji Luo
Abstract:In this work we investigate the asymptotically best-possible succinctness and efficiency of functional encryption (FE) and attribute-based encryption (ABE), focusing on simultaneously minimizing the sizes of secret keys and ciphertexts and the decryption time. To this end, we consider the notion of partially hiding functional encryption (PHFE) that captures both FE and ABE, and the most efficient computation model of random access machine (RAM). A PHFE secret key \mathsf{sk}_f is tied to a function f, whereas a ciphertext \mathsf{ct}_x(y) is tied to a public input x (e.g., ABE attribute) and encrypts a private input y. Decryption reveals f(x,y) and nothing else about y.
We present the first PHFE scheme for RAMs based on the necessary assumption of FE for circuits. It achieves nearly optimal succinctness and efficiency:
-
The secret keys \mathsf{sk}_f are of (optimal) constant size, independent of the description size |f| of the function tied to it.
-
The ciphertexts \mathsf{ct}_x(y) have (nearly optimal) rate-2 dependency on the private input length |y| and (optimal) independency of the public input length |x|.
-
Decryption is efficient, running in time linear in the instance running time T of the RAM computation, in addition to the input and function sizes, i.e., {T_{\mathsf{Dec}}=(T+|f|+|x|+|y|)\operatorname{poly}(\lambda)}.
Our construction significantly improves upon the asymptotic efficiency of prior schemes. As a corollary, we obtain the first ABE scheme with both constant-size keys and constant-size ciphertexts, and the best-possible decryption time matching an existing lower bound.
We show barriers to further improvement on the asymptotic efficiency of (PH-)FE. We prove the first unconditional space-time trade-off for (PH-)FE. No secure (PH-)FE scheme can have both key size and decryption time sublinear in the function size |f|, and no secure PHFE scheme can have both ciphertext size and decryption time sublinear in the public input length |x|. These space-time trade-offs apply even in the simplest selective 1-key 1-ciphertext secret-key setting. Furthermore, we show a conditional barrier towards achieving the optimal decryption time {T_{\mathsf{Dec}}=T\operatorname{poly}(\lambda)} — any such (PH-)FE scheme implies a primitive called secret-key doubly efficient private information retrieval (SK-DE-PIR), for which so far the only known candidates rely on new and non-standard hardness conjectures.
ePrint: https://eprint.iacr.org/2022/1317
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .