# Supporting Privacy of Computations in Mobile Big Data Systems +
## 3 Background
### [PERSON]'s Garbled Circuit  
Any computation (simple examples of which could be addition of two numbers, computation of hamming distance between two bit sequences, _etc._) can be represented as a Boolean circuit. Such a Boolean circuit can be expressed using only \(\{AND,XOR\}\) gates, which corresponds to a \"functionally-complete\" set of operators. Therefore, any mechanism capable of performing \(AND\) and \(XOR\) operations, homomorphically, can enable secure delegation of any arbitrary computation. In our work, we achieve the homomorphic computation of \(AND\) and \(XOR\) gates using garbled circuits [6; 7; 8; 9].  
Each wire in the circuit is associated with a pair of keys known as \"garbled values\" that correspond to the underlying binary values. For example, the circuit in Figure 2 has seven wires, \(\omega_{i}\) (\(0\leq i\leq 6\)), and three gates, \(P,Q,R\), denoting \(OR\), \(AND\), \(XOR\) gates respectively. Keys \(\omega_{i}^{0}\), \(\omega_{i}^{1}\) represent the garbled values corresponding to binary values \(0\), \(1\) respectively on the wire \(\omega_{i}\).  
Figure 2: A circuit with three gates, \(P,Q,R\), and seven wires, \(\omega_{i}\) (\(0\leq i\leq 6\)).  
Each gate in the circuit, is associated with a list of four values, in a random order, known as \"garbled table\". Table 1 shows the garbled tables for the gates \(P,Q,R\) of Figure 2. Let \(x,y\in\{0,1\}\). Let \(E_{k}[v]\) denote the encryption of \(v\) using \(k\) as the key. Then, each entry in the garbled table for \(P\) is of the form, \(E_{\omega_{0}^{x}}[E_{\omega_{1}^{y}}[\omega_{4}^{x\oplus y}])\). Similarly, each entry in the garbled table for \(Q\) and \(R\) are of the forms, \(E_{\omega_{2}^{x}}[E_{\omega_{3}^{y}}[\omega_{5}^{x,y}]]\) and \(E_{\omega_{4}^{x}}[E_{\omega_{5}^{y}}[\omega_{6}^{x\oplus y}]]\), respectively.  
Suppose that the client wishes to delegate the computation of Figure 2, _i.e.,_ (\((a|b)\oplus(c.d)\)), to a server in the cloud. The server is provided with a description of the circuit (Figure 2) along with the set of the garbled tables (Table 1), which together represents a \"garbled circuit\". However, the client keeps the mapping between the garbled values and the underlying binary values as secret. For example, to evaluate the circuit with inputs \(a=1,\ b=0,\ c=0,\ d=1\), the client provides the set of garbled inputs, \(\omega_{0}^{1},\ \omega_{1}^{0},\ \omega_{2}^{0},\ \omega_{3}^{1}\), to the cloud server.  
Now, assume that there exists a mechanism to determine whether a value is decrypted correctly; for example, through zero-padding. Using \(\omega_{0}^{1}\), \(\omega_{1}^{0}\) as keys, the server attempts to decrypt all the four entries in the garbled table for gate \(P\); however, only the fourth entry will decrypt correctly to reveal the garbled output \(\omega_{4}^{1}\). Similarly, using \(\omega_{2}^{0}\), \(\omega_{3}^{1}\) as keys, the first entry in the garbled table for gate \(Q\) reveals the garbled output \(\omega_{5}^{0}\). Finally, on using \(\omega_{4}^{1},\ \omega_{5}^{0}\) as keys, the third entry in the garbled table for gate \(R\) reveals the garbled output \(\omega_{6}^{1}\). Thus, the server can perform an \"oblivious evaluation\" of the garbled circuit and return the result of the computation \(\omega_{6}^{1}\) to the client. Using the secret mapping, the client can determine that the garbled value \(\omega_{6}^{1}\) corresponds to the binary value 1.  
In our work, we use an alternative garbled circuit design from Beaver, Micali, Rogaway (BMR [11; 12]), and adapt it, as we describe in Section 4, for the purpose of building a secure cloud computing system.