동형암호 컴파일러를 위한 다항식 최적화 알고리즘

Abstract

동형암호 컴파일러에 장착될 다항식 최적화 알고리즘을 개발하고 실험을 통해 최적화 성능을 측정하였다. 딥뉴럴 네트워크 모델의 작성에 자주 사용되는 수학 함수들의 근사다항식에서 비용이 큰 곱셈 연산의 횟수가 연산 순서를 다르게 함에 따라 달라지는 것에 착안하여 다항식의 곱셈 횟수를 최소화하는 최적화 알고리즘을 고안하였다. 본 알고리즘은 차수가 작은 다항식의 계산결과를 통해 큰 다항식의 결과를 계산하는 동적 프로그래밍 기반의 방법으로, 이미 계산한 곱셈의 횟수를 중복으로 계산하지 않으며 모든 경우를 다 탐색하여 저장하여 활용도가 높아진다는 장점이 있다. 본 알고리즘은 적당한 차수의 다항식에서 기존 방법에 비해 최대 33\%로 곱셈 횟수를 감소시켜 성능을 개선하였다. 그러나 적당한 차수에서는 의미있는 결과를 보여주지만, 차수가 올라감에 따라서 연산횟수가 지수적으로 늘어난다.

This paper introduces a polynomial optimization algorithm which would be on a homomorphic compiler and checks the optimization performance through experiments. We devise an optimization algorithm that minimizes the number of multiplications of polynomials, focusing on the number of multiplication operations which is very expensive in the approximate polynomial of mathematical functions frequently used in the creation of deep neural network models. This algorithm is a dynamic programming-based method that calculates the result of a large polynomial through the calculation result of a polynomial with smaller order, and has the advantage of increasing utilization by searching and storing all cases without duplicating the number of multiplications already calculated. This algorithm improves performance by reducing the number of multiplications up to 33\% in a suitable order polynomial compared to the existing method. However, the number of operations increases exponentially as the order increases.