# Supporting Privacy of Computations in Mobile Big Data Systems +
## Complexity
### Computation Cost of Creating the Garbled Circuit  
Let \(W\) denote the total number of wires in the circuit \(B\). For each wire, each server, \(p_{i}\)\((1\leq i\leq n)\), generates \((2k+1)\) bits using the Blum, Blum, Shub (BBS) pseudorandom number generator (PRNG) [13; 14] for its share of garbled values and the \(\lambda\) value. Therefore, the \(n\) servers collectively generate a total of \(b_{1}=n(2k+1)W\) bits using the BBS PRNG. Let \(N\) denote the modulus value in BBS PRNG (note: \(|N|=3072\) achieves 128-bit security [17]). Then, \(n(2k+1)W\) modular multiplication operations in \(Z_{N}^{*}\) are necessary to generate bits using BBS PRNG. Let \(W_{o}\) denote the number of output wires in the circuit \(B\). Let \(G\) denote the PRNG, which we have described in Section 4.1.3, that outputs a sequence of \((2 nk+2)\) bits on providing a \(k\)-bit input seed. Each server uses the PRNG \(G\), on its share of each garbled value for every non-output wire in the circuit \(B\). Then, while creating the garbled circuit, the \(n\) servers collectively use the PRNG \(G\), \(2n(W-W_{o})\) times to generate a total of \(b_{2}=4n(nk+1)(W-W_{o})\) bits. Let \(N_{g}\) denote the total number of gates in the circuit \(B\). For protocol of Goldreich, the total number of pseudorandom bits generated by each party using the PRNG \(R\), equals \(8(n-1)m\times N_{g}\), where \(m=(3+2(nk+1)+2k)\) (Section 4.2). Thus, the \(n\) parties collectively generate a total of \(b_{3}=8n(n-1)(3+2(nk+1)+2k)\times N_{g}\) bits using the PRNG \(R\). Note that both the PRNG \(G\) and PRNG \(R\) can be realized using a block cipher such as AES (which stands for advanced encryption standard) operating in output feedback mode. Let \(t_{1:4}\) denote the number of 1-out-of-4 OTs to create one garbled table entry (Section 5.2). Then, the total number of 1-out-of-4 OTs to create the complete garbled circuit \(GC\) is at most \(4N_{g}\times t_{1:4}=4N_{g}\times(nk+1)\times n(n-1)/2\). Figure 4: Amount of network traffic to compute one garbled table entry as a function of \(n\). During a 1-out-of-2 oblivious transfer, the sender and chooser generate a total of \(|C|+|k|+|r_{0}|+|r_{1}|=(4|p|-1)\) bits. Each 1-out-of-4 oblivious transfer involves the cost of two 1-out-of-2 oblivious transfers, in addition to generating a total of \(|L_{0}|+|L_{1}|+|R_{0}|+|R_{1}|=4k\) bits. A very small constant number of modular arithmetic operations, AES and SHA crypto operations are carried out during each OT. While creating the garbled circuit \(GC\), these sets of operations are performed \(4N_{g}\times(nk+1)\times n(n-1)/2\) times; and a total of \(b_{4}=4N_{g}\times(nk+1)\times(n(n-1)/2)\times(8|p|+4k-2)\) bits are generated during the OTs. To summarize, the total number of bits that are generated by the \(n\) parties while creating the garbled circuit is \(b=b_{1}+b_{2}+b_{3}+b_{4}=(n(2k+1)W)+(4n(nk+1)(W-W_{o}))+(8n(n-1)(3+2(nk+1)+2 k)\times N_{g})+(4N_{g}\times(nk+1)\times(n(n-1)/2)\times(8|p|+4k-2))\). Thus, for any given Boolean circuit, when the security parameters \(k\) and \(|p|\) are fixed, the total number of bits generated randomly is a cubic function of \(n\). For example, consider the construction of a garbled circuit for adding two 32-bit numbers. The corresponding Boolean circuit has a total of \(W=439\) wires, \(W_{o}=33\) output wires, and \(N_{g}=375\) gates (The 32-bit adder circuit in [18] has 127 \(AND\) gates, 61 \(XOR\) gates and 187 \(NOT\) gates. Note that a \(NOT\) gate is equivalent to an \(XOR\) gate, since \(NOT(x)=(1\oplus x)\). As we have mentioned in Section 4.1, we consider only two different types of gates, namely, \(\{AND,XOR\}\) in our work. Alternatively, note that more efficient constructions are possible; for example, an \(AND\) gate with a \(NOT\) gate on its output wire may be replaced with a single \(NAND\) gate, if the output wire of the \(AND\) gate is not an input wire for any other gate in the circuit).