Wednesday, October 23, 2013

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 C1C and C2C, the two distributions iO(C1) and iO(C2) are indistinguishable.

The covered paper provides an indistinguishability obfuscator constructions for NC1 (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 NC1 can be transformed into an oblivious branching program using 2k square matrices M01,…, M0k and M11,…, M1k. Therefore, evaluating C on input x where |x|=l can be done via the following matrix product equation C(x) =0 iff ∏i=1kMixf(i)= I. 
This observation forms the basis of transforming any NC1 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≤4d. The program is defined by the tuples (inp(i), Ai,1 , Ai,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 Ai,b are 5x5 permutation matrices. For any input ( computing the program on the input corresponds to computing P=∏i=1nAi,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∈NC1 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 R1,...,Rn and computes their inverses. Then she sets Ãi,b=Ri-1 Ai,b Ri-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 NC1 with a fully homomorphic encryption scheme (FHE). The obfuscator generates to pairs (SK1,PK1) and (SK2,PK2) 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 NC1 obfuscator for decrypting using SK1 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 e1 and e2 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, e1 and e2 to the  NC1 obfuscator. If ciphertexts e1 and e2 are consistent, the obfuscator decrypt e1 using SK1 to reveal C(x).

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

1 comment:

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

    you mean unintelligible no?