Indistinguishability Obfuscation

Last week's study group was given by Joop. The theme was Indistinguishability Obfuscation and the talk centered around the recent results in [PDF].

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₁∈C and C₂∈C, the two distributions iO(C₁) and iO(C₂) 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 NC¹ can be transformed into an oblivious branching program using 2k square matrices M⁰₁,…, M⁰_k and M¹₁,…, M¹_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^kM_i^x_f(i)= I. 
This observation forms the basis of transforming any NC¹ circuit into a branching program.
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ⁿ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). 

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₁,...,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₁,PK₁) and (SK₂,PK₂) 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₁ 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₁ and e₂ 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₁ and e₂ to the  NC¹ obfuscator. If ciphertexts e₁ and e₂ are consistent, the obfuscator decrypt e₁ using SK₁ to reveal C(x).

Since the proof ensures that e₁ and e₂ are always consistent, we can switch back and forth to decrypting using the other secret key and thus realize the required indistinguishability.