Optimizing Homomorphic Evaluation Circuits via Search-based Method

Abstract

In this dissertation 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 dissertation, 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, term rewriting, and equality saturation. 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 uses the equational matching with generalized version of the learned rules, and its soundness property is formally proven. Our optimizations also try to explore every possible alternative order of applying rewrite rules by time-bounded exhaustive search technique called equality saturation. Experimental results show that our method generates circuits that can be homomorphically evaluated 1.08x – 3.17x faster (with the geometric mean of 1.56x) than the state-of-the-art method. Our method is also orthogonal to existing domain-specific optimizations.

본 논문에서는 탐색기반 기법을 통해 동형암호 회로를 최적화하는 새로운 방법론을 제시한다. 완전동형암호 기술은 제3자에게 개인정보의 가공 및 보관을 위탁할 수 있게 해주는 차세대 기술이지만, 동형암호 프로그램의 매우 큰 계산비용이라는 한계점 때문에 널리 쓰이지 못하고 있는 실정이다. 동형암호 상용화를 위해 다양한 방식으로 동형암호 프로그램 최적화가 이루어지고 있지만, 수동으로 동형암호 프로그램의 성능을 최적화하는 것은 대체로 높은 수준의 전문성을 필요로 하고, 충분한 전문성을 갖추고 있다고 하더라도 매우 고된 과정이다. 또한 동형암호 프로그램을 자동으로 최적화하는 동형 컴파일러 기술들은 대부분 수동으로 고안된 간단한 최적화 규칙에 의존하고 있기 때문에, 만족할만한 최적화 성능이 나오지 않고 있는 실정이다. 우리는 프로그램 합성 기술을 통해 자동으로 동형암호 회로의 최적화 규칙을 발굴하고 식 다시쓰기 및 동일식 모두탐색 기술을 이용해 이러한 규칙들을 효율적으로 적용하는 방법론을 제시한다. 우리의 방법론은 동형암호 회로 성능을 결정짓는 가장 중요한 요인인 곱셈깊이를 줄이는 것에 집중한다. 먼저 프로그램 합성을 통해 학습대상 동형암호 프로그램의 작은 일부분과 똑같은 실행의미를 가지면서 곱셈깊이는 더 작은 새로운 프로그램을 찾아내고, 이 부분 프로그램 쌍을 일반화하여 하나의 최적화 규칙으로 학습한다. 학습한 최적화 규칙은 식 다시쓰기 기술을 기반으로 한 E-매칭을 통해 입력으로 들어오는 최적화 대상 프로그램에 유연하게 적용되며, 이때 최적화의 안전성이 보장된다는 것이 증명되어있다. 또한 우리의 최적화 방법론은 동일식 모두탐색 기술을 사용해 주어진 제한시간 내에 최적화 규칙들을 적용할 수 있는 서로다른 모든 경우의 수를 탐색하여 보다 최적에 가까운 결과를 찾아낸다. 널리 쓰이는 실제 동형암호 프로그램들에 대해 최적화를 적용해본 결과, 기존의 동형암호 최적화 방법론에 비해 최소 1.08배에서 최대 3.17배까지 성능향상을 관측할 수 있었다.(기하평균 1.56배) 우리의 최적화 방법론은 기존의 수동 최적화 방법론을 통한 성능향상을 해치지 않으면서 추가로 적용가능하다는 강점이 있다.