Homomorphic Encryption (동형 암호)
동형암호란? (Homomorphic Encryption)
Homomorphic Encryption 종류
1. 부분적 동형암호 (Partial Homomorphic Encryption, PHE)
오직 한 유형의 연산만 지원한다.
2. 준 동형암호 (Somewhat Homomorphic Encryption, SHE)
암호문에 난수화된 에러를 포함하는 것으로써, 다수의 연산후에는 에러가 증폭되어 그 크기가 일정 수준을 넘어서면 정확한 복호화가 불가능한 한계가 있다.
덧셈과 곱셈 모두 지원하며 몇 번의 연산에도 값 보존 처리를 한다.
3. 완전 동형암호 (Fully Homomorphic Encryption, FHE)
Gentry는 SHE에 재부팅(bootstrapping)이라는 과정을 통해 대수연산(Addition, Multiplication)이 이론산 무한번 가능하게 만들었으며, 이를 FHE라 부른다.
-
Bootstrapping : 암호화된 비밀키를 이용하여 노이즈가 감소된 새로운 암호문 생성 후 연산 수행하는 설계 원리
-
Squashing : 노이즈 증가 감소, 평문 변형되지 않도록 구성하는 원리 / 복호화 알고리즘 및 공개키 일부 변형
Homomorphic Encryption 분류
1. 1세대
2009년 Gentry에 의해 처음 제안된 동형암호를 1세대로 구분한다.
2. 2세대
2011년 Brakerski-Gentry-Vaikuntanathan에 의해 발표된 논문에서는, 곱셈시 생기는 잡음의 크기를 줄이는 기법이 제안되어, 재부팅없이 가능한 곱셈 횟수를 암호문 길이에 대해 기하급수적으로 늘릴 수 있게 되었다. 소위 모듈러스, 혹은 키 교환(modulus/key-switching) 이라 부르는 과정이며 이러한 과정을 도입한 스킴들을 2세대 동형암호라 부른다.
-
The Brakerski-Gentry-Vaikuntanathan (BGV, 2011) scheme,[2] (Brakerski-Vaikuntanathan 의 기법에 기반한 설계);[3]
-
The NTRU-based scheme by Lopez-Alt, Tromer, and Vaikuntanathan (LTV, 2012);[4]
-
The Brakerski/Fan-Vercauteren (BFV, 2012) scheme,[5] (Brakerski 의 스케일보존 암호시스템에 기반한 설계);[6]
-
The NTRU-based scheme by Bos, Lauter, Loftus, and Naehrig (BLLN, 2013),[7] (LTV 스킴과 Brakerski의 스케일보존 암호시스템에 기반한 설계);[6]
3. 3세대
2013년 Gentry-Sahai-Water 에 의해 발표된 논문에서는 이 곱셈과정의 잡음을 한층 더 줄이고 동형곱셈시 비용이 많이 드는 재선형화(relinearization) 과정을 없애는 기술을 소개하였다. 이를 활용하는 동형암호를 3세대 동형암호라고 부르는데, 특히 평문을 1 비트로 제한하는 대신 매우 빠른 재부팅을 가능하게 한 Ducas-Micciancio14의 FHEW스킴과 Chillotti-Gama-Georgieva-Izabachene16의 TFHE스킴이 이에 속한다.
4. 4세대
2016년 Cheon-Kim-Kim-Song[8] 은 덧셈과 곱셈 외에 반올림이라는 세 번째 연산이 암호화상태에서 가능한 혜안(HEaaN)이라는 동형암호를 발표하였다. HEAAN의 최초 버전은 깃허브에 2016년 5월 15일 공개되었으며[9] 나중에 부트스트래핑 알고리즘을 갖춘 HEAAN 신버전이 출시되었다.[10] 현재 최신 버전은 버전 2.1이다.
기존의 동형암호도 반올림연산을 수행할 수는 있으나 재부팅에 준하는 매우 복잡한 연산을 수행하여야 하는 반면, 혜안 스킴에서는 이를 덧셈 수준으로 빠르게 처리할 수 있어 산술연산이 대폭 개선되었다. 실제로 비트당 30분이 걸리던 재부팅연산이 2019년에는 0.5ms가 걸리게 되어 300만배의 개선을 이루었고, 이는 매년 8배의 고속화에 해당하는데 이중 최근 3년간의 개선은 혜안 스킴에 힘입은 바가 크다. 이에 따라 기계학습 등 근사연산을 활용하는 응용분야의 상용화가 가능해지게 되었고, 이를 4세대 동형암호로 부른다.
Reference
- 위키백과, 동형암호
- 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.
- Andrey Kim; Kyoohyung Han; Miran Kim; Yongsoo Song. “An approximate HE library HEAAN”.
- Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim and Yongsoo Song. Bootstrapping for Approximate Homomorphic Encryption. In EUROCRYPT 2018(springer).
