# Supporting Privacy of Computations in Mobile Big Data Systems +
## Complexity
### Cost for the Client  
In order to create the garbled circuit, the client provides: (i) a unique seed value, \(s_{i}\), to each server \(p_{i}\) (\(1\leq i\leq n\)); and (ii) a seed value, \(s_{ik}\), to each pair of servers \((p_{i},p_{k})\), \((1\leq i,k\leq n)\).  
The length of each seed value, \(|s_{i}|=|N|\) for the BBS PRNG. The length of each seed \(|s_{ik}|=k\) for the PRNG \(R\), which can be implemented using a block cipher such as AES in output feedback mode. Let \(b_{s}\) denote the total number of bits that the client exchanges for the seed values. Then, \(b_{s}=n|N|+n(n-1)k=n(|N|+(n-1)k)\).  
For each plaintext input bit to the circuit, the client is required to generate the garbled input. Each garbled value is \((nk+1)\) bits long, whose least significant bit depends on the \(\lambda\) value, and the \(\lambda\) value, in turn, depends on the 1-bit shares for the \(n\) parties. Let \(b_{i}\) denote the number of bits that the client needs to generate for each input wire. Then, \(b_{i}=(nk+n)\).  
The client needs to generate both possible garbled outputs for each output wire to enable the verification of outputs. Let \(b_{o}\) denote the number of bits that the client needs to generate for each output wire. Then, \(b_{o}=(2 nk+n)\).  
Let \(W_{i}\) and \(W_{o}\) denote the number of input and output wires, respectively, in the Boolean circuit \(B\). Then, the client generates/exchanges a total of \(b_{s}+W_{i}\times b_{i}+W_{o}\times b_{o}=n[|N|+(n-1)k+W_{i}(k+1)+W_{o}(2k+1)]\) bits.  
Figure 7 shows the total number of Kbits that the client generates in order to enable the servers to construct and evaluate the garbled circuit, as well as for the verification of outputs for the 32-bit adder. This circuit has \(W_{i}=64\) input wires and \(W_{o}=33\) output wires. The security parameters are \(k=128\) and \(|N|=3072\).  
Figure 6: Size of the garbled circuit in Kbits for the 32-bit adder.  
Figure 7: Total number of Kbits that the client generates to delegate the construction and evaluation of the garbled circuit, and to verify the outputs for the 32-bit adder.  
For example, when \(n=10\), the client generates about 209 Kbits, if the security parameters are \(k=128\) and \(|N|=3072\). Furthermore, note that even when the security parameters are increased to \(k=256\) and \(|N|=15,360\), the client generates only 510 Kbits (The security parameters \(k\) and \(|N|\) are related; [PERSON] _et al._[17] provide a tabular listing of recommended combination of value-pairs \((k,|N|)\)).  
Comparing Figure 7 with Figures 4 and 5, we notice that while the servers generate and exchange Gigabytes of information to create the garbled circuit, the resource constrained mobile client, on the other hand, generates and exchanges only Kbytes of information with the evaluator and the other servers in the cloud.  
While the network traffic among the servers is a cubic function of \(n\) (Section 5.2), our result in Figure 7 shows that it is feasible to perform privacy preserving computations on behalf of resource-constrained clients, and that our system is well-suited for such clients, since they generate and exchange only compact cipher text messages with the servers - that are many orders of magnitude smaller than the amount of network traffic between the servers.