공개 키를 넘어: 함수형 암호

기존 공개 키 암호화는 간단한 모델을 따릅니다. 공개 키로 암호화하고 이에 대응하는 개인 키로 복호화합니다. 복호화 수행자는 평문 메시지 전체를 알게 됩니다. 이러한 전부 아니면 전무 방식은 많은 애플리케이션에 지나치게 단순합니다. 예를 들어 의료 데이터베이스에서는 의사가 환자의 전체 의료 기록이 아니라 특정 질환이 있는지만 알 수 있도록 하고 싶을 수 있습니다. 함수형 암호화는 이러한 한계를 해결합니다.

ID 기반 암호화(IBE)는 1984년에 Shamir가 제안하고 2001년에 Boneh와 Franklin이 구축한 방식으로, 신원 문자열(이메일 주소, 도메인 이름, 직원 ID)을 공개 키로 사용할 수 있게 합니다. 신뢰할 수 있는 키 기관이 특정 신원에 대한 개인 키를 생성합니다. IBE는 공개 키 인증서가 필요하지 않게 하며 키 배포를 간소화합니다. IBE는 가장 단순한 형태의 함수형 암호화입니다.

함수형 암호화(FE)는 Boneh, Sahai, Waters가 2011년에 형식적으로 정의했으며 IBE를 일반화합니다. FE 방식에서는 키 기관이 어떤 함수 f에 대해서든 함수 키 sk_f를 생성할 수 있습니다. 암호화 Enc(x)와 함수 키 sk_f가 주어지면 복호화 수행자는 f(x)를 계산할 수 있지만, f(x)가 드러내는 정보 외에는 x에 대해 아무것도 알 수 없습니다. 함수 f는 해당 방식이 지원하는 함수 부류 안에서 계산 가능한 어떤 함수든 될 수 있습니다.

내적 함수형 암호화를 사용하면 sk_y를 가진 복호화 수행자가 벡터 x의 암호화 결과에서 내적 <x, y>를 계산할 수 있습니다. 이를 통해 비공개 기계 학습 추론이 가능합니다. 사용자의 특징 벡터 x를 암호화하고 모델 소유자에게 가중치 벡터 y에 대한 sk_y를 제공하면, 모델 소유자는 사용자의 특징을 알지 못한 채 내적(가공되지 않은 예측 점수)만 알 수 있습니다. 실용적인 내적용 FE 방식은 여러 가지가 있습니다(ABDALLA et al. 2016).

동등성 검사를 위한 FE를 사용하면 한 당사자가 암호화된 값이 특정 값 v와 일치하는지 확인하면서 동등성이 성립하는지만 알 수 있습니다. 이를 통해 개인정보 보호 데이터베이스 질의가 가능합니다. 서버는 암호화된 레코드를 보유하고, 사용자는 서버가 무엇을 검색하는지 알거나 예/아니요 일치 여부를 넘어선 결과를 알 수 없도록 특정 값과 일치하는 레코드를 질의할 수 있습니다. 실용적인 구성에서는 쌍선형 페어링을 사용합니다.

가장 강력한 형태의 FE는 함수로 임의의 불리언 또는 산술 회로를 지원합니다. 어떤 다항 시간 함수 f에 대한 sk_f를 가진 복호화 수행자는 Enc(x)에서 f(x)를 계산할 수 있습니다. 일반 회로 FE는 Garg, Gentry, Halevi, Raykova, Sahai, Waters(2013)가 다중선형 사상을 사용하여 이론적으로 구축했지만, 현재의 일반 FE 구성은 불완전한 다중선형 사상 가정에 의존하기 때문에 실용적이지 않습니다.

구별 불가능 난독화(iO)는 현재 알려진 가장 강력한 암호학적 기본 요소이며 함수형 암호화와 밀접하게 관련되어 있습니다. iO 방식은 회로 C를 입력으로 받아 동일한 함수를 계산하지만 입력과 출력의 동작을 넘어 C에 관한 어떤 정보도 드러내지 않는 난독화된 버전 O(C)를 생성합니다. iO는 일반적인 FE를 비롯해 현재 알려진 대부분의 암호학적 기본 요소를 함의합니다. 격자 문제를 이용한 후보 구성은 존재하지만 실제로 사용하기에는 아직 매우 비현실적입니다.

속성 기반 암호화(ABE)는 함수 f가 정책 평가로 제한되는, 실제로 구현 가능한 함수형 암호화의 한 형태입니다. 즉, 속성 집합 x가 정책을 만족하면 f(x) = 1이고 그렇지 않으면 0입니다. ABE를 사용하면 사용자의 속성에 따라 복호화 권한이 달라지는 세밀한 접근 제어가 가능합니다. ABE는 클라우드 저장소, 의료 분야, 사물 인터넷에서 구현되어 가장 널리 실제 배포된 함수형 암호화 형태입니다.

FE 구성의 역사는 단순한 방식에서 강력한 방식으로 발전해 왔습니다. IBE(Boneh-Franklin 2001) → 등식용 FE(여러 연구, 2005~2010) → 내적용 FE(ABDALLA 2016) → 깊이가 제한된 회로용 FE(다중선형 사상 기반, 2013) → 일반 FE(iO에서 유추됨) 순서입니다. 각 단계는 더 강력하지만 동시에 더 복잡하고 효율성은 낮습니다. 실제 배포에서는 원하는 기능을 달성하는 가장 단순한 형태를 사용합니다.

FE 보안은 두 메시지 x0과 x1의 암호화가 구별 불가능하다는 성질로 정의됩니다. 공격자에게 임의의 함수 f에 대한 함수 키가 주어지더라도, 질의한 모든 함수에 대해 f(x0) = f(x1)인 경우에는 이 성질이 유지됩니다. 이를 통해 복호화 주체는 정확히 f(x)만 학습하고 그 이상은 알 수 없습니다. 보안 수준은 두 가지입니다. 선택적 보안에서는 공격자가 공개 키를 보기 전에 도전 메시지를 정하고, 적응형 보안에서는 완전한 시뮬레이션 기반 보안을 사용합니다.

일반 FE는 여전히 실용적이지 않지만, 내적용 FE와 ABE는 현재 배포할 수 있습니다. 주요 과제로는 신뢰할 수 있는 키 기관의 필요성(단일 장애 지점), 키 폐기의 복잡성, 페어링 연산으로 인한 성능 오버헤드, 제한적인 표준화가 있습니다. 연구 방향으로는 다중 기관 FE(단일 신뢰 기관이 없음), 분산 키 생성, 다중선형 사상 없이 더 다양한 함수 종류를 지원하는 FE 등이 있습니다.

함수형 암호화(Boneh-Sahai-Waters 2011)는 IBE를 일반화하여, Enc(x)에서 x 전체를 알아내지 않고도 f(x)를 계산할 수 있는 함수 키 sk_f를 제공합니다. 내적용 FE(비공개 기계 학습 추론)와 등식 검사에는 실용적인 구성이 존재합니다. ABE는 접근 정책 평가를 위한 실제 배포 사례가 있는 특수한 형태입니다. 일반 회로용 FE에는 다중선형 사상이 필요하므로 실용적이지 않습니다. iO는 이와 관련된 가장 강력한 기본 요소입니다. 핵심 과제는 이론을 효율적인 실제 구현으로 발전시키는 것입니다.