IACR News item: 05 October 2022
Aayush Jain, Huijia Lin, Ji Luo
ePrint Report
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.
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.
Additional news items may be found on the IACR news page.