# Supporting Privacy of Computations in Mobile Big Data Systems +
## 4 Secure and Verifiable Cloud Computing for Mobile Systems
### Recovery and Verification of Outputs  
We address the following questions in this subsection:  
1. How does the client efficiently recover the result of the computation without carrying out the delegated computations by itself? 2. How does the client verify that the evaluator, in fact, evaluated the garbled circuit? Stated differently, is it possible for the client to determine whether the evaluator returned arbitrary numbers without carrying out any computation at all, instead of the actual garbled output for each output wire? We can enable the client to efficiently retrieve and verify the outputs received from the evaluator, \(p_{e}\). To accomplish this, each of the \(n\) parties that participates in the creation of the garbled circuit uses the cryptographically secure Blum, Blum, Shub pseudorandom number generator [13; 14], as we have described below. Let \(N=p\times q\) denote the product of two large prime numbers such that \(p\) and \(q\) are congruent to \(3\ mod\ 4\). The client chooses a set of \(n\) seed values, \(\{s_{1},s_{2},\ldots,s_{n}\}\); each seed value \(s_{i}\) belongs to \(Z_{N}^{s}\), the set of integers relatively prime to \(N\). Over a secure communication channel, the client sends the modulus value \(N\) and a unique seed value \(s_{i}\) to each party \(p_{i}\ (1\leq i\leq n)\). However, the client retains the prime factors, \(p\), \(q\), of \(N\) as secret. Let \(b_{i,j}=LSB(x_{i,j})\) denote the \(j^{th}\) bit generated by the party \(p_{i}\); here \(x_{i,j}=x_{i,(j-1)}^{2}\ mod\ N\), and \(x_{i,0}=s_{i}\). In the Boolean circuit, each wire \(\omega\) is associated with \((\omega_{0},\omega_{1})\), a pair of garbled values, and \(\lambda_{\omega}\), a 1-bit value. These are expressed as follows:  
\(\omega_{0}=\omega_{01}||\omega_{02}||\omega_{03}||\ldots||\omega_{0n}||0\),  
\(\omega_{1}=\omega_{11}||\omega_{12}||\omega_{13}||\ldots||\omega_{1n}||1\), and  
\(\lambda_{\omega}=\lambda_{\omega i}\oplus\lambda_{\omega 2}\oplus\lambda_{ \omega 3}\oplus\ldots\oplus\lambda_{\omega n}\). In the above expressions: \(\omega_{0i}\), \(\omega_{1i}\) and \(\lambda_{\omega i}\) are shares of the party \(p_{i}\ (1\leq i\leq n)\), and \(|\omega_{0i}|=|\omega_{1i}|=k\), and \(|\lambda_{\omega i}|=1\). Let \(W\) denote the number of wires in the Boolean circuit. For each wire \(\omega\ (0\leq\omega\leq W-1)\), in the Boolean circuit, each party, \(p_{i}\ (1\leq i\leq n)\), generates \((2k+1)\) pseudo random bits. Therefore, each party, \(p_{i}\), generates a total of \((W(2k+1))\) pseudorandom bits. To generate its shares \(\omega_{0i}\), \(\omega_{1i}\), and \(\lambda_{\omega i}\) for wire \(\omega\), party \(p_{i}\) concatenates the \(b_{i,j}\) values, where the indices \(j\) belong to the range: \([(\omega(2k+1)+1),(\omega+1)(2k+1)]\). Let \(\Omega_{\omega k}=\omega(2k+1)\) for concise notation. Then,  
\(\omega_{0i}=b_{i,(\Omega_{\omega k}+1)}||b_{i,(\Omega_{\omega k}+2)}||\ldots ||b_{i,(\Omega_{\omega k}+k)}\),  
\(\omega_{1i}=b_{i,(\Omega_{\omega k}+k+1)}||b_{i,(\Omega_{\omega k}+k+2)}|| \ldots||b_{i,(\Omega_{\omega k}+2k)}\),  
\(\lambda_{\omega i}=b_{i,(\Omega_{\omega k}+2k+1)}\). Short-Cut: Note that each server \(p_{i}\) must compute all the previous \((j-1)\) bits before it can compute the \(j^{th}\) bit. However, using its secret knowledge of the prime factors of \(N\), _i.e.,_\(p\), \(q\), the client can directly calculate any \(x_{i,j}\) (hence, the bit \(b_{i,j}\)) using the relation: \(x_{i,j}=x_{i,0}^{2^{j}\ mod\ C(N)}\ mod\ N\); here \(C(N)\) denotes the \"Carmichael function\", which equals the least common multiple of \((p-1)\) and \((q-1)\). Therefore, without having to compute \(\omega_{0},\ \omega_{1}\), and \(\lambda_{\omega}\) for any intermediate wire in the circuit, the client can readily compute \(\omega_{0},\ \omega_{1}\), and \(\lambda_{\omega}\) for any output wire \(\omega\) in the circuit using the secret values \(p\), \(q\).