Optimizing homomorphic evaluation circuits by program synthesis and term rewriting
Woosuk Lee is an assistant professor of college of computing at Hanyang University ERICA. He received a Ph.D in computer science from Seoul National University in 2016. He was a postdoctoral researcher at Georgia Institute of Technology and University of Pennsylvania from 2016 to 2017 and 2017 to 2018, respectively.
In this talk, I will 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 aim to lower the hurdle, generate outcomes that are typically sub-optimal as they rely on manually-developed optimization rules. 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 automatically 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 over 2x faster than the state-of-the-art method with manually crafted optimization rules.