Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IACR Communications in Cryptology

An Efficient Framework for Collusion Resistant Multiparty FHE

Robin Jadoul, Barry Van Leeuwen, Oliver Zajonc

Published Oct 26, 2026• 0 citations
Publisher

Abstract

Multiparty fully homomorphic encryption (MPFHE) is a generalization of (multi-key) fully homomorphic encryption ((MK)FHE) that lives on the cusp between multiparty computation (MPC) and FHE, enabling a computation over encrypted data using multiple keys. However, contrary to MKFHE, it seeks to reduce the noise inflation based on the number of parties by allowing the parties to first compute shared data in MPC before executing the computation in FHE. However, many works use specific constructions, e.g. Chang-Li, Koirala et. al., and Ma et. al., reliant on the behaviour of a particular scheme and do not consider security against colluding servers and parties, e.g. Passelègue-Stehlé, Okada-Takagi, and Mouchet et. al. In this work we present a new framework that is secure against collusion between servers and parties and allows the use of a broad spectrum of MPC and FHE protocols, while eliminating the noise inflation based on the participating number of parties. We then show a case study of this using the FINAL scheme and show that we reduce the required key material by 60–99.9% compared to the MKFHE FINAL scheme, FINALLY, and 65–70% compared to the Park-Rovira scheme in all cases, and by up to 71% compared to the AKÖ scheme when there are 4 or more parties. Moreover, we reduce the bootstrapping time for the AKÖ, Park-Rovira, and KMS schemes by 75–99.7%.

DOI
10.62056/ak86chevtw

Related papers

FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE

Jeongeun Park, Barry Van Leeuwen, Oliver Zajonc

Multi-key fully homomorphic encryption (MKFHE), a generalization of fully homomorphic encryption (FHE), enables a computation over encrypted data under multiple keys. The first MKFHE schemes were based on the NTRU primitive, however these early NTRU based FHE schemes were found to be insecure due to the problem of over-stretched parameters. Recently, in the case of standard (non-multi key) FHE a secure version, called FINAL, of NTRU has been found. In this work we extend FINAL to an MKFHE scheme, this allows us to benefit from some of the performance advantages provided by NTRU based primitives. Thus, our scheme provides competitive performance against current state-of-the-art multi-key TFHE, in particular reducing the computational complexity from quadratic to linear in the number of keys.

IACR Communications in Cryptology•Oct 7, 2024•10 citations

An efficient multi-key BFV fully homomorphic encryption scheme with optimized relinearization

Sai Hu, Ruwei Huang, Liang Zhou

Abstract Traditional fully homomorphic encryption(FHE) schemes allow computation only on data encrypted under the same public key. Multi-Key Fully Homomorphic Encryption (MKFHE) enables arbitrary operations on data encrypted with different public keys, allowing all participating users jointly decrypting the final ciphertext. The multi-key BFV FHE scheme inherits BFV’s advantages in ring element encryption and scale invariance. Nonetheless, it also has some disadvantages, such as additional noise generated during the relinearization process, the need for costly transformations during the external product process, and the requirement for a Common Reference String (CRS). In this paper, we investigate the MKFHE scheme for RLWE-based BFV. Firstly, we improve the modulus size of the evaluation key and the public key to construct a modulus enchancement relinearization method, which can significantly reduce the noise generated during the relinearization process. Secondly, we propose to use an inner product via Gadget decomposition in the relinearization based on the MK-BFV scheme instead of the original outer product operation, which can reduce the complexity of the NTT operation to $$\left( {d + 2\tilde{d}} \right)r^{\prime } /\left( {d + 2} \right)\tilde{l}$$ d + 2 d ~ r ′ / d + 2 l ~ of the original one. Finally, we propose a MK-BFV without CRS on the basis of the previous ones, which enhances the user's control over his own key.

Cybersecurity•Jun 26, 2025•3 citations

Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE.

Gilad Asharov, Abhishek Jain, Daniel Wichs

Abstract. Fully homomorphic encryption (FHE) enables secure computation over the encrypted data of a single party. We explore how to extend this to multiple parties, using threshold fully homomorphic encryption (TFHE). In such scheme, the parties jointly generate a common FHE public key along with a secret key that is shared among them; they can later cooperatively decrypt ciphertexts without learning anything but the plaintext. We show how to instantiate this approach efficiently, by extending the recent FHE schemes of Brakerski, Gentry and Vaikuntanathan (CRYPTO ’11, FOCS ’11, ITCS ’12) based on the (ring) learning with errors assumption. Our main tool is to exploit the property that such schemes are additively homomorphic over their keys. Using TFHE, we construct simple multiparty computation protocols secure against fully malicious attackers, tolerating any number of corruptions, and providing security in the universal composability framework. Our protocols have the following properties: Low interaction: 3 rounds of interaction given a common random string, or 2 rounds with a public-key infrastructure. Low communication: independent of the function being computed (proportional to just input and output sizes). Cloud-assisted computation: the bulk of the computation can be efficiently outsourced to an external entity (e.g. a cloud service) so that the computation of all other parties is independent of the complexity of the evaluated function. 1

•Jan 1, 2011•8 citations

Practical and Efficient MPC from FHE, without ZKPoKs

Kelong Cong, Nigel Paul Smart, Titouan Tanguy +1 more

Fully Homomorphic Encryption (FHE) enables one to implement low-round and low-communication complexity Multi-Party Computation (MPC) which is secure in the static malicious corruption model. By expanding on an idea presented in the full version of the FHE-based MPC protocol of Smart (IMA, 2023), we show how to completely remove the need for Zero-Knowledge Proofs-of-Knowledge in that protocol. This simplification makes the final security proof of the MPC protocol much simpler, and more modular. The new protocol makes use of an FHE scheme with an encrypted PRF functionality, and in addition to our main result we formalize the security of such encrypted PRFs and prove the construction of Deo et al. (CCS 2025) secure in this model.

IACR Communications in Cryptology•Oct 26, 2026•0 citations

Towards Round-Optimal Secure Multiparty Computations: Multikey FHE Without a CRS

Eunkyung Kim, Hyang-Sook Lee, Jeongeun Park

Multikey fully homomorphic encryption (MFHE) allows homomorphic operations between ciphertexts encrypted under different keys. In applications for secure multiparty computation (MPC) protocols, MFHE can be more advantageous than usual fully homomorphic encryption (FHE) since users do not need to agree with a common public key before the computation when using MFHE. In EUROCRYPT 2016, Mukherjee and Wichs constructed a secure MPC protocol in only two rounds via MFHE which deals with a common random/reference string (CRS) in key generation. After then, Brakerski et al. replaced the role of CRS with the distributed setup for CRS calculation to form a four round secure MPC protocol. Thus, recent improvements in round complexity of MPC protocols have been made using MFHE. In this paper, we go further to obtain round-efficient and secure MPC protocols. The underlying MFHE schemes in previous works still involve the common value, CRS, it seems to weaken the power of using MFHE to allow users to independently generate their own keys. Therefore, we resolve the issue by constructing an MFHE scheme without CRS based on LWE assumption, and then we obtain a secure MPC protocol against semi-malicious security in three rounds. We also define a new security notion “multikey-CPA security” to prove that a multikey ciphertext cannot be decrypted unless all the secret keys are gathered and our scheme is multikey-CPA secure.

International Journal of Foundations of Computer Science•Feb 1, 2020•13 citations

New Models for Multi-party Computation

Wutichai Chongchitmate

Secure multi-party computation (MPC) is one of the most important primitives in cryptography. Several directions to construct and improve MPC protocols have been studied over the past decades. The majority of existing MPC protocols rely on assumptions such as every party communicates with every other party or every party needs to know every other party and the computation algorithm well in advance. Such assumptions can be difficult to achieve in modern large scale networks. This thesis explores two distinct lines of work leading to new practical models in response to these scenarios.First, we examine communication locality, the total number of other parties that each party communicates with in the protocol, as a new measure for an MPC protocol. Although progress has been made, the question of achieving low communication locality and round complexity at the same time for adaptive adversaries corrupting t < n/2 parties remains open. We show that by assuming a public-key infrastructure (PKI) and a symmetric-key infrastructure (SKI) the above question can be answered affirmatively, under standard assumptions. In particular, we describe a protocol with polylogarithmic communication locality and round complexity which tolerates up to t < n/2 adaptive corruptions. Our results are based on a new model of hidden random graphs obtained from the SKI, and using them to emulate a complete network in polylogarithmic rounds and polylogarithmic locality.We then examine multi-key fully homomorphic encryption (MFHE) schemes, which allow computation on data encrypted under different public keys chosen independently of each other. One of the main problems left in MFHE has been on how to deal with malicious users without trusted setup assumptions. We show how this can be done through circuit privacy, which guarantees that even if both ciphertexts and public keys are not well-formed, no information is revealed regarding the computation, other than what follows from the output on some well-formed inputs. Generalizing the result for circuit-private FHE, we provide a framework for adding circuit privacy to existing MFHE schemes.Finally, we incorporate the circuit privacy in a variant of server-assisted MPC, called on-the-fly MPC, where a server or a “cloud” performs an arbitrary dynamically chosen computation on a subset of data uploaded by multiple clients and encrypted under different keys on-the-fly. Circuit privacy allows the server to keep the algorithm used in the computation private even from a malicious adversary corrupting any number of clients. In particular, we construct a three-round on-the-fly MPC protocol with circuit privacy against malicious clients without the trusted setup.

•Jan 1, 2016•0 citations
Multiparty fully homomorphic encryption (MPFHE) is a generalization of (multi-key) fully homomorphic encryption ((MK)FHE) that lives on the cusp between multiparty computation (MPC) and FHE, enabling a computation over encrypted data using multiple keys. However, contrary to MKFHE, it seeks to reduce the noise inflation based on the number of parties by allowing the parties to first compute shared data in MPC before executing the computation in FHE. However, many works use specific constructions, e.g. Chang-Li, Koirala et. al., and Ma et. al., reliant on the behaviour of a particular scheme and do not consider security against colluding servers and parties, e.g. Passelègue-Stehlé, Okada-Takagi, and Mouchet et. al. In this work we present a new framework that is secure against collusion between servers and parties and allows the use of a broad spectrum of MPC and FHE protocols, while eliminating the noise inflation based on the participating number of parties. We then show a case study of this using the FINAL scheme and show that we reduce the required key material by 60–99.9% compared to the MKFHE FINAL scheme, FINALLY, and 65–70% compared to the Park-Rovira scheme in all cases, and by up to 71% compared to the AKÖ scheme when there are 4 or more parties. Moreover, we reduce the bootstrapping time for the AKÖ, Park-Rovira, and KMS schemes by 75–99.7%.
Multi-key fully homomorphic encryption (MKFHE), a generalization of fully homomorphic encryption (FHE), enables a computation over encrypted data under multiple keys. The first MKFHE schemes were based on the NTRU primitive, however these early NTRU based FHE schemes were found to be insecure due to the problem of over-stretched parameters. Recently, in the case of standard (non-multi key) FHE a secure version, called FINAL, of NTRU has been found. In this work we extend FINAL to an MKFHE scheme, this allows us to benefit from some of the performance advantages provided by NTRU based primitives. Thus, our scheme provides competitive performance against current state-of-the-art multi-key TFHE, in particular reducing the computational complexity from quadratic to linear in the number of keys.
Abstract Traditional fully homomorphic encryption(FHE) schemes allow computation only on data encrypted under the same public key. Multi-Key Fully Homomorphic Encryption (MKFHE) enables arbitrary operations on data encrypted with different public keys, allowing all participating users jointly decrypting the final ciphertext. The multi-key BFV FHE scheme inherits BFV’s advantages in ring element encryption and scale invariance. Nonetheless, it also has some disadvantages, such as additional noise generated during the relinearization process, the need for costly transformations during the external product process, and the requirement for a Common Reference String (CRS). In this paper, we investigate the MKFHE scheme for RLWE-based BFV. Firstly, we improve the modulus size of the evaluation key and the public key to construct a modulus enchancement relinearization method, which can significantly reduce the noise generated during the relinearization process. Secondly, we propose to use an inner product via Gadget decomposition in the relinearization based on the MK-BFV scheme instead of the original outer product operation, which can reduce the complexity of the NTT operation to (d+2d~)r′/(d+2)l~\left( {d + 2\tilde{d}} \right)r^{\prime } /\left( {d + 2} \right)\tilde{l}(d+2d~)r′/(d+2)l~ d + 2 d ~ r ′ / d + 2 l ~ of the original one. Finally, we propose a MK-BFV without CRS on the basis of the previous ones, which enhances the user's control over his own key.
Abstract. Fully homomorphic encryption (FHE) enables secure computation over the encrypted data of a single party. We explore how to extend this to multiple parties, using threshold fully homomorphic encryption (TFHE). In such scheme, the parties jointly generate a common FHE public key along with a secret key that is shared among them; they can later cooperatively decrypt ciphertexts without learning anything but the plaintext. We show how to instantiate this approach efficiently, by extending the recent FHE schemes of Brakerski, Gentry and Vaikuntanathan (CRYPTO ’11, FOCS ’11, ITCS ’12) based on the (ring) learning with errors assumption. Our main tool is to exploit the property that such schemes are additively homomorphic over their keys. Using TFHE, we construct simple multiparty computation protocols secure against fully malicious attackers, tolerating any number of corruptions, and providing security in the universal composability framework. Our protocols have the following properties: Low interaction: 3 rounds of interaction given a common random string, or 2 rounds with a public-key infrastructure. Low communication: independent of the function being computed (proportional to just input and output sizes). Cloud-assisted computation: the bulk of the computation can be efficiently outsourced to an external entity (e.g. a cloud service) so that the computation of all other parties is independent of the complexity of the evaluated function. 1
Fully Homomorphic Encryption (FHE) enables one to implement low-round and low-communication complexity Multi-Party Computation (MPC) which is secure in the static malicious corruption model. By expanding on an idea presented in the full version of the FHE-based MPC protocol of Smart (IMA, 2023), we show how to completely remove the need for Zero-Knowledge Proofs-of-Knowledge in that protocol. This simplification makes the final security proof of the MPC protocol much simpler, and more modular. The new protocol makes use of an FHE scheme with an encrypted PRF functionality, and in addition to our main result we formalize the security of such encrypted PRFs and prove the construction of Deo et al. (CCS 2025) secure in this model.
Multikey fully homomorphic encryption (MFHE) allows homomorphic operations between ciphertexts encrypted under different keys. In applications for secure multiparty computation (MPC) protocols, MFHE can be more advantageous than usual fully homomorphic encryption (FHE) since users do not need to agree with a common public key before the computation when using MFHE. In EUROCRYPT 2016, Mukherjee and Wichs constructed a secure MPC protocol in only two rounds via MFHE which deals with a common random/reference string (CRS) in key generation. After then, Brakerski et al. replaced the role of CRS with the distributed setup for CRS calculation to form a four round secure MPC protocol. Thus, recent improvements in round complexity of MPC protocols have been made using MFHE. In this paper, we go further to obtain round-efficient and secure MPC protocols. The underlying MFHE schemes in previous works still involve the common value, CRS, it seems to weaken the power of using MFHE to allow users to independently generate their own keys. Therefore, we resolve the issue by constructing an MFHE scheme without CRS based on LWE assumption, and then we obtain a secure MPC protocol against semi-malicious security in three rounds. We also define a new security notion “multikey-CPA security” to prove that a multikey ciphertext cannot be decrypted unless all the secret keys are gathered and our scheme is multikey-CPA secure.
Secure multi-party computation (MPC) is one of the most important primitives in cryptography. Several directions to construct and improve MPC protocols have been studied over the past decades. The majority of existing MPC protocols rely on assumptions such as every party communicates with every other party or every party needs to know every other party and the computation algorithm well in advance. Such assumptions can be difficult to achieve in modern large scale networks. This thesis explores two distinct lines of work leading to new practical models in response to these scenarios.First, we examine communication locality, the total number of other parties that each party communicates with in the protocol, as a new measure for an MPC protocol. Although progress has been made, the question of achieving low communication locality and round complexity at the same time for adaptive adversaries corrupting t < n/2 parties remains open. We show that by assuming a public-key infrastructure (PKI) and a symmetric-key infrastructure (SKI) the above question can be answered affirmatively, under standard assumptions. In particular, we describe a protocol with polylogarithmic communication locality and round complexity which tolerates up to t < n/2 adaptive corruptions. Our results are based on a new model of hidden random graphs obtained from the SKI, and using them to emulate a complete network in polylogarithmic rounds and polylogarithmic locality.We then examine multi-key fully homomorphic encryption (MFHE) schemes, which allow computation on data encrypted under different public keys chosen independently of each other. One of the main problems left in MFHE has been on how to deal with malicious users without trusted setup assumptions. We show how this can be done through circuit privacy, which guarantees that even if both ciphertexts and public keys are not well-formed, no information is revealed regarding the computation, other than what follows from the output on some well-formed inputs. Generalizing the result for circuit-private FHE, we provide a framework for adding circuit privacy to existing MFHE schemes.Finally, we incorporate the circuit privacy in a variant of server-assisted MPC, called on-the-fly MPC, where a server or a “cloud” performs an arbitrary dynamically chosen computation on a subset of data uploaded by multiple clients and encrypted under different keys on-the-fly. Circuit privacy allows the server to keep the algorithm used in the computation private even from a malicious adversary corrupting any number of clients. In particular, we construct a three-round on-the-fly MPC protocol with circuit privacy against malicious clients without the trusted setup.