Informally, obfuscating a program is the process of concealing what the program is doing while at the same time preserving its functionality. Among other things this serves to protect against code tampering and reverse engineering. Barak et al. [PDF] showed a number of interesting cryptographic applications of such a paradigm including: constructing homomorphic encryption and removing random oracles [PDF].

In a bit more details, an obfuscator

**O**is an efficient (probabilistic) compiler that takes a program (or a circuit) P and produces an intelligible version

**O**(P) of P with the same functionality as that of P. This is formalized by viewing

**O**(P) as a black-box in the sense that whatever

**O**(P) can compute, can also be computed given an oracle access to the original program P.

Barak et al. [PDF] showed that the above
formalism of obfuscation is problematic and is, in fact, infeasible. They showed that for some families of functions with a property Π :

**ℱ**→ {0,1}, there is f ∈**ℱ**where given any program that computes f, Π(f) can be efficiently computed. However, Π(f) cannot be efficiently computed given oracle access to f other than by random guessing. Thus, they suggested the following weaker definition termed*indistinguishability obfuscation*to replace the above formalism:
An indistinguishability obfuscator

**iO**for a class of circuits**C**ensures that given any two equivalent circuits C_{1}∈**C**and C_{2}∈**C**, the two distributions**iO**(C_{1})**and****iO**(C_{2}) are indistinguishable.The covered paper provides an indistinguishability obfuscator constructions for

**NC**(i.e. all polynomial-size, log-depth circuits) using Multilinear Jigsaw Puzzles. It exploits the theorem proven by Barrington [PDF] that proves any circuit in

^{1}**NC**can be transformed into an oblivious branching program using 2k square matrices M

^{1}^{0}

_{1},…, M

^{0}

_{k}and M

^{1}

_{1},…, M

^{1}

_{k}. Therefore, evaluating C on input x where |x|=l can be done via the following matrix product equation C(x) =0 iff ∏

_{i=1}

^{k}M

_{i}

^{xf(i)}= I.

This observation forms the basis of transforming any

**NC**circuit into a branching program.

^{1 }Barrington also showed how to transform any circuit {0,1}

^{m}→ {0,1} of depth d into a width-5 permutation branching program of length n≤4

^{d}. The program is defined by the tuples (inp(i), A

_{i,1 }, A

_{i,0}) for 1≤i≤n, where inp(i) is the function inp: [n]→[m] describing the bit of the input examined at step i, and the matrices A

_{i,b}are 5x5 permutation matrices. For any input (b

_{l}...b

_{m}) computing the program on the input corresponds to computing P=∏

_{i=1}

^{n}A

_{i,binp(i)}an returning 1 if P=I (i.e. the identity matrix) and 0 otherwise.

Now, suppose that two parties Alice with input x and
Bob with input y want to evaluate a circuit C∈

**NC**on their inputs, i.e. jointly compute C(x,y).^{1}
The construction is based on an earlier scheme by
Kilian [PDF]
which is as follows: Alice computes a randomized version of the branching program for the circuit by choosing n invertible matrices R

_{1},...,R_{n}and computes their inverses. Then she sets Ã_{i,b}=R_{i-1}A_{i,b}R_{i}^{-1}for i=1,...,n and b ∈ {0,1}. Alice now sends to Bob the matrices corresponding to her input x. Also, the two parties run an oblivious transfer protocol so that Bob obtains the matrices corresponding to his own input y. By putting the matrices in the right order, Bob can now compute C(x,y).
The OT protocol ensures that Alice does not learn Bob's
input. On the other hand, the randomization step ensures that Bob also does not
learn Alice's input.

Here Alice is regarded as the obfuscator,
whereas Bob is the evaluator.

The authors classify possible attacks on Kilian's scheme into 3
categories as follows:

- Partial Evaluation Attacks: The adversary computes and compares partial products corresponding to the same input x but different inputs y and y'. Thus, learning some information about x.

- Mixed Input Attacks: The adversary performs the matrix product correctly but does not respect the input function.

- Non-Multilinear Attacks: The attacker either computes non-multilinear functions over the matrices or does not conform to the algebraic structure of the matrices.

To apply this to Poly-sized circuits, the authors combine the above obfuscator for

**NC**with a fully homomorphic encryption scheme (FHE). The obfuscator generates to pairs (SK

^{1}_{1},PK

_{1}) and (SK

_{2},PK

_{2}) of secret/public keys for the FHE scheme. The circuit C is then encrypted under both public keys. Both public keys, both ciphertexts and an

**NC**obfuscator for decrypting using SK

^{1}_{1}are published. To evaluate the program on an input x, the evaluator uses the Eval algorithm of the FHE scheme on x and both ciphertexts to get the ciphertexts e

_{1}and e

_{2}of C(x) under both public keys. The evaluator keeps a track of all the intermediate bits in the evaluation phase which acts as a proof. The evaluator then feeds the proof along with x, e

_{1}and e

_{2}to the

**NC**obfuscator. If ciphertexts e

^{1}_{1}and e

_{2}are consistent, the obfuscator decrypt e

_{1}using SK

_{1}to reveal C(x).

Since the proof ensures that e

_{1}and e

_{2}are always consistent, we can switch back and forth to decrypting using the other secret key and thus realize the required indistinguishability.

> O is an efficient (probabilistic) compiler that takes a program (or a circuit) P and produces an intelligible version O(P)

ReplyDeleteyou mean unintelligible no?