Welcome to the resource topic for 2022/1317
Title:
On the Optimal Succinctness and Efficiency of Functional Encryption and AttributeBased Encryption
Authors: Aayush Jain, Huijia Lin, Ji Luo
Abstract:In this work we investigate the asymptotically bestpossible succinctness and efficiency of functional encryption (FE) and attributebased 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) rate2 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 constantsize keys and constantsize ciphertexts, and the bestpossible 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 spacetime tradeoff 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 spacetime tradeoffs apply even in the simplest selective 1key 1ciphertext secretkey 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 secretkey doubly efficient private information retrieval (SKDEPIR), for which so far the only known candidates rely on new and nonstandard 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 .