‘동형(Homomorphic)’이란, ‘같음(Same)’ 뜻하는 고대 그리스어인, ὁμός(Homos)와 “모양(Shape)이나 형체(form)”를 뜻하는 μορφή(morphe) 의 결합에서 유래되었습니다. 한 걸음 더 나아가서, ‘동형’이라는 단어는 대수학(Algebra)에서 비롯된 단어로, 연산의 구조가 유지되는 함수를 가리킵니다. 예를 들면, 지수 함수인 f(x) = ex는 동형함수입니다. 왜냐하면, ex+y = ex * ey 로서, 지수 함수는 양의 실수군에 대해 동형인 함수입니다.
그렇다면 ‘동형암호(Homomorphic Encryption)’는 무엇일까요? ‘동형(同形)암호’란 평문에 대한 연산을 수행한 후 암호화한 결과(암호문)와 각각의 암호문에 대하여 연산을 수행한 결과가 같은 값을 가지는 암호화 방식을 말합니다.
시저(Ceasar) 암호를 가지고 동형암호 개념을 설명해 보겠습니다.1 시저 암호는 하나의 알파벳을 특정한 알파벳과 자리를 바꾸는 치환 암호입니다. 엄밀히 말하면, 문자열 연결(Concatenation)에 대하여 부분적으로 동형입니다. 13자리 알파벳과 자리를 바꾸는 시저 암호를 가지고 동형암호의 원리를 설명하면 다음과 같습니다.
Encrypt(13, ‘A’) = ‘N’, Encrypt(13,’B’) = ‘O’…., Encrypt(13, ‘H’) = U
“HELLO”와 “WORLD”를 각각 암호화해 문자열 연결을 한 뒤, 이 결과(“URYYBJBEYQ”)를 복호화 하면, “HELLOWORLD”를 얻을 수 있습니다.
var c1 = Encrypt(13, “HELLO”); // c1 = URYYB
var c2 = Encrypt(13, “WORLD”); // c2 = JBEYQ
var c3 = Concat (c1, c2); // c3 = URYYBJBEYQ
var c4 = Encrypt(13, “HELLO”||”WORLD”) // c4 = URYYBJBEYQ
var p = Decrypt(13, c3); // p = HELLOWORLD
한편 동형암호는 중대한 약점을 갖고 있습니다. 동형암호는 일정 회수 이상 연산을 수행하면 노이즈가 발생해 더 연산을 수행할 수 없어 연산 횟수에 제한이 있습니다. 암호문의 노이즈를 작게 하는 재부팅(Bootstrapping) 과정을 통해 동형암호의 약점인 연산 횟수 제한을 없앨 수 있는 암호화 방식을 ‘완전동형암호(Fully Homomorphic Encryption)’라고 부릅니다.
덧셈 연산을 가지고 완전동형암호를 설명해보도록 하겠습니다. 완전동형암호는 메시지를 특정한 두 개의 수로 나누어 나머지 두 개를 상대방에게 보내는 방식입니다. 아래 예시에서 사용하는 평문은 10과 15이고, 사용하는 키는 4와 7입니다. 이때 사용한 연산은 덧셈 연산입니다. 암호화는 모듈러 연산(mod4, mod7)입니다. 10과 15의 덧셈 연산 결과를 암호화한 것과 평문인 10과 15를 각각 암호화한 후 덧셈 연산한 결과가 같은지 확인하면 됩니다.
예를 들어 메시지 10은 4와 7로 각각 나눠 나온 나머지 2와 3으로 암호화됩니다. 여기서 10과 15를 암호화해서 (2, 3)과 (3, 1) 이렇게 두 암호를 받았다고 가정합니다. 그리고 두 암호 결과를 덧셈 연산합니다. 같은 수로 나눈 나머지끼리 더해야 하므로 2는 3과 3은 1하고만 더할 수 있습니다. 그러면 암호 결과를 연산한 값은 (5, 4)가 됩니다.2
이제 (5, 4)를 복호화 해 봅시다. 연산된 암호를 풀기 위해선 암호화할 당시 사용한 키를 알면 됩니다. 여기서 사용한 키는 4와 7이었습니다. 그런데 5는 4로 한 번 더 나눠집니다. 따라서 1이라고 생각해야 합니다. 결국 4로 나눴을 때 나머지가 1이고, 7로 나눴을 때 나머지가 4인 수를 구하면 되는데, 그 값은 25입니다. 그런데 이 값은 원래 메시지인 10과 15를 더한 값과 같습니다. 따라서 이런 원리를 이용하면 암호가 걸린 상태에서도 통계적인 분석이 가능하게 되는 것입니다.
동형암호는 언제부터 만들어지고, 알려지게 되었을까요?
동형암호는 이미 1978년에 발표되었습니다. PKI(Public Key Infrastructure)의 핵심인 공개키 암호 알고리즘 RSA와 같은 해에 발표되었으며, RSA의 두 개 이니셜 ‘R’과 ‘A’의 주인공 Rivest, Addleman이 Dertouzous3과 함께 발표한 암호 알고리즘입니다.
이론적으로 안전성이 증명되지 않아 오랫동안 관심에서 멀어져 있다가, 2009년 Gentry4(현재 IBM Thomas J. Watson Research Center 소속)에 의해 안전성이 증명된 동형암호가 발표되고, 2011년 MIT가 동형암호 기술을 10대 Emerging Technology로 선정5하면서 학계와 산업계의 관심이 더욱 촉발했습니다.
그렇다면 동형암호 기술이 최근 학계는 물론 산업계에서 더욱 이슈화되고 있는 이유가 무엇일까요?
동형암호는 암호화된 데이터의 복호화 없이 암호문의 연산이 가능합니다. 이러한 특징에 기반한 완전동형암호의 장점은 암호화 후 통계 처리뿐만 아니라 검색, 기계 학습까지 가능하다는 점입니다. 특히, 해커가 데이터를 유출해도 볼 수 없다는 점에서 안전성이 부각되고 있습니다. 더욱이 기존 동형암호의 문제점인 평문 연산 대비 암호문의 연산 속도가 현저히 느린 점도 연산의 종류에 따라 최적화하는 기술이 발전되고 있습니다.
특히 의료계나 금융권은 오래전부터 쌓아온 방대한 데이터를 기반으로 유전자 정보 기반 정밀 치료나 신용 정보의 안전한 활용 등과 같은 새로운 기회 발굴에 활용하고자 하지만, 민감 정보를 포함한 개인정보의 빅데이터 활용에 대한 규제와 기술적인 어려움이 큰 허들로 작용하여 전환점을 찾지 못하고 있었습니다.
인공지능을 활용한 데이터 분석을 연구하는 학계와 이를 활용하려는 산업계가 공히 이러한 답답한 상황을 해결할 수 있는 도구로서, 동형암호 기술을 주목하게 된 것입니다.
그렇다면, 현재 동형암호를 IT 기술로 구현하고, 표준화를 주도하고 있는 이들은 누가 있을까요?
IBM의 HELib(2012), MS의 SEAL(2015)6, European HEAT 프로젝트의 PALISADE(2017)7, cuHE(2017)8, 서울대학교의 HEAAN(혜안) 등이 있습니다. 이러한 다양한 동형암호 구현 그룹들은 표준화를 위한 워크숍을 진행했고, 2017년 7월 MS 리서치에서 첫 번째 워크숍을 진행한 이후로, 2018년 3월 미국 MIT 대학교에서 두 번째 워크숍을, 2018년 10월 토론토에서 세 번째 워크숍을 개최했습니다.
이외에도 표준화 모임에는 미국 국립보건원, 미국 MIT, 스위스 EPFL, 삼성, Gemplus, 인텔, SAP 등 정부, 학교, 스타트업 및 IT 기업 등이 포함되어 있습니다.
보안 업체가 주도한 기존 암호 기술과는 달리 동형암호는 데이터 분석 업체가 주도하고 있습니다. MS는 인공지능(AI) 보호를 위해 동형암호를 채택했으며, IBM은 향후 5년간 연구 분야로 동형암호 기술을 꼽았습니다. 이와 함께 ENVIL, Cryptolab 등의 스타트업 기업들도 동형암호에 관심을 보이고 있습니다.
동형암호의 장점과 단점은 무엇?
기존에 알려진 암호와 비교해 동형암호의 장점과 단점은 무엇일까요?
동형암호는 암호문을 복호화 하지 않아도 검색, 통계 처리 및 기계 학습이 가능하고, 데이터를 처리하는 중간 과정에서 복호화 하지 않아도 되므로, 데이터 유출 위험이 감소하는 장점이 있습니다.
단점은 기존 암호의 확장률(평문 대비 암호문이 커지는 비율)에 비해 10배에서 100배 정도 커질 수 있고, 암복호화 속도가 1ms인 RSA 대비 수십 ms가 소요되며, 암호문 곱셈 연산의 경우, 수백 ms가 소요됩니다. 한편 앞에서 언급했던 노이즈 감소를 위한 재부팅 시간이 필수적으로 필요하며, 2015년 기준 재부팅 시간이 0.02초 정도로 보고되었습니다.
성능이나 소요 자원 측면에서 개선되어야 할 부분이 있지만, 개인정보를 처리하는 과정에서 복호화 없이 활용 가능한 장점을 활용한 완전동형암호의 활용 예시를 살펴보도록 하겠습니다.
첫 번째 활용 분야는 생체 인식 분야입니다. 출입 통제에 사용하는 생체 정보를 안전하게 처리할 수 있습니다. 완전동형암호화된 지문 등의 생체 정보를 복호화 하지 않고, 암호화된 채로 인증을 수행할 수 있다면, 생체 정보를 복호화 해 평문으로 보관하거나, 검증을 위해 원본을 전송할 필요 없이 받은 암호문과 보관 중인 암호화된 생체 정보를 비교해 일치 여부를 확인할 수 있도록 할 수 있습니다.
2018년 11월 ‘개인식별 방지 기술 세미나’에서 한국스마트인증(대표 문기봉)이 이러한 완전동형암호 기술을 활용해 홍채 인증 기술을 개량 발전시켜 인증 시간을 0.25초로 앞당긴 시스템을 발표했습니다.
두 번째 활용 분야는 금융 분야입니다. 완전동형암호는 컴퓨터가 할 수 있는 연산을 모두 수행할 수 있어 데이터의 기밀성을 보호하면서 금융 데이터를 동형 기계 학습의 훈련 단계에서 활용할 수 있습니다.
동형 기계 학습의 훈련 단계에서 암호화된 데이터 연산을 통해 예측•분류 모형을 얻고 그 모형으로부터 실시간 계산이 필요한 예측 단계에서는 함수 암호를 사용합니다. 동형 기계 학습은 데이터의 기밀성을 보호할 수 있어 개인의 민감한 정보의 유출에 대한 보안 문제를 해결할 수 있으며 데이터의 손실 없이 신용도 평가 예측 모형의 고도화가 가능하다고 할 수 있습니다.
실제 사례로, 2018년 11월 ‘개인식별 방지 기술 세미나’에서 코리아크레딧뷰로(KCB, 대표 강문호)는 50만 명의 신용 데이터를 동형암호화된 상태에서 기계 학습을 수행해 개인정보를 보호하면서 신용 평가 모형의 신뢰성, 정확성, 안전성을 성공적으로 확보할 수 있음을 검증했습니다.
완전동형암호를 효율적으로 구현할 수 있는 여러 알고리즘 설계 방식 및 구현 방법에 대한 연구에 많은 진전이 이루어지고 있습니다. 하지만, 아직 다양한 공격 시나리오에 대한 충분한 검증이 이루어지지 않았습니다. 키의 길이와 파라미터 크기를 확정하여 안전성을 평가하는 다양한 연구가 필요합니다. 또한 클라우드, 빅데이터 등 실제 응용 환경에서 어떻게 사용할 것인가에 대한 실제적인 적용에 대한 연구가 필요합니다.
글 l LG CNS 보안컨설팅팀
[참고문헌]
- 개인정보가 보호되는 동형머신러닝, 천정희, 제1회 가우스 콜로퀴움, 3월 2018년
- 개인정보가 보호되는 동형암호기반 금융데이터분석, 천정희 외 2명, 한국금융정보학회, 2월 2018년
- 완전 동형암호 라이브러리의 성능 분석, 조은지 외 2명, 한국정보과학회, 2월 2018년
- 최신 정보보호 이슈 및 국외 암호기술 연구 동향, 김주혁 외 1명, 10월 2014년
- Craig Stuntz (2010-03-18). “What is Homomorphic Encryption, and Why Should I Care?” [본문으로]
- 미래를 여는 수학 ‘② 완전동형암호로 개인정보를 보호한다.’ 사이언스피디아 조가현 기자 [본문으로]
- Rivest, R., L. Addleman, and M. Dertouzos, 1978, On Data Banks and Privacy Homomorphism, in Foundations of Secure Computation, 169-177. [본문으로]
- Gentry, C., 2009, Fully Homomorphic Encryption Using Ideal Lattices, in the 41st ACM Symposium on Theory of Computing, 169-178. [본문으로]
- 2011 MIT Technical Review, 10 Breakthrough Technologies, http://www2.technologyreview.com/tr10/?year=2011 [본문으로]
- SEAL(Simple Encrypted Arithmetic Library), Nathan Dowlin, Ran Gilad-Bachrach, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. Manual for using homomorphic encryption for bioinformatics. [본문으로]
- Technical report, Microsoft Research, 2015. http://research.microsoft.com/apps/pubs/default.aspx?id=258435. [본문으로]
- cuHE: A Homomorphic Encryption Accelerator Library, Wei Dai and Berk Sunar. Worcester Polytechnic Institute, Massachusetts, USA [본문으로]
