Efficient Oblivious Computation Techniques for Privacy-Preserving Mobile Applications
MetadataShow full item record
The growth of smartphone capability has led to an explosion of new applications. Many of the most useful apps use context-sensitive data, such as GPS location or social network information. In these cases, users may not be willing to release personal information to untrusted parties. Currently, the solutions to performing computation on encrypted inputs use garbled circuits combined with a variety of optimizations. However, the capability of resource-constrained smartphones for evaluating garbled circuits in any variation is uncertain in practice. In , it is shown that certain garbled circuit evaluations can be optimized by using homomorphic encryption. In this paper, we take this concept to its logical extreme with Efficient Mobile Oblivious Computation (EMOC), a technique that completely replaces garbled circuits with homomorphic operations on ciphertexts. We develop applications to securely solve the millionaire’s problem, send tweets based on location, and compute common friends in a social network, then prove equivalent privacy guarantees to analogous constructions using garbled circuits. We then demonstrate up to 68% runtime reduction from the most efficient garbled circuit implementation. In so doing, we demonstrate a practical technique for developing privacy-preserving applications on the mobile platform.