Privacy Preserving Machine Learning (3) - Homomorphic Encryption

이전 포스트에서 Privacy를 보존하며 머신러닝을 할 수 있는 기법의 예시로 Federated Learning과 Differential Privacy에 대해서 알아보았습니다(혹시 이전 글을 읽어보시지 않았다면 한번쯤 읽어보는것을 추천드립니다). 시리즈의 마지막이 될 이번 글에서는 Homomorphic Encryption(동형암호)에 대해서 소개하도록 하겠습니다.

 

암호에 대해서는 많이들 들어보셨을거라고 생각합니다. 보안이라는 개념에 대해서 가장 많이들 떠올리는 예시가 바로 암호이며, 암호는 우리가 공개하고 싶지 않은 정보를 숨길 수 있도록 도와줍니다. 암호는 크게 대칭키 암호와 공개키 암호로 나눌 수 있는데, 예시를 들어 설명하자면 다음과 같습니다. 살다보니 갑자기 하늘에서 다이아 여러개가 떨어져서(?) 친구에게 나눔을 하려고 합니다. 그냥 택배로 보내면 중간에 탈취당할 위험이 있기 때문에, 다이아를 금고에 넣어서 보낼 계획입니다. 그렇다면 저와 제 친구 둘 다 동일한 금고의 비밀번호를 알고 있으면 되는데, 이는 대칭키 암호에 해당합니다. 이 경우에는 암호화(금고에 다이아를 넣고 잠금)에 필요한 비밀키(비밀번호)와 복호화(금고에서 다이아를 꺼냄)에 필요한 비밀키(비밀번호)가 동일합니다. 반면에, 어떤 금고는 금고에 물건을 넣고 잠글 때 특수한 비밀번호를 입력할 필요가 없이 "42"라는 번호만 입력하면 누구나 잠글 수 있다고 합니다. 다만, 금고에서 물건을 꺼내기 위해서는 앞의 경우와 똑같이 해당 비밀번호를 알고 있어야만 열린다고 합시다. 이 상황은 공개키 암호에 해당되는데, 공개키 암호에서는 암호화를 할 때에는 모두에게 알려진 공개키("42")를 입력하면 되지만, 복호화를 하기 위해서는 특정 비밀키(비밀번호)를 입력해야만 합니다. 공개키 암호는 일반적으로 대칭키 암호에 비해서 속도가 느리지만, 대칭키 암호와는 다르게 송신자와 수신자 사이에 비밀키를 공유할 필요가 없어서 좀 더 안전하다는 장점이 있습니다. 공개키 암호의 대표적인 예시로는 큰 수의 소인수분해가 어렵다는 것을 이용한 RSA암호나 타원곡선에서의 discrete logarithm problem을 푸는 것이 힘들다는 사실에 기반한 ECDH암호가 있습니다. 

 

비밀키 암호와 공개키 암호, https://www.thesecuritybuddy.com/encryption/symmetric-key-encryption-vs-public-key-encryption/

 

지금까지 만들어진 암호 기술들은 역사순으로 1세대부터 4세대까지 분류하는데, 여기서 2세대와 3세대에 해당하는것이 각각 대칭키 암호와 공개키 암호입니다. 1세대 암호는 고대 그리스에서 사용되었던 시저암호처럼 문자를 다른 문자들로 치환하는 가장 기본적인 형태의 암호를 의미합니다. 눈치가 빠르신 분들은 예상하셨을수도 있을텐데, 이 글에서 소개하고자하는 동형암호는 4세대 암호에 해당됩니다. (양자컴퓨터로도 풀기 힘든 양자내성암호도 4세대 암호입니다.) 동형암호를 이해하기 위해서는 동형이라는 단어의 의미를 아는것이 가장 중요한데, 이는 수학에서의 (준)동형사상(homomorphism)에서 나온 개념입니다. 쉽게 말하면, 동형사상은 한 집합에서 다른 집합으로 가는 함수 중에서 연산을 보존하는 함수를 말하는데, 예를 들어 정수 집합에서 정수 집합으로 가는 f(x) = 2x라는 함수는 정수의 덧셈을 보존합니다. (f(x+y) = 2(x+y) = 2x + 2y = f(x) + f(y)이기 때문입니다.) 또한, 제곱을 하는 함수 g(x) = x^2는 덧셈이 아닌 곱셈을 보존합니다. 하지만, 우리가 실제로 원하는건 완전동형암호(FHE, Fully Homomorphic Encryption), 즉 모든 연산을 보존하는 암호입니다. 즉, 암호화와 복호화 하는 과정이 덧셈과 곱셈을 둘 다 보존하길 원하는 것이죠. 식으로는 다음과 같이 쓸 수 있습니다.

여기서 m1, m2는 평문(plaintext), c1, c2는 암호문(ciphertext)입니다. 앞에서 언급한 RSA나 ECDH와 같은 암호들은 특정 연산은 보존하지만 모든 연산을 보존하지는 않기 때문에 완전동형암호는 아닙니다.

 

그렇다면, 완전동형암호가 중요하게 여겨지는 이유가 뭘까요? 연산을 보존한다는 동형암호의 성질 때문에, 암호문상에서 연산을 한 뒤에 복호화를 해도 원하던 결과를 얻을 수 있고, 그 때문에 원래의 메세지를 몰라도 암호문만 가지고 데이터 분석을 할 수 있게 된다는 엄청난 장점이 생깁니다. 예를 들어, 의료 데이터의 경우 여러 병원에 흩어져있는 데이터를 한 곳에 모아서 활용하는것이 매우 어려운데, 이를 모두 동형암호화한다면 프라이버시 이슈를 해결함과 동시에 모든 데이터를 활용함으로써 좀 더 나은 모델을 만들 수 있을것입니다. Federated Learning에서도 하나의 모델을 각 병원에서 업데이트한 뒤 서버로 전송함으로써 프라이버시 문제를 해결한다고 볼 수도 있지만, 첫번째 글에서 언급했듯이 gradient를 이용해서 역으로 입력 데이터를 알아내는것도 어느정도 가능하기 때문에 FL이 완벽히 안전하다고는 할 수 없습니다. 하지만, 동형암호는 비밀키를 갖고있지 않는 이상 이론적으로 암호를 푸는것이 거의 불가능하기 때문에 훨씬 안전합니다.

동형암호를 이용한 데이터분석, https://www.ntt-review.jp/archive/ntttechnical.php?contents=ntr201407fa5.html

동형암호라는 개념이 처음으로 제시된건 1970년대 후반이지만, 실제로 작동하는 완전동형암호 기술이 개발된것은 2009년입니다. Gentry는 자신의 박사 논문에서 기존의 유한번의 연산만 처리할 수 있는 SHE(Somewhat Homomorphic Encryption)을 재부팅(Bootstrapping)이라는 방법을 통해서 개선함으로써 모든 연산을 처리할 수 있는 최초의 FHE를 제안하였습니다. 그 이후 Brakerski, Gentry, Vaikuntanathan은 재부팅이 필요없는 FHE인 BGV스킴을 만들었고, Fan과 Vercauteran은 다항식을 이용해서 BGV스킴의 속도를 개선한 BFV스킴을 제시했습니다. 마지막으로, 앞에서 언급한 동형암호스킴들은 모두 정수형의 데이터만을 다루는 반면 2017년에 발표된 CKKS스킴은 실수 연산이 가능한 최초의 동형암호로써 요즘 사용되는 머신러닝/딥러닝 기술에 좀 더 적합한, 가장 신세대 동형암호 기법으로 볼 수 있습니다.

 

앞에서 언급한 FHE스킴들은 여러 종류의 암호들 중에서 격자암호에 기반을 두고 있습니다. 여기서의 격자는 보통 생각하는 그 격자와 같은 의미입니다. 이러한 격자 암호는 주어진 격자 위의 가장 짧은 벡터를 찾는 문제(SVP, Shortest Vector Problem)등의 고전적인 격자 문제들이 다항시간내에 풀기 어렵다는 강한 추측에 기반하고 있습니다. (Regev의 LWE(Learning With Error)에 관한 논문을 참고하시길 바랍니다.) 간략히 설명하자면, Ax = b꼴의 연립 일차 방정식은 가우스 소거법등을 이용해서 다항시간안에 쉽게 풀어낼 수 있지만 b에 우리가 모르는 error가 더해진 경우, 즉 Ax = b + e로 바꾼 경우에는 놀랍게도 x를 알아내는것이 매우 어려워짐을 증명할 수 있습니다. (Regev는 앞의 논문에서 이와 같은 LWE 문제를 푸는 것이 SVP를 푸는것만큼 어렵다는것을 증명합니다.)

 

여기까지만 보면, Federated Learning이나 Differential Privacy에 비해서 동형암호가 가장 안전하게 데이터분석을 할 수 있는 기술이라고 생각할 수 있지만, 동형암호는 치명적인 단점을 가지고 있습니다. 바로 속도가 매우 느리다는 것입니다. 동형암호의 암호화/복호화 속도를 개선하려는 연구들이 많이 이루어지고 있지만, 아직까지는 GPT-3와 같은 거대한 딥러닝 모델에 사용하기에는 역부족입니다. 또한, 덧셈과 곱셈을 보존하지만 사실 sigmoid나 ReLU와 같은 딥러닝에서 많이 사용되는 활성함수의 연산은 보존하지 않기 때문에 다항함수가 아닌 활성함수들은 다항함수로 근사하거나 아얘 다항함수로 대체해야 하는데, 테일러 급수등을 이용해서 고차 다항식으로 근사를 할 수록 연산에 필요한 시간이 지수적으로 증가하기 때문에 이 역시 해결해야하는 문제입니다. 비교적 최근에 와서야 로지스틱 회귀를 시작으로 매우 간단한 CNN부터 ResNet까지 동형암호로 처리하는 연구들이 나오고 있는 상태이며, 딥러닝 모델들의 경우에는 대부분의 경우 모델의 추론만을 다루고 있습니다. 모델을 완전히 동형암호화된 상태로 훈련시킨 연구도 없지는 않지만(논문1, 논문2) 요즘 시대(?)에서 사용되는 크기의 모델을 학습시킨 연구는 아직 없는 것으로 보입니다. 동형암호의 연산 속도가 더욱 개선이 된다면 언젠간 GPT-3와 같은 거대한 딥러닝 모델도 완벽하게 암호화된 데이터 위에서 학습하는것이 가능한 날이 오지 않을까... 생각하며 글을 마치겠습니다.