두 수의 비교 연산은 딥러닝을 포함한 여러 응용에서 가장 빈번하게 사용되는 연산 중 하나이다. 이에 따라 동형암호화 체계에서 비교 연산을 효율적으로 평가하기 위한 목표로 많은 연구가 수행되어 왔다. 최근 Cheon et al.(Asiacrypt 2020)은 합성 다항식을 사용하여 동형암호화된 데이터에 대해 부호 함수(sign function)를 근사하는 새로운 비교 방법을 제안하였고, 이 방법들이 최적의 점근적 복잡도를 가진다는 것을 증명하였다. 본 논문에서는 극값 최소화(minimax) 근사 다항식의 합성(composition)을 이용하여 부호 함수를 근사하는 실용적으로 최적인 방법을 제안한다. 우리는 이 근사 방법이 깊이 소모(depth consumption) 및 비(非)스칼라 곱셈의 개수 측면에서 최적임을 증명한다. 또한 제안한 동형암호 비교 연산에 대해 극값 최소화 근사 다항식의 최적 합성을 동적 계획법(dynamic programming)으로 결정하는 다항시간 알고리즘을 제안한다. 수치 분석 결과, 실행 시간을 최소화할 때 제안한 비교 연산은 이전 알고리즘에 비해 평균적으로 약 45%의 실행 시간 감소를 보였다. 마찬가지로 깊이 소모를 최소화할 때도 제안한 알고리즘은 평균적으로 약 41%의 실행 시간 감소를 보였다. 더 나아가 비교 연산에서 높은 정밀도가 요구되는 경우, 이전 알고리즘은 128비트 보안을 달성하지 못하는 반면, 제안한 알고리즘은 그 작은 깊이 소모로 인해 128비트 보안을 달성한다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.