동형암호

동형암호(Homomorphic Encryption;HE)는 암호화된 데이터를 복호화 없이도 연산할 수 있는 암호 기술이다. 암호화된 상태에서 연산한 결과 값을 복호화하면 평문 상태의 데이터를 연산한 결과와 동일한 값을 얻을 수 있게 된다. 이렇게 암호화한 상태에서나 하지 않은 상태에서 분석한 결과물의 형태가 같다는 의미에서 동형이라고 한다.

개요

동형암호는 정보를 암호화한 상태에서 각종 연산을 했을 때, 그 결과가 암호화하지 않은 상태의 연산 결과와 동일하게 나오는 4세대 암호체계를 말한다. 동형암호는 튜링완전성을 갖는다. 이로부터 통계처리뿐만 아니라 검색, 기계학습까지 가능하다. 동형암호는 데이터를 사용하는 환경에 키가 저장되지 않는다. 키를 함께 제공하지 않고 암호화한 상태의 데이터만 맡겨 계산을 할 수 있게 해줌으로써 보안을 높여 해커의 데이터 유출을 막을 수 있다. 암호화한 상태에서나 하지 않은 상태에서 분석한 결과물의 형태가 같다는 의미에서 '동형(同型)'이라는 이름이 붙었다.

등장 배경

암호화는 데이터의 보안에 필수이지만, 기존의 암호화 기술은 암호화된 상태에서 연산, 탐색, 분석 등의 작업이 불가능했다. 기존의 암호화는 평문을 복호화키가 없이는 난수와 구별할 수 없는 문자열로 변환하는 것을 목표로 하므로 암호문을 가지고 의미있는 작업을 수행하는 것은 불가능하였다. 이와 달리 Rivest, Addleman and Dertouzous (1978)에 의해 제안된 동형암호는 암호화된 상태에서도 복호화키 없이 평문의 연산을 수행할 수 있어서 이상적인 암호로 여겨졌으나, 그 안전성에 대해서는 Gentry가 처음으로 안전한 동형암호를 제시한 2009년전까지 30여 년간 미해결 문제였다. Gentry (2009)는 그의 논문에서 정수론과 격자분야의 난제에 기반을 둔 동형암호를 설계하였고 그 안전성이 난제로 환원됨을 증명하였는데, 처음에는 매우 비효율적이었다. 그러나 그 후 많은 연구자들의 개선을 거치면서 동형암호기술은 최근에 들어 실용화를 앞두고 있으며 2011년 MIT Technical Review에서 10대 Emerging Technology로도 선정이 되는 등 IT전반에 큰 이슈가 되고 있다.

특징

동형암호의 개념도 및 예시

평문 $m_{1}$, $m_{2}$에 대한 암호문 $c_{1}$, $c_{2}$가 주어졌을 때 $m_{1}+m_{2}$의 암호문을 만드는 문제를 생각할 때, 이 암호에 대한 비밀키를 가지고 있으면 암호문 $c_{1}$, $c_{2}$를 복호화하여 평문 $m_{1}$, $m_{2}$를 얻고 이를 더한 후 다시 암호화하여 $m_{1}+m_{2}$의 암호문을 계산할 수 있다. 동형암호에서는 이 과정을 비밀키 없이 수행할 수 있으며, 덧셈뿐 아니라 곱셈도 수행할 수 있고 더 나아가 컴퓨터가 하는 모든 연산을 복호화 없이 수행할 수 있다. 실제 컴퓨터가 하는 모든 연산은 and, or, not 등의 논리연산의 합성으로 이루어져 있으므로 이들 세 가지 논리연산만 암호화한 상태에서 수행할 수 있으면 이를 반복하여 임의의 연산을 암호화한 상태에서 수행할 수 있다. 이에 반해 암호화한 상태에서 일부 연산만 수행할 수 있는 암호를 부분동형암호(partial homomorphic encryption)이라고 하는데 유한체 위의 ElGamal암호가 곱셈만 가능한 곱셈동형암호(multiplicative homomorphic encryption)이고 Okamoto-Uchiyama암호, Pailler암호가 대표적으로 덧셈만 보호하는 덧셈동형암호(additive homomorphic encryption)이다. 다만 Gentry가 제안한 동형함호는 제한된 횟수의 연산만을 수행할 수 있었는데, 이는 어느 정도의 연산을 수행하고 나면 암호문 안에 들어있는 잡음(noise)이 커져서 평문이 훼손되기 때문이다. 만일 이 잡음이 큰 암호문을 평문을 유지하면서 잡음이 작은 새로운 암호문으로 바꿀 수 있으면 다시 연산을 지속할 수 있게 되는데 이러한 과정을 재부팅(bootstrapping)이라 한다. (물론 복호화키 없이 수행하여야 한다.) 이 재부팅 과정이 허용되는 암호는 무한한 회수의 연산도 가능하게 되며 이렇게 임의의 연산을 무한히 계속 할 수 있는 암호를 완전동형암호(fully homomorphic encryption)라고 부른다. 이에 반해 제한된 회수의 연산만 수행할 수 있는 암호는 제한동형암호(somewhat homomorphic encryption)라 부른다. 완전동형암호는 암호화된 상태의 데이터에 대해서도 컴퓨터로 할 수 있는 모든 연산을 원하는 대로 수행할 수 있으므로 검색이나 통계적인 분석뿐 아니라 기계학습이나 영상처리 등 매우 복잡한 연산에도 적용할 수 있다. 개인정보를 기반으로 한 기계학습의 경우 암호화된 데이터 상에서 분석을 수행하고 분석결과를 확인하는 마지막 단계에서만 복호화하여 개인정보 열람을 최소화할 수 있다. 완전동형암호는 컴퓨터가 하는 모든 연산을 암호화한 상태로도 수행할 수 있는 이론적 강점이 있는 반면 평문 연산에 비해 암호문 연산의 효율성에서는 떨어진다는 단점이 있다. 그러나 응용 연산의 종류에 따라 속도의 차이가 크기 때문에 개별 연산에 대해 최적화하여 적용하는 방법으로 효율성을 높일 수 있다. 또한 동형암호 연구가 아직 초기단계이므로 알고리즘의 개발에 따라 효율이 크게 향상될 여지가 있다. 예를 들면, 동형암호 연산 중에 가장 비효율적인 재부팅시간이 2011년도에는 30분이었던 것이 2013년에는 0.32초, 2015년에는 0.02초까지 계산속도가 빠르게 개선되고 있다.

• 구현 원리

원리	설명
부분 동형 암호 (SHE)	Somewhat homomorphic encryption(SHE), 덧셈과 곱셈 모두 지원(곱셈은 특정 횟수 K번까지만 지원하도록 설계) ElGamal암호가 곱셈만 가능한 곱셈 동형 암호
스쿼싱 (Squashing)	복호화 알고리즘 및 공개키 일부 변형 곱셈 k회 이하만 적용 시 복호화 가능(복호화 알고리즘이 동형으로 계산 가능) 노이즈 증가 감소, 평문 변형되지 않도록 구성하는 원리
부트스트래핑 (Bootstrapping)	암호화된 키와 이중 암호화된 암호문 입력한 후 복호화 알고리즘 실행, 새로운 암호문 생성(Recrypt), 동형 연산 후 매번 Recrypt 수행하여 FHE를 생성 암호문에 암호화된 비밀키를 이용하여 노이즈가 감소된 새로운 암호문 생성 후 연산 수행하는 설계원리

• 특성

서킷 프라이버시	서킷 프라이버시는 연산 진행 시 연산에 대한 정보를 알지 못하는 성질이다.
다중 도약 동형성	다중 도약 동형성은 생성된 암호문이 다른 동형 연산의 입력으로 사용이 가능한 성질이다.
보안성	보안성은 암호화된 형태로 연산이 진행되어 해킹 차단할 수 있는 성질을 말한다.

• 격자기반암호

동형암호는 암호체계 중 높은 난이도를 가졌다고 언급되는 격자기반암호(lattice problem)의 한 종류이다. 3차원까지는 인간의 머릿속에서 이미지를 그릴수 있지만 4차원부터는 오직 수식으로만 표현이 가능하다. 수백 차원의 격자 위의 임의의 위치에서 가장 가까운 점을 찾기가 어렵다는 것을 근거로 하여 동형암호는 계산되는데 엄청난 시간이 필요하고 양자 컴퓨터도 찾아내기 힘들다. 그로 인해 동형암호는 양자컴퓨팅의 보안방법 중 하나로 주목받고 있다.

• 장단점

동형암호는 높은 보안성으로 인해 해커의 데이터 유출을 원천 봉쇄한다는 장점이 있다. 하지만 실제 동형암호는 훨씬 복잡하여 평문연산에 비해 속도가 수십배 느리고 저장공간은 수백배를 차지하는 단점이 있다.

• 성능비교

공개키 암호와 동형암호의 성능비교

	공개키 크기	암호문 크기	평문 크기	암호화 시간	복호화 시간	덧셈 시간	곱셈 시간	허용 depth	안전성
RSA	2048bit	2048bit	-	6.1ms	205.5ms	-	-	-	-
ECC	193bit	80B	-	8.7ms	18.1ms	-	-	-	-
Helib	343KB	105KB	≤1KB	17ms	6ms	0.6ms	54.3ms	6	128bit
SEAL2.4v	2000KB	224KB	≤1KB	5.9ms	1.6ms	0.2ms	24ms	9	128bit
HEAAN	80KB	96KB	16KB	43ms	12ms	5ms	100ms	6	128bit

종류

서울대학교 천정희교수

• 혜안(HeaAn)

혜안(HeaAn) 알고리즘은 천정희 교수가 설립한 '크립토 랩'에서 동형암호학 알고리즘을 획기적으로 개선시킨 알고리즘이다. 전산의 이론을 보면 비트 단위의 더하기와 곱하기를 실행할 수 있을 때, 실제로 컴퓨터가 하는 모든 연산을 수행할 수 있다는 증명할 수 있다. 이를 튜링 완전성이라고도 한다. 동형암호가 모든 것을 할 수 있다는 건 증명이 됐으나, 그것을 실용적으로 쓸 수 있는지 확인을 하기 위해서 데이터들을 더하는 32비트 데이터 여러 개를 덧셈과 곱셈 연산들을 해보았을때, 결과는 가능하지만 속도가 너무 느리다는 결론이 나온다. 데이터를 곱하면 곱할수록 숫자가 다룰 수 없을 만큼 큰 크기가 되버리기 때문이다. 숫자를 반올림하여 유효숫자가 아닌 숫자를 버리고 짧은 숫자들만 연산을 진행하는 것을 근사계산이라고 하는데 근사계산을 수행할 때, 매 연산마다 라운딩을 할 수 있도록하여 다른 암호보다 월등히 좋은 성능을 보이게 된 것이다.

• HELib

HElib는 준 유사 암호화(HE)를 구현하는 소프트웨어 라이브러리이다. 현재 Smart-Vercauteren 암호문 패킹 기술과 Gentry-Halevi-Smart 최적화의 효과적인 사용에 주로 초점을 맞추어 동질성 평가를 빠르게 수행하는 많은 최적화와 함께 Brakerski-Gentry-Vaikuntanathan (BGV) 체계의 구현이 가능하다. 기본 암호 시스템은 동형에 적용 할 수 있는 일련의 운용을 정의하고 비용을 명시한다는 점에서 HElib의 '하드웨어 플랫폼'과 동일한 역할을 한다. 이 플랫폼은 SIMD 환경(Intel SSE 등과 유사)이지만 고유한 비용 지표와 매개변수를 가지고 있다. 동형 암호화를 위해 공개키가 구성되는 방식은 키 스위칭 매트릭스 때문에 비용이 많이 든다. 각 매트릭스는 공개키에 수 메가바이트를 추가하며, HElib에서는 공개키에 수백 개의 매트릭스가 있을 수 있다. 연구원들은 일반적인 작업에 대해 매트릭스의 크기를 33-50% 줄일 수 있다고 말한다. 또한, HElib는 연구 수준 프로젝트이며 유사 암호화를 위한 어셈블리 언어를 사용한다.

• 간단한 암호화 알고리즘(SEAL)

간단한 암호화 알고리즘은 128비트 키에 대해 128비트 블록을 변환한다. 통계 분석을 기반으로 알고리즘의 특징은 강력함과 균일하게 분포 된 출력이 있다. 키 또는 일반 텍스트 블록의 비트가 변경되면 암호화 텍스트 블록이 크게 달라진다. 구현 시 오류가 없음을 확인할 수 있는데, 이것은 알고리즘이 실행되는 속도를 극대화하기 위해 처리 된 모든 블록에 대한 오류 검사가 암호화의 성능을 낮출 수 있기 때문이다. 구현시 동일한 키에 대한 다중 블록 암호화 / 암호 해독에 SEAL이 사용되는 모드를 제공하지 않는다. 이것은 중요한 데이터를 보호하기 위해 알고리즘을 사용하는 것에 대한 억제 수단으로 생략되었다.

전망

동형암호는 의료 분야, 금융분야 뿐만 아니라 블록체인과 양자컴퓨팅 분야에 활용할 수 있을 것으로 예상된다. 블록체인은 연산 과정을 모두 파악할 수 있다는 특성이 있어 민감한 개인정보를 다루기 어려웠는데 동형 암호 기술을 활용한다면 효용성이 매우 상승할 것으로 기대된다. 또한 클라우드 기반 데이터 분선을 가능하게 하여 데이터를 활용하는 분야에 유용한 정보를 제공할 수 있을 것으로 전망된다.

참고 자료

• 개인정보보호, 〈안전한 개인정보 활용을 위한 동형 암호〉, 《네이버 블로그》, 2019-02-08
• 과학기술정보통신부, 〈4세대 암호, '동형암호'를 소개합니다!〉, 《네이버 블로그》, 2019-04-19
• 기술사를위해, 〈동형암호〉, 《네이버 블로그》, 2019-05-03
• IMDARC, 〈암호기술 혁명 - 동형암호〉, 《IMDARC》, 2018-10-26
• 천정희, 어윤희, 김재윤, 〈개인정보가 보호되는 동형암호기반 금융데이터분석〉, 《한국금융정보학회》, 2019-02-28
• HASHED, 〈해시드 인터뷰: 서울대학교 천정희 교수 (Jung-hee Cheon), 동형암호와 블록체인〉, 《Medium》, 2019-05-22
• Richard Chirgwin, 〈IBM's homomorphic encryption accelerated to run 75 times faster〉, 《The Register》, 2018-03-08
• GitHub 공식 홈페이지 - 〈HElib〉
• GitHub 공식 홈페이지 - 〈Simple Encryption ALgorithm〉

같이 보기

• 알고리즘
• 암호 알고리즘
• 혜안
• 근사계산
• 암호화
• 천정희

이 동형암호 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반