A Study on Homomorphic Packing

Abstract

In cryptography, using large or complex mathematical structures is often required for security or other functionality. On the other hand, small or moderate-sized messages with a familiar algebraic structure are used in real-life computations. Regarding this discrepancy, similar concepts of embedding multiple messages into a large structure while preserving their algebra have been independently studied in various contexts of secure computation. This includes the packing technique in homomorphic encryption (HE) and the reverse multiplication-friendly embedding (RMFE) in information-theoretically secure multi-party computation (MPC). In this thesis, we formally define homomorphic packing and initiate a unified study of related concepts in various contexts of cryptography. We review existing packing methods through our systematic framework and prove several mathematical limitations on the performance of homomorphic packing. As an application, we devise a new packing method and utilize it to design an HE-based MPC protocol for Z2k-messages. Our results on the limitations of homomorphic packing justify our approaches and design choices for the packing method and the MPC protocol.

암호학에서는 안전성 혹은 기능성을 위해 종종 크고 복잡한 수학적 구조를 사용한다. 반면 우리는 일상에서 작고 단순한 대수적 구조 위에서 주로 계산한다. 이러한 불일치와 관련하여, 대수적 구조를 보존하면서 큰 구조에 여러 개의 메시지를 채워 넣는 기법이 암호학의 다양한 세부분야에서 독립적으로 연구되어 왔다. 대표적으로 동형암호에서의 패킹기법과 정보이론적으로 안전한 다자간계산(MPC)에서의 역곱셈친화적 임베딩(RMFE)이 있다. 본 논문에서는 암호학의 다양한 맥락에서 등장하는 관련 개념들을 포괄하여 새롭게 동형팩킹을 정의한다. 통합된 정의를 바탕으로 기존의 기법들을 분석하고 동형패킹의 성능에 대한 몇 가지 수학적 한계를 증명한다. 또한, 새로운 동형패킹 방법을 고안하고 이를 활용하여 Z2k를 메시지공간으로 갖는 효율적인 동형암호 기반 MPC 프로토콜을 설계한다. 증명한 동형패킹의 한계는 새로운 동형팩킹과 MPC 프로토콜의 설계방식을 정당화한다.