IT 기술이 발전하면서 사람들의 생활도 편리해졌지만, 그만큼 위험성도 높아졌다. 은행업무와 SNS 등 인터넷 망으로 일상 생활의 방대한 부분이 해결되면서 개인정보 유출과 국가와 기업적으로는 핵심 보안 정보 유출 등의 위험이 도사리고 있다.

이런 가운데 국내 연구진이 대용량 데이터 상태로 연산이 가능한 제4세대 암호기술을 개발했다. 이는 대용량 데이터를 처리하기 위한 완전동형암호로서, 일반적으로 암호화된 정보는 해제과정을 통해 정보를 이용할 수 있는데 이 기술은 암호화된 상태 그대로 연산이 가능해 데이터 처리 속도가 높고 외부 유출로부터 데이터의 안전성을 지킬 수 있다. 예를 들어 기업이나 보험회사, 국가 등에서 통계나 보험료 등을 계산할 때 암호화된 개인정보를 해제(복호)하지 않고도 처리할 수 있는 가능성이 생긴 셈이다.

암호 안에 더 많은 원문 저장

이 연구를 통해 개발된 암호는 완전동형 암호로, 이는 암호화한 상태에서 복호화 없이 평문의 연산을 가능케 해주는 것을 의미한다. 암호문들을 더해서 생기는 암호문이 각각의 암호문에 해당되는 평문들의 덧셈의 암호문이 되는 암호로, 특별히 암호문만으로 임의의 연산을 가능케 해 주는 것을 완전동형 암호라고 부른다. 완전동형 암호는 아니지만 어느 정도까지의 연산을 허용해 주는 암호는 준동형 암호다.

이번 연구는 최근 개인정보 유출과 같은 해킹이 많이 발생하면서 천정희 교수 연구팀이 암호 안전성의 중요성을 인식하며 시작됐다. 천 교수는 “최근 개인정보 유출과 같은 해킹 사건이 많이 보도되면서 해킹대비책의 필요성이 대두되고 있다. 해커 양성이나 시스템 보안을 강화하는 방법도 대안책으로 거론되고 있지만 이런 방법들은 임시적인 방법일 뿐, 근본적인 해결책은 되지 못한다”고 언급했다.

이러한 해결책으로 거론되는 것이 제4세대 암호로 불리는 완전동형 암호다. 예상치 못한 정보 유출에 대비할 수 있는 가장 좋은 미래기술로 언급되는 완전동형 암호는 기관 내부자의 정보 오남용이나 외부 해킹 등에도 안전성을 지켜준다.

“일반적으로 암호화된 정보들은 검색이나 통계처리 등을 위해 모두 복호화해 연산한 후 다시 암호화해 저장해야 하는데, 이는 매우 비효율적이다. 동형 암호를 사용하면 암호화된 상태에서 데이터 연산을 할 수 있으며, 클라우드와 모바일 정보 이용 환경에서의 공공‧금융 등 주요서비스 제공과 관련된 보안 목표를 달성하기 위해 꼭 필요하다. 이 연구 결과로 제안된 동형 암호화 방식은 비트 단위가 아니라 큰 숫자 단위로 암호화를 하는 것이 가능해 같은 암호문이라도 그 안에 더 많은 원문 정보를 저장할 수 있고, 숫자들 간의 사칙연산이나 다항식 연산과 같은 널리 쓰이는 연산을 비트 단위가 아니라 직접적으로 수행할 수 있어 훨씬 효율적이다. 목적에 따라서는 여러 숫자들이 모여 이루어진 이진 벡터들을 암호화하고 이에 대해 벡터 연산을 수행하는 것도 가능하다.”

그동안에는 완전동형 암호가 미래유망기술로 선정되는 등 주목을 받았지만 한 비트(bit)를 암호화하는 데 필요한 암호문의 크기가 너무 커 실제로 구현하기에는 한계가 있었다. 미국 방위연구고등계획국(DARPA) 역시 이러한 난제로 인해 지난 2011년부터 5년 동안 약 2천만 달러의 거액을 투자하며 연구에 매진하고 있으며 영국 정부에서도 Nigel Smart의 연구에 2011년에만 100만 파운드를 지원했다.

“기존 Gentry의 방식을 비롯한 대부분의 완전동형 암호화 방식은 모든 데이터를 0과 1을 사용한 이진수로 표현해, 각각의 비트 0 또는 1을 암호화는 방식으로 이루어진다. 이는 비트 단위의 임의 연산을 가능케 하지만 한편으로는 고작 1비트의 정보량을 암호화하기 위해 매우 긴 암호문을 생성해야 하는 문제와 함께 모든 연산을 비트 단위로 수행해야 하므로 비효율적이다. 따라서 이번 연구는 매우 중요한 의미를 가진다고 할 수 있다.”

이 연구를 통해 개발된 암호화 방식은 Gentry의 방식과 마찬가지로 완전동형성을 제공하도록 사용하는 것도 가능하도록 설계, 정수론의 고전적 결과인 중국인의 나머지 정리(Chinese Remainder Theorem)를 새로운 방식으로 적용했다. 천 교수팀의 논문은 동일한 문제에 대한 연구결과를 제출한 프랑스 팀의 논문과 합병돼 발표‧게재될 예정인데, 큰 정수 연산을 지원하는 결과는 해당 논문에서만 제시됐다.

암호해제 과정 건너뛰는 암호?

천 교수 연구팀이 개발한 방식은 중국인의 나머지 정리에 기반해 암호문에 대응하는 유일한 원문을 복구해내는 방식으로 암호를 해제하지 않고 곧바로 수십에서 수만 자리에 이르는 정수들의 연산을 지원할 수 있는 완전동형 암호다.

중국인의 나머지 정리란 1세기경 중국의 수학자 Sun-Tsu가 증명한 것으로, 이는 서로소인 두 양의 정수 p와 q가 있고, 어떤 수 x가 각각의 정수로 나눴을 때의 나머지를 알 경우 이 수를 n=pq로 나눴을 때의 나머지는 유일하며 p와 q를 알면 쉽게 구할 수 있다는 정리다. 다항식 환에 비해 정수환에선 주어지는 구조가 많지 않기 때문에 중국인 나머지 정리를 적용한다는 것은 어려운 문제다. 때문에 연구팀은 기존에 나와 있는 문제가 아닌 새로운 문제를 정의했고, 이 문제가 풀리기 어렵다는 사실에 기반해 암호 알고리즘을 만들어냈다. 구조가 비교적 없는 공간에서 중국인 나머지 정리를 적용해 동형암호를 만들어냈다는 점에서 이 연구결과의 의의가 있다고 할 수 있는 셈이다.

이를 통해 개발된 연구는 중간보안등급의 경우 암호화에 42초, 복호화에 0.04초가 걸리게 된다. 동일한 시간에 처리할 수 있는 데이터 용량이 기존에는 1비트에 불과하나 개발된 완전동형 암호로는 5천 비트를 처리할 수 있다. 동시에 처리할 수 있는 정보량이 수천 배로 늘게 되어 클라우드, 모바일 금융 등에서 실제 구현될 가능성이 높아진 것이다. 그렇다면 이것이 어떻게 가능한 것일까. 이 연구를 통해 개발된 암호는 해제 과정을 생략하고 암호화된 상태 그대로 연산이 가능하도록 만들어졌다.

“암호화할 때 덧셈과 곱셈을 모두 보존하는 성질을 가지는 함수를 사용하게 된다면, 복호화 과정 없이 연산이 가능하게 된다.”

이렇게 처리할 경우 기존의 암호 방식에서는 해결할 수 없던 추가적인 작업의 진행이 가능해진다. 기존에는 한번 암호화된 데이터에 대해서는 추가적인 작업을 진행을 하는 것이 어려웠다. 일단 암호화를 통해 무의미해 보이는 암호문으로 변환된 다음에는 무의미한 데이터에 대해 유의미한 작업을 하기가 어렵기 때문이다. 데이터 보안을 위해서는 암호화해 저장하는 것이 필수지만, 이러한 데이터에 대해 검색과 계산, 분석 등 작업을 진행하기 위해서는 일반적으로 그때 그때마다 복호화 과정을 통해 다시 원 데이터를 복구하는 게 필요했고, 이 과정에서 계산량이 늘어나게 된다.

“이러한 경우 복구된 원 데이터에 대해 침입이나 해킹, 내부자 접근 등으로 정보가 유출되는 경우가 많기 때문에 근본적인 해결책이 되지 못했다. 그러나 완전동형 암호는 데이터의 비밀을 유지하면서 데이터를 이용한 다양한 업무와 처리를 가능하게 하는 큰 장점이 있다. 비록 현재까지 제안된 방식들은 실제적인 활용에 있어 그 효율성이 매우 떨어지는 문제가 있지만 효율성을 대폭 개선한 이 연구의 결과물은 앞으로 완전동형 암호의 실용화를 이루어 컴퓨터 보안 기능 강화에 크게 공헌할 수 있고 향후 다양한 관련 연구의 기폭제가 될 수 있을 것으로 보인다.”

이번 연구는 특히 정수 기반 동형암호로는 최초로 한 번의 연산으로 여러 데이터 처리가 가능한 SIMD(Single Instruction Multiple Data) 연산이 가능하도록 설계됐다. SIMD는 한 번의 연산만으로 여러 데이터에 대해 한꺼번에 같은 연산을 해주는 기법을 통칭하는 것으로, 중국인 나머지 정리의 가장 기본적이고 핵심적인 성질 중 하나가 환동형 맵(map)을 갖고 있다는 점인데, 이 맵의 성질에 의해 SIMD가 지원되는 것이다. 이번 연구결과는 정수기반의 동형암호 중 최초로 SIMD연산을 지원하는 알고리즘인 것이다.

이번 연구는 추후 병원진단기록과 보험료 지급, 은행데이터처리 등 다양한 곳에서 사용이 가능할 것으로 보인다.

천정희 교수는 “최근 인터넷 쇼핑몰과 은행 등의 해킹으로 개인정보나 계좌 정보 등이 유출됐다. 그리고 게임사에 가입된 회원들의 개인정보도 유출되면서 아이들의 정보도 함께 유출, 이로 인해 보이스피싱(phishing)의 금전적인 피해 뿐 아니라, 유괴 등 심각한 범죄로 이어지고 있다. 이번 기술은 이러한 사건들에 대해 완전한 해결책이 없는지 고민하다가 얻게 된 결과다. 암호화된 상태에서도 탐색은 물론, 제한된 열람이라든지 통계처리가 가능한 암호를 만들게 된다면 내부자들로 인한 유출과 같은 사고를 완전히 막을 수 있을 것이고 연장선상에서 발생하는 범죄도 예방할 수 있을 것이다.”