Porcupine: A Synthesizing Compiler for Vectorized Homomorphic Encryption

ACM SIGPLAN Conferences on Programming Languages, Design, and Implementation (PLDI)


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.

Related Publications

All Publications

ICML - July 19, 2021

Making Paper Reviewing Robust to Bid Manipulation Attacks

Ruihan Wu, Chuan Guo, Felix Wu, Rahul Kidambi, Laurens van der Maaten, Kilian Q. Weinberger

IEEE Access Journal (IEEE Access) - August 1, 2021

Coded Machine Unlearning

Nasser Aldaghri, Hessam Mahdavifar, Ahmad Beirami

HPCA - May 1, 2021

Cheetah: Optimizing and Accelerating Homomorphic Encryption for Private Inference

Brandon Reagen, Wooseok Choi, Yeongil Ko, Vincent T. Lee, Hsien-Hsin S. Lee, Gu-Yeon Wei, David Brooks

Trusted Smart Contracts Workshop at Financial Cryptography (FC) - May 12, 2021

Reactive Key-Loss Protection in Blockchains

Sam Blackshear, Konstantinos (Kostas) Chalkias, Panagiotis Chatzigiannis, Riyaz Faizullabhoy, Irakliy Khaburzaniya, Lefteris Kokoris Kogias, Joshua Lind, David Wong, Tim Zakian

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy