International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Collusion-Resistant Functional Encryption for RAMs

Prabhanjan Ananth , UCSB
Kai-Min Chung , Academia Sinica
Xiong Fan , Rutgers University
Luowen Qian , Boston University
Search ePrint
Search Google
Conference: ASIACRYPT 2022
Abstract: 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.
  title={Collusion-Resistant Functional Encryption for RAMs},
  author={Prabhanjan Ananth and Kai-Min Chung and Xiong Fan and Luowen Qian},