FAST GARBLING OF CIRCUITS UNDER STANDARD ASSUMPTIONS

Yao’s Garbled circuits provide a method to compute circuits based on double decryption where keys for double decryption are the random values assigned to the input of the gates. The output of double decryption is once again a random value assigned to one of the two possible outputs (0, 1) which may be further used as input to next gate. Many optimizations of Yao’s garbled circuits have then come up one of which is free XOR. Free XOR enables the computation of XOR gates for free and it involves no necessity of any cipher text corresponding to output.

Implementation of XOR gate [free XOR]

Lct W_i⁰ be a random value associated with input i

W_a⁰, W_b⁰∈_R{0,1}ⁿ  W_c⁰ = W_a⁰ ⊕W_b⁰

Choose R∈_R {0,1}ⁿ

W_a¹= W_a⁰⊕R, W_b¹= W_b⁰⊕R and  W_c¹ = W_c⁰⊕R

Correctness of “FREE XOR” by example

Let W_c¹=W_a⁰⊕W_b¹

W_c¹ = W_a⁰⊕W_b⁰⊕R

W_c¹=W_c⁰⊕R

Implementation of AND gates (Free - XOR)

We need a hash function to analyse the gates securely. Also we have to assign permutation bits P_a,P_b ∈{0,1} for the inputs (a,b) associated with respect to AND gate.

W_a⁰ = <K_a⁰, P_a⁰> ∈_R {0,1} ⁿ⁺¹

W_b⁰ = <K_b⁰, P_b⁰>∈_R {0,1} ⁿ⁺¹

W_c⁰ = <K_c⁰, P_c⁰> ∈_R {0,1} ⁿ⁺¹

Choose R ∈_R {0,1}ⁿ

W_a¹ = <K_a⁰⊕R, P_a⁰⊕1>

W_b¹ = <K_b⁰⊕R, P_b⁰⊕1>

W_c¹ = <K_c⁰⊕R, P_c⁰⊕1>

The corresponding table entries T_⊼(i,j)  Permutated over  P_aⁱ, P_b^j,  i,j∈{0,1} will be

T_⊼ij   = H <K_a⁰ || K_b⁰ || g) ⊕ W_c⁰

T_⊼ij   = H <K_a⁰ || K_b⁰ || g) ⊕ W_c⁰

T_⊼ij   = H <K_a¹ || K_b⁰ || g) ⊕ W_c⁰

T_⊼ij   = H <K_a¹ || K_b¹ || g) ⊕ W_c¹

The above four entries pertain to garbled circuit K. The evaluator obtains W_c^g(a,b) by   XORing the hash of the input keys given to him with corresponding  tuple in table  obtained by combination of P_aⁱ, P_b^j .

This hash function is secure under circular secure correlation robustness or related key assumption

Garbled XOR with a single cipher text

The method is built using 4 PRF calls for garbling the circuit. Let the four inputs be K_i⁰, K_i¹, K_j⁰, K_j¹. Note that K_i¹=K_i⁰+△_l  

Step 1 : Compute  k_i⁰ = F_Ki(0,i)(g) and  k_c¹ = F_K(1,i) (g)

Step 2 : Compute △_l=  k_i⁰ ⊕ k_i¹

Step 3 : Compute  k_j^⊼j = F_K(⊼j,j)(g) and k_j^!⊼j =  k_j^⊼j + △_l

Step 4 : Compute output K_l⁰ =  k_i⁰ ⊕ k_j⁰ and K_l¹ = K_l⁰ ⊕△_l

Step 5 : Consider if the input in K_i⁰ and K_j¹. In such a case we cannot compute k_j¹ as it is function of K⁰_j . This can be solved by providing a cipher text T= F_K(!⊼j,j)(g) ⊕ k_j^!⊼j . Now given K_j^!⊼j it is possible to compute k_j^!⊼j as well. Not that (!⊼j )is complement of   (⊼j).

Reducing the number of PRF calls to Step 3

The output k_j⁰ can be simply taken as K_j⁰ and the pseudo random function to compute  k_j⁰ from K_j⁰ can be skipped. This reduces PRF calls from 4 to 3. Since  k_j⁰= K_j⁰ , T₀ entry of table T will be 0.

Algorithm to Implement XOR gates

1..  Set the output wire permutation bit for the ‘0’: ^⊼_l := ^⊼_i⊕^⊼_j

2.  Compute translate keys for wire  i : Compute  k_i⁰ = F_Ki(0,i)(g) and  k_c¹ = F_K(1,i) (g)

3.  Compute new offset for the output wire △_l=   k_i⁰ ⊕ k_i¹

4 .  Compute translated keys for wire j and the ciphertext for this gate

          a.      If  ⊼_j =0 , set  k_j⁰ = F_K(0,j)(g||0), k_j^{1 =} k_j^{0 +}△_l and T= F_K(1,j)(g) ⊕ k_j¹

           b.      If  ⊼_j =1 , set  k_j¹ = F_K(1,j)(g||0), k_j^{0 =} k_j^{1 +}△_l and T= F_K(0,j)(g) ⊕ k_j⁰

      5.  Compute the keys for output wire l : K_l⁰ =  k_i⁰ ⊕ k_j⁰ and K_l¹ = K_l⁰ ⊕△_l

      6.  Return (K_l⁰, K_l¹, ⊼_l,T)

Simple and Fast 4-2 garbled row reduction of non XOR gates

In previous section we removed one row of T representing garbled circuits, by setting one of the keys on the output wire to be actually K_0, than using K₀ to mask the output key. Here we improve by performing 4-2 reduction on cipher text for non-XOR gates. For case of understanding we explain the evaluation of gate first.

The gate evaluated, receives as input to gate, a table with two entries [T₁, T₂] and index I ∈ {0,1,2,3} and a value of K_i computed from the two garbled values of the input wire.

We compute K_out as follows

If i = 0 then K_out = K₀

If i = 1 then   K_out = K₁⊕T₁

If i = 2 then   K_out = K₂⊕T₂

If i = 3 then   K_out =  K₃⊕T₁⊕T₂

Let K[T_i] denote the output key with respect to i^th row of table T. We have K[T₀] = K₀ because K₀= K₀⊕T = K₀⊕0. An AND gate has two possible outputs. If K₀ is one output then we can consider K₁⊕K₂⊕K₃ to be another possible output or vice versa.

Now we need to define K[T₁], K[T₂]  and K[T₃]  and values of  T₁, T₂ and T₃ correspondingly

If K[T₁] = K₀ then T₁ = K₀⊕K₁

                  else

If K[T₁] = K₁⊕K₂⊕K₃ then T₁ = K₂⊕K₃

If K[T₂] = K₀ then T₂ = K₀⊕K₂

                   else

If K[T₂] = K₁⊕K₂⊕K₃ then T₂ = K₁⊕K₃

K[T₃] follow from values of T₁ and T₂ because T₃ = T₁⊕T₂ and K[T₃] = K₃⊕T₁⊕T₂

Since the evaluation can always compute T₃ given T₁ and T_2, the table T can be reduced to two rows.

Following is the table for garbled circuit

S	Truth table	T1	T2	K0out	K1out
3	0001	K0 ⊕ K1	K0 ⊕ K2	K0	K1⊕ K2⊕ K3
2	0010	K0 ⊕ K1	K1⊕ K3	K0	K1⊕ K2⊕ K3
1	0100	K2⊕ K3	K0 ⊕ K2	K0	K1⊕ K2⊕ K3
0	1000	K2⊕ K3	K1⊕ K3	K1⊕K2⊕ K3	K0

Correctness

K[T₃] = K₃⊕T₁⊕T₂

               = K₃⊕(K₁⊕K[T₁]) ⊕ (K₂⊕K[T₂])

               = K₁⊕K₂⊕K₃ ⊕ (K[T₁]) ⊕ (K[T₂])

If  K[T₁] = K[T₀] = K₀  or  K₁⊕ K₂⊕ K₃  then  K[T₃] is K₁⊕ K₂⊕ K₃

If  K[T₁] ≠ K[T₀]  then surely K[T₁] ⊕ K[T₂]  = K₀ ⊕ K₁⊕ K₂⊕ K₃  in which case            

K[T₃]=K₀