# Supporting Privacy of Computations in Mobile Big Data Systems +
## 4 Secure and Verifiable Cloud Computing for Mobile Systems
### Construction and Evaluation of Garbled Circuits  
#### 4.1.1 Construction of the Garbled Circuit, \(GC\)  
Garbled Value Pairs: In order to denote the underlying plaintext bits 0 and 1, each wire in the circuit is associated with a pair of garbled values. Let \(x,y\) denote two input wires, and \(z\) denote the output wire of a specific gate \(A\) in the circuit. Assume that \((\alpha_{0},\alpha_{1})\), \((\beta_{0},\beta_{1})\) and \((\gamma_{0},\gamma_{1})\) are the pair of garbled values associated with the wires \(x\), \(y\), and \(z\), respectively. Let \(LSB(v)\) denote the least significant bit of the number \(v\). Then, \(LSB(\alpha_{0})=LSB(\beta_{0})=LSB(\gamma_{0})=0\) and \(LSB(\alpha_{1})=LSB(\beta_{1})=LSB(\gamma_{1})=1\).  
Let \(n\) denote the number of servers and \(k\) denote the security parameter. Then, each garbled value is \((nk+1)\) bits long, and is a concatenation of shares from the \(n\) servers. Let \(a,b,c\in\{0,1\}\). Then the garbled values for gate \(A\) are as follows: \(\alpha_{a}=\alpha_{a1}||\alpha_{a2}||\alpha_{a3}||\ldots||\alpha_{an}||a\); \(\beta_{b}=\beta_{b1}||\beta_{b2}||\beta_{b3}||\ldots||\beta_{bn}||b\), \(\gamma_{c}=\gamma_{c1}||\gamma_{c2}||\gamma_{c3}||\ldots||\gamma_{cn}||c\); here \(\alpha_{ai}\), \(\beta_{bi}\), \(\gamma_{ci}\) are shares of server \(p_{i}\ (1\leq i\leq n)\).  
\(\lambda\) Value: A 1-bit \(\lambda\) value is associated with each wire in the circuit, which determines the semantics for the pair of garbled values associated with that wire. Specifically, for a garbled value \(v\) whose \(LSB(v)=b\), the underlying plaintext bit is \((b\oplus\lambda)\).  
Collusion Resistance: Let \(\lambda_{x},\lambda_{y},\lambda_{z}\) denote the \(\lambda\) values for the three wires \(x,y,z\) respectively. Then, \(\lambda_{x}=\bigoplus_{i=1}^{n}\lambda_{xi}\), \(\lambda_{y}=\bigoplus_{i=1}^{n}\lambda_{yi}\), \(\lambda_{z}=\bigoplus_{i=1}^{n}\lambda_{zi}\), where \(\lambda_{xi},\lambda_{yi},\lambda_{zi}\) are shares of server \(p_{i}\ (1\leq i\leq n)\).  
Since the \(\lambda\) value of each wire is unknown to any individual server, the evaluator of the garbled circuit must collude with each of the \(n\) servers to interpret the garbled values.  
Garbled Table: Each gate, \(A\), in the circuit, is associated with an ordered list of four values, \([A_{00},A_{01},A_{10},A_{11}]\), representing the garbled table for gate \(A\). Note that the \(\lambda\) values of the input wires, which are random, and also unknown to any of the \(n\) servers, determine the order of the entries in the garbled table. Let \(\otimes\) denote the binary operation of gate \(A\), where \(\otimes\in\{XOR,AND\}\). Then, the value of one specific entry is expressed as, \(A_{ab}=\gamma_{[(A_{x}\oplus a)\otimes(\lambda_{y}\oplus b))\oplus\lambda_{z }]}\oplus[G_{b}(\alpha_{a1})\oplus G_{b}(a_{a2})\oplus\ldots\oplus G_{b}( \alpha_{an})]\oplus[G_{a}(\beta_{b1})\oplus G_{a}(\beta_{b2})\oplus\ldots \oplus G_{a}(\beta_{bn})]\), where \(G_{a}\) and \(G_{b}\) are pseudorandom functions that expand \(k\) bits into \((nk+1)\) bits. In the expression for \(A_{ab}\), \(G_{0}(s)\) and \(G_{1}(s)\) denote the first and last \((nk+1)\) bits of \(G(s)\) respectively, where \(G\) denotes a pseudorandom generator, which on providing a \(k\)-bit input seed, outputs a sequence of \((2 nk+2)\) bits, _i.e._, if \(|s|=k\), then \(|G(s)|=(2 nk+2)\). \(G\) may represent the output of AES block cipher in output feedback mode, for example.  
For each gate in the circuit, to compute each garbled table entry \(A_{ab}\), the \(n\) servers use the secure multiparty computation protocol of [PERSON] [8; 9] (Section 4.1.2), where \(f(x_{1},x_{2},\ldots,x_{n})=A_{ab}\), and for each server, \(p_{i},(1\leq i\leq n)\), its private input, \(x_{i}=[\lambda_{xi},\lambda_{yi},\lambda_{zi},G_{b}(\alpha_{ai}),G_{a}(\beta_{ bi}),\gamma_{0i},\gamma_{1i}]\) is a vector of length \(m=(3+2(nk+1)+2k)\) bits.