Write a Blog >>
PLDI 2020
Mon 15 - Fri 19 June 2020

We present a new and general method for optimizing homomorphic
evaluation circuits. Although fully homomorphic encryption (FHE) holds
the promise of enabling safe and secure third party computation,
building FHE applications has been challenging due to their high
computational costs.
Domain-specific optimizations require a great deal of expertise on the
underlying FHE schemes, and FHE compilers that aims to lower the
hurdle, generate outcomes that are typically sub-optimal as they rely
on manually-developed optimization rules.
In this paper, based on the prior work of FHE
compilers, we propose a method for automatically learning and using
optimization rules for FHE circuits. Our method focuses on reducing
the maximum multiplicative depth, the decisive performance bottleneck,
of FHE circuits by combining program synthesis and term rewriting.
It first uses program synthesis to learn equivalences of
small circuits as rewrite rules from a set of training circuits. Then,
we perform term rewriting on the input circuit to obtain a new circuit
that has lower multiplicative depth. Our rewriting method maximally
generalizes the learned rules based on the equational matching and its
soundness and termination properties are formally proven.
Experimental results show that our method generates
circuits that can be homomorphically evaluated
1.18x – 3.71x faster (with the geometric mean of 2.05x)
than the state-of-the-art method.
Our method is also orthogonal to existing domain-specific optimizations.

Thu 18 Jun
Times are displayed in time zone: Pacific Time (US & Canada) change

16:00 - 17:00
Multi-modal Synthesis of Regular Expressions
PLDI Research Papers
Qiaochu ChenUniversity of Texas at Austin, USA, Xinyu WangUniversity of Michigan at Ann Arbor, USA, Xi YeUniversity of Texas at Austin, USA, Greg DurrettUniversity of Texas at Austin, USA, Isil DilligUniversity of Texas at Austin, USA
Optimizing Homomorphic Evaluation Circuits by Program Synthesis and Term Rewriting
PLDI Research Papers
DongKwon LeeSeoul National University, South Korea, Woosuk LeeHanyang University, South Korea, Hakjoo OhKorea University, South Korea, Kwangkeun YiSeoul National University, South Korea
CacheQuery: Learning Replacement Policies from Hardware Caches
PLDI Research Papers
Pepe VilaIMDEA Software Institute, Spain, Pierre GantyIMDEA Software Institute, Spain, Marco GuarnieriIMDEA Software Institute, Spain, Boris KöpfMicrosoft Research, n.n.