IACR News item: 01 May 2015
Yu-Chi Chen, Sherman S. M. Chow, Kai-Min Chung, Russell W. F. Lai, Wei-Kai Lin, Hong-Sheng Zhou
ePrint ReportAs our main results, we construct CiO for parallel RAM (PRAM) computation based on iO for circuits and one-way functions, and demonstrate the power of CiO by the following applications.
o With digital signatures, our CiO for PRAM immediately implies the first two-message (publicly-
verifiable) delegation scheme for outsourcing PRAM computation, where the delegator\'s runtime depends only on the program description and input/output size, and the server\'s complexity matches the PRAM complexity of the computation up to polylogarithmic factors.
o With public-key encryption, our CiO for PRAM, and a specific oblivious PRAM construction, we construct the first fully succinct randomized encoding (RE) for PRAM computation, where the encoder\'s runtime (and thus the encoding size) depends only on the program description and input/output size, and the decoding complexity matches PRAM complexity of the computation up to polylogarithmic factors.
o By plugging our fully succinct RE for PRAM into existing transformations, we obtain the first constructions of several cryptographic primitives for PRAM, such as functional encryptions with succinct (PRAM) function keys, succinct reusable garbling schemes, and succinct indistinguishability obfuscations (the later requires sub-exponential security). Notably, this implies that, while CiO is weaker than iO, sub-exponentially secure CiO for PRAM implies sub-exponentially secure iO for PRAM.
Additional news items may be found on the IACR news page.