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 [2]. 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]
Let
Wi0 be a random value associated with input i
Wa0,
Wb0∈R{0,1}n Wc0 = Wa0
⊕Wb0
Choose
R∈R
{0,1}n
Wa1=
Wa0⊕R, Wb1=
Wb0⊕R and Wc1
= Wc0⊕R
Correctness of “FREE XOR” by example
Let Wc1=Wa0⊕Wb1
Wc1 = Wa0⊕Wb0⊕R
Wc1=Wc0⊕R
Implementation of AND gates (Free - XOR)
We
need a hash function to analyse the gates securely. Also we have to assign
permutation bits Pa,Pb ∈{0,1} for the
inputs (a,b) associated with respect to AND gate.
Wa0
= <Ka0, Pa0> ∈R
{0,1} n+1
Wb0
= <Kb0, Pb0>∈R
{0,1} n+1
Wc0
= <Kc0, Pc0> ∈R
{0,1} n+1
Choose
R ∈R
{0,1}n
Wa1
= <Ka0⊕R, Pa0⊕1>
Wb1 = <Kb0⊕R, Pb0⊕1>
Wc1 = <Kc0⊕R, Pc0⊕1>
The corresponding table entries T⊼(i,j) Permutated over Pai, Pbj, i,j∈{0,1} will be
T⊼ij = H <Ka0 || Kb0
|| g) ⊕ Wc0
T⊼ij = H <Ka0 || Kb0
|| g) ⊕ Wc0
T⊼ij = H <Ka1 || Kb0
|| g) ⊕ Wc0
T⊼ij = H <Ka1 || Kb1
|| g) ⊕ Wc1
The above four entries pertain to garbled circuit
K. The evaluator obtains Wcg(a,b) by XORing the hash of the input keys given to him
with corresponding tuple in table obtained by combination of Pai,
Pbj .
This
hash function is secure under circular secure correlation robustness or related
key assumption.
Garbled
XOR with a single cipher text
[1] tries to remove the non-standard
assumption of secure correlation
The method is built using 4 PRF calls for
garbling the circuit. Let the four inputs be Ki0, Ki1,
Kj0, Kj1. Note that Ki1=Ki0+△l
Step 1 :
Compute ki0 = FKi(0,i)(g)
and kc1
= FK(1,i) (g)
Step 2 :
Compute △l= ki0 ⊕ ki1
Step 3 :
Compute kj⊼j = FK(⊼j,j)(g) and kj!⊼j = kj⊼j + △l
Step 4 :
Compute output Kl0 = ki0 ⊕ kj0 and Kl1
= Kl0 ⊕△l
Step 5 : Consider if the input in Ki0
and Kj1. In such a case we cannot compute kj1
as it is function of K0j . This can be solved by providing
a cipher text T= FK(!⊼j,j)(g) ⊕ kj!⊼j . Now given Kj!⊼j it is possible to compute kj!⊼j as well. Not that (!⊼j )is complement of (⊼j).
Reducing the number of PRF calls to 3
The
output kj0 can be simply taken as Kj0 and the pseudo random
function to compute kj0 from Kj0 can be skipped. This reduces PRF calls from 4 to
3. Since kj0=
Kj0 , T0 entry of table T will be 0.
Algorithm
for garbling of XOR gate.
Algorithm
for garbling of AND gate.
Algorithm
for evaluation
of Gate
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 K0, than using K0 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 [T1,
T2] and index I ∈
{0,1,2,3} and a value of Ki computed from
the two garbled values of the input wire.
We
compute Kout as follows
If i = 0
then Kout = K0
If i = 1 then
Kout = K1⊕T1
If
i = 2 then Kout = K2⊕T2
If
I = 3 then Kout = K3⊕T1⊕T2
Let
K[Ti] denote the output key with respect to ith row of
table T.
We
have K[T0] = K0 because K0= K0⊕T
= K0⊕0
An
AND gate has two possible outputs. If K0 is one output then we can consider
K1⊕K2⊕K3 to be another possible output or
vice versa.
Now we need to define K[T1], K[T2] and K[T3] and values of T1, T2 T3 correspondingly
If K[T1] = K0 then T1
= K0⊕K1
else
If K[T1] = K1⊕K2⊕K3 then T1 = K2⊕K3
If K[T2] = K0 then T2
= K0⊕K2
else
If K[T2] = K1⊕K2⊕K3 then T2 = K1⊕K3
K[T3] follow from values of T1
and T2 because T3 = T1⊕T2 and K[T3] = K3⊕T1⊕T2
Since the evaluation can always compute T3
given T1 and T2, the table T can be reduced to two
rows.
Following is the table for garbled circuit
Correctness
K[T3] = K3⊕T1⊕T2
= K3⊕(K1⊕K[T1]) ⊕ (K2⊕K[T2])
= K1⊕K2⊕K3 ⊕ (K[T1]) ⊕ (K[T2])
If K[T1]
= K[T0] = K0 or K1⊕ K2⊕ K3
then K[T3]
is K1⊕ K2⊕ K3
If K[T1]
≠ K[T0] then surely K[T1]
⊕ K[T2] = K0 ⊕ K1⊕ K2⊕ K3
in which case
K[T3]=K0
References
1. Fast Garbling of Circuits Under Standard Assumptions - Shay Gueron,
Yehuda Lindell, Ariel Nof and Benny Pinkas
2. Improved Garbled Circuit: Free XOR Gates and Applications - V.
Kolesnikov and T. Schneider.
