International Association for Cryptologic Research

International Association
for Cryptologic Research


Optimal Bounded-Collusion Secure Functional Encryption

Prabhanjan Ananth
Vinod Vaikuntanathan
DOI: 10.1007/978-3-030-36030-6_8
Search ePrint
Search Google
Abstract: We construct private-key and public-key functional encryption schemes in the bounded-key setting; that is, secure against adversaries that obtain an a-priori bounded number of functional keys (also known as the collusion bound).An important metric considered in the literature on bounded-key functional encryption schemes is the dependence of the running time of the encryption algorithm on the collusion bound $$Q=Q(\lambda )$$ (where $$\lambda $$ is the security parameter). It is known that bounded-key functional encryption schemes with encryption complexity growing with $$Q^{1-\varepsilon }$$ , for any constant $$\varepsilon > 0$$ , implies indistinguishability obfuscation. On the other hand, in the public-key setting, it was previously unknown whether we could achieve encryption complexity growing linear with Q, also known as optimal bounded-key FE, based on well-studied assumptions.In this work, we give the first construction of an optimal bounded-key public-key functional encryption scheme under the minimal assumption of the existence of any public-key encryption scheme. Moreover, our scheme supports the class of all polynomial-size circuits.Our techniques also extend to the private-key setting. We achieve a construction of an optimal bounded-key functional encryption in the private-key setting based on the minimal assumption of one-way functions, instead of learning with errors as achieved in prior works.
  title={Optimal Bounded-Collusion Secure Functional Encryption},
  booktitle={Theory of Cryptography},
  series={Lecture Notes in Computer Science},
  author={Prabhanjan Ananth and Vinod Vaikuntanathan},