동형암호

 이번에 학교에서 학부생 인턴 연구 주제로 동형암호에 대해 진행하였다. 동형 암호 내용 자체가 학부생 수준에서 이해하기 어렵다고 교수님도 그려셔서 그냥 개념과 특징만 정리해보겠다. 

 보고서에는 SEAL이랑 HElib 사용한 것도 첨부하였는데 그건 깃헙이랑 보고서 읽어봐도 무슨 원리로 한지 이해가 되지 않고 (너무 어려운 대수학 내용이 가득하다.) 그냥 유튜브에 설치 방법 따라해서 소스코드 파일에 있는 예제들 돌려본 수준이라 따로 올리진 않겠다. 

 

 0. 최신 암호 시스템의 필요성

현재 양자 컴퓨팅에 관한 연구가 활발하다. 제작년인가 구글에서 슈퍼컴퓨터로 1만년 걸리는 계산을 양자컴퓨터로 200초만에 해결했다는 기사가 나왔다. 

www.aitimes.kr/news/articleView.html?idxno=15037

[초점] 구글 양자컴퓨터의 진짜 위력은? - 인공지능신문

 제한적이고 유리한 환경으로 조성하여 계산했다지만 슈퍼컴퓨터를 몇 십 배도 아닌 몇 만 배 (하루가 3600초니까 1만년이면 13140000000초이다. 65,700,000배 빠르다. 6570만배...) 빠른 연산을 수행한다. 그럼 현존하는 암호체계가 깨지는 건 금방이다. 

 일반적으로 많이 사용하는 RSA 같은 경우 아무 조건이 없이 그냥 때려 맞춘다 가정하면 모든 경우를 조사해야하므로 2^256의 경우의 수가 존재한다. (meet in the middle 같은 걸로 좀 줄일 수 있지만 그런건 생략하자.)

2^256을 슈퍼컴퓨터로 돌려도 몇 만년 걸린다 그랬는데 이제 양자 컴퓨터가 상용화되면 몇 분만에 깨진다. 현대 암호 체계가 다 무너지는 것이다. 그렇기 때문에 새로운 암호 시스템이 필요하다. 

 현재 양자 암호 분야도 활발히 연구 중이고, 동형암호를 비롯하여 많은 암호 체계가 양자 컴퓨팅에 대응하기 위해 업그레이드 중이다. 

 

 1. 동형 암호 개념

 동형 암호의 개념이 나온 것은 오래되었다. 7,80년대에 나왔지만 당시 개발한 동형암호는 취약점이 계속해서 예상되어졌다. 하지만 21세기 들어 다시 동형암호가 쓰이기 시작한다.

 동형 암호는 데이터를 암호화된 상태에서 연산시킬 수 있는 방법이다. 가장 간단한 것은 modulo 연산을 생각하면 된다. Z*_p field에서 곱셈과 덧셈 모두 잘 정의되므로 Z*_p field 내에서 암호화된 것은 덧셈과 곱셈 연산이 가능하다. 이와 같이 암호화된 데이터를 복호화하지 않고 연산한 뒤, 복호화 했을 때, 원래의 데이터의 연산 결과와 일치하는 원리를 이용한 것이 동형 암호이다.

출처 : http://wiki.hash.kr/index.php/%EB%8F%99%ED%98%95%EC%95%94%ED%98%B8

2. 완전동형암호

 위에서 설명한 동형암호의 개념만으로는 뚫린다는게 7,80년대에 밝혀졌다. Gentry라는 분이 동형암호의 개념을 좀 더 발전시켜 현재 동형암호 이론의 기초(SHE, Somewhat Homomorphic Encryption)가 되었다. Gentry는 기존의 동형암호 개념과 lattice-problem(격자 문제, 수 백, 수 천 차원의 임의의 점에서 가장 가까운 점을 구할 수 있느냐하는 문제, 수학적 난제이다.)을 적용하여 SHE의 틀을 다졌다. 하지만 Gentry의 방법을 이용하면 뚫리지는 않지만, 일정 수준 이상의 연산 (곱셈) 을 진행하면 복호화도 되지 않는다. 그렇다면 쓸모가 없어진다! 그래서 이를 방지하기 위해 나온 것이 완전동형암호 (FHE, Fully Homomorphic Encryption) 이다.

 먼저 완전동형암호에 많이 쓰이는 원히는 부트스트래핑(boot strapping)과 스쿼싱(squashing)이다. 완전동형암호 동형암호는 연산 과정에서 노이즈라고하는 에러가 계속 발생되고, 이 에러가 지수적으로 증가한다. (그래서 곱셈 연산 일정 횟수 이상이면 복호화가 불가하다.) 그리고 이 노이즈의 발생을 줄이기 위해 재부팅을 위한 시간이 필수적이고, 평문에 비해 암호문의 길이가 10~100배 가량 길어지기 때문에 항상 비효율성의 지적을 받았다. 

 부트스트래팡은 암호문에 암호화된 비밀키를 넣어, 연산 과정에서 노이즈가 감소된 새로운 암호문을 만들도록 하는 것이다. 스쿼싱은 복호화 알고리즘과 공개키를 일부 변형하여 미리 필요한 연산을 수행한다. 그리하여 노이즈 증가량을 감소시키는 것이다. (정확한 내용은 어렵다... 부트스트래핑과 스쿼싱 모두 이론적으로 맞으면 알맞은 것이기 때문에 다양한 동형 암호에서 사용 중인 부트스트래핑과 스쿼싱은 알고리즘이 서로 다르다.)

 이렇게 부트스트래핑과 스쿼싱을 이용하여 노이즈 발생을 줄이고 시간을 줄인 동형암호가 완전동형암호의 기초이다. 하지만 완전동형암호라고 제시된 모델들 또한 결국 노이즈 자체가 쌓이게 되어 재부팅 시간이 필요하거나, 아예 특정 횟수 이상 곱셈 연산이 여전히 불가능하다. 그리고 스쿼싱을 위한 사전 계산 과정이 너무 비효율적이라 판단되어 최근에는 부트스트래핑과 스쿼싱이 없는 완전동형암호를 개발 중이다. (CRT 기반, 또는 다른 수학적 난제 등)

 대표적인 완전동형암호 오픈소스 라이브러리는 MS의 SEAL, IBM의 HElib, 서울대의 HEAAN 등이 있다. 현재 나온 동형암호 중 성능이 가장 좋은 것은 서울대학교 천정희 교수님 연구팀의 HEAAN이라고 알려져 있다. (지난 번 여름 암호 학교 때 뵜었는데 똑똑함이 느껴지시는 분.... 나는 뭘까...)

 

3. 전망

 일단 전망은 밝다. 왜냐하면 일단 양자컴퓨터는 계속 개발 중이고, 거기에 적용될 암호 모델이기 때문이다. 기존의 대칭키나 공개키와 달리 암호문의 길이가 평문보다 몇 십배 길고, 암호문 자체를 연산시키기 때문에 제 아무리 양자 컴퓨터라도 살아있는 동안 뚫지 못한다. (암호문을 연산하는 시간보다 짧은 시간 안에 뚫어야만 암호 체계를 뚫을 수 있다. 그렇게 못하면 다시 암호화 시켜버리면 되기 때문이다.) 또한 데이터의 암호화가 필연적으로 (모든 데이터는 중요하지만!) 필요한 군사, 의료, 금융 등의 분야에서 더욱 필요할 것이고, 블록체인의 경우 탈중앙화를 최종 목적으로 두고 있는데 탈중앙화를 하게 되면 보안상의 문제가 크게 발생할 수 있다. 이를 방지해줄 기술 또한 동형암호로 기대 중이다. 

 이처럼 많은 분야에서 동형암호의 쓰임새는 무궁무진하다. 다만 아직은 암호화에 시간이 오래 걸리고, 메모리도 많이 잡아먹고, 무엇보다 아주아주 어렵고 해서 실생활에 쓰이기까지는 좀 걸릴 듯하다. 아마 블록체인 기술이 일상 생활에 많이 쓰인다면 그 때 쯤은 동형암호도 지금의 RSA나 SHA와 같이 쓰이지 않을까 싶다. (한참 먼 미래 얘기란 뜻!)

 이 부분을 지금부터 공부해도 상용화될 때 1세대 칭호를 받을 수 있다. (Gentry 모델이 나오고 제대로 연구된지 10년 정도 밖에 안 됐으니 ㅎㅎㅎ) 근데 설명을 아무리 읽어도 내 머리론 이해할 수 없는 녀석이었다. 한 마디로 개어렵다.