Izaak Meckler

Indistinguishability amplification

Posted on June 21, 2017

\(\newcommand{\ob}{\mathcal{O}}\) \(\newcommand{\Q}{\mathbb{Q}}\) \(\newcommand{\what}{\widehat}\)

This blog post is about a generalization of indistinguishability obfuscation, which might be useful.

Indistinguishability obfuscation (IO) is a cryptographic primitive (which may or may not exist). The usual way it's defined is as follows.

Definition: An indistinguishability obfuscator \(\ob\) is a probabilistic function satisfying the following.

If \(C, D : 2^n \to 2\) are two circuits computing the same function, then \(\ob(C) \cong \ob(D)\) (where \(\cong\) is computational indistinguishability.)

A way to think about this definition is that IO takes two values which are indistinguishable according to a certain weak class of distinguishers (namely, those that are only allowed to evaluate circuits at points and observe the outputs) and promote that to an indistinguishability by arbitary distinguishers.

Thought of this way, a generalization of this functionality becomes apparent. Before discussing it in full generality, let's examine another instance of this kind of indistinguishability amplification.

Definition: Consider the field (for example) \(\Q[i]\), with \(a + b i\) represented as the pair (a, b).

An indistinguishability amplifier for \(\Q[i]\) is a probabilistic function satisfying the following.

Suppose \(\alpha, \beta \in \Q[i]\) are indistinguishable by all circuits that only use the following operations to compute on values from \(\Q[i]\):

  • \(\mathsf{mul} : \Q[i] \times \Q[i] \to \Q[i]\)
  • \(\mathsf{add} : \Q[i] \times \Q[i] \to \Q[i]\)
  • \(\mathsf{div} : \Q[i] \times \Q[i] \to \Q[i] + \{ \texttt{divide_by_zero} \}\)
  • \(\mathsf{equal} : \Q[i] \times \Q[i] \to \{ 0, 1 \}\)

Then \(\ob(\alpha) \cong \ob(\beta)\). Moreover, we demand that the above operations can be lifted to work on obfuscated numbers. I.e., there are functions \(\what{\mathsf{mul}}, \what{\mathsf{add}}, \dots\) such that

  • \(\what{\mathsf{mul}}(\ob(x), \ob(y))\) is an obfuscation of \(\mathsf{mul}(x, y)\)
  • \(\what{\mathsf{add}}(\ob(x), \ob(y))\) is an obfuscation of \(\mathsf{add}(x, y)\)
  • If \(y \neq 0\), \(\what{\mathsf{div}}(\ob(x), \ob(y))\) is an obfuscation of \(\mathsf{div}(x, y)\) and \(\what{\mathsf{div}}(\ob(x), \ob(0))\) is the plaintext \(\texttt{divide_by_zero}\).
  • \(\what{\mathsf{equal}}(\ob(x), \ob(y))\) is the plaintext bit \(\mathsf{eqal}(x, y)\).

In other words, \(\ob\) is an indistinguishability amplifier for \(\Q[i]\) if whenever two numbers \(\alpha, \beta\) are algebraically indistinguishable, \(\ob(\alpha)\) and \(\ob(\beta)\) are computationally indistinguishable. For example, since \(i\) and \(-i\) satisfy all the same rational polynomials, they are algebraically indistinguishable according to our definition, and so their obfuscations \(\ob(i)\) and \(\ob(-i)\) would be computationally indistinguishable.

I'll describe the full general formal setup in a follow up post.