| L | R | G |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Yao's SFE: Obfuscating Boolean Circuits
Let \(C\) be a public circuit, where \(C:\{0,1\}^n \rightarrow \{0,1\}\). Suppose A has \(x\in\{0,1\}^n\), and B has \(y\in\{0,1\}^n\), and the goal is \(F_A = C(x,y), F_B = 0\).
-
A encrypts the circuit \(C\) gate by gate starting from the input. For each input wire \(i\), A chooses two random keys \(K_i^0, K_i^1\).
It is perhaps easiest to describe how to encrypt a gate by example. Suppose A wishes to encrypt an AND gate. First its truth table is written out:
Each row is encrypted as follows:
\[ \array { E_{K^0_i}(T_1) & E_{K^0_j}(T_2) & \textrm{such that }T_1 \oplus T_2 = [K_k^0 \| 0^R] \\ E_{K^0_i}(T_1) & E_{K^1_j}(T_2) & \textrm{such that }T_1 \oplus T_2 = [K_k^0 \| 0^R] \\ E_{K^1_i}(T_1) & E_{K^0_j}(T_2) & \textrm{such that }T_1 \oplus T_2 = [K_k^0 \| 0^R] \\ E_{K^1_i}(T_1) & E_{K^1_j}(T_2) & \textrm{such that }T_1 \oplus T_2 = [K_k^1 \| 0^R] } \]The \(0^R\)'s are marker bits, to let B know that decryption has been correctly performed. An encrypted gate (Yao gate) is a random permutation of these four tuples.
-
A sends the encrypted circuit along with \(K_1^{x_1},...,K_n^{x_n}\) where \(x = x_1...x_n\).
-
B needs \(K^{y_1}_{n+1},...,K^{y_n}_{2n}\), where \(y = y_1...y_n\), and these are obtained from A by doing \(n\) 1-out-of-2 OT’s.
-
B evaluates the encrypted circuit to get \(K^b_C\) where \(b = C(x,y)\). B sends \(B^b_C\) to A.
-
A validates it by checking that it is one of \(K^0_C, K^1_C\).
So by the end has \(C(x,y)\) and B has nothing, and neither have any extra information. The communication is linear in the size of the circuit. B does the work and A gets the answer. The scheme is information theoretically secure against A, while complexity assumptions are used to argue for security against B.
An open problem is to reduce the communication so that is linear in the size of the input.
Example: distributed AES: A has \(K_1\), B has \(K_2\), let \(K = K_1 \oplus K_2\) and \(C = AES(M,K)\) for some message \(M\). Then Yao’s protocol allows joint decryption of \(C\) without reconstructing the key.
Example: software rental: A has \(x\), B has \(F\), A wants \(F(x)\). B can send A the encryption of the circuit F and then use 1-out-of-2 OT’s to let A evaluate on \(x\) only. But the same encryption of the circuit cannot be used more than once. Finding a multiuse SFE protocol is an open problem.