Paper 2015/720
OutputCompressing Randomized Encodings and Applications
Huijia Lin, Rafael Pass, Karn Seth, and Sidharth Telang
Abstract
We consider randomized encodings (RE) that enable encoding a Turing machine Pi and input x into its ``randomized encoding'' \hat{Pi}(x) in sublinear, or even polylogarithmic, time in the runningtime of Pi(x), independent of its output length. We refer to the former as sublinear RE and the latter as compact RE. For such efficient RE, the standard simulationbased notion of security is impossible, and we thus consider a weaker (distributional) indistinguishabilitybased notion of security: Roughly speaking, we require indistinguishability of \hat{Pi}_0(x_0) and \hat{Pi}_0(x_1) as long as Pi_0,x_0 and Pi_1,x_1 are sampled from some distributions such that Pi_0(x_0),Time(Pi_0(x_0)) and Pi_1(x_1),Time(Pi_1(x_1)) are indistinguishable. We first observe that compact RE is equivalent to a variant of the notion of indistinguishability obfuscation (iO)which we refer to as puncturable iOfor the class of Turing machines without inputs. For the case of circuits, puncturable iO and iO are equivalent (and this fact is implicitly used in the powerful ``punctured program'' paradigm by Sahai and Waters [SW13]). We next show the following:  Impossibility in the Plain Model: Assuming the existence of subexponentially secure oneway functions, subexponentiallysecure sublinear RE does not exists. (If additionally assuming subexponentiallysecure iO for circuits we can also rule out polynomiallysecure sublinear RE.) As a consequence, we rule out also puncturable iO for Turing machines (even those without inputs).  Feasibility in the CRS model and Applications to iO for circuits: Subexponentiallysecure sublinear RE in the CRS model and oneway functions imply iO for circuits through a simple construction generalizing GGM's PRF construction. Additionally, any compact (even with sublinear compactness) functional encryption essentially directly yields a sublinear RE in the CRS model, and as such we get an alternative, modular, and simpler proof of the results of [AJ15,BV15] showing that subexponentiallysecure sublinearly compact FE implies iO. We further show other ways of instantiating sublinear RE in the CRS model (and thus also iO): under the subexponential LWE assumption, it suffices to have a subexponentially secure FE schemes with just sublinear ciphertext (as opposed to having sublinear encryption time).  Applications to iO for Unboundedinput Turing machines: Subexponentiallysecure compact RE for natural restricted classes of distributions over programs and inputs (which are not ruled out by our impossibility result, and for which we can give candidate constructions) imply iO for unboundedinput Turing machines. This yields the first construction of iO for unboundedinput Turing machines that does not rely on (publiccoin) differinginput obfuscation.
Metadata
 Available format(s)
 Publication info
 Preprint.
 Keywords
 randomized encodingsobfuscation
 Contact author(s)
 sidtelang @ cs cornell edu
 History
 20151223: last of 3 revisions
 20150720: received
 See all versions
 Short URL
 https://ia.cr/2015/720
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/720, author = {Huijia Lin and Rafael Pass and Karn Seth and Sidharth Telang}, title = {OutputCompressing Randomized Encodings and Applications}, howpublished = {Cryptology ePrint Archive, Paper 2015/720}, year = {2015}, note = {\url{https://eprint.iacr.org/2015/720}}, url = {https://eprint.iacr.org/2015/720} }