동형 암호화의 개념 및 현황

최근 데이터 기반 연구 및 산업이 발전함에 따라 개인정보 보호 이슈도 함께 떠오르고 있습니다. 예를 들어 IT 기업들은 다수의 고객 데이터를 이용하여 서비스를 구축하거나 개인 사용자에게 맞춤형 서비스를 제공하는 과정에서 개인정보의 수집과 분석이 일어나게 됩니다. 문제는 이 과정에서 민감한 개인정보가 노출될 여지가 크다는 데 있습니다.

개인정보를 보호하기 위해 데이터에 대한 접근을 막을 수 있지만 이는 데이터의 사용을 원천적으로 차단하게 되어 올바른 해답이 아닙니다. ‘프라이버시 보호’의 목적은 데이터의 유용성과 기능성을 보존하면서 데이터 제공자들이 의도하지 않은 방향의 정보 오남용을 방지하는 것입니다.

데이터 프라이버시를 달성하려는 노력은 정책수립, 기술적 연구 등 다양한 방향으로 지속되어 왔습니다. 대표적으로 미국의 HIPAA, EU GDPR과 같은 개인정보 보호에 대한 규정들이 있으며 국내에서는 최근 데이터 3법을 개정하는 등 개인정보와 데이터기반 과학 및 산업발전 두 마리 토끼를 잡으려는 노력을 하고 있습니다. 대표적인 프라이버시 기술로 고전적으로는 익명화, 매스킹, 랜덤화, 범주화 등 데이터의 정보 일부를 삭제하거나 변형하는 방법들이 주로 쓰였는데 프라이버시 보호를 위해 손실되는 정보량으로 인해 활용성이 저하된다는 고질적인 단점이 있었습니다.

다행히도 최근 학계에서는 프라이버시 보존에 사용가능한 시큐어컴퓨팅 기술의 급격한 발전이 이루어지고 있습니다. 기존의 암호 기술이 단순히 암호화, 디지털 서명 등을 이용하여 데이터 보호와 신원확인에 초점을 맞췄다면 최근에는 이를 넘어서서 데이터 결합과 계산과정을 보호하는 등 추가적인 기능성을 제공하는 다양한 기반기술들이 등장하고 있습니다. 현재 가장 주목받는 시큐어컴퓨팅 기술로는 차등정보보호(Differential Privacy), 영지식 증명(Zero-Knowledge Proof), 다자간 연산(Multi-Party Computation), 그리고 오늘의 주제인 동형암호(Homomorphic Encryption) 등이 있습니다.

그림 1. 동형사상의 성질

그림 2. 동형암호 개요

그림 3. 동형암호를 이용한 프라이버시 보존 개인맞춤형 서비스

동형사상(Homomorphism)이란 대수학 분야에서 사용하는 용어로 두 집합 사이의 대수적 구조를 보존하는 함수들을 지칭하는 말입니다. 다시 말해서 동형사상이 주어진다면 <연산을 수행한 뒤에 함수 값을 계산>하는 경우와 <함수를 먼저 계산하고 연산을 수행>하는 두 가지 방법이 동일한 결과를 도출하게 됩니다(그림 1).

그렇다면 동형암호란 무엇일까요? 동형암호란 간단히 말해서 암호화 과정이 동형사상인 암호시스템입니다. 동형암호에서는 우리가 평문(plaintext)에서 계산을 진행하듯이 암호문(ciphertext) 위에서 특정한 연산들을 수행할 수 있으며 그 결과로 얻어진 암호문을 비밀키 소유자가 복호화하면 마치 평문 위에서 같은 계산을 진행한 것과 동일한 결과를 얻을 수 있습니다(그림 2).

동형암호는 처음에 언급했던 데이터 프라이버시 문제를 해결할 수 있는 가장 전도유망한 기술 중 하나로 평가되고 있습니다. 대표적인 용례로 IT 기업들이 제공하는 맞춤형 서비스에서의 개인정보 보호를 꼽을 수 있는데 사용자가 서비스 제공을 위해 보내야 하는 쿼리(query)에 민감한 정보가 포함되어 있다면 이를 암호화하여 전송하고 서비스 제공자는 암호화된 쿼리 상에서 계산을 진행하는 방법을 통해 개인정보의 유출을 막을 수 있습니다(그림 3). 또한 정부, 금융기관 등 다수의 기관에서 산발적으로 보유하고 있지만 공유가 금지되어 있는 데이터를 안전하게 취합하고 분석하여 그 활용성을 높이는 데에도 사용 할 수 있습니다. 특히 동형암호를 통계데이터 분석에 적용한다면 데이터베이스 연계를 통해 더 다양하고 정확한 통계지표를 제공하는 국가통계 분석시스템 구축에 큰 역할을 할 것입니다.

동형암호는 보통 지원하는 연산을 기준으로 몇 종류로 나뉩니다. 일반적으로 동형암호는 덧셈과 곱셈을 모두 지원하는 암호시스템을 지칭하지만 이 중 하나의 연산만 지원하는 스킴은 부분동형암호(Partial Homomorphic Encryption)로 불리우며 RSA, ElGamal 등이 대표적인 예입니다. 반면 두 가지 연산 모두 계산이 가능하지만 연산의 횟수에 제한이 있는 경우는 준동형암호(Somewhat Homomorphic Encryption), 마지막으로 연산의 종류와 횟수에 제한 없이 임의의 계산을 수행 가능한 암호시스템을 완전동형암호(Fully Homomorphic Encryption)로 분류합니다. 개념적으로는 완전동형암호가 우월하지만 실제 응용분야에서는 효율성과 편의성 등의 이유로 준동형암호 역시 좋은 선택이 될 수 있습니다.

잠시 동형암호에 대해 흔히 생기는 오해 중 하나를 소개하려 합니다. 만약 0을 암호화하여 암호문 c=Enc(0)를 얻고 이 암호문을 두 번 더한다면 동형암호 성질에 의해 그 결과물 c+c 역시 0+0=0의 암호문일 것입니다. 그렇다면 c+c=c가 성립해야 하고 결과적으로 c=0이 되어 안전성이 보장되지 않는다고 생각할 수 있습니다. 위와 같은 문제가 발생하지 않은 이유는 하나의 평문에 대응되는 암호문이 유일하지 않기 때문입니다. 동형암호의 암호화 과정은 일종의 확률적 알고리즘으로 주어진 평문에 대응하는 수많은 암호문 중 하나를 랜덤하게 도출하게 됩니다. 이렇게 생성된 암호문 상에서 연산을 진행하면 그 결과에 대응하는 수많은 암호문 중 하나를 얻게 되므로 이로부터 평문에 대한 정보를(일부라도) 얻어내는 것은 불가능합니다.

현재 가장 널리 쓰이고 있는 효율적인 동형암호 시스템들은 대부분 격자(lattice) 이론에 기반하고 있습니다. 격자이론은 수학과 컴퓨터과학 내에서 오랫동안 연구된 주제로 암호시스템의 설계와 안전성 증명에 널리 사용되고 있습니다. 기존 RSA, ECDSA 등에 사용되었던 소인수분해(integer factoring)나 이산로그(discrete logarithm)와 다르게 격자기반 문제들은 이를 효율적으로 풀 수 있는 양자 알고리즘이(아직까지는) 존재하지 않기 때문에 양자컴퓨터의 등장 이후에도 사용 가능한 차세대 암호의 가장 강력한 후보로 여겨지고 있습니다.

동형암호의 개념은 1978년에 이미 Rivest, Adleman 그리고 Dertouzos에 의해 구상되었습니다. 하지만 함께 제시되었던 스킴들의 취약점이 발견되면서 안전한 동형암호의 설계문제는 암호학계의 성배로 불리며 30년이 넘는 시간동안 미해결 상태로 남아있었습니다. 2009년 Gentry가 소위 재부팅(Bootstrapping)으로 불리는 방법을 제시하며 증명가능한 안전성을 가지는 최초의 완전동형 암호를 설계하면서 본격적인 동형암호 연구의 장을 열었습니다.

동형암호 연구 초창기에는 학계 내에서도 동형암호의 실용화는 수십 년 이상의 시간이 걸릴 것이라는 부정적인 의견이 많았습니다. 그도 그럴 것이 2011년에 발표된 최초의 동형암호 개념증명(proof-of-concept) 구현결과는 재부팅 한 번에 30분이라는 비현실적인 수준의 실행시간을 보여줬기 때문입니다. 하지만 그 뒤로 약 10년간 다양한 측면에서 급격한 발전이 이루어졌습니다.

먼저 2012년 유한체 위에서의 모듈러 연산(modular arithmetic)을 지원하는 BGV, FV 스킴이 등장하였고 이와 함께 수백에서 수천 개의 숫자를 하나의 암호문에 저장할 수 있는 패킹(packing) 기술이 개발되었으며, 같은 해 이를 구현하여 3만개의 Boolean gate로 이루어진 AES-128 복호화를 동형암호 상에서 36시간 내에 계산하는 결과가 보고되었습니다. 다음 해 IBM에서는 다양한 최적화 과정을 거쳐 최초의 공개 동형암호 라이브러리 HElib을 출시하였고 이를 바탕으로 위와 같은 AES-128 계산시간을 4분으로 줄이는 성과를 거두었습니다. 한편 지원하는 연산의 종류를 다양화 하는 방향의 노력도 있었는데 2016년 Chillotti 등이 개발한 TFHE 스킴은 단일 비트 연산에 적합하며, 마지막으로 2017년에 발표된 CKKS(a.k.a. HEAAN) 스킴은 기본적으로 근사계산을 지원하고 데이터 패킹이 가능하여 기계학습 등 실수연산을 포함하는 빅데이터 분석에 가장 적합하다는 평가를 받고 있습니다. 2020년에는 동형암호 기술의 산업적 활용을 목적으로 ISO/IEC 준화가 제안되어 현재 표준화 과정이 진행 중입니다.

표 1. 동형암호 스킴과 특징

그 외에도 다양한 동형암호 스킴들이 연구되었지만 지금으로서는 위에 언급된 세 종류의 동형암호가 가장 경쟁력 있는 후보들이며 이들을 기반으로 학계 및 기업 다수의 기관에서 동형암호 라이브러리를 개발하고 관리하고 있습니다(표2). 동형암호의 성능은 무어의 법칙(Moore’s Law)을 상회하는 속도로 발전하고 있는데 현재 공개된 라이브러리를 기준으로 수천 개의 실수를 저장하고있는 BGV나 CKKS 암호문의 곱셈 연산은 인수(parameter) 선택에 따라 약 10ms 에서 0.1s의 성능을 보여주고 있으며 TFHE 암호문의 재부팅은 약 13ms가 소요됩니다(표 1).

동형암호 계산에 필요한 알고리즘 대부분은 병렬처리가 용이한 형태를 가지고 있습니다. 위에 소개된 모든 실험수치는 CPU 상에서 얻어진 결과이며 GPU나 FPGA등 다중코어를 이용한 구현을 통해 손쉽게 개선할 수 있습니다. 작년부터 미국 국방부 방위고등연구계획국(DARPA) 에서는 동형암호 구현을 위한 하드웨어 가속기 개발에 3300만 달러 예산 규모의 사업에 착수하여 Microsoft, Intel과 업무협약을 체결한 상태입니다.

표 2. 대표적 동형암호 라이브러리 목록

동형암호 기초 라이브러리의 구축 이후에는 자연스럽게 이를 바탕으로 좀 더 복잡하고 실용적인 문제들에 적용하려는 시도들이 있었습니다. 대표적으로 미국 국립보건원(NIH)에서 후원하는 iDASH Security & Privacy Competition이 있는데 매년 생명과학 분야에서의 주요 프라이버시 문제를 선정하고 이를 동형암호를 포함한 최신 암호기술을 이용하여 해결하는 대회가 진행되고 있습니다. 최근 몇 년간의 결과를 살펴보면 현재 동형암호 기술이 로지스틱 회귀분석이나 소수의 층을 가지는 인공신경망 등 비교적 간단한 기계학습 모델의 학습(training)이나 추론(inference) 계산을 무리 없이 해내는 수준에 도달했음을 알 수 있습니다.

본격적인 동형암호의 사용 예로는 최근 Microsoft Edge에서 시작한 ‘Password Monitor’를 들 수 있는데 이 서비스는 사용자의 비밀번호가 유출되었는지 여부를 확인하고 경고하는 것을 목표로 합니다. 기업에서 보유하고 있는 유출된 비밀번호 목록과 사용자 계정 비밀번호 목록에 공통된 항목이 있는지를 암호화된 상태에서 계산하는 방식을 통해 사용자 비밀번호 목록에 대한 접근 없이 원하는 결과만을 도출할 수 있습니다.

동형암호의 빠른 발전에도 불구하고 기술의 상용화를 위해 해결해야 할 과제들이 남아 있습니다. 암호화된 상태에서는 덧셈, 곱셈과 같이 제한된 연산만 가능하며 평문 상태와 비교해서 전혀 상이한 계산 복잡도를 가집니다. 그러므로 동형암호 상에서의 프로그래밍은 기술에 대한 깊은 이해를 요구하며 같은 계산을 수행하는 프로그램이더라도 최적화 수준에 따라 막대한 성능 차이를 보일 수 있습니다. 최근 비전문가의 진입장벽을 낮추기 위해 원하는 계산을 수행하는 스킴의 인수 및 알고리즘을 자동적으로 선택하여 동형암호 배경지식이 없이도 합리적인 수준의 프로그래밍을 가능하도록 하는 컴파일러 연구들이 진행되고 있습니다. 지금까지는 행렬-벡터 곱셈이나 인공신경망 추론을 도와주는 기초적인 수준이지만 근 미래에 통계적 분석과 기계학습 등 보다 복잡하고 일반적인 프로그래밍을 지원하는 컴파일러가 등장할 것으로 생각됩니다.

한편 데이터 3법 개정 및 데이터기반 산업의 팽창에 따라 동형암호를 포함한 최신 암호기술의 개발 및 전문가에 대한 수요가 빠르게 늘어날 것으로 예상하고 있습니다. 학계, 산업계 및 정부기관에 소속된 다양한 분야의 전문가들의 암호분야 진입과 전공자 배출을 통한 인력 육성을 통해 데이터 분석과 공유경제 시대에 대비하는 것이 절실한 시점입니다.