Cryptology ePrint Archive: Report 2014/154

Non-Interactive Cryptography in the RAM Model of Computation

Daniel Apon and Xiong Fan and Jonathan Katz and Feng-Hao Liu and Elaine Shi and Hong-Sheng Zhou

Abstract: Using recently developed techniques for program obfuscation, we show several constructions of non-interactive cryptosystems in the random-access machine (RAM) model of computation that are asymptotically more efficient than what would be obtained using generic RAM-to-circuit compilation. In particular, let $T$ denote the running time and $n$ the memory size of a RAM program. We show that using differing-inputs obfuscation, functional encryption for arbitrary RAM programs can be achieved with evaluation time $\tilde{O}(T+n)$.

Additionally, we provide a number of RAM-model constructions assuming the stronger notion of virtual black-box (VBB) obfuscation. We view these as initial feasibility results and leave instantiating similar protocols from weaker assumptions for future work. Specifically, using VBB obfuscation we show how to construct RAM-model functional encryption with function privacy, fully homomorphic encryption, and stateful, privacy-preserving verifiable computation in the memory-delegation model.

Category / Keywords: random access machine; program obfuscation; functional encryption; fully homomorphic encryption; verifiable computation

Date: received 28 Feb 2014, last revised 2 Mar 2014, withdrawn 14 Jul 2014

Contact author: dapon at cs umd edu

Available format(s): (-- withdrawn --)

Note: Added authors' contact information

Version: 20140715:024731 (All versions of this report)

Short URL: ia.cr/2014/154

Discussion forum: Show discussion | Start new discussion