# Output-Compressing Randomized Encodings and Applications

Calvin Lab Auditorium

We consider randomized encodings (RE) that enable encoding a Turing machine P and input x into its “randomized encoding” \hat{P(x)} in sublinear, or even polylogarithmic, time in the running-time of P(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 simulation-based notion of security is impossible, and we thus consider a weaker (distributional) indistinguishability-based notion of security: Roughly speaking, we require indistinguishability of \hat{P0(x0)} and \hat{P0(x1)} as long as P0, x0 and P1, x1 are sampled from some distributions such that P0(x0), Time(P0(x0)) and P1(x1), Time(P1(x1)) 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 iO—for 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 [SW14]).

We next show the following:

1. Impossibility in the Plain Model: Assuming the existence of one-way functions, subexponentially-secure sublinear RE does not exists. (If additionally assuming subexponentially-secure iO for circuits we can also rule out polynomially-secure sublinear RE.) As a consequence, we rule out also puncturable iO for Turing machines (even those without inputs).

2. Feasibility in the CRS model and Applications to iO for circuits: Subexponentially-

3. Applications to iO for Unbounded-input Turing machines: Subexponentially-