Paper 2022/1269

Collusion-Resistant Functional Encryption for RAMs

Prabhanjan Ananth, University of California, Santa Barbara
Kai-Min Chung, Academia Sinica
Xiong Fan, Rutgers, The State University of New Jersey
Luowen Qian, Boston University

In recent years, functional encryption (FE) has established itself as one of the fundamental primitives in cryptography. The choice of model of computation to represent the functions associated with the functional keys plays a critical role in the complexity of the algorithms of an FE scheme. Historically, the functions are represented as circuits. However, this results in the decryption time of the FE scheme growing proportional to not only the worst case running time of the function but also the size of the input, which in many applications can be quite large. In this work, we present the first construction of a public-key collusion-resistant FE scheme, where the functions, associated with the keys, are represented as random access machines (RAMs). We base the security of our construction on the existence of: (i) public-key collusion- resistant FE for circuits and, (ii) public-key doubly-efficient private-information retrieval [Boyle et al., Canetti et al., TCC 2017]. Our scheme enjoys many nice efficiency properties, including input-specific decryption time. We also show how to achieve FE for RAMs in the bounded-key setting with weaker efficiency guarantees from laconic oblivious transfer, which can be based on standard cryptographic assumptions. En route to achieving our result, we present conceptually simpler constructions of succinct garbling for RAMs [Canetti et al., Chen et al., ITCS 2016] from weaker assumptions.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Functional Encryption RAMs
Contact author(s)
prabhanjan @ cs ucsb edu
kmchung @ iis sinica edu tw
xiong fan @ rutgers edu
luowenq @ bu edu
2022-09-26: approved
2022-09-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Prabhanjan Ananth and Kai-Min Chung and Xiong Fan and Luowen Qian},
      title = {Collusion-Resistant Functional Encryption for RAMs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1269},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.