동형 암호

Homomorphic Encryption

데이터를 암호화한 채로 연산할 수 있는 암호화 기법

개념

500px 동형암호 개념은 Rivest, Adleman, and Dertouzos에 의해 1978년 제시되고, IBM의 연구원인 Craig Gentry에 의해 2009년 격자 기반 암호화를 사용하는 완전한 동형암(FHE)를 위한 구조가 최초로 제시되었다.

특징

• 데이터를 복호화하지 않음로 원본 데이터 유출 원천 차단 가능
• 개인정보 비식별 조치와 달리 원본 데이터의 손실이 거의 없음
  • 개인정보나 민감한 데이터를 대상으로 한 분석에 효과적(PPDM 실현)
• 데이터의 무결성을 보장하지 않으며 가단성(Malleability)을 제공

동형암호의 한계

• 연산 시 마다 암호문에 Noise가 발생하여 복잡한 계산이 불가
  • Noise가 한계치를 넘으면 복호화 불가
  • Bootstrap 기법을 통해 중도에 복호화하여 Noise를 제거하는 방향으로 연구 중
  • Bootstrap 사용 시 연산 속도가 느려지고 계산 결과에 오차가 생기는 문제 발생
• 현재 Noise 발생을 줄이거나 Bootstrapping을 효율적으로 수행하는 방법 연구 중

동형암호의 분류

세대 구분

• 1세대: 곱셈, 덧셈 등 일부 연산만 가능
• 2세대: 전체 사칙연산 가능. 성능상의 한계 존재
• 3세대: 모든 연산 가능, 실무에 적용 가능한 효율성

기능에 따른 구분

• 부분동형암호(Partial Homomorphic Encryption)
  • 연산의 종류 제한
  • 예) 덧셈이나 곱셈만 가능
• 준동형암호(Somewhat Homomorphic Encryption)
  • 연산 횟수 제한
  • 예) 사칙연산이 모두 가능하지만 연산이 반복될 경우 데이터 길이가 기하급수적으로 증가
• 완전동형암호(Fully Homomorphic Encryption)
  • 연산의 종류나 횟수의 제한이 없음
  • 부트스트래핑, 스쿼싱, 근사값 계산 이용

구현 모델

• 엘가말
• HELib: IBM에서 개발
  • Slot 단위로 평문을 나누어 연산 처리
  • 비트 단위 이동연산자 지원
• SEAL: 마이크로소프트에서 개발
  • 정수의 덧셈, 곱셈 연산을 지원
  • 부트스트래핑을 수행하지 않음
• 혜안(HeaAn): 서울대학교 천정희 교수 개발
  • 근사계산법을 사용하여 성능을 월등히 높였다.

같이 보기

• PPDM