Porcupine: a synthesizing compiler for vectorized homomorphic encryption
Open Access
- 18 June 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 375-389
Abstract
Homomorphic encryption (HE) is a privacy-preserving technique that enables computation directly on encrypted data. Despite its promise, HE has seen limited use due to performance overheads and compilation challenges. Recent work has made significant advances to address the performance overheads but automatic compilation of efficient HE kernels remains relatively unexplored. This paper presents Porcupine, an optimizing compiler that generates vectorized HE code using program synthesis. HE poses three major compilation challenges: it only supports a limited set of SIMD-like operators, it uses long-vector operands, and decryption can fail if ciphertext noise growth is not managed properly. Porcupine captures the underlying HE operator behavior so that it can automatically reason about the complex trade-offs imposed by these challenges to generate optimized, verified HE kernels. To improve synthesis time, we propose a series of optimizations including a sketch design tailored to HE to narrow the program search space. We evaluate Porcupine using a set of kernels and show speedups of up to 52% (25% geometric mean) compared to heuristic-driven hand-optimized kernels. Analysis of Porcupine’s synthesized code reveals that optimal solutions are not always intuitive, underscoring the utility of automated reasoning in this domain.Keywords
All Related Versions
This publication has 39 references indexed in Scilit:
- TinyGarble: Highly Compressed and Scalable Sequential Garbled Circuits2015
- (Leveled) Fully Homomorphic Encryption without BootstrappingACM Transactions on Computation Theory, 2014
- From relational verification to SIMD loop synthesis2013
- Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme2013
- Differential Privacy for Relational Algebra: Improving the Sensitivity Bounds via Constraint SystemsElectronic Proceedings in Theoretical Computer Science, 2012
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP2012
- Computing arbitrary functions of encrypted dataCommunications of the ACM, 2010
- Fully homomorphic encryption using ideal lattices2009
- Boolector: An Efficient SMT Solver for Bit-Vectors and Arrays2009
- Calibrating Noise to Sensitivity in Private Data Analysis2006