AI시대의 동형암호와 데이터주권(feat. CKKS 스킴, NEAR 프로토콜)
개요
다가오는 AI 시대에서 데이터는 석유라고 불러도 될 만큼 귀중한 자원이지만 현재까지는 기업들이 개인정보를 무분별하게 수집 및 저장, 활용하고 있는 것이 현실이다. 따라서 이에 따른 자연스러운 수순으로 데이터 주권 및 프라이버시 문제가 대두되고 있으며, 이러한 맥락에서 동형암호(Homomorphic Encryption) 기술이 주목받고 있다.
동형암호 기술은 암호문 상태에서의 연산을 가능케 하는 기술이다. 동형암호 기술을 활용하면 종단간 암호화(end-to-end encryption)가 가능해지는데, 데이터를 넘겨주고 가공 및 사용하는 전 과정에서 암호화 된 상태를 유지함으로써, 데이터의 기밀성을 보장할 수 있다.
이 아티클에서는 먼저 동형암호 스킴인 CKKS 스킴의 원리와 머신러닝에서의 활용에 대해서 얘기하고, 나아가 동형암호 기술과 NEAR 프로토콜 및 블록체인 기술과의 결합을 통해 AI 시대에서 데이터 주권을 확보할 수 있는 방법에 대해서 얘기해보고자 한다.
동형암호(Homomorphic Encryption)
동형암호(Homomorphic Encryption)에서 “동형(Homomorphic)”이라는 용어는 본래 대수학 개념으로, 준동형사상(Homomorhpism)은 특정 함수가 대수적 구조를 보존함을 의미한다.
위 성질을 만족하는 암호화 함수(Encryption function)를 사용함으로써, 동형암호는 암호문 상태에서의 연산을 지원하게 된다. 이를 수식으로 표현하면 다음과 같다.
Enc(pt1) + Enc(pt2) = Enc(pt1 + pt2) (덧셈에 대한 준동형성)
Enc(pt1) * Enc(pt2) = Enc(pt1 * pt2) (곱셈에 대한 준동형성)
(여기서 Enc(Encryption)는 암호화 함수, pt1과 pt2는 평문(plaintext)이다.)
- 참고: SHE와 FHE
덧셈은 무제한으로 가능하지만, 곱셈은 제한적으로 가능한 동형암호 스킴들은 SHE(Somewhat Homomorhpic Encryption)로 부르며, 임의의 횟수의 덧셈과 곱셈을 수행할 수 있는 동형암호 스킴은 완전동형암호(Fully Homomorphic Encryption)라고 부른다.
RLWE 기반 동형암호
차세대 동형암호 스킴들(BGV, BFV, CKKS, TFHE)은 LWE 문제와 그의 변형인 RLWE 문제를 기반으로 하고 있으며, 이들의 보안성 또한 LWE, RLWE 문제의 어려움(hardness)을 기반으로 한다. 따라서, CKKS 스킴을 이해하기 위해서는 먼저 RLWE를 기반으로 동형암호 스킴을 만드는 방법을 이해해야 한다.
- LWE 문제와 RLWE 문제
LWE 문제는 2005년 Regev에 의해 소개되었으며, 다음과 같이 기술된다.
- n, q를 양의 정수라 하자.
- Zq 를 정수 공간을 q로 나눈 나머지로 구성된 환(ring)이라 하자.
(예시로, q = 5이면, Zq = {0,1,2,3,4}가 된다. Zq는 덧셈과 곱셈에 대해 특정 대수적 특징을 만족하는 환(ring)이 된다.) - χ를 Zq 상의 오류 분포라 하자.
- s ∈ Zq^n을 ‘비밀’이라고 하자.
LWE 문제의 정의:
(1) a를 Zq^n에서 균등하게 선택하고, e는 오류 분포 χ에서 선택한다.
(즉 a = (a1, a1, …a_n)이며 각 a_i는 Zq로부터 균등하게 선택된 값이다.)
(2) b = <a, s> + e (mod q)를 계산한다. 여기서 <a, s>는 a와 s의 내적이다.
(3) 이때, (Search) LWE는 문제는 (a,b)(∈ Zq^n × Zq)가 공개되었을 때, s를 역산하는 문제를 일컫는다.
RLWE 문제는 LWE 문제를 다항식 환을 활용해 변형한 것으로 다음과 같이 기술된다.
- R을 다항식 환 Z[X]/(X^n + 1)이라 하자. 여기서 n은 2의 거듭제곱이다.
(Z[X]는 계수가 정수인 다항식들로 이루어진 환이며, Z[X]/(X^n + 1)은 Z[X]에서 다항식들을 (X^n + 1)로 나눈 나머지로 이루어진 환이다.) - q를 소수라 하고, Rq를 R의 각 계수를 q로 나눈 나머지, 즉 (mod q)로 구성된 환이라 하자. 즉 Rq = Zq[X]/(X^n + 1).
- χ를 Rq 상의 오류 분포라 하자.
- s ∈ Rq 를 ‘비밀’이라고 하자.
RLWE 문제는 다음과 같이 정의된다.
(1) a를 Rq에서 균등하게 선택하고, e는 오류분포인 χ에서 선택한다.
(2) Rq 위에서 b = a*s + e 를 계산한다. (*은 Rq상에서 다항식 간 곱셈이다)
(3) 이 때, Search-RLWE 문제는 공개된 (a, b) (∈ Rq × Rq)로부터 s를 계산하는 문제를 말한다.
결국, LWE와 RLWE 문제의 차이점은 a를 Zq^n의 원소에서 뽑나, 다항식 환인 Rq에서 뽑는지에 기인한다. RLWE 기반 암호 스킴은 LWE 기반 암호 스킴에 비해 효율성 측면에서 다음과 같은 장점이 있다:
- Zq에서 n개의 원소를 균일하게 뽑는 것보다 Rq에서 원소를 하나 뽑는 것이 비교적으로 저렴하다.
- (a,b) ∈ Rq × Rq 를 저장하는 것이 (a, b) ∈ (Zq^n × Zq) 메모리 차원에서 유리하며, 이에 따라 key size가 줄어든다.
- 두 Rq 원소끼리의 곱셈은 각 다항식들을 NTT(Number Theoretic Transform)꼴로 표현함으로써 O(nlogn) 시간 안에 효율적으로 수행할 수 있다.
*참고: LWE 가정과 RLWE 가정
LWE 가정과 RLWE 가정은 앞서 기술한 문제들이 “어렵다”는 가정이다. LWE 및 RLWE 문제는 이상 격자(ideal lattice) 상에서의 특정 문제들로 환원될 수 있다는 것이 수학적으로 증명되었으며, 이 문제들을 다항시간 안에 풀 수 있는 알고리즘(양자알고리즘 포함)은 현재까지 발견되지 못하였다. 따라서 해당 가정 하에 LWE와 RLWE 기반 암호 스킴은 양자저항성이 있는 Post-Quantum Cryptography(PQC) 암호 스킴으로도 주목받고 있다.
2. RLWE 기반 동형암호 스킴
RLWE 를 바탕으로 한 동형암호 스킴에 대한 감을 잡기 위해 먼저 RLWE 기반의 아주 간단한 대칭키 동형암호 스킴을 설계해보자. (실제 BGV, BFV, CKKS 비대칭키 스킴이며, 아래 스킴보다 훨씬 복잡하지만 연산이 보존되는 원리는 비슷하다.)
pt (∈ Rq) 를 평문, s(∈ Rq)를 비밀키라 할 때 Enc, Dec, Add, Mul를 다음과 같이 정의하자:
- Enc(pt) = (b, a) = (-as + pt + e, a) (∈ Rq × Rq)
- Dec(ct) = Dec((b,a)) = b + as (∈ Rq)
- Add(ct1, ct2) = (b1 + b2, a1 + a2) (∈ Rq × Rq)
- Mul(ct1, ct2) = (b1b2, a1b2 + a2b1, a1a2)(∈ Rq × Rq × Rq) with secret key (1, s, s²)
위 스킴을 바탕으로 몇 가지 간단한 명제들을 간단하게 살펴보자.
명제 1) Dec(Enc(pt)) = pt
(sketch of pf)
Dec(Enc(pt)) = Dec((-as + pt + e, a)) = -as + pt + e + as = pt + e
이 때, 우리가 원하는 평문인 pt가 아닌 pt+e 가 튀어나온다. BGV나 BFV 스킴 같은 경우는 e가 충분히 작다면 복호화 과정에서 노이즈가 사라지도록 스킴이 설계되어있는데, 노이즈가 일정 수준 이상이 되면 평문을 복호화 할 수 없게 되어 노이즈가 일정 수준이 넘어가면 이를 초기화해주는 부트스트래핑(bootstrapping)연산을 시행해주어야 한다.
명제 2) Dec(Add(ct1, ct2)) = pt1 + pt2
(sketch of pf)
Dec(Add(ct1, ct2))
= Dec((b1 + a1, b2 + a2))
= pt1 + pt2 + e1+ e2
= pt1 + pt2 + e’
(e’ = e1+ e2)
명제 3) Dec(Mul(ct1, ct2)) = pt1 * pt2
(sketch of pf)
Dec(Mul(ct1, ct2)) = Dec((b1b2, a1b2 + a2b1, a1a2))
= b1b2 + (a1b2 + a2b1)* s + a1a2 * s²
= pt1*pt2 + pt1*e2 + pt2*e1 + e1*e2
= pt1 * pt2 + e’’
(e’’ = pt1*e2 + e1*pt2 + e1*e2)
*Mul에서는 두 가지 문제가 발생하는데 첫째는 발생하는 오차 e’’는 원래 오차 e나 Add에서 발생하는 오차 e’보다 훨씬 크다는 점이며, 두 번째는 Mul을 반복할 수록 키의 크기가 기하급수적으로 늘어난다는 점이다. 따라서 첫 번째 문제의 해결을 위해 일정 횟수 이상 곱셈 후 부트스트래핑(bootstrapping) 연산으로 노이즈를 초기화해주며, 두 번째 문제의 해결을 위해서는 재선형화(relinarization) 연산으로 키를 (1,s,s²)에서 다시 (1,s)로 바꾸어준다.
위에 서술한 대칭키 동형암호 스킴을 바탕으로 비대칭키 동형암호 스킴을 설계할 수 있으며, BGV, BFV, CKKS 스킴 모두 이러한 원리를 바탕으로 한다.
CKKS 스킴
CKKS 스킴은 2017년 [Homomorphic Encryption for Arithmetic of Approximate Numbers] 라는 논문[4]에서 소개된 동형암호 스킴으로, 저자들인(Cheong, Kim, Kim, Song)의 앞글자를 따 CKKS라는 이름이 붙여졌다. CKKS의 꽃은 다른 스킴들과 다르게 실수와 복소수 연산을 지원한다는 점이다.
CKKS 스킴은 다음 두 가지 특성 덕분에 머신러닝에 최적화되었다:
- 실수 및 복소수 연산을 지원한다.
- 여러 데이터(통상적으로 2¹⁴ 혹은 2¹⁵)가 하나의 암호문에 들어가 병렬 연산을 하는 것이 가능하다.
(이와 같이, 하나의 암호문에 여러 데이터를 암호화하는 것을 “패킹”이라 부른다.)
인코딩: 복소수에서 다항식으로
CKKS 스킴에서는 메세지(Message)와 평문(Plaintext)이 구분된다. 우리가 암호화하고자 하는 실수(또는 복소수) 데이터를 메세지라 볼 수 있는데, 메세지는 먼저 인코딩이라는 과정을 통해 다항식 꼴의 평문으로 변환된다.
연산을 보존한다는 동형암호의 특징을 잘 유지하기 위해서는 암호문과 평문 사이 뿐 아니라, 평문과 메세지를 오가는 과정에서도 연산이 보존되어야 한다. CKKS 스킴에서는 복소수 공간과 다항식 공간을 오가기 위해 동형사상(isomorphism)인 이산 푸리에 변환(Discrete Fourier Transform)을 활용한다. 인코딩은 다음 두 과정을 통해 이루어진다:
(1) 역이산 푸리에 변환(Inverse Discrete Fourier Transform)을 통해 C^(N/2) 상의 실수(복소수)벡터를 실수 계수 다항식(R[x]/(X^N+1) 상의 다항식)으로 변환한다.
(2) 실수 계수 다항식에 scaling factor를 곱한 후 정수로 근사시켜줌으로써 정수 계수 다항식(즉 Z[x]/(X^N+1) 상의 다항식)으로 변환한다.
(ex) 12.345 -> 12345 * 10^(-3))
CKKS 스킴은 인코딩 과정에서 하나의 다항식에 N/2 개의 데이터를 패킹해서 넣을 수가 있게 되고, 이에 따라 대규모 데이터에 대한 병렬 연산이 가능해진다.
*참고: CKKS 스킴에서의 오차
CKKS 스킴에서는 복호화 과정에서 노이즈가 완전히 사라지지 않는다. 그렇기 때문에 암호화 복호화 및 연산 과정에서 작은 오차가 발생하게 되는데 이러한 특성 때문에 Approximate Homomorphic Encryption이라고도 부른다.
HE-Operations
CKKS 스킴에서는 암호화된 상태에서 아래 기본 연산들이 가능하다.
(1) HE-Add
암호화된 상태에서 N/2 개의 데이터를 병렬로 slot-wise하게 더한다.
(2) HE-Mul
암호화된 상태에서 N/2 개의 데이터를 병렬로 slot-wise하게 곱한다.
(3) LeftRot(k)
암호화된 상태에서 슬롯들을 왼쪽으로 k 칸만큼 회전시켜준다.
HE-Add와 HE-Mul의 원리는 ‘RLWE 기반 동형암호 스킴’ 에서와 유사하며, LeftRot(k)는 다항식 p(x)를 다항식 p(x^{kg})(즉 x에 x^{kg} 대입한 다항식)로 바꾸어줌으로써 이루어진다.
머신러닝에서의 응용
동형암호는 머신러닝에서 다음과 같이 활용될 수 있다.
- 사용자 데이터 암호화
사용자 데이터를 암호화 해, 의료 데이터 등 민감한 개인정보를 보호하면서 AI 모델 추론 및 학습이 가능하다.
(*일례로, 동형암호를 활용해 개인의 유전자형을 추론하는 연구는 활발히 진행되고 있다.) - AI 모델 가중치 암호화
AI 모델의 가중치를 암호화한 상태로 사용함으로써 모델의 소유권 보장하며 컴퓨팅을 아웃소싱하거나 서비스를 제공하는 것이 가능해진다. - 사용자 데이터와 AI 모델 모두 암호화
사용자 데이터와 모델 가중치를 모두 암호화해 사용자의 프라이버시를 보호하고, 나아가 AI 모델의 소유권을 보장할 수 있다.
CKKS 스킴을 ML에 응용하는 상황에서는 위에서 설명한 연산들을 빌딩블록으로 사용하여 행렬연산, ReLu 등 ML에 필요한 연산들을 구현해야 하는데, 이러한 연산들을 어떻게 최적화된 형태로 구현하는 지에 따라 연산속도에서 큰 차이가 나기 때문에 이러한 최적화 방법은 중요한 연구 주제 중 하나이다.
(1)Ab 연산
AI 모델을 추론할 때 Ab(A는 n x n 행렬, b는 n x 1벡터) 연산을 해야하는 경우가 있는데, 위 그림과 같이 매트릭스의 대각방향 벡터들을 각각 하나의 다항식으로 인코딩을 한다면 훨씬 빠르게 연산을 수행하는 것이 가능하다.
A_i를 A의 i번째 대각벡터라 하였을 때, 다음이 성립한다.[5]
Ab = A_0*b + A_1 * LeftRot(b,1) + … A_(n-1) * LeftRot(b,n-1)
따라서 각각 O(n)의 HE-Add, HE-Mul, LeftRot을 통해 Ab를 암호화된 상태로 연산 하는 것이 가능하다.
(2)ReLU 연산
CKKS 스킴에서는 암호화된 상태에서 실수(복소수)의 덧셈과 곱셈이 가능하기에 다항식은 모두 구현이 가능하다. 따라서 ReLU와 같은 함수는 다항식으로 근사하여 연산을 해야하는데, 데이터의 분포를 가정하고 특정 범위 내에서 최대 오차가 최소가 되는 minimax polynomial로 근사하는 것이 가장 일반적이다.[6]
블록체인 x AI에서의 활용: NEAR AI
NEAR 프로토콜의 사용자 소유 AI(user-owned AI)비전
NEAR 프로토콜은 블록체인을 통해 현 AI 업계를 혁신하고자 하는 비전을 제시하고 있다. 현재 소수의 기업들이 AI에 있어서 대부분의 주도권을 쥐고 있는데에 반해, NEAR 프로토콜의 목표는 사용자가 스스로의 개인정보를 보호하면서도 AI의 강력한 기능을 활용할 수 있는 “완전한 주권을 가진 운영체제”를 만드는 것이다.
NEAR 프로토콜의 사용자 소유 AI(user-owned AI) 비전은 다음과 같다.
- 맞춤형 AI 어시스턴트: 사용자의 니즈에 맞춘 최적화된 서비스를 제공한다.
- 개인정보 보호: 사용자의 데이터나 자산에 대한 개인정보를 노출하지 않으면서 맞춤형 AI 어시스턴트가 작동할 수 있어야 한다.
- P2P AI 상호작용: 다른 사용자의 AI나 커뮤니티 AI와 상호작용하고 거래할 수 있는 기능을 제공한다.
동형암호 기술의 역할
퍼블릭 블록체인 상에서 AI 스택을 구축하고, 동시에 개인정보를 보호하는 것은 상당한 도전 과제다. 퍼블릭 블록체인의 특성상 모든 데이터가 공개되며, 다수의 노드가 검증과 컴퓨팅에 참여한다. 이러한 환경에서 동형암호는 NEAR 프로토콜의 사용자 소유 AI(user-owned AI) 비전 실현을 위한 핵심 기술적 솔루션이 될 수 있다. 동형암호를 통해 데이터의 기밀성을 유지하면서도 분산 환경에서의 AI 연산이 가능해지기 때문이다.
구체적으로 동형암호는 다음과 같은 방식으로 NEAR 프로토콜에서 활용될 수 있다:
- 암호화된 데이터 처리: 사용자의 개인 데이터를 암호화된 상태로 블록체인에 저장하고, 동형암호를 통해 이 암호화된 데이터를 복호화하지 않고도 처리할 수 있다. 이를 통해 개인정보를 보호하면서도 AI 모델의 학습 및 추론을 가능케 한다.
- AI 모델 소유권 확립: AI 모델의 가중치를 암호화된 상태로 유지하면서 추론을 수행할 수 있다. 이를 통해 허가받지 않은 사용을 차단함으로써, AI 모델의 소유권을 보장할 수 있다.
- AI 모델의 공동 학습: 여러 사용자의 데이터를 활용해 AI 모델을 학습시킬 때, 각 사용자의 데이터를 암호화된 상태로 유지하면서 학습을 진행할 수 있다.
이러한 동형암호의 적용은 NEAR 프로토콜이 지향하는 사용자 소유 AI(user-owned AI) 비전을 실현하는 데 핵심적인 역할을 할 수 있다. 개인정보 보호, AI 모델의 안전한 운영, 그리고 생태계 참여자들 간의 안전한 상호작용을 가능케 함으로써, NEAR는 현재 중앙화된 AI 산업의 한계를 극복하고 사용자 중심의 새로운 AI 생태계를 구축할 수 있을 것이다.
결론
이 아티클에서는 CKKS 스킴을 중심으로 동형암호의 작동원리에 대해 알아보았고, 동형암호를 AI에 적용하는 방법까지 알아보았다. FHE ML은 아직까지 일반적인 머신러닝에 비해 연산속도가 느려 제한적인 상황에서만 활용되고 있으나, 미국 국방부 산하 기관인 DARPA(Defense Advanced Research Projects Agency)는 동형암호 연구에 매년 수십억 이상을 투입하고 있는 뜨거운 연구주제이다.
더불어, 동형암호 기술과 NEAR 프로토콜 같은 블록체인 기술의 융합은 사용자들이 자신의 데이터와 AI 활용에 대한 주권을 확보할 수 있는 새로운 미래를 열어줄 것으로 기대된다.
Reference
Oded Regev. 2009. On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56, 6, Article 34 (September 2009), 40 pages. [1]
Lyubashevsky, V., Peikert, C., and Regev, O. 2013. On ideal lattices and learning with errors over rings. J. ACM 60, 6, Article 43 (November 2013), 35 pages. [2]
Gentry, C., Halevi, S., Smart, N.P. (2012). Homomorphic Evaluation of the AES Circuit. In: Safavi-Naini, R., Canetti, R. (eds) Advances in Cryptology — CRYPTO 2012. CRYPTO 2012. Lecture Notes in Computer Science, vol 7417. Springer, Berlin, Heidelberg. [3]
Cheon, J.H., Kim, A., Kim, M., Song, Y. (2017). Homomorphic Encryption for Arithmetic of Approximate Numbers. In: Takagi, T., Peyrin, T. (eds) Advances in Cryptology — ASIACRYPT 2017. ASIACRYPT 2017. Lecture Notes in Computer Science(), vol 10624. [4]
Halevi, S., Shoup, V. (2014). Algorithms in HElib. In: Garay, J.A., Gennaro, R. (eds) Advances in Cryptology — CRYPTO 2014. CRYPTO 2014. Lecture Notes in Computer Science, vol 8616. Springer, Berlin, Heidelberg. [5]
Cheon, J.H., Kim, D., Kim, D., Lee, H.H., Lee, K. (2019). Numerical Method for Comparison on Homomorphically Encrypted Numbers. In: Galbraith, S., Moriai, S. (eds) Advances in Cryptology — ASIACRYPT 2019. ASIACRYPT 2019. Lecture Notes in Computer Science(), vol 11922. [6]
서울대학교 FHE-School 2024 강의안 [7]
https://near.org/blog/self-sovereignty-is-near-a-vision-for-our-ecosystem [8]
[10]
