Randomized encodings and Indistinguishability obfuscation

Question

I want to understand the difference between randomized encodings and indistinguishability obfuscation (iO).

Are randomized encodings a special type of iO?

Answer 1

No, randomized encodings are not really a form of obfuscation. Intuitively, in a randomized encoding, you encode a function $f$ into a simpler function $\hat f$ using randomness:

$\mathsf{Encode}(f;r) \rightarrow \hat f$

such that given $\hat f(x)$, you can reconstruct $f(x)$, and nothing more.

There are two crucial differences with obfuscation: (1) you are not allowed to see $\hat f$ in the clear, but only its evaluation on a point, and (2) this property only gives you security for a single evaluation of $\hat f$: if you get $\hat f(x_1), \hat f(x_2)$, this becomes completely broken in general!

On the other hand, obfuscation gives you some $\hat f$ that does not reveal which $f$ was obfuscated (among all functionally equivalent candidates), even if you see its evaluation on many points - actually, even if you get the circuit of $\hat f$ in the clear!

If it helps, randomized encodings are essentially equivalent to garbled circuits, up to some details in the exact template. More precisely, a garbled circuit would be what we call a decomposable randomized encoding, where $\hat f(x)$ contains an input-independent part, denoted $\mathsf{G}(f)$ - that's the garbling of $f$, and an input-dependent part, denoted $\mathsf{T}_x$.

For example, the standard garbled circuit construction of Yao is a computational randomized encoding of all polysize circuits as a low-depth circuit. In a sense, a garbled circuit gives you a token-based one-time obfuscation: given a circuit $f$, you can get a garbled circuit $\mathsf{G}(f)$. Now, given $\mathsf{G}(f)$ and an appropriate token $\mathsf{T}_x$ for an input $x$, you can compute $f(x)$ and nothing more.

So, decomposable randomized encodings (i.e. garbled circuits) would be a form of obfuscation where:

1. You cannot evaluate the "obfuscated" circuit on an arbitrary input: you need to get a special evaluation token for this input
2. You are only allowed to receive a single evaluation token

If you relax the second property, you get the notion of reusable garbled circuit, which are known to exist under assumptions such as LWE. This comes closer to obfuscation, but is still very far from full-fledged obfuscation: you still need an external party with private information that sends you token for every input you want to evaluate.

Answer 2

It seems that randomised encoding, as you are probably already aware, allows for two functions f(x) and g(x, r) that satisfy the following two properties.

1. Correctness: there exists some function D such that f(x) = D(g(x, r)).
2. Privacy: knowledge of g(x, r) will not feasibly reveal any knowledge of f(x) to differentiate it from f(y) without comparing g(x, r) and g(y, r).

On the other hand indistinguishability obfuscation allows a function f(x) that satisfies the following two properties.

1. Completeness: there exists some function E such that f(x) = E(x).
2. Indistinguishability: knowledge of E(x) will not feasibly reveal any knowledge of f(x) to differentiate it from f(y) without comparing E(x) and E(y).

If E(x) = g(x, r) = D(g(x, r)) was true, and the properties were otherwise satisfied, then completeness and indistinguishability would be satisfied as equivalent to correctness and privacy. Hence, in this case randomised encryption would be equivalent to indistinguishability obfuscation. However, randomised encryption expands further on this to say that g(x, r) could be any function, and not necessarily equal to E(x).

Further reading that might be of interest for the topic can be found here and here.