# Supporting Privacy of Computations in Mobile Big Data Systems +
## 7 Related Work  
Homomorphic encryption methods enable computations directly on the encrypted data, without requiring private decryption keys. For example, the product of two ciphertext messages produces a ciphertext corresponding to the product of the underlying plain text messages in the RSA public key system [2]. [PERSON] _et al._[23] present an additive and multiplicative homomorphic scheme in which polynomials are used to represent ciphertext; however, multiplication operations drastically increase the size of the cipher text in their scheme. Recently, fully homomorphic encryption (FHE) schemes (e.g., [3; 4; 5]) have been proposed, which enable performing any arbitrary computation on encrypted data. However, FHE schemes are currently not suitable for mobile cloud computing applications due to extremely large cipher text size and computational requirements beyond the capabilities of mobile devices today. Our work presents a far better alternative suitable for mobile systems. [PERSON]'s garbled circuits have been mainly used in the context of secure two-party computation [6; 7; 24]. [PERSON] _et al._[25] present an extensive survey of secure multiparty computation, along with numerous potential applications--some examples of which are privacy preserving data mining, private set intersection, electronic voting and electronic auction. Over the years, a number of secure two-party and multiparty computation systems have been built (e.g., [26; 27; 28]). In secure multiparty computation systems, multiple parties hold private inputs and receive the result of the computation. While multiple parties participate in the creation of garbled circuits, only the client has the private inputs and obtains the result of the computation, in garbled form however, in our secure cloud computing system. As we have described in Section 4.2, in our work, we adapt secure multiparty computation protocols [8; 9; 11; 12], for building a secure and verifiable cloud computing for mobile systems. Some existing works [29; 30] use arithmetic circuits for performing homomorphic addition and multiplication operations. However, Boolean circuits are sufficient for our purpose of creating the garbled table entries, since it only involves simple binary operations such as _XOR_ and _AND_ (Section 4.1.1). Additionally, Boolean circuits are more efficient than arithmetic circuits for  
Figure 14: Client-side cost to determine the nearest ATM. homomorphic comparison of numbers, which we have used abundantly in our privacy preserving search application (Section 6), since comparison using an arithmetic circuit involves a large number of multiplications and communication rounds among the participants [29; 30]. Branching programs offer an alternate method for representing Boolean functions. [PERSON] _et al._[31] present a branching program formulation for secure health monitoring using homomorphic encryption. [PERSON] _et al._[31] present simulation results on real ECG (which stands for electrocardiogram) data, and note that their approach of using branching programs provides significant speedup in comparison to methods using traditional circuits. It could be a very interesting avenue for future research to explore the use of garbled circuits in conjunction with branching programs, especially for secure cloud computing applications and mobile big data systems. In the Twin clouds [32] secure cloud computing architecture, the client uses a private cloud for creating garbled circuits and a public commodity cloud for evaluating them. Our solution, however, utilizes multiple public cloud servers for creating as well as evaluating the garbled circuits. Stated alternatively, our solution obviates the requirement of private cloud servers. Furthermore, in twin clouds, the privacy of the client data is lost if the evaluator colludes with the sole/only server that constructs the garbled circuit. In our work, on the other hand, the use of multiple servers for construction of garbled circuits offers greater resistance to collusion (Section 2).