PAL: A pseudo assembly language for optimizing secure function evaluation in mobile devices

Secure function evaluation (SFE) on mobile devices, such as smartphones, allows for the creation of compelling new privacy-preserving applications. Generating garbled circuits on smartphones to allow for executing customized functions, however, is infeasible for all but the most trivial problems due to the high memory overhead incurred. We develop a new methodology of generating garbled circuits that is memory-efficient. Using the standard language (SFDL) for describing secure functions as input, we design a new pseudo-assembly language (PAL) and a template-driven compiler, generating circuits that can be evaluated with the canonical Fairplay framework. We deploy this compiler for Android devices and demonstrate that a large new set of circuits can now be generated on smartphones, with memory overhead to generate circuits solving the set intersection problem reduced by 95.6% for the 2-set case. We show our compiler's ability to interface with other execution systems and perform mobile phone specific optimizations on that execution system. We develop a password vault application to show how runtime generation of circuits can be used in practice. We also show that our circuit generation techniques can be used in conjunction with other SFE optimizations. These results demonstrate the feasibility of generating garbled circuits on mobile devices while maintaining the convenience of high-level function specification.