back

Efficient MPC via Multi-Party Homomorphic Encryption

Master Thesis

Motivation

Secure Multi-Party Computation (MPC) protocols enable a group of parties to securely compute joint functions over their private inputs without revealing any information beyond the output. Homomorphic encryption (HE) approaches have been known to reduce the communication complexity of MPC [1]. HE is a scheme that supports computation on encrypted data. Concretely, HE schemes enable secure outsourcing computation in an untrusted cloud and have a wide range of applications between multiple data providers. In MPC, multiple parties should build an interactive protocol to evaluate a circuit without revealing auxiliary information beyond the computation result, but it usually suffers from a high communication and round complexity. There are some scenarios where an interactive circuit evaluation does not fit the system and network model. To solve these issues, Multi-Party HE (MPHE) can be used to design round-efficient MPC protocols with minimal communication cost [2,3,4].

Mouchet et al. [4] proposed an MPC solution based on BFV [5] and CKKS [6] homomorphic encryption schemes in the semi-honest model with a dishonest majority, based on MPHE. López-Alt et al. [7] proposed a Multi-Key Homomorphic Encryption (MKHE) scheme, which is a cryptographic primitive performing arithmetic operations on encrypted ciphertexts under different keys. Chen et al. [3] present multi-key variants of BFV and CKKS with packed ciphertexts by adapting the state-of-the-art bootstrapping algorithms to the multi-key scenario. In the same line of work, Chen et al. proposed an MKHE scheme [2] by generalizing the low-latency homomorphic encryption by Chillotti et al. [8]. They evaluated a binary gate on ciphertexts encrypted under different keys followed by a bootstrapping.

Most of the current HE schemes can be classified into Arithmetic Circuit-based HE (such as BFV [5] and CKKS [6]) and Boolean Circuit-based HE (such as FHEW [9] and TFHE [8]). Each type has its advantages and disadvantages. It becomes challenging to compute non-polynomial functions like min/max on the ciphertexts of Arithmetic Circuit-based HE schemes, and to compute polynomial functions like multiplication over Boolean Circuit-based HE. In another line of research, to address this issue, the CHIMERA framework [10] allows to switch between TFHE ciphertexts and ciphertexts of the torus variant of the CKKS/BFV schemes to enable to perform arithmetic operations via CKKS/BFV and to compute Boolean gates via TFHE. Recently, PEGASUS [11] allows to efficiently switch back and forth between a packed CKKS ciphertext and FHEW ciphertexts without decryption, allowing to evaluate arithmetic functions via CKKS and LUTs on FHEW ciphertexts. This work will consider conversions between different Multi-Party Homomorphic Encryption (MPHE) schemes.

Goal

All the previous works were purely abstract and far from practical for real-world applications. In particular, the efficiency of MPHE remained an open question because there has been no analysis and study to compare and combine them. At the first stage, this thesis will study and analyze different MPHE schemes, especially the works proposed in [2,3,4] and the conversion between them. Such an analysis is essential to understand better which MPHE scheme to use in which use case and for which part of secure computation. Then, the thesis will propose a practical hybrid solution for combining and switching between popular MPHE schemes inspired by [10, 11]. More concretely, the thesis should design and implement a mixed protocol framework that efficiently combines secure computation schemes based on MPHE. In the end, an implementation of hybrid MPHE schemes is provided and the performance is experimentally evaluated for basic applications that involve combinations of arithmetic and boolean operations such as modular exponentiation, private set intersection, biometric matching, supervised and unsupervised machine learning. The performance of the applications should be compared against solutions that are based purely on MPHE of Boolean Circuits and should also be compared with the performance that can be achieved by interactive solutions based on state-of-the-art MPC (e.g., by comparing with corresponding benchmarks from the MOTION paper [12]).

Requirements

  • Good programming skills in C/C++
  • At least basic knowledge of lattice-based cryptography
  • High motivation + ability to work independently
  • Knowledge of the English language, Git, LaTeX, etc. goes without saying

References

Supervisor