Paper 2022/1317
On the Optimal Succinctness and Efficiency of Functional Encryption and AttributeBased Encryption
Abstract
We investigate the optimal (asymptotic) efficiency of functional encryption (FE) and attributebased encryption (ABE) by proving inherent spacetime tradeoffs 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 randomaccess machines (RAM). In PHFE, a secret key $\mathsf{sk}_f$ is associated with a function $f$, whereas a ciphertext $\mathsf{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 $\mathsf{sk}_f$ is of *constant size* (optimal), independent of the function description length $f$, i.e., ${\mathsf{sk}_f=\operatorname{poly}(\lambda)}$.  Its ciphertext $\mathsf{ct}_x(y)$ is *rate2* in the private input length $y$ (nearly optimal) and *independent* of the public input length $x$ (optimal), i.e., ${\mathsf{ct}_x(y)=2y+\operatorname{poly}(\lambda)}$.  Decryption time is *linear* in the *instance* RAM running time $T$, plus the function and public/private input lengths, i.e., ${T_{\mathsf{Dec}}=(T+f+x+y)\operatorname{poly}(\lambda)}$. As a corollary, we obtain the first ABE with both keys and ciphertexts being constantsize, while enjoying the bestpossible decryption time matching the lower bound by Luo [ePrint '22]. We also separately achieve several other PHFE and ABE schemes. We study the barriers to further efficiency improvements. We prove the first unconditional spacetime tradeoffs for (PH)FE:  *No* secure (PH)FE can have $\mathsf{sk}_f$ and $T_{\mathsf{Dec}}$ *both* sublinear in $f$.  *No* secure PHFE can have $\mathsf{ct}_x(y)$ and $T_{\mathsf{Dec}}$ *both* sublinear in $x$. Our lower bounds apply even to the weakest secretkey 1key 1ciphertext selective schemes. Furthermore, we demonstrate a conditional barrier towards the optimal decryption time ${T_{\mathsf{Dec}}=T\operatorname{poly}(\lambda)}$ while keeping linear size dependency — any such (PH)FE scheme implies doubly efficient private information retrieval (DEPIR) with ideal efficiency, for which so far there is no satisfactory candidate.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2023
 DOI
 10.1007/9783031306204_16
 Keywords
 functional encryptionattributebased encryptionlower boundsobfuscationgarblingPIR
 Contact author(s)

aayushja @ andrew cmu edu
rachel @ cs washington edu
luoji @ cs washington edu  History
 20231101: revised
 20221004: received
 See all versions
 Short URL
 https://ia.cr/2022/1317
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1317, author = {Aayush Jain and Huijia Lin and Ji Luo}, title = {On the Optimal Succinctness and Efficiency of Functional Encryption and AttributeBased Encryption}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/1317}, year = {2022}, doi = {10.1007/9783031306204_16}, url = {https://eprint.iacr.org/2022/1317} }