Ⅰ. 서 론

동형암호(homomorphic encryption)는 암호화된 상태에서도 대수 연산을 수행할 수 있게 해 주는 특수한 암호 방식이다. 초창기에는 암호화된 데이터 위에 제한된 횟수의 동형 연산만 허용되었으나, 2009년 Gentry가 무제한 연산을 지원하는 완전동형암호(fully homomorphic encryption, FHE) 체계를 제안하면서 획기적인 진전이 이뤄졌다^[1]. 이후 연구들은 연산 속도와 정밀도를 지속적으로 개선해 왔으며, 현재 완전동형암호는 컴퓨터 비전, 자연어 처리, 통계 분석, 의료 데이터 등 다양한 분야에서 프라이버시 보호 도구로 활용되고 있다^[2].

최근에는 완전동형암호 환경에서 컨볼루션 신경망(convolutional neural networks)을 실행하려는 연구가 활발하다^[3-6]. 이 연구들이 초점을 두고 있는 클라이언트-서버 시스템에서는 사용자가 이미지를 완전동형암호로 암호화해 서버에 전송하면, 서버는 복호화 없이 이미지 추론을 수행한 뒤 암호화된 결과만 돌려준다. 덕분에 서버는 원본 데이터를 전혀 볼 수 없고, 비밀키를 가진 클라이언트만이 결과를 확인할 수 있다.

본 연구는 완전동형암호 스킴 가운데 널리 쓰이는 RNS-CKKS(residue number system variant of Cheon–Kim–Kim–Song)^[7,8] 기반 컨볼루션 신경망 연산에 초점을 맞춘다. RNS-CKKS는 실수형 데이터를 한 암호문에 대량으로 담아 빠르게 계산할 수 있어 각광받고 있다. 최근 RNS-CKKS를 이용해 residual network(ResNet)으로 CIFAR-10 이미지를 분류한 연구가 보고됐는데^[4], 이들은 효율적인 데이터 인코딩 기법과 rectified linear unit(ReLU) 함수의 다항식 근사 덕분에 높은 정확도를 달성했다.

하지만 선행 연구^[4]에서는 처리 시간이 여전히 길었으며, 이는 주로 부트스트래핑 단계 때문이었다. RNS-CKKS 스킴에서 부트스트래핑이 가장 고비용 연산이므로, 그 횟수를 줄이는 것이 필수적이다. Canadian Institute for Advanced Research-10 (CIFAR-10) 이미지 데이터를 분류하는 경우 암호문에 포함되는 데이터의 양이 전체 슬롯(slot) 개수에 비해 적어, 기존 연구에서는 암호문 전체 슬롯을 완전히 활용하지 않은 상태에서 부트스트래핑을 수행하였다. 이러한 방식은 비효율적이며, 결과적으로 더 많은 부트스트래핑을 요구하게 된다.

본 논문에서는 여러 이미지에 대해 동시에 ResNet 연산을 수행하는 경우, 암호문 전체 슬롯을 활용한 상태에서 부트스트래핑을 수행함으로써 연산 시간을 줄이는 방법을 제안한다. 구체적으로는 병합 알고리즘 Merge(k,s) 및 분리 알고리즘 Split(k,s)을 도입한다. 부트스트래핑을 수행하기 직전에 여러 암호문들을 하나의 암호문으로 병합한 후 부트스트래핑을 수행하고, 다시 여러 암호문으로 분리하는 방식이다. 이렇게하면 여러 암호문에 대해 수행해야 할 부트스트래핑을 하나의 부트스트래핑으로 대체함으로써 전체적인 연산 시간을 크게 줄일 수 있다.

본 연구에서는 유명한 RNS-CKKS 스킴 라이브러리인 Lattigo^[9]를 활용하여 제안하는 병합 부트스트래핑 사용 시, 전체 ResNet에서 필요한 부트스트래핑 수행 시간을 분석한다. 제안하는 병합 부트스트래핑을 사용해 각각 2개, 4개, 8개의 CIFAR-10 이미지를 동시에 ResNet-20으로 분류할 경우, 분할 상환 시간(이미지 당 시간)이 각각 415초, 306초, 283초가 소요된다. 이는 기존 연구^[4]에서 제시된 분할 상환 시간인 683초에 비해 각각 39%, 55%, 59%의 시간이 줄어든 것을 의미한다. 또한, 2개의 이미지를 병합 부트스트래핑을 사용하여 동시에 분류하는 경우를 실제로 구현한 결과 분할 상환 시간이 기존 연구에 비해 37% 감소하였다.

Ⅱ. 배경지식

본 장에서는 완전동형암호 RNS-CKKS에 대한 개념과 RNS-CKKS 상에서의 컨볼루션 신경망 연산 방법에 대해 소개한다.

2.1 RNS-CKKS

RNS-CKKS 스킴^[7,8]은 완전동형암호를 대표하는 방식 가운데 하나로, 암호화된 상태에서도 대수 연산을 수행할 수 있게 한다. 스킴의 모든 연산은 다항식 환(polynomial ring)에서 정의되며, 다항식 차수가 N 이면 하나의 암호문에는 n=N/2개의 실수(또는 복소수) 요소로 이루어진 벡터가 담긴다. RNS-CKKS는 이 벡터에 대해 성분별 덧셈과 곱셈을 동형적으로 지원한다. 암호화와 복호화를 각각 Enc, Dec로 표기하면, 벡터 [TeX:] $$a \in \mathbb{R}^n$$을 암호화한 결과는 Enc(a)이고 복호화를 거치면 a=Dec(Enc(a))가 성립한다. 벡터 a의 각 요소는 암호문에서 '슬롯'으로 불리며 슬롯의 총 개수는 n이다.

RNS-CKKS 스킴의 동형 덧셈(⊕) 스칼라 곱셈(⊙) 넌스칼라 곱셈(⊗) 연산은 다음을 만족한다.

여기서 [TeX:] $$a \cdot b$$는 두 벡터 a,b의 성분별 곱셈 결과 벡터를 나타낸다.

또한, RNS-CKKS 스킴에서는 벡터의 성분들의 위치를 이동시키는 회전 연산 [TeX:] $$\operatorname{Rot}(\cdot)$$을 제공한다. 어떤 벡터 [TeX:] $$a=\left(a_0, a_1, \cdots, a_{n-1}\right) \in \mathbb{R}^n$$ 및 음이 아닌 정수 r에 대해 다음 식이 성립한다.

여기서 [TeX:] $$\left(a_r, a_{r+1}, \cdots, a_{n-1}, a_0, \cdots a_{r-1}\right)$$은 벡터 a를 왼쪽으로 r만큼 순환 이동(cylic shift)시킨 벡터를 나타낸다. 만약 r이 음수라면 Rot(Enc(a);r)은 벡터 a의 성분들을 오른쪽으로 r만큼 순환 이동시킨다.

RNS-CKKS 스킴을 활용하면 어떤 대수적 연산이든 암호화된 상태에서 수행 가능하다. 예를 들어, 어떤 실수 벡터 x에 대해 다수의 성분별 덧셈, 곱셈을 사용하여 실수 벡터 y를 출력하는 연산 회로 F를 생각해보자. 즉, y=F(x)가 성립하는 상황이다. 이 때, 모든 덧셈을 ⊕로 대체하고 모든 상수곱을 ⊙로, 모든 변수간의 곱셈을 ⊗로 대체하여 생성한 동형 연산 회로를 [TeX:] $$\bar{F}$$라 하자. 이 경우, 다음의 식이 성립한다.

따라서, 입력 x에 대해 연산 회로 F를 수행하는 것은, 먼저 x를 암호화한 다음에 암호화된 상태에서 F에 대응하는 동형 연산 회로 [TeX:] $$\bar{F}$$을 수행하고, 마지막으로 결과를 복호화하는 과정과 동일하다는 것을 알 수 있다. 이를 클라이언트-서버 시스템에 적용해본다면, 서버는 클라이언트의 암호화된 이미지 Enc(x)에 대해 동형 연산 회로 [TeX:] $$\bar{F}$$를 수행하는 상황에 해당된다. 이러한 방식으로, 클라이언트는 자신의 데이터를 서버에게 노출하지 않아도 이미지 추론 서비스를 이용할 수 있게 된다.

RNS-CKKS 스킴에서는 연속적인 곱셈을 수행할 수 있는 횟수가 암호문의 ‘레벨’로 제한된다. 곱셈을 한 번 실행할 때마다 레벨이 감소하고, 레벨이 0에 도달하면 부트스트래핑^[10]을 통해 레벨을 다시 높여야 한다. 이 과정을 주기적으로 거치면 사실상 무제한으로 동형 연산을 이어갈 수 있지만, 부트스트래핑은 스킴 전체에서 가장 시간이 오래 걸리는 단계이므로 그 횟수를 최소화하는 것이 성능 개선의 핵심이다.

2.2 RNS-CKKS 상에서의 컨볼루션 신경망

최근에 RNS-CKKS 상에서 암호화된 데이터로 컨볼루션 신경망을 계산하는 연구가 활발히 진행되고 있다^[5,6]. 컨볼루션 신경망에서는 비대수적 활성화 함수(activation function) ReLU 함수를 포함하는 경우가 많아, 이를 RNS-CKKS 스킴에서 직접적으로 계산하는 것은 어렵다. 그래서 일반적으로 ReLU 함수를 다항식으로 근사하고, 이 근사된 다항식을 동형 연산으로 연산한다. 최근에는 ReLU 함수를 정밀하게 다항식으로 근사하는 방법^[11,12]이 연구되었고, ReLU 함수를 이 근사 다항식으로 대체한 근사 컨볼루션 신경망이 기존 컨볼루션 신경망과 매우 유사한 추론 정확도를 보이는 것이 확인되었다^[3].

또한, 컨볼루션 신경망은 기본적으로 3차원 텐서(tensor) 간의 복잡한 연산을 수행하는데 RNS-CKKS에서는 1차원 벡터 연산만을 지원한다. 기존 연구^[4]에서는 RNS-CKKS 상에서 1차원 벡터 연산만을 활용하면서도 대표적인 컨볼루션 신경망인 ResNet을 수행하는 방법을 개발하였다^[4]. 이 논문에서는 먼저 3차원 텐서 [TeX:] $$A=\left(A_{i, j, k}\right)_{0 \leq i\lt h_i, 0 \leq j\lt w_i, 0 \leq k\lt c_i} \in \mathbb{R}^{h_i \times w_i \times c_i}$$을 1차원 벡터 [TeX:] $$v \in \mathbb{R}^{h_i w_i c_i}$$로 맵핑하는 함수 MultPack를 정의한다. 3차원 텐서를 1차원 벡터에 맵핑할 때 일정한 간격(gap)을 두면서 맵핑하는데 그 간격을 [TeX:] $$k_i$$라 하자. 간단한 설명을 위해 [TeX:] $$k_i^2 \mid c_i$$이라고 가정하자. 만약, [TeX:] $$c_i$$가 [TeX:] $$k_i^2$$의 배수가 아니라면 텐서에 0 값을 가진 추가적인 채널을 채널 A에 덧붙여 채널 개수가 [TeX:] $$k_i^2$$의 배수가 되도록 조정한다. [TeX:] $$t_i=c_i / k_i^2$$라 하자. MultPack 함수를 수행하기 위해, 먼저 텐서 A를 또 다른 3차원 텐서 [TeX:] $$A^{\prime}=\left(A_{i, j, k}^{\prime}\right)_{0 \leq i \lt k_i, 0 \leq j \lt w_i, 0 \leq k \lt t_i} \in \mathbb{R}^{k_i h_i \times k_i w_i \times t_i}$$로 맵핑하는데 이 때, [TeX:] $$A_{i, j, k}^{\prime}=A_{\left\lfloor i / k_i\right\rfloor,\left\lfloor j / k_i\right\rfloor, k_i^2 k+k_i\left(i \bmod k_i\right)+j \bmod k_i}$$가 되도록 한다. 이 과정은 [TeX:] $$k_i^2$$개의 채널 텐서를 하나의 큰 텐서에 멀티플렉싱(multiplexing)^[4]하는 형태이다. 그 후, 텐서 [TeX:] $$A^{\prime}$$를 1차원 벡터 [TeX:] $$v \in \mathbb{R}^{k_i^2 h_i w_i t_i}=\mathbb{R}^{h_i w_i c_i}$$에 맵핑하는데 래스터-스캔 방식(raster-scan fashion)으로 순차적으로 맵핑한다. 구체적으로는, 첫 번째 채널부터 마지막 채널까지 순서대로 데이터를 맵핑한다. 각 채널의 데이터를 맵핑할 때, 왼쪽에서 오른쪽으로 수평적으로 값을 나열하고, 이후 아래 행으로 이동하여 이 과정을 반복한다. 이 때, 이 [TeX:] $$v \in \mathbb{R}^{h_i w_i c_i}$$가 바로 MultPack(A)가 된다.

ResNet 파라미터의 경우 어떤 [TeX:] $$n_s \mid n\left(=2^{15}\right)$$에 대해 [TeX:] $$h_i w_i c_i=n_s$$가 된다. 이 때, [TeX:] $$\operatorname{MultPack}(A) \in \mathbb{R}_s^n$$를 [TeX:] $$n / n_s$$번만큼 반복하여 얻은 벡터를 [TeX:] $$v^{\prime} \in \mathbb{R}^n$$이라고 할 때 CptMultPack 함수는 CptMultPack [TeX:] $$(A)=v^{\prime} \in \mathbb{R}^n$$를 만족시키도록 정의된다. 즉, [TeX:] $$v^{\prime}=[v|v| \cdots \mid v]$$를 만족한다.

기존 연구^[4]에서 제시된 멀티플렉스 병렬 컨볼루션(multiplexed parallel convolution)은 CptMultPack 형태로 RNS-CKKS로 암호화된 데이터에 대해 컨볼루션을 수행하더라도 결과가 동일한 CptMultPack 형태로 유지되도록 설계되었다. 평문 ResNet에서의 특정 컨볼루션의 입력 텐서를 [TeX:] $$A \in \mathbb{R}^{h_i \times w_i \times c_i}$$라 하고 출력을 [TeX:] $$A^{\prime} \in \mathbb{R}^{h_0 \times w_0 \times c_0}$$라 하자. 그러면 이에 대응하는 멀티플렉스 병렬 컨볼루션은 Enc(CptMultPack(A))를 입력으로 받아 Enc(CptMultPack(A'))를 출력하는 알고리즘이다. 기존 연구에서 구현된 RNS-CKKS 기반의 ResNet은 입력 이미지를 CptMultPack 형태로 암호문에 패킹하고, 암호화된 상태에서 멀티플렉스 병렬 컨볼루션과 ReLU 등의 연산을 반복적으로 수행한다. 그리고 이 과정을 거친 후 마지막에 복호화를 통해 암호화된 상태에서의 ResNet 연산 전체를 완료한다.

Ⅲ. 병합 부트스트래핑

기존 연구^[4]에서의 ResNet 구현에서 수행 시간의 70% 이상을 부트스트래핑이 차지하므로, 실행 시간을 줄이기 위해서는 부트스트래핑 과정의 시간을 최소화하는 것이 중요하다. 현재 문제점은 기존 연구에서 부트스트래핑 과정에서 암호문의 슬롯 전체를 활용하지 않아 비효율성이 발생하는 점이다. 본 연구에서는 이러한 문제를 해결하기 위해 여러 CIFAR-10 이미지에 대해 동시에 ResNet을 수행하면서 n개의 슬롯 전체를 최대한 활용하려고 한다. 이를 위해 제안하는 병합 및 분리 알고리즘을 사용하여 암호문의 모든 슬롯을 효율적으로 활용하여, 이를 통해 필요한 부트스트래핑의 횟수를 줄이고자 한다.

3.1 병합 알고리즘

기존 연구^[4]에서 사용된 CptMultPack 패킹 방법은 데이터를 [TeX:] $$n / n_s$$만큼 중복하여 암호문에 담는다. 이는 실제 데이터 개수 [TeX:] $$n_s$$가 암호문의 전체 슬롯 개수 n보다 작기 때문이며, 전체-슬롯 부트스트래핑 대산 희소-슬롯 부트스트래핑^[10]을 사용하여 수행 시간을 줄이기 위한 것이다. 본 논문에서는 이러한 중복을 최소화하고, 데이터 전체 슬롯을 보다 효율적으로 활용하여 부트스트래핑의 횟수를 줄이기 위한 암호문의 병합 과정을 제안한다.

2의 거듭제곱인 k와 s가 주어졌다고 하자. k개의 암호문 [TeX:] $$c t_0, c t_1, \cdots, c t_{k-1}$$ 각각에는 n/ks개의 슬롯에만 실제 데이터가 들어 있고, 나머지 슬롯들은 0으로 채워져 있다. 이 암호문들을 하나로 합쳐, n개 모든 슬롯에 데이터가 가득한 단일 암호문을 만들 수 있다. 구체적으로는 [TeX:] $$c t_0$$부터 [TeX:] $$c t_{k-1}$$까지 포함된 총 n/s개의 데이터를 순서대로 이어 붙인 뒤, 이 배열을 s번 반복해 n개의 데이터를 채운다. s > 1인 경우 동일 데이터를 여러 번 복제해 두는 이유는 희소-슬롯 부트스트래핑 기법을 활용하기 위해서다. 알고리즘1은 이렇게 k개의 암호문을 하나로 합치는 Merge(k,s) 절차를 설명하며, 여기서 [TeX:] $$c t_{\text {zero }}$$는 영벡터를 암호화한 암호문을 뜻한다.

여기서 주목해야 할 점은 기존 연구^[4]에서 멀티플렉스-병렬 컨볼루션을 수행한 후의 암호문이 텐서 [TeX:] $$A \in \mathbb{R}^{h_i \times w_i \times c_i}$$에 CptMultPack 함수를 적용하여 얻은 [TeX:] $$\operatorname{CptMultPack}(A) \in \mathbb{R}^n$$ 꼴이며 이는 어떤 [TeX:] $$n^{\prime} \mid n$$을 만족하는 [TeX:] $$n^{\prime}$$에 대해 [TeX:] $$n^{\prime}$$ 개의 데이터가 [TeX:] $$n / n^{\prime}$$번 반복된 형태라는 점이다. 이는 알고리즘 1의 암호문 형태, 즉, 반복이 안 된 형태와는 다르다. 알고리즘1에서의 입력 암호문은 m/ks개의 슬롯에만 MultPack(A) 형태의 데이터가 있고 나머지 슬롯은 0으로 채워져 있다. 그러나 기존 연구에서의 멀티플렉스-병렬 컨불루션 과정을 살펴보면 먼저 MultPack(A) 꼴을 만들고 이를 회전 및 덧셈 연산을 사용하여 반복함으로써 CptMultPack(A)를 얻는다. 이러한 점을 고려하면, 마지막 회전/덧셈 연산 과정을 생략하고 MultPack(A) 꼴을 얻은 상태에서 바로 Merge(k,s) 알고리즘을 사용할 수 있다. 이후에 설명할 Split(k,s) 알고리즘을 통해 다시 CptMultPack(A) 꼴을 얻게 되므로, 후속 멀티플렉스-병렬 컨볼루션 수행에는 문제가 없다.

알고리즘(Algorithm) 1.

Merge(k,s) 알고리즘 (Merge(k.s) algorithm)

그림 1은 k=4인 경우 Merge(4,1)의 동작과정을 시각화하며, 각 암호문들을 복호화했을 때 얻을 수 있는 데이터를 표현하고 있다. 이 그림에서 색칠된 사각형은 데이터가 존재하는 부분을 나타내며, 이는 [TeX:] $$2^{15} / 4=2^{13}$$개의 숫자로 구성되어 있다. 반면, 흰색 사각형은 0으로 전부 채워진 부분을 나타낸다. 4개의 암호문에 각각 적절히 회전 연산 Rot을 적용하여 회전시킨 후 합치면, 모든 슬롯에 데이터가 존재하는 병합된 암호문 [TeX:] $$c t_{\text {merge }}$$를 얻을 수 있다.

그림(Fig.) 1.

Merge(4,1) 알고리즘의 동작 과정 (Process of Merge(4,1) algorithm)

이렇게 4개의 암호문을 병합한 후 부트스트래핑을 수행하면, 단 한 번의 전체-슬롯 부트스트래핑만으로 충분하다. 이를 “병합 부트스트래핑”이라 부르며, 이는 연산 효율성을 크게 향상시킨다. 이와 대조적으로, 병합을 하지 않는 경우, 총 4번의 희소-슬롯 부트스트래핑이 필요하게 된다. 희소-슬롯 부트스트래핑은 전체-슬롯 부트스트래핑에 비해 시간이 약간 덜 소요되지만, 이를 4번 반복하게 되면 전체-슬롯 부트스트래핑보다 많은 시간이 소요된다.

3.2 분리 알고리즘

Merge(k.s) 알고리즘으로 k개의 암호문을 하나로 합친 뒤 부트스트래핑을 적용하면, 본래 k번 수행해야했던 (희소-슬롯) 부트스트래핑을 단 한 번으로 줄일 수 있다. 다만 합친 암호문에 부트스트래핑을 끝낸 뒤에는, 이후 멀티플레스 병렬 컨볼루션을 위해 다시 여러 암호문으로 분리하는 과정이 필요하다

가령 n/ks개의 슬롯에만 데이터가 있고 나머지는 0으로 채워진 k개의 암호문을 합쳐 암호문 ct를 얻었다고 하자. ct는 n개의 슬롯 모두에 데이터가 존재하며, 원래 k개 암호문에 있떤 값이 슬롯마다 s회씩 반복 저장돼 있다. 이때 ct를 n/ks개의 데이터를 ks회 반복한 형태로 구성된 k개의 암호문 [TeX:] $$c t_{\text {split }}^{(0)}, c t_{\text {split }}^{(1)}, \cdots, c t_{\text {split }}^{(k-1)}$$로 되돌리고자 한다. 알고리즘2는 이와 같이 병합된 ct를 다시 k개의 암호문으로 분할하는 Split(k,s) 절차를 설명한다.

알고리즘2에서 [TeX:] $$S_{k, s, i} \in \mathbb{R}^n$$는 원소가 1과 0으로만 이루어진 일차원 벡터이다. 각각의 [TeX:] $$0 \leq j \lt s$$에 대해 [TeX:] $$[(k j+i) n / k s,(k j+i+1) n / k s-1)$$ 범위 안에 있는 인덱스 l에 대해 [TeX:] $$S_{k, s, i}[l]=1$$이 되며, 그 외의 l에 대해서는 [TeX:] $$S_{k, s, i}[l]=0$$이다. 이 [TeX:] $$S_{k, s, i}$$는 모든 슬롯에 데이터가 들어있는 암호문에서 선택된 데이터에만 1을 곱하고 나머지 데이터에는 0을 곱하여 제거하는 기능을 수행한다.

알고리즘(Algorithm) 2.

Split(k,s) 알고리즘 (Split(k.s) algorithm)

그림 2는 Split(4,1)의 동작과정을 시각적으로 보여준다. 4개의 암호문이 병합된 암호문 ct가 주어져있을 때 [TeX:] $$S_{k, s, i}$$ 벡터를 곱하여 원하는 부분만 추출하고 나머지 값들은 0으로 만든다. 그 후 동형 회전 및 덧셈 연산을 사용하여 동일한 데이터가 4번 반복되어 모든 슬롯에 데이터가 차게 한다. 이는 어떤 텐서 [TeX:] $$A \in \mathbb{R}^{h_i \times w_i \times c_i}$$에 CptMultPack 함수를 적용하여 얻은 CptMultPack [TeX:] $$(A) \in \mathbb{R}^n$$ 꼴이며, 이는 이후 멀티플렉스 병렬 컨볼루션의 수행을 가능하게 한다.

그림(Fig.) 2.

Split(4,1) 알고리즘의 동작 과정 (Process of Split(4,1) algorithm)

3.3 병합 부트스트래핑을 사용한 ResNet-20

기존 연구^[4]에서는 RNS-CKKS 상에서 ResNet이 CIFAR-10 이미지들을 독립적으로 분류하는 방식을 구현하였다. ResNet을 수행하는 과정에서 암호문에 포함된 데이터의 수는 [TeX:] $$2^{14} \rightarrow 2^{13} \rightarrow 2^{12}$$ 순서대로 감소하며, ResNet-20의 경우 각 데이터의 수에 대해 암호문에 대한 부트스트래핑을 6번씩 수행한다. 즉, [TeX:] $$n_s=2^{12}, 2^{13}, 2^{14}$$ 각각에 대해 6번의 희소-슬롯 부트스트래핑을 수행한다.

이 때, 병합 부트스트래핑을 활용하여 2개의 CIFAR-10 이미지를 동시에 분류하는 경우를 고려해보자. [TeX:] $$n_s=2^{14}, 2^{13}, 2^{12}$$ 만큼의 데이터가 포함되어 있는 두 암호문(서로 다른 이미지에 대한)을 각각 Merge(2,1), Merge(2,2), Merge(2,4) 알고리즘을 통해 병합한다. 이렇게 하면 병합된 암호문은 각각 [TeX:] $$n_s=2^{15}, 2^{14}, 2^{13}$$개의 데이터가 1,2,3번씩 반복된 형태가 될 것이다. 즉, [TeX:] $$n_s=2^{13}, 2^{14}$$ 각각에 대해 6번의 희소-슬롯 부트스트래핑 및 [TeX:] $$n_s=2^{15}$$에 대한 6번의 전체-슬롯 부트스트래핑을 수행하면 된다. 그 후에는 Split(2,1), Split(2,2), Split(2,4) 알고리즘을 사용하여 병합된 암호문을 분리하면, 이후에 후속 ResNet 레이어를 계속 수행할 수 있다.

4개의 CIFAR-10 이미지를 동시에 분류하는 경우를 생각해보자. 데이터 크기가 [TeX:] $$n_s=2^{13}, 2^{12}$$인 경우 네 이미지에 대한 암호문을 Merge(4,1), Merge(4,2) 알고리즘을 사용하여 병합하면 된다. 그런데 [TeX:] $$n_s=2^{14}$$인 경우 최대 2개의 암호문만 Merge(2,1) 알고리즘을 사용하여 병합할 수 있다. 따라서, 총 [TeX:] $$n_s=2^{14}$$에 대한 희소-슬롯 부트스트래핑 6번, [TeX:] $$n_s=2^{15}$$에 대한 전체-슬롯 부트스트래핑 18번이 필요하게 된다.

마지막으로 8개의 CIFAR-10 이미지를 동시에 분류하는 경우를 살펴보자. 데이터 크기가 [TeX:] $$n_s=2^{12}$$인 경우 Merge(8,1) 알고리즘을 이용하여 암호문을 병합하면 된다. [TeX:] $$n_s=2^{13}$$인 경우 최대 4개의 암호문을 Merge(4,1) 알고리즘을 통해 병합할 수 있으며, [TeX:] $$n_s=2^{14}$$인 경우 최대 2개의 암호문을 Merge(2,1) 알고리즘을 통해 병합할 수 있다. 결과적으로 총 42번의 전체-슬롯 부트스트래핑이 필요하게 된다.

이렇게 8개의 이미지가 병합되는 것이 평균 부트스트래핑 시간을 줄일 수 있는 최대 암호문 개수라 할 수 있다. 이는 ResNet에서 데이터 양이 가장 적은 경우인 [TeX:] $$n_s=2^{12}$$에서 최대 8개의 암호문을 병합할 수 있기 때문이다. 만약 데이터가 [TeX:] $$2^{12}$$보다 더 적은 다른 신경망을 사용하는 경우, 8보다 큰 k에 대하여 Merge(k,s) 및 Split(k,s) 알고리즘을 적용할 수 있을 것이다.

Ⅳ. 실험 결과

이 장에서는 병합 부트스트래핑을 활용한 RNSCKKS 기반의 ResNet-20 성능에 대한 실험 결과를 제시한다.

4.1 실험 환경

이 실험은 유명한 오픈소스 RNS-CKKS 스킴 라이브러리인 Lattigo^[9]를 기반으로 진행되었다. 실험에 사용된 컴퓨터는 2.096 GHz의 AMD Ryzen Threadripper PRO 3995WX 프로세서와 512 GB의 RAM을 탑재하였으며, Ubuntu 22.04를 운영체제로 사용한다. 본 실험에서는 1개의 CPU 코어를 사용한다.

4.2 파라미터

이 실험에서는 기존 연구^[4]에서 사용한 RNS-CKKS 기반의 ResNet-20 구현을 대상으로 하므로 비슷한 RNS-CKKS 파라미터를 채택하였다. 먼저, 다항식 차수 파라미터는 [TeX:] $$N=2^{16}$$로 설정하였고, 따라서 암화화된 벡터의 성분 개수는 [TeX:] $$n=2^{15}$$가 된다.

RNS-CKKS 스킴의 비밀키의 해밍 무게(Hamming weight)는 192로 설정하였다. 특수 모듈러스(special modulus)와 기초 모듈러스(base modulus)로는 51 비트 소수를 사용하였으며, 그 외의 모듈러스로는 46 비트 소수를 사용하였다. 본 논문에서는 연산 속도를 향상시키기 위해 기존 연구^[4]에서 사용한 1개 대신 2개의 특수 모듈러스를 사용하였다^[13]. 기존 연구에서 사용한 SEAL 라이브러리는 여러 개의 특수 모듈러스 사용 기법을 지원하지 않아, 당시에는 1개의 특수 모듈러스만 사용할 수 있었다. 스케일링 팩터(scaling factor)는 [TeX:] $$2^{46}$$으로 설정하였다.

4.3 희소-슬롯 부트스트래핑 시간

기존 연구^[4]에서 RNS-CKKS 상에서 ResNet을 수행하는데 필요한 희소-슬롯 부트스트래핑에서의 슬롯 개수 [TeX:] $$n_s$$은 [TeX:] $$2^{12}, 2^{13}, 2^{14}$$로 설정되었다. 본 논문에서 제안하는 병합 부트스트래핑을 사용할 경우에는 [TeX:] $$n_s=2^{15}$$의 경우도 필요하게 된다. 결과적으로, 총 [TeX:] $$n_s=2^{12}, 2^{13}, 2^{14}, 2^{15}$$ 슬롯에 대한 부트스트래핑을 수행하게 되며 이에 대한 부트스트래핑 시간을 비교하고자 한다. 이 때, 병합 부트스트래핑을 사용하는 경우 레벨을 하나 더 필요로 하게 된다. 구체적으로 Split(k,s) 알고리즘에서 상수벡터와의 곱셈에서 레벨을 하나 추가로 소모하며, 기존 연구^[4]에서는 레벨 30 (부트스트래핑을 위한 레벨 포함)을 사용하였는데 병합 부트스트래핑을 쓰면 레벨 31을 사용하게 된다. 병합 부트스트래핑 사용으로 인한 레벨 추가는 약간의 부트스트래핑 시간 증가로 이어지지만 그럼에도 필요한 부트스트래핑 횟수가 줄어들기 때문에 결과적으로 평균 부트스트래핑 시간을 줄일 수 있다.

표1는 슬롯 개수 및 레벨에 따른 부트스트래핑 시간을 나타낸다. 표 1의 결과는 4.4절에서 병합 부트스트래핑의 수행 시간을 구하기 위해 사용된다.

4.4 병합 부트스트래핑을 사용한 ResNet-20 수행 시간

표 2는 ResNet-20을 이용한 CIFAR-10 이미지 분류에 소요되는 총 부트스트래핑 시간을 보여준다. 이는 기존 방법을 사용하여 한 번에 1개의 이미지를 분류하는 경우와, 본 연구에서 제안하는 병합 부트스트래핑 기법을 사용하여 한 번에 2개, 4개, 8개의 이미지를 동시에 분류하는 경우를 비교한다. 실험 결과, 병합 부트스트래핑 기법을 통해 2개, 4개, 8개의 이미지를 동시에 ResNet-20을 이용하여 분류하는 경우, 기존 방법에 비해 부트스트래핑의 분할 상환 시간이 각각 39%, 55%, 59% 줄어든 것을 확인할 수 있다.

또한, 본 연구에서는 2개의 이미지를 병합 부트스트래핑을 사용하여 동시에 분류하는 경우를 실제로 구현하고 각 구성요소 별 수행시간을 분석한다. 그림 3은 병합 부트스트래핑 기법을 활용하여 ResNet-20으로 두 이미지를 동시에 분류하는 아키텍처를 보여준다.

여기서 컨볼루션과 배치 정규화(batch normalization)를 합한 알고리즘인 ConvBN’는 기존 연구^[4]의 알고리즘을 거의 그대로 사용하되 마지막 부분에서 동일한 데이터를 여러 번 반복하여 나열하는 부분만 생략한 것이며 구분을 위해 프라임(’) 기호를 사용하였다. 다만, 가장 먼저 사용되는 ConvBN 알고리즘은 여러 번 반복하여 나열하는 부분까지 그대로 포함한다. 구체적인 ConvBN 알고리즘이 필요하면 기존 논문^[4]의 ConvBN 알고리즘과 공개 소스코드를 참고할 수 있다.

그림(Fig.) 3.

병합 부트스트래핑 기법을 활용하여 ResNet-20으로 두 이미지를 동시에 분류하는 아키텍처 (Architecture for simultaneous classification of two images using ResNet-20 with merged bootstrapping technique)

알고리즘 3은 위 아키텍처에서 사용되는 Select(s) 알고리즘을 보여준다.

알고리즘(Algorithm) 3.

Select(s) 알고리즘 (Select(s) algorithm)

먼저 [TeX:] $$S^{(s)} \in \mathbb{R}^n$$을 다음과 같이 정의한다.

이 때, Select(s)은 단순히 입력 암호문 ct에 대해 [TeX:] $$c t \odot S^{\prime(s)}$$를 반환한다. 이는 동일한 데이터가 s번 반복되어있는 형태인 입력 암호문에서 첫 n/s개의 데이터만 남겨두고 나머지는 0으로 만듦으로써 반복을 없애는 역할을 한다.

표 3은 그림 3의 아키텍처를 사용하여 병합 부트스 트래핑을 활용한 ResNet-20에 의한 두 이미지 분류를 수행할 때의 수행 시간을 나타낸다.

2개의 이미지를 동시에 분류할 때 컨볼루션, ReLU, 다운샘플링, 평균-풀링(average-pooling), 완전연결 레이어(fully-connected layer)의 경우 더 많은 횟수 수행이 필요하므로 시간이 더 오래 걸린다. 부트스트래핑의 경우 횟수 자체는 동일하지만 파라미터의 레벨이 하나 더 크고 슬롯 개수를 더 많이 필요로 하므로 (희소-슬롯) 부트스트래핑 시간이 증가한다. 따라서 전체 수행 시간은 증가하지만 분할 상환 시간을 계산하기 위해 2로 나누어야 한다. 그 결과 분할 상환 시간은 기존의 888s에서 558s로 감소하게 되며 이는 37% 감소에 해당한다.

4.5 병합·분리 알고리즘의 정확도·수행시간 영향과 확장성 분석

RNS-CKKS 기반의 ResNet-20 추론 과정에서는, 일반적인(평문 상의) ResNet-20 대비 다소의 정확도 하락이 발생할 수 있다. 이러한 정확도 저하는 주로 동형 덧셈, 스칼라 곱셈, 회전 등의 RNS-CKKS의 근사 연산, 부트스트래핑, 그리고 근사 ReLU에 기인한다. 그러나 충분히 큰 스케일링 팩터를 사용하는 경우, RNS-CKKS 연산 자체의 오차는 상대적으로 무시할 수 있을 정도이며, 전체 정확도 저하는 대부분 부트스트래핑과 근사 ReLU의 근사화에 의해 결정된다. 실제로 본 연구에서 사용한 환경에서는, 부트스트래핑과 근사 ReLU의 평균 오차가 약 [TeX:] $$2^{-17} \sim 2^{-15}$$ 수준인 반면, 일반적인 RNS-CKKS 연산의 평균 오차는 [TeX:] $$2^{-36} \sim 2^{-35}$$ 수준으로 측정되어, 후자의 영향은 매우 작다.

제안하는 병합 부트스트래핑 기법은 기존의 RNS-CKKS 기반 ResNet-20 추론 구조를 그대로 유지하면서, 병합 및 분리 알고리즘을 추가한 형태이다. 이 알고리즘들은 동형 덧셈, 스칼라 곱셈, 회전 연산만을 사용하며, 이들 연산의 오차는 앞서 설명한 바와 같이 전체 정확도에 거의 영향을 미치지 않을 것으로 예상된다.

또한 병합·분리 알고리즘은 매우 낮은 연산 레벨(레벨 1~3)에서 수행되며, 연산 복잡도 역시 낮기 때문에 전체 추론 시간에 미치는 영향이 제한적이다. 실제 표 3에 따르면 병합 알고리즘과 분리 알고리즘의 전체 수행시간은 0.63초, 1.56초로 부트스트래핑 연산 827초에 비해 매우 미미한 수준이다. 다만, 분리 연산은 추가적인 레벨 소모로 인해 부트스트래핑 수행 시간이 소폭 증가하며, 이는 표1, 2를 통해 확인할 수 있다. 그러나 이러한 오버헤드는 부트스트래핑 횟수 감소 효과에 비해 작기 때문에, 결과적으로 분할 상환 시간이 감소하는 이점이 있다. 추가적인 레벨 소모를 최소화하기 위해 향후 분리 알고리즘을 컨볼루션 등의 연산과 적절히 통합하여 레벨을 공유하는 전략은 향후 연구 과제로 고려될 수 있다.

제안된 병합·분리 알고리즘은 부트스트래핑 사용으로 인해 슬롯 크기는 크지만 실제 데이터가 적어 슬롯이 비효율적으로 사용되는 상황에 효과적이다. 특히 한 클라이언트가 여러 이미지의 추론을 요청할 때 유용하다. 이 알고리즘은 FHE 기반 ResNet-20과 유사한 조건을 가진 상황은 물론, 컨볼루션 신경망 외의 다른 종류의 모델에도 활용될 수 있을 것으로 예상된다.

본 연구에서는 RNS-CKKS를 중심으로 분석하였으나, 제안한 알고리즘은 벡터 패킹 및 슬롯 회전을 지원하는 Brakerski-Gentry- Vaikuntanathan(BGV)^[14], Brakerski- Fan-Vercauteren(BFV)^[15] 등 다른 Ring Learning With Errors(RLWE) 기반 FHE 스킴에도 적용 가능하다. 또한, 본 기술은 순수 FHE만을 사용하는 환경에 적합하며, FHE와 다자간 계산을 결합한 하이브리드 접근법과 비교하면 수행 시간이 상대적으로 길지만 통신량이 적다는 장점이 있다.

Ⅴ. 결 론

본 연구는 암호문의 슬롯을 모두 활용해 여러 이미지를 동시 처리하도록 ResNet을 실행함으로써 부트스트래핑 시간의 대폭 절감을 실현하는 방안을 제시한다. 제안한 병합–분리 절차를 적용하면, 원래 각 암호문마다 수행해야 했던 부트스트래핑을 단 한 번의 작업으로 대체할 수 있다. 이 방법을 사용하여 2개, 4개, 8개의 CIFAR-10 이미지를 동시에 ResNet-20으로 분류한 경우, 부트스트래핑의 분할 상환 시간(amortized runtime; 이미지 당 시간)이 기존 방법에 비해 각각 39%, 55%, 59% 줄어들었다. 또한, 2개의 이미지를 병합 부트스트래핑을 사용하여 동시에 ResNet-20으로 분류하는 경우를 전체를 구현한 결과 분할 상환 시간이 기존 연구에 비해 37% 감소한 것을 확인하였다. 이 결과는 본 연구에서 제안한 방법이 암호화된 딥러닝 연산의 효율성을 크게 향상시킬 수 있음을 보여준다.

제안한 병합-분리 알고리즘은 정확도에 미치는 영향이 거의 없다. 다만, 이 알고리즘은 추가적인 암호문 레벨을 하나 소모하여 부트스트래핑 수행 시간이 소폭 증가하지만, 부트스트래핑 횟수 감소로 인해 전체적인 분할 상환시간은 감소한다. 향후 연구에서는 레벨 소모에 따른 오버헤드까지 제거할 수 있는 방안을 모색할 필요가 있다.

본 연구에서 제안한 기법은 부트스트래핑을 사용해야 하는 구조로 인해 슬롯은 충분하지만 실제 데이터는 적어 슬롯을 다 활용하지 못하는 비효율적인 상황에 특히 효과적이다. 이러한 상황을 가지는 다양한 암호화 딥러닝 응용에 적용 가능하며, RNS-CKKS 뿐만 아니라 BGV, BFV 등 RLWE 기반의 다른 완전동형암호 스킴에도 유사한 방식으로 적용할 수 있을 것으로 기대된다.