초록

큰 깊이에서 수행되는 Ring-LWE 기반 동형 암호화 연산은 다음 두 가지 기법의 조합을 사용합니다: 1) 큰 수를 작은 부분수/자리수로 분해하는 것, 그리고 2) X N + 1 모듈로 효율적인 순환 곱셈. 오랫동안 이 두 메커니즘은 NTT 친화적인 소수 집합 위에서 큰 수에 대한 CRT 분해를 사용하고, 곱셈에는 동일한 소수들에 대한 NTT를 사용하는 풀-RNS(full-RNS) 설정과 같이 밀접하게 연관되어 있어야 한다고 여겨져 왔습니다. 그러나 이러한 설정에서 NTT는 모든 대규모 깊이 FHE 연산의 병목 현상이었습니다. Kim 등(Crypto’2023)의 획기적인 연구 결과는 두 번째 가젯 분해를 도입하고, 이것이 실제로 병목 지점을 이동시켜 나머지 계산에 비해 NTT 계산 비용을 무시할 수 있을 정도로 낮춘다는 것을 보여줌으로써 이러한 한계를 극복하는 데 성공했습니다. 본 논문에서는 이 결과를 풀-RNS 설정을 훨씬 넘어 확장하여, 큰 수의 분해를 순환 산술 측면과 완전히 분리할 수 있음을 보여줍니다. 그 결과, 모듈러스 전환/재스케일링을 별도의 노력 없이 얻을 수 있게 되었다. 우리는 이론적 및 실증적 검증을 통해, 본 논문의 표현법을 사용한 키 전환, 외부 및 내부 곱셈, 자동형 연산의 성능이 Kim 등(2023)의 결과보다 빠름을 입증하였으며, 이러한 결과가 저수준 또는 하드웨어 최적화에 미치는 큰 영향과 FHE 컴파일러를 위한 새로운 매개변수화의 이점에 대해 논의한다. 심지어 FFT의 8분의 1과 선형 연산의 6분의 1을 제거함으로써 TFHE의 게이트 부트스트래핑 실행 시간을 단축하는 데 성공했으며, 이로 인해 최신 CPU에서 실행 시간이 5.5ms 미만으로 단축되었다.

키워드

동형 암호화, 가젯 분해, 키 전환, 2변수 표현, 부트스트래핑