동형암호

정의

동형암호는 데이터를 암호화한 채로 연산할 수 있게 하는 암호 기법이다.

암호문끼리 연산한 결과를 복호화하면 평문으로 계산한 결과와 같아진다.

그래서 키가 없는 클라우드 서버에도 계산을 맡길 수 있다.

구성요소와 원리

동형암호 시스템은 키 생성, 암호화, 암호문 연산, 복호화로 구성된다.

연산을 맡는 평가기는 비밀키 없이 암호문만 다룬다.

암호화 함수는 평문 연산과 암호문 연산이 대응되는 준동형 관계를 따른다.

그래서 키 생성기와 평가기가 분리되는 것이 핵심 구조다.

노이즈와 재암호화

암호문에는 작은 오차인 노이즈가 섞여 있다.

덧셈은 노이즈를 조금 키우지만 곱셈은 크게 키운다.

노이즈가 임계값을 넘으면 복호화가 깨지므로 재암호화로 줄인다.

PHE·SWHE·FHE 유형 비교

동형암호는 지원 연산 범위와 연산 횟수 제한에 따라 세 유형으로 나눈다.

부분동형은 덧셈이나 곱셈 중 한 가지만 무제한 지원한다. 대표 방식은 Paillier다.

완전동형은 임의 연산을 지원하며, 2009년 Gentry가 제시한 방식이 최초다.

다항동형은 노이즈가 쌓여 허용 깊이를 넘으면 복호화가 깨진다.

Paillier 예제와 CKKS

두 값 3과 5를 각각 암호화한 뒤 암호문끼리 곱한다.

복호화하면 두 평문의 합인 8이 나온다. 덧셈 준동형 성질이다.

근사 연산인 CKKS는 실수 0.5를 2배 해도 정확히 1.0이 아닌 오차를 허용한다.

정수 정확 연산은 BFV·BGV, 실수 근사 연산은 CKKS로 구분해 기억한다.

한계와 정리

동형암호의 가장 큰 한계는 연산 부하와 암호문 크기 증가다.

FPGA, GPU, ASIC 같은 하드웨어 가속과 근사 연산이 함께 연구된다.

클라우드 검색과 의료 데이터 분석처럼 개인정보를 보호하는 활용이 대표적이다.

동형암호는 암호문 상태에서 연산하는 기술이라는 점을 기억하자.