비공모 서버를 이용한 안전하고 효율적인 연산 기법

Abstract

MPC(Multiparty Computation) 프로토콜이란 다수의 사용자가 각각 데이터를 제공하고, 이를 이용하여 협력적으로 연산을 수행하되 각자의 데이터는 노출하지 않는 암호학적 기초기술이다. Yao 등에 의해 처음 제안한 MPC는 두 사용자가 자신의 재산을 공개하지 않은 채로 누가 부자인지 계산하는 것으로서, 백만장자 문제라 불린다. 과거의 MPC 프로토콜들은 데이터를 제공한 사용자가 직접 연산을 수행했기 때문에, 한 명이라도 오프라인인 경우 연산이 중단되거나 처음부터 다시 시작해야 했다. 즉, 연산이 수행되는 동안 모든 사용자가 온라인 상태를 유지해야 한다. 2012년에 López-Alt 등은 이와 같은 문제점을 지적하며 공모하지 않은 두 서버에 MPC 연산을 위탁한 프로토콜을 제안했다. 하지만 López-Alt 등의 기법도 복호화 과정에서 모든 사용자의 참여가 필요하다. Peter 등은 2013년에 모든 사용자의 참여를 배제한 서버기반 MPC 프로토콜을 제안하였고, 이후 이를 확장한 여러 프로토콜들이 연구되고 있다. 지금까지 다양한 프로토콜들이 제안되었지만 서버간 통신 오버헤드, 공모공격 취약점, 불완전한 복호화 등 다양한 문제점이 존재한다. 본 논문에서는 Peter 등의 기법 이후로 제안된 다양한 프로토콜들을 살펴보고, 이들의 문제점으로부터 보안요구사항을 도출하여 이를 만족하는 서버기반 MPC 프로토콜을 제안한다. 제안하는 기법의 핵심은 덧셈동형특성을 갖는 암호시스템과 단방향 재암호화 기법을 결합하는 것이다. 덧셈동형특성을 이용하면 각 암호문에 독립적인 블라인드 요소를 사용할 수 있다. 더불어 단방향 재암호화 기법을 적용함으로써 각 사용자가 자신의 공개키로 암호화한 데이터를 하나의 키로 암호화 되도록 단일화 시킨다. 제안하는 기법의 기반이 되는 덧셈동형 암호시스템에는 재암호화 기법을 그대로 적용할 수 없기 때문에, 이를 일부 변형하여 적용했다. Peter 등의 기법에서는 암호문에 사용된 키를 단일화하기 위하여 모든 사용자의 데이터를 두 서버가 주고 받아야 했다. 제안하는 기법을 이용하면 이 과정을 생략할 수 있으므로, 서버에 맡겨지는 데이터의 양의 2배만큼 전체 통신비용을 줄일 수 있다.