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₀

Software Protection and Simulation on Oblivious RAMs

In the talk “Software Protection and Simulation on Oblivious RAMs”, we explored a very different and amazing side of Secure Computation that shows how widespread its applications are. The major motivation for designing Oblivious RAM (ORAM) was to prevent duplication of software. We know that to keep the contents of the memory secure, we can use an appropriate encryption scheme to encrypt the program code and data. Is that enough? No - Software protection needs to go beyond that.

An adversary can get valuable information looking at the sequence of memory accesses. Access patterns in programs having properties like, say, a loop structure for instance, can leak some information about the program / the input in the program execution. Consider the example of a sorting program – Suppose the adversary only knows that the program is a sorting algorithm, looking at the access patterns he may be able to figure out what kind of sorting algorithm is used – for example in case of a binary search. An adversary can conduct some experiments with different inputs and get more information than he is supposed to; by looking at the sequence of memory accesses. Oblivious RAM is proposed as a solution to prevent this type of security breach.               

What does “oblivious” mean in the context of machines? – A machine is oblivious if the sequence in which it accesses memory locations is equivalent for any two inputs with the same running time. We consider the following setup - CPU has a small number of registers which can be shielded but the encrypted data and program is not shielded. The adversary cannot inspect or modify the contents of the CPU registers but can see the communication between the CPU and memory. Consider a “smart CPU” that handles the program execution in such a way that the memory access patterns leak no extra information to the adversary. We looked at two different definitions –

1)      Consider two cases when given an encrypted program as input –

(a)    Let { ap₁ } denote the memory access pattern when the program is run on smart CPU.

(b)   Let { ap₂ } denote the memory access pattern when a dummy program with same running time is run on fake CPU.

The smart CPU achieves obliviousness if the access patterns are computationally indistinguishable. Mathematically, it can be denoted as { ap₁} » { ap₂}

2)      The conditional probability for a particular input given a sequence of memory accesses which occur during an execution on that input, equals the apriori probability for that particular input. Mathematically, this can be denoted as Pr[Input|{ap}] = Pr[Input]  

Let us look at a couple of ways to design such a smart CPU. Suppose a program runs in “t” steps. Here “t” is the number of memory accesses which can be either a read/ update or a write instruction. Suppose M denotes the content of the RAM. Its size can be denoted by |M| = m. We assume m >>> t. Memory contents of the ORAM are of the form (v, x) where v denotes the virtual address in the actual RAM and x denotes the data at that address.

A trivial way to design a smart CPU that can achieve obliviousness is as follows - For every access, the CPU scans the entire memory content. This will have O(t.m) complexity. This will clearly serve the purpose to defeat the adversary since for every access, irrespective of the input, all the locations of the memory are accessed. So the adversary will not be able to distinguish when the same program is run with two different inputs. The goal has been achieved but at a very high cost. We will see how this can be optimized.

 Let us look at the “square root” algorithm – RAM is simulated by an oblivious RAM of size (m + 2√m) as shown.

m words

√m dummy words

√m shelter words

Initialization : The first (m+√m) locations are allotted to the virtual m memory words and √m dummy words. The remaining √m locations serve to store shelter words as we shall see.

The algorithm runs in epoch of √m steps. In each epoch –

A.      Contents of locations from 1 to (m + √m) are randomly permuted. Let π(v) denote the current location of address v in this epoch.

B.      Shelter is used to maintain the values retrieved in the current epoch.

Consider a single memory access to virtual address ‘v’. There is a boolean variable “found” stored in one of the CPU register initialized to false. 

1.       First the entire shelter is scanned to check whether (v,x) is present in the shelter. If the address is found, the variable “found” is set to true and the scan is continued till the entire shelter has been scanned.

2.       If the address was not found in the shelter, it is retrieved from the actual word π(v) which is the current location of the content of address v in this epoch.

3.       If the virtual address had been found in the shelter, we still need to make an access in the first (m+√m) locations to maintain the obliviousness. We access a dummy word at location (m + count) which is currently present at π(m + count). “count” is a variable that increments through the √m steps of the epoch so that different dummy words are accessed in each iteration.

4.       Now the value retrieved (updated value if there was a change, the same value otherwise) is encrypted and written into the first empty location at the shelter. All the shelter words are scanned again. Since the encryption is randomized, the adversary will not be able to distinguish if the same value was written back or the updated value.

Analysis - The access pattern is independent of the input – For each virtual access we scan through the entire shelter (√m locations), then we access one location among the first (m + √m) locations (either the actual word location or the dummy word location – this cannot be distinguished since these locations are in permuted order) and during the write-back we access √m locations of the shelter again. Thus we access a total of (2√m + 1) locations for every virtual address access. The adversary will not be able to get any additional information looking at this access pattern.

How is the permutation on the first (m + √m) locations done? The elements are tagged with randomly chosen integers drawn from the set T = {1, 2 …… n²/Ꜫ }. Say τ: {1,2…n} à T is the function that does the random allocation of tags. Then π(i) = k iff  τ(i) is the kth smallest element in { τ(j) : 1<= j <= n} . The n elements can be sorted according to the tags using Batcher’s oblivious sorting. So, suppose we want to access a location i – we actually need to perform a binary search on the tag τ(i). This is how we can retrieve the location π(i) . So what we had considered as a single access for π(i) is actually log (m+√m) accesses needed for the binary search for the tag. We need a total of (2√m + log (m+√m)) = O(√m) accesses for every virtual address access. Thus, this algorithm shows a way to simulate ORAM of size (m + 2√m) and with a complexity of O(t.√m) accesses for t virtual address accesses.

                                              

Software Protection and Simulations on Oblivious RAMs

This paper provides a "theoretical treatment of software protection" by reducing the problem to the problem of efficient simulation on oblivious RAM. It tries to create a smart system which can defeat the adversary who is trying to duplicate the software. 

The problem with our normal software (even if encrypted) is that, adversary can view the memory access patterns made by the processor and infer the underlying algorithm. The adversary can run the program multiple times and record the patterns of memory accesses each time. As a simple example, take the binary search algorithm.  

Example Attack on Normal Systems

The processor will initially access the middle element and the depending on that element, will either access the middle element in the left half or the middle element in the right half and so on. The adversary has access to the memory and can see the (encrypted) data flowing from memory to the CPU. By noticing this access pattern the adversary can ascertain with high confidence that binary search is used in the underlying software. 

So there is a need to hide the data in the memory as well as the memory accesses (type and address) made by the CPU. The adversary should not be able to infer anything new by looking at the access pattern.  

Role of Hardware 

The paper claims that purely software-based solution is impossible to prevent piracy since any software (even if encrypted) can be copied bit by bit and can be run on any machine. Therefore a Software-Hardware-package consisting of a physically shielded CPU and an encrypted program needs to be used. 

Shielded CPU: 

·           Has a small amount of storage (registers) 

·          Will run the encrypted program using the memory and other components of the computer 

·          Has to be physically shielded (meaning adversary cannot see what is happening inside and cannot interfere with it in any way) 

The adversary tries to learn the software by initiating executions of the encrypted program on a choice of inputs and watching both the memory contents and the communication between CPU and memory. 

The CPU defeats the adversary if no probabilistic polynomial-time adversary can distinguish  

So there are two types of protection that is needed 

1.             The program along with the data needs to be encrypted 

2.              The access patterns must be hidden 

The example of binary search shows that encryption alone is not sufficient. We call a machine oblivious if the sequence in which it accesses memory locations is equivalent for any two inputs with the same running time. 

Hiding Access Patterns – Trivial Method 

Whenever CPU needs to access a variable, the entire contents of the memory is read and written in some fixed order. This shows that it is possible to completely hide the access pattern. For deterministic schemes, this is the best technique.  To do better, randomization needs to be introduced. 

Hiding Access Patterns – ORAM 

To hide the access patterns, RAM need to be simulated in an oblivious way. To do that ORAM technique is used. 

Let M be the RAM we need to simulate and let m=|M| 

Number of accesses is t. 

To simulate RAM of size m, ORAM of size m+2√m is required 

The ORAM can be visualized as 

<Virtual>	<Dummy>	<Shelter>
m	√m	√m

Each entry in the ORAM is of the form (v_i,d_i) where v_i is the address in the original RAM and d_i is the data stored at v_i. 

√m dummy values along with the m actual contents of the RAM are permuted in some random order using the permutation π(1, ..., m +√m ) and placed in the first m +√m locations (Virtual + Dummy) of the ORAM (rest are filled with empty values).  This permutation is done using Batcher's sorting network and the randomization comes from inside the secure CPU. So after this permutation, the adversary cannot make out the mapping of the order in ORAM to the actual order. 

The CPU keeps a counter count that counts the number of memory accesses. Initially this is kept to zero. 

1.       The CPU is trying to access address v_i . 

2.       Initialize found flag = false 

3.       First go to the shelter and scan (read) every element. Even if the address has been found, continue scanning. Total √m accesses. If v_i is found, set flag=true. 

4.       If flag=false, go to π(i) and take it to CPU. 

·          Write it back to count position of shelter. 

5.       If flag=true, go to π(m+count). This will be in the dummy part of ORAM. This is done so that adversary cannot learn whether a new address was accessed or an old one. 

6.       After accessing the updating is done on the shelter. If the address was found on the shelter, then that location is updated. Else the leftmost empty is updated.

7.       If count=m, permute again and repeat. 

In order to permute again, sort first based on v and then based on σ where σ=0 means the value was modified and σ=1 means it is unmodified. Then all the entries with σ=1 is made as empty in the sorted order. The permutation has to ensure that all the empty values will go to the shelter.

After the permutation, the first m+√m entries will have the m data along with some dummy data. The process can be repeated then.

Correctness

All the memory accesses look the same to the adversary.

Step 3 - √m accesses are fixed

Step 4 and Step 5 – are indistinguishable because the original data has been randomized throughout the first m+√m entries.

Step 6 - √m accesses are fixed

References:

Goldreich, O., Ostrovsky, R.: Software protection and simulation by oblivious RAMs. JACM (1996)