For your phone only: custom protocols for efficient secure function evaluation on mobile devices

Mobile applications increasingly require users to surrender private information, such as GPS location or social networking data. To facilitate user privacy when using these applications, secure function evaluation (SFE) could be used to obliviously compute functions over encrypted inputs. The dominant construction for desktop applications is the Yao garbled circuit, but this technique requires significant processing power and network overhead, making it extremely expensive on resource-constrained mobile devices. In this work, we develop Efficient Mobile Oblivious Computation, a set of SFE protocols customized for the mobile platform. Using partially homomorphic cryptosystems, we develop protocols to meet the needs of two popular application types: location-based and social networking. Using these applications as comparison benchmarks, we demonstrate execution time improvements of 99% and network overhead improvements of 96% over the most optimized garbled circuit techniques. These results show that our protocols provide mobile application developers with a more practical and equally secure alternative to garbled circuits. Copyright (C) 2013 John Wiley & Sons, Ltd.