We present the first RAM delegation scheme that provide both soundness and privacy guarantees in the adaptive setting, where the sequence of delegated RAM programs are chosen adaptively, depending potentially on the encodings of the database and previously chosen programs. Prior works either achieved only adaptive soundness without privacy [Kalai and Paneth, ePrint'15], or only security in the selective setting where all RAM programs are chosen statically [Chen et al. ITCS'16, Canetti and Holmgren ITCS'16].
Our scheme assumes the existence of indistinguishability obfuscation ($\iO$) for circuits and the decisional Diffie-Hellman (DDH) assumption. However, our techniques are quite general and in particular, might be applicable even in settings where iO is not used. We provide a "security lifting technique" that "lifts" any proof of selective security satisfying certain special properties into a proof of adaptive security, for arbitrary cryptographic schemes. We then apply this technique to the delegation scheme of Chen et al. and its selective security proof, obtaining that their scheme is essentially already adaptively secure. Because of the general approach, we can also easily extend to delegating parallel RAM (PRAM) computations. We believe that the security lifting technique can potentially find other applications and is of independent interest.Category / Keywords: foundations / delegation, RAM computation, adaptive security, security lifting, histroy-less accumulators Original Publication (with minor differences): TCC 2016-B Date: received 7 Nov 2015, last revised 18 Oct 2016 Contact author: kmchung at iis sinica edu tw, rachel lin@cs ucsb edu, prabhanjan@cs ucla edu, wycchen@iis sinica edu tw, wklin@iis sinica edu tw Available format(s): PDF | BibTeX Citation Version: 20161018:222740 (All versions of this report) Short URL: ia.cr/2015/1082 Discussion forum: Show discussion | Start new discussion