Output-Compressing Randomized Encodings and Applications | Springer Nature Link

In this section, we define our succinct indistinguishability obfuscator for Turing machines. Let \(\mathsf {RE}= (\mathsf {Enc}, \mathsf {Eval})\) be a compact randomized encoding scheme for Turing machines with sub-exponential indistinguishability security. Let c be the constant for the security loss associated with the indistinguishability security of \(\mathsf {RE}\). We assume without loss of generality that \(\mathsf {Enc}(1^\lambda ,\cdot ,\cdot )\) requires a random tape of length \(\lambda \). Let \(\mathsf{PRG}\) be a sub-exponentially secure pseudorandom generator and let \(\epsilon \) be the constant associated with the sub-exponential security of \(\mathsf{PRG}\).

For every \(\lambda \in \mathbb {N}\), \(D \le 2^\lambda \), define

where \(d > 0\) is any constant strictly greater than c.

Construction 1

Consider a Turing machine \(\varPi \), security parameter \(\lambda \in \mathbb {N}\), and time bound \(T\) of \(\varPi \). For every partial input \(s \in \{0,1\}^*\) with \(|s| \le 2^\lambda \) and \(R \in \{0,1\}^{2l(\lambda ,|s|)}\), we recursively define a Turing machine \(\widetilde{\varPi }_{s, R}\) to be as follows:

• When \(|s| < 2^\lambda \):

  On the empty input, \(\widetilde{\varPi }_{s, R}\) outputs:

  $$\begin{aligned}&\mathsf {Enc}(1^{l(\lambda , |s|+1)},\widetilde{\varPi }_{s0, R_0}, T'(\lambda , |s|+1, |\varPi |, \log (T));R_1)\\&\mathsf {Enc}(1^{l(\lambda , |s|+2)},\widetilde{\varPi }_{s1,R_2}, T'(\lambda , |s|+1, |\varPi |, \log (T));R_3)\\&\mathsf {Enc}(1^{l(\lambda ,|s|+1)},\varPi ,s, T;R_4) \end{aligned}$$

  where \((R_0,R_1,R_2,R_3,R_4) \leftarrow \mathsf{PRG}(R,5\cdot 2l(\lambda ,|s|+1))\) and \(T'\) is some fixed polynomial in \(\lambda , |s|+1, |\varPi |\) and \(\log (T)\). In the special case when \(|s| = 2^\lambda - 1\), the time bound used in the first two encodings is set to \(T\). On all other inputs, \(\widetilde{\varPi }_{s, R}\) outputs \(\bot \).

• When \(|s| = 2^\lambda \):

  On the empty input, \(\widetilde{\varPi }_{s, R}\) outputs \(\mathsf {Enc}(1^{l(\lambda ,|s|+1)},\varPi ,s, T;R)\). On all other inputs, \(\widetilde{\varPi }_{s, R}\) outputs \(\bot \).

We define \(T'(\cdot , \cdot , \cdot , \cdot )\) (corresponding to the bound placed on the running time of \(\widetilde{\varPi }_{s,R}\)) to be the smallest polynomial such that for all \(\lambda \), \(s \in \{0,1\}^{\le 2^\lambda }\), \(R \in \{0,1\}^{2l(\lambda ,|s|)}\), \(\varPi \) and \(T\),

where \(\lambda _{|s| + 1} = l(\lambda , |s|+1)\), \(T'_{|s|+1} = T'(\lambda , |s|+1, |\varPi |, \log (T))\) (corresponding to the security parameter and time bound used for each of \(\widetilde{\varPi }_{s0,R_0}\) and \(\widetilde{\varPi }_{s1,R_1}\)), \(\mathsf{Time}_\mathsf{PRG}\) is the bound on the running time of the PRG, and \(p(\cdot , \cdot , \cdot , \cdot )\) is the bound on \(\mathsf{Time}_\mathsf {Enc}\) from the compactness of \(\mathsf {RE}\). We note that the polynomial \(T'\) exists because p is a polynomial, each of \(\lambda _{|s| + 1}\) and \(|\widetilde{\varPi }_{s, R}|\) are of size polynomial in \(\lambda , |s|\) and \(|\varPi |\), and the self-dependence of \(T'(\lambda , |s|, |\varPi |, \log (T))\) on \(T'_{|s|+1}\) is only poly-logarithmic.

We note that \(|\widetilde{\varPi }_{s, R}|\) is always \(poly(\lambda , |\varPi |, |s|, \log (T))\). This is because \(\widetilde{\varPi }_{s, R}\) is fully described by \(\lambda \), \(\varPi \), s, R and \(T\), and the size of each of these is bounded by \(poly(\lambda , |\varPi |, |s|, \log (T))\).

Given this definition of \(\widetilde{\varPi }_{s,R}\), we define our indistinguishability obfuscator as follows:

Construction 2

(Indistinguishability Obfuscator). On input \(\lambda \in \mathbb {N}\), Turing machine \(\varPi \) and time bound \(T\), define \(\widetilde{\varPi }\), the indistinguishability obfuscation of \(\varPi \), to be

where \(\epsilon \) is the empty string, and \(R \mathop {\leftarrow }\limits ^{\tiny \$}\{0,1\}^{2l(\lambda ,0)}\) and \(T'\) a fixed polynomial in \(\lambda , |\varPi |\) and \(\log (T)\), as described above.

The algorithm to evaluate \(\widetilde{\varPi }\) on input \(x\in \{0,1\}^d, d < 2^\lambda \) proceeds as follows:

1. 1.

   For every \(0\le i \le d\), compute encodings of \(\widetilde{\varPi }_{x_{\le i}, R}\) successively, starting with \(\widetilde{\varPi }\), an encoding of \(\widetilde{\varPi }_{\epsilon , R}\), and subsequently, for every \(0 < i \le d\), computing the encoding of \(\widetilde{\varPi }_{x_{\le i}, R}\) by evaluating the encoding of \(\widetilde{\varPi }_{x_{<i}, R}\), and selecting the encoding of \(\widetilde{\varPi }_{x_{\le i}, R}\) from its output.

2. 2.

   Evaluate the encoding of \(\widetilde{\varPi }_{x, R} = \widetilde{\varPi }_{x_{\le d}, R}\) and obtain from its output \((\hat{\varPi }, \hat{x}) = \mathsf {Enc}(1^{l(\lambda ,|x|+1)},\varPi ,x, T;R_4)\).

3. 3.

   Run \(\mathsf {Eval}(\hat{\varPi }, \hat{x})\) to obtain \(\varPi (x)\).

We defer analysis of the correctness, running time, and compactness of our \(\mathbf{iO } \) construction to the full version of our paper [LPST15].

4.1 Security Proof

Theorem 8

Let \((\mathsf {Enc}, \mathsf {Eval})\) be a sub-exponentially-indistinguishability-secure, compact randomized encoding scheme and let \(\mathsf{PRG}\) be a sub-exponentially-secure pseudorandom generator. Then the indistinguishability obfuscator defined in Construction 2 is subexponentially-secure.

Proof

Consider any pair of ensembles of Turing machines and time bounds \(\left\{ {\varPi _{\lambda }^0, \varPi _{\lambda }^1, T_\lambda } \right\} \) where for every \(\lambda \in \mathbb {N}\), \(\varPi ^0 = \varPi _{\lambda }^0\), \(\varPi ^1 = \varPi _{\lambda }^1\), \(T= T_\lambda \),

We first introduce some notation to describe the distributions of randomized encodings generated by \(i\mathcal {O}(1^\lambda , \varPi ^0_{\lambda }, T_\lambda )\) and \(i\mathcal {O}(1^\lambda , \varPi ^1_{\lambda }, T_\lambda )\). For \(\lambda \in \mathbb {N}\), \(s \in \{0,1\}^{*}, |s| \le 2^{\lambda }\), we define the following distributions

where R is uniformly random, \(T'\) is as described in Construction 1 and \(\widetilde{\varPi }_{s,R}^b\) is defined for the Turing machine \(\varPi ^b_\lambda \), security parameter \(\lambda \) and time bound \(T_{\lambda }\). We will show something stronger than the theorem statement. In particular, we have the following claim.

Claim. There exists \(\lambda _0, \epsilon \in \mathbb {N}\) such that for every \(\lambda > \lambda _0\), for every \(s \in \{0,1\}^{*}, |s| \le 2^{\lambda }\) we have that the distributions \(D_{\lambda , 0,s}\) and \(D_{\lambda , 1,s}\) are \(S(\lambda )\) indistinguishable where \(S(\lambda ) \ge 10 \cdot 2^{l(\lambda , |s|-1)^{\epsilon }}\).

Using the above claim with s as the empty string and recalling \(l(\lambda ,0) = \lambda \), the theorem statement follows. Therefore, in the remainder of the proof, we prove the above claim.

Let \(\epsilon \) be the larger of the constants associated with the sub-exponential security of the pseudorandom generator \(\mathsf{PRG}\) and the indistinguishability security of the encoding scheme \((\mathsf {Enc}, \mathsf {Eval})\) (these constants are also named \(\epsilon \) in their respective security definitions). Similarly, We consider \(\lambda _0\) to be large enough so that the security of the encoding scheme \((\mathsf {Enc}, \mathsf {Eval})\) and the pseudorandom generator \(\mathsf{PRG}\) is applicable. We will actually require a larger \(\lambda _0\) so that certain asymptotic conditions (depending only on the polynomial size bounds of \(\varPi ^0_\lambda \), \(\varPi ^1_\lambda \) and \(T_\lambda \)) hold, which we make explicit in the remainder of the proof. For every \(\lambda > \lambda _0\), we prove the claim by induction on |s|. Our base case will be when \(|s| = 2^\lambda \) and in the inductive step we show the claim holds for all s of a particular length d, if it holds for all s of length \(d+1\).

For every \(s \in \{0,1\}^{\le 2^\lambda }\), the distributions \(D_{\lambda , 0,s}\) and \(D_{\lambda , 1,s}\) are \(10\cdot 2^{l(\lambda ,|s|-1)^{\epsilon }}\) indistinguishable.

In this case, recall that the output of \(\widetilde{\varPi }^b_{s,R}\) is simply \((\hat{\varPi }^{b,T}_{\lambda }, \hat{s})\). We first claim that, for all s, \((\hat{\varPi }^{0,T}_{\lambda } \hat{s})\) and \((\hat{\varPi }^{1,T}_{\lambda }, \hat{s})\) are \(2^{\lambda '^\epsilon }\) indistinguishable where \(\lambda ' = l(\lambda ,|s|)\), as follows.

Recall that the output of evaluating \(\hat{\varPi }^{b,T}_{\lambda }, \hat{s}\) is simply \(\varPi ^{b,T}_{\lambda }(s)\). Since we have that \(\varPi ^{0,T}_{\lambda }(s) = \varPi ^{1,T}_{\lambda }(s)\) for all s, we can apply the security of the randomized encoding scheme. More concretely, since the output (point) distributions are identical, they are \(10\cdot 2^{\lambda '^\epsilon }\)-indistinguishable where \(\lambda ' = l(\lambda ,|s|+1)\). Let \(B(\cdot )\) be a polynomial such that \(B(\lambda ')\) bounds from above \(|\varPi ^b|, |s|\) and \(T\). By the security of the encoding scheme, the encodings \((\hat{\varPi }^{0,T}_{\lambda } \hat{s})\) and \((\hat{\varPi }^{1,T}_{\lambda } \hat{s})\) are \(S'\) indistinguishable where

where the first inequality holds for sufficiently large \(\lambda \) and in the second inequality, we use the fact that \(l(\lambda , |s|+1) = l(\lambda , |s|) + \lambda ^{d/\epsilon }\). Thus \((\hat{\varPi }^{0,T}_{\lambda }, \hat{s})\) and \((\hat{\varPi }^{1,T}_{\lambda }, \hat{s})\) are \(10 \cdot 2^{l(\lambda ,|s_{\lambda }|)^{\epsilon }}\)-indistinguishable.

Now, recall that the output of \(\widetilde{\varPi }^b_{s,R}\) is simply \((\hat{\varPi }^{b,T}_{\lambda }, \hat{s})\). By the above argument, we have that, for all s, \((\hat{\varPi }^{0,T}_{\lambda } \hat{s})\) and \((\hat{\varPi }^{1,T}_{\lambda }, \hat{s})\) are \(2^{\lambda '^\epsilon }\)-indistinguishable where \(\lambda ' = l(\lambda ,|s|)\). Let \(B'\) be the polynomial such that \(B'(l(\lambda , |s|))\) bounds \(|\widetilde{\varPi }^b_{s,R}|\) and the running time of \(\widetilde{\varPi }^b_{s,R}\). The encodings \(D_{\lambda ,0,s}\) and \(D_{\lambda ,1,s}\) are \(S'\) indistinguishable where

where, as before, the first inequality holds for sufficiently large \(\lambda \) and in the second inequality, we use the fact that \(l(\lambda , |s|+1) = l(\lambda , |s|) + \lambda ^{d/\epsilon }\). Hence the claim holds for \(|s| = 2^\lambda \).

. By the induction hypothesis, we assume the claim holds for all \(s'\) such that \(|s'| = |s| + 1\). Recall that the output of \(\widetilde{\varPi }^b_{s,R}\) (where \(R \mathop {\leftarrow }\limits ^{\tiny \$}\{0,1\}^{2l(\lambda ,|s|)}\)) is

where \((R_0,R_1,R_2,R_3,R_4) \leftarrow \mathsf{PRG}(R,5 \cdot 2l(\lambda ,|s|+1))\). Let \(H^b\) denote the above output distribution. We will show \(H^0\) and \(H^1\) are indistinguishable by a hybrid argument as follows.

• Let \(G_1\) be a hybrid distribution exactly as \(H^0\) except that \((R_0,R_1,R_2,\) \(R_3,R_4) \mathop {\leftarrow }\limits ^{\tiny \$}\{0,1\}^{5 \cdot 2l(\lambda , |s|+1)}\). We claim that for both the distributions \(H^0\) and \(G_1\) are \(5 \cdot 2^{\lambda '^\epsilon }\) indistinguishable where \(\lambda ' = l(\lambda , |s|)\). This follows from the \(\mathsf{PRG}\) security as follows: any size \(5 \cdot 2^{\lambda '^\epsilon }\) adversary A that distinguishes \(H^0\) and \(G_1\) can be turned into an adversary \(A'\) that can break the PRG security with seed length \(2\lambda '\) with the same advantage. \(A'\) has \(\varPi ^0_{\lambda }\), \(\varPi ^1_{\lambda }\), \(T_\lambda \) and s hardcoded in it. Hence, the size of \(A'\) is

  $$5 \cdot 2^{\lambda '^\epsilon } + {{\mathrm{poly}}}(\lambda ) + {{\mathrm{poly}}}(|s|) \le 5 \cdot 2^{\lambda '^\epsilon } + {{\mathrm{poly}}}(\lambda ') \le 2^{(2\lambda ')^\epsilon }$$

  where the last inequality holds when \(\lambda \) is sufficiently large. Hence, \(A'\) breaks the \(2^{(2\lambda ')^\epsilon }\)-security of \(\mathsf{PRG}\) and we have a contradiction.

  Writing out the components of \(G_1\), we have that it is identical to

  $$\begin{aligned} G_1 \equiv D_{\lambda , 0, s0}, D_{\lambda , 0, s1}, \mathsf {Enc}(1^{l(\lambda ,|s|+1)},\varPi ^0_{\lambda },s, T_\lambda ;R) \end{aligned}$$

• Let \(G_2\) be a hybrid distribution obtained by modifying the first component of \(G_1\) as follows.

  $$\begin{aligned} G_2 \equiv D_{\lambda , 1, s0}, D_{\lambda , 0, s1}, \mathsf {Enc}(1^{l(\lambda ,|s|+1)},\varPi ^0_{\lambda },s, T_\lambda ;R) \end{aligned}$$

  We show that \(G_1\) and \(G_2\) are \(5 \cdot 2^{\lambda '^\epsilon }\) indistinguishable. This follows from the induction hypothesis as follows: any size \(5 \cdot 2^{\lambda '^\epsilon }\) adversary A that distinguishes \(G_1\) and \(G_2\) with advantage better than \(1/(5 \cdot 2^{\lambda '^\epsilon })\) can be turned into an adversary \(A'\) that can distinguish \(D_{\lambda , 0, s0}\) and \(D_{\lambda , 1, s0}\) with the same advantage. As before, \(A'\) has \(\varPi ^0_{\lambda }\), \(\varPi ^1_{\lambda }\), \(T_\lambda \) and s hardcoded in it, and therefore the size of \(A'\) is at most \(5 \cdot 2^{\lambda '^\epsilon } + {{\mathrm{poly}}}(\lambda ') \le 10 \cdot 2^{\lambda '^\epsilon }\). Hence, \(A'\) breaks the induction hypothesis that says \(D_{\lambda , 0, s0}\) and \(D_{\lambda , 1, s0}\) are \(10 \cdot 2^{\lambda '^\epsilon }\)-indistinguishable.

• Similarly, let \(G_3\) be a hybrid distribution obtained by modifying the second component of \(G_2\) as follows.

  $$\begin{aligned} G_3 \equiv D_{\lambda , 1, s0}, D_{\lambda , 1, s1}, \mathsf {Enc}(1^{l(\lambda ,|s|+1)},\varPi ^0_{\lambda },s, T_\lambda ;R) \end{aligned}$$

  Similarly as above, we have that \(G_2\) and \(G_3\) are \(5 \cdot 2^{\lambda '^\epsilon }\)-indistinguishable.

• Let \(G_4\) be a hybrid distribution obtained by modifying the third component of \(G_3\) as follows.

  $$\begin{aligned} G_4 \equiv D_{\lambda , 1, s0}, D_{\lambda , 1, s1}, \mathsf {Enc}(1^{l(\lambda ,|s|+1)},\varPi ^1_{\lambda },s, T_\lambda ;R) \end{aligned}$$

  We show \(G_3\) and \(G_4\) are \(5 \cdot 2^{\lambda '^\epsilon }\)-indistinguishable. First, since \(\varPi ^{0,T}_{\lambda }(s) = \varPi ^{1,T}_{\lambda }(s)\), by the security of the encoding scheme, we have that the encodings that form the third component of \(G_3\) and \(G_4\) are \(S'\) indistinguishable where, similar to the base case, \(B(l(\lambda , |s|))\) bounds from above \(|\varPi ^b_\lambda |, |s|\) and \(T\)

  $$\begin{aligned} S' \ge \frac{10\cdot 2^{l(\lambda ,|s|)^\epsilon }}{l(\lambda ,|s|)^c} - B(l(\lambda ,|s|))^c \ge \frac{10\cdot 2^{l(\lambda ,|s|)^\epsilon }}{l(\lambda ,|s|)^d} \ge 10 \cdot 2^{l(\lambda ,|s|-1)^\epsilon } \end{aligned}$$

  Hence by a similar argument as before, the hybrid distributions are \(5 \cdot 2^{\lambda '^\epsilon }\)-indistinguishable.

• Finally we observe that \(G_4\) and \(H^1\) are \(5 \cdot 2^{\lambda '^\epsilon }\)-indistinguishable just as \(G_1\) and \(H^0\) were. By a simple hybrid argument, we have that \(H^0\) and \(H^1\) are \(2^{\lambda '^\epsilon }\)-indistinguishable.

  Recall that \(H^0\) and \(H^1\) are the distributions of outputs of \(\widetilde{\varPi }^0_{s,R}\) and \(\widetilde{\varPi }^1_{s,R}\) respectively. By the security of the randomized encoding scheme, the encodings of these machines, i.e. \(D_{\lambda , 0, s}\) and \(D_{\lambda , 1, s}\) are \(S'(\lambda )\)-indistinguishable where

  $$\begin{aligned} S'(\lambda ) \ge \frac{2^{l(\lambda ,|s|)^\epsilon }}{l(\lambda ,|s|)^c} - B'(l(\lambda , |s|)^c \ge \frac{2^{l(\lambda ,|s|)^\epsilon }}{l(\lambda ,|s|)^d} \ge \frac{2^{l(\lambda ,|s|-1)^\epsilon } \cdot 2^{({2d\lambda })}}{2^{d\lambda } \cdot (2d\lambda )^{d/\epsilon }} \ge 10 \cdot 2^{l(\lambda ,|s|-1)^\epsilon } \end{aligned}$$

  where \(B'(l(\lambda , |s|))\) bounds from above \(|\varPi ^b_{s,R}|\) and \(T'\). The second inequality holds for sufficiently large \(\lambda \). In the third inequality, we use the fact that \(l(\lambda , |s|) \le |s|(2d\lambda )^{1/\epsilon } \le 2^\lambda (2d\lambda )^{1/\epsilon }\) and the last inequality holds for sufficiently large \(\lambda \).

4.2 Nice Distributions

Later in Sect. 6, we show that compact RE does not exist for general distributions in the plain model. However, here we observe that the above construction of unbounded input IO relies only on compact RE for certain “special purpose” distributions that is not ruled out by the impossibility result in Sect. 6. We now abstract out the structure of these special purpose distributions. Let \(\mathsf {RE}= (\mathsf {Enc}, \mathsf {Dec})\) be a randomized encoding scheme; we define “nice” distributions w.r.t. \(\mathsf {RE}\).

• 0-nice distributions: We say that a pair of distribution ensembles \(\left\{ {\mathcal {D} _{0, \lambda }} \right\} \) and \(\left\{ {D_{1, \lambda }} \right\} \) are 0-nice if \(D_{0, \lambda }\) always outputs a fixed tuple \((\varPi _{0}, x, T)\) while \(D_{1, \lambda }\) always outputs a fixed tuple \((\varPi _{1}, x, T)\), satisfying that \(\varPi ^{T}_{0}(x) = \varPi _{1}^{T}(x)\).

• k -nice distributions: We say that a pair of distribution ensembles \(\left\{ {\mathcal {D} _{0, \lambda }} \right\} \) and \(\left\{ {\mathcal {D} _{1, \lambda }} \right\} \) are k-nice if there exist some \(\ell = {{\mathrm{poly}}}(\lambda )\) pairs of distributions \((\{ {\mathcal{E}^i_{0, \lambda }} \},\{ {\mathcal{E}^i_{1, \lambda }} \})_{i \in [\ell ]}\), where the \(i^{th}\) pair is \(k^i\)-nice with \(k^i \le k-1\), such that, \( \mathcal {D} _{b,\lambda }\) samples tuple \((\varPi _b, x_b, T_b)\) satisfying the following:

  • – For each \(i \in [\ell ]\), sample \((\varLambda ^i_b, z^i_b, T^i_b)\mathop {\leftarrow }\limits ^{\tiny \$}\mathcal{E}^i_{b, \lambda }\).

  • –The output of \(\varPi _b(x_b)\) consists of \(\ell \) randomized encodings, where the \(i^{th}\) encoding is in the support of \(\mathsf {Enc}(1^{\lambda '}, \varLambda ^i_b, z^i_b, T^i_b)\), for some \(\lambda ' = {{\mathrm{poly}}}(\lambda )\).

Finally, we say that a pair of distribution ensembles \(\left\{ {\mathcal {D} _{0, \lambda }} \right\} \) and \(\left\{ {\mathcal {D} _{1, \lambda }} \right\} \) are nice w.r.t. \(\mathsf {RE}\) if they are k-nice w.r.t. \(\mathsf {RE}\) for some integer k.

Our construction of unbounded input IO and its analysis in previous sections relies only on compact RE for nice distribution ensembles. Hence we can refine Theorem 8 to the following:

Proposition 1

Assume the existence of a compact randomized encoding scheme \(\mathsf {RE}\) which is sub-exponentially-indistinguishability-secure for every pair of distribution ensemble that are nice w.r.t. \(\mathsf {RE}\); assume further the existence of sub-exponentially secure one-way functions. Then, there is an unbounded-input indistinguishability obfuscator for Turing machines.

We stress again that compact RE for nice distributions is not ruled out by the impossibility result in Sect. 6. Hence, we obtain unbounded input IO from a new assumption different from the extactability assumptions used in previous work [BCP14, ABG+13, IPS15].

Finally, we describe a candidate construction of compact RE for nice distributions using the KLW indistinguishability obfuscator for bounded-input Boolean Turing machines: Given input \((1^\lambda , M, x, T)\), the encoding is an obfuscation, using the KLW scheme, of the program \(\varPi _{M,x}\) that on input \(i \in [T]\) outputs the \(i^{th}\) bit of the output \(M^T(x)\). Since \(\varPi _{M, x}\) is Boolean, the KLW obfuscator can be applied, and the encoding time is \({{\mathrm{poly}}}(\lambda , |M|, |x|, \log T)\) (hence compact). By the security of indistinguishability obfuscation, for any \(M_1, x_1\) and \(M_2, x_2\) with identical outputs, their encodings are indistinguishable, and thus this construction is a weak compact RE. We here consider it also a candidate construction for compact RE with distributional indistinguishability.

We note that relying on a very similar construction as above, a randomized encoding scheme with only sublinear compactness (as opposed to full compactness) can be used to construct a bounded-input indistinguishability obfuscator for Turing machines. We refer the reader to the full version of this paper [LPST15] for more details.