동형암호
 | |
| 일반 | |
|---|---|
| 기원 | RLWE(Ring learning with errors) |
| 관련 방식 | 사적 집단 교차(Private set intersection) |
동형암호(同型暗號,Homomorphic Encryption, HE)는 데이터를 암호화된 상태에서 연산할 수 있는 암호화 방법이다. 암호문들을 이용한 연산의 결과는 새로운 암호문이 되며, 이를 복호화하여 얻은 평문은 암호화하기 전 원래 데이터의 연산 결과와 같다.
동형암호는 개인정보를 안전하게 보호한 채로 외부매체에 저장 및 계산하는 목적으로 사용할 수 있다. 동형암호를 이용하면 데이터를 암호화한 채로 상업용 클라우드 서비스에 외주를 맡겨 암호화된 채로 데이터 처리를 할 수 있다. 의료분야와 같이 개인정보 보호에 대한 규제가 심한 분야에서 동형암호를 사용함으로써 데이터 공유를 막는 장벽을 극복하고 새로운 서비스를 개척할 수 있다. 예를 들어 예측분석의료는 개인의료데이터 보호가 문제가 되어 응용하기 어려웠으나, 동형암호를 이용하여 예측분석의료 서비스를 제공한다면 프라이버시 보존에 대한 염려를 불식시킬 수 있다.
설명[편집]
동형암호는 암호화의 한가지 형태로, 복호화 혹은 비밀키 접근이 필요없이 암호화된 데이터를 이용해 연산할 수 있는 추가적인 기능을 제공한다. 그 연산결과는 여전히 암호화된 상태이다. 동형암호는 대칭키암호나 공개키암호의 확장된 형태로 이해할 수 있다. 동형이라는 단어는 대수학 용어인 준동형사상에서 따온 용어이다 : 암호화 및 복호화 함수(혹은 장치)는 평문공간과 암호문공간 사이의 준동형사상 혹은 동형사상으로 작동한다.
동형암호의 종류와 역사[편집]
동형암호라는 개념이 처음 제안된 것은 1978년, Rivest, Adleman과 MIT의 Laboratory for Computer Science (LCS)의 Director였던 Dertouzos 가 공동으로 저술한 논문 RAD78[1]에서였다. 세 저자들은 이 논문에서 동형암호의 개념을 소개하고 몇가지 후보 스킴과 한가지의 응용을 제시하였다. 데이터베이스를 운영하기 어려운 소규모 대부업자가 외부 업체에 데이터의 저장을 위탁하고 이 데이터를 가공하여 얻고 싶은 계산결과를 프라이버시를 보존하면서 수행하고 싶을 때 동형암호를 사용한다는 시나리오이다. 요즘은 널리 사용되는 외주계산(outsourced computation) 혹은 클라우드(cloud)의 개념과 같다.
최초의 정수 덧셈을 보존하는 암호는 1998년 발표된 Okamoto-Uchiyama[2]과 이를 개선하여 1999년에 발표된 Paillier 스킴[3]을 들 수 있다. 그 이전의 암호도 일부 연산에 대해 동형암호를 구현할 수 있었다. 예를 들어 RSA 암호도 곱셈연산을 암호화한 상태에서 수행할 수 있으므로 부분동형암호의 일종인 곱셈동형암호이다. 유한체 상의 엘가말 암호도 곱셈을 보존하는 곱셈동형암호이다. 1982년 발표된 최초의 증명가능한 암호인 Goldwassser-Micali82 스킴도 동형암호인데 XOR연산을 보존한다.
1978년 Rivest, Addleman, Dertouzos[1]의 논문에서 제시된 스킴은 암호화한 상태에서 덧셈과 곱셈을 모두 수행할 수 있는 암호체계로서, 이를 이용하면 임의의 연산을 암호화한 상태에서 수행할 수 있다. 이를 튜링완전성이라 하는데, 이는 유한체상 임의의 연산은 덧셈과 곱셈의 반복으로 이루어진 다항식으로 표시할 수 있기 때문이다. 다만 RAD78에 제시된 스킴들은 모두 공격이 되었고, 마지막 하나 남은 스킴마저 1981년 최초의 Crypto 학회에서 제시된 Brickell-Yacobi의 논문에서 취약점이 드러났다. 이 공격은 암호문 단독공격만을 고려하던 기존의 틀에서 벗어나 실제 현실에서는 암호문과 이에 상응하는 평문을 알 수도 있다는 고찰을 기반으로 한 기지평문공격(Known Plaintext Attack)으로 이루어졌다. 이후 이를 보완하기 위해, 대수학 이론을 이용한 다양한 시도가 있었지만 마지막으로 남아있던 Domingo-Ferrer의 암호스킴이 깨진 이후[Cheon-Kim-Nam06] 더는 흥미로운 제안이 나오지 않았다. 오히려 Boneh-Lipton96처럼 동형암호의 불가능을 증명하려는 방향의 연구들이 다수 출판되었다. 이중 최종판으로는 유한체간의 동형연산을 보존하는 복호화함수는 다항식시간에 공격이 된다는 결과가 있다.[Maurer-Raub07]
현재 연구되고 있는 동형암호는 2009년 Gentry가 제안한 임의의 연산을 암호화상태에서 무한번 반복할 수 있는 동형암호에 기반하고 있다. Gentry는 먼저 유한동형암호(somewhat homomorphic encryption, SHE)를 설계하였다. SHE란 암호문에 난수화된 에러를 포함하는 것으로써, 다수의 연산후에는 에러가 증폭되어 그 크기가 일정 수준을 넘어서면 정확한 복호화가 불가능한 한계가 있다. Gentry는 이 유한동형암호에 재부팅(bootstrapping)이라는 과정을 통해 대수연산(덧셈, 곱셈)이 이론상 무한번 가능하게 만들었으며, 이를 완전동형암호(fully homomorphic encryption, FHE)라 부른다. 동형암호는 이후 MIT Technical Review에서 선정하는 2011년 10대 혁신기술(breakthrough technology)로 선정되었고, 2011년에는 미국 고등국방연구계획국(DARPA)에서 이를 구현하는 PROCEED라는 과제를 지원하였다.
완전동형암호의 분류[편집]
1세대[편집]
2009년 Gentry에 의해 처음 제안된 동형암호를 1세대로 구분한다.
2세대[편집]
2011년 Brakerski-Gentry-Vaikuntanathan에 의해 발표된 논문에서는, 곱셈시 생기는 잡음의 크기를 줄이는 기법이 제안되어, 재부팅없이 가능한 곱셈 횟수를 암호문 길이에 대해 기하급수적으로 늘릴 수 있게 되었다. 소위 모듈러스, 혹은 키 교환(modulus/key-switching) 이라 부르는 과정이며 이러한 과정을 도입한 스킴들을 2세대 동형암호라 부른다.
- The Brakerski-Gentry-Vaikuntanathan (BGV, 2011) scheme,[4] (Brakerski-Vaikuntanathan 의 기법에 기반한 설계);[5]
- The NTRU-based scheme by Lopez-Alt, Tromer, and Vaikuntanathan (LTV, 2012);[6]
- The Brakerski/Fan-Vercauteren (BFV, 2012) scheme,[7] (Brakerski 의 스케일보존 암호시스템에 기반한 설계);[8]
- The NTRU-based scheme by Bos, Lauter, Loftus, and Naehrig (BLLN, 2013),[9] (LTV 스킴과 Brakerski의 스케일보존 암호시스템에 기반한 설계);[8]
3세대[편집]
2013년 Gentry-Sahai-Water 에 의해 발표된 논문에서는 이 곱셈과정의 잡음을 한층 더 줄이고 동형곱셈시 비용이 많이 드는 재선형화(relinearization) 과정을 없애는 기술을 소개하였다. 이를 활용하는 동형암호를 3세대 동형암호라고 부르는데, 특히 평문을 1 비트로 제한하는 대신 매우 빠른 재부팅을 가능하게 한 Ducas-Micciancio14의 FHEW스킴과 Chillotti-Gama-Georgieva-Izabachene16의 TFHE스킴이 이에 속한다.
4세대[편집]
2016년 Cheon-Kim-Kim-Song[10] 은 덧셈과 곱셈 외에 반올림이라는 세 번째 연산이 암호화상태에서 가능한 혜안(HEaaN)이라는 동형암호를 발표하였다. 기존의 동형암호도 반올림연산을 수행할 수는 있으나 재부팅에 준하는 매우 복잡한 연산을 수행하여야 하는 반면, 혜안 스킴에서는 이를 덧셈 수준으로 빠르게 처리할 수 있어 산술연산이 대폭 개선되었다. 실제로 비트당 30분이 걸리던 재부팅연산이 2019년에는 0.5ms가 걸리게 되어 300만배의 개선을 이루었고, 이는 매년 8배의 고속화에 해당하는데 이중 최근 3년간의 개선은 혜안 스킴에 힘입은 바가 크다. 이에 따라 기계학습 등 근사연산을 활용하는 응용분야의 상용화가 가능해지게 되었고, 이를 4세대 동형암호로 부른다.
평문데이터 구조에 따른 동형암호 분류[편집]
| 스킴 | 평문데이터 구조 |
|---|---|
| TFHE | bit |
| CKKS | double |
| BFV | int |
활용 및 전망[편집]
RAD78[1]에서 처음 제시된 바와 같이 동형암호는 프라이버시보존 데이터분석 분야에 적용할 수 있으며, 금융·의료·교육 등 분야의 데이터를 보호하면서 활용하는데 쓰일 수 있다. 예를 들어, 대한민국에서는 2019년 12월 동형암호가 금융위원회의 혁신금융서비스로 지정되어 동형암호를 금융분야 데이터 결합을 위한 방법으로 사용할 수 있게 하는 제도가 임시로 마련되었다. 이에 따라 230만명의 KCB의 금융정보와 국민연금의 연금납부 데이터를 암호화한 상태로 결합하여 통계분석을 수행하였고, 그 결과를 발표하였다.[1]
그동안 동형암호의 속도가 개선된 것은 암호학적 연구와 수학적 알고리즘의 개선에 힘입은 바가 크다. 이에 따라 암호문 상태의 연산이 평문 상태의 연산 대비 평균 1000x 수준에 이르렀으나 산업화가 활성화 되기 위해서는 추가적인 개선이 필요하다. 소프트웨어(SW)적인 최적화에 더불어 동형암호 하드웨어(HW) 가속기가 연구되고 있다. 2020년 DARPA는 3000만불 수준의 DPRIVE 과제를 공모중인데 이 과제의 목표는 평문연산 대비 10x 수준의 HW 가속기 개발이다. HW 가속기를 활용하면 다양한 데이터분석 뿐 아니라 자율주행 자동차 등 실시간 연산이 필요한 분야까지 더 많은 응용들이 현실화될 전망이다.
동형암호를 산업적으로 널리 활용하기 위해서는 표준화도 중요한 역할을 한다. 2017년에는 동형암호 관련 학자·기업·관료 등이 모여 동형암호 표준화 기구(HomomorphicEncryption.org)를 발족하였고, 여기서 동형암호 스킴의 안전성·응용 관련 백서를 만들어 공표하고 매년 1-2회의 워크샵을 개최하고 있다. 대한민국에서는 2019년 TTA에 의해 HEaaN의 국내 표준화가 제정 공표되었다. 2020년 4월 Microsoft와 Intel 등에 의해 세계표준기구(ISO)에 완전동형암호 표준이 제안되었는데 표준 제정까지는 3년정도의 시간이 소요될 전망이다. 여기에 제안된 동형암호 스킴은 BGV/BFV와 HEaaN 두가지이다.
활용사례 : 코로나 확진자 동선 확인 앱[편집]
참조[편집]
- ↑ 가 나 다 Rivest, Ronald; Adleman, Len; Dertouzos, Michael (1978). 〈ON DATA BANKS AND PRIVACY HOMOMORPHISMS〉. 《Foundations of secure computation 4(11)》. 169–180쪽.
- ↑ Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). 《A new public-key cryptosystem as secure as factoring.》. International conference on the theory and applications of cryptographic techniques. Springer, Berlin.
- ↑ Paillier, Pascal (1999). 《Public-key cryptosystems based on composite degree residuosity classes》. International conference on the theory and applications of cryptographic techniques. Springer, Berlin.
- ↑ Z. Brakerski, C. Gentry, and V. Vaikuntanathan. Fully Homomorphic Encryption without Bootstrapping, In ITCS 2012
- ↑ Z. Brakerski and V. Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. In FOCS 2011 (IEEE)
- ↑ A. Lopez-Alt, E. Tromer, and V. Vaikuntanathan. On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption. In STOC 2012 (ACM)
- ↑ Fan, Junfeng; Vercauteren, Frederik (2012). “Somewhat Practical Fully Homomorphic Encryption”.
- ↑ 가 나 Z. Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP, In CRYPTO 2012 (Springer)
- ↑ J. Bos, K. Lauter, J. Loftus, and M. Naehrig. Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme. In IMACC 2013 (Springer)
- ↑ Cheon, Jung Hee; Kim, Andrey; Kim, Miran; Song, Yongsoo (2017). 〈Homomorphic encryption for arithmetic of approximate numbers〉. 《Takagi T., Peyrin T. (eds) Advances in Cryptology – ASIACRYPT 2017》. ASIACRYPT 2017. Springer, Cham. 409–437쪽. doi:10.1007/978-3-319-70694-8_15.