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

Cybersecurity

Dynamic multi-key FHE without CRS from LWE

Junjie Wang, Ruwei Huang, Xiaolong Tang

Published Feb 18, 2026• 0 citations
Publisher

Abstract

Abstract In dynamic multi-key Fully Homomorphic Encryption (MFHE) scheme, homomorphic operations on ciphertexts encrypted under different keys are allowed. Moreover, the resulting ciphertext can be further computed with ciphertexts under other keys. In 2016, Peikert and Shiehian presented a dynamic MFHE scheme that relies on using a Common Reference String (CRS) and circular security assumptions. Subsequently, various variants of dynamic MFHE schemes were proposed based on this scheme, but these variant schemes still rely on a CRS and circular security assumption. Therefore, constructing a MFHE GSW scheme relies solely on the LWE assumption and does not require a CRS remains a valuable challenge. This paper introduces a new dynamic MFHE scheme. Compared to existing solutions, our scheme does not require the circular security assumption and depends solely on the LWE assumption, which theoretically provides an enhanced level of security. Additionally, it eliminates the need for a shared CRS but instead replaces the CRS with each party independently generate random matrices. This decentralized approach enhances the ability of users to generate keys independently. The size of ciphertexts and public keys in our scheme is comparable to other existing solutions, thus maintaining efficiency in both computation and ciphertext extension.

DOI
10.1186/s42400-025-00431-z

Related papers

Multi-key Fully Homomorphic Encryption without CRS from RLWE

Fucai Luo, Haiyan Wang, Saif M. Al-Kuwari +1 more

Fully Homomorphic Encryption (FHE) is a powerful encryption system in cloud computing that allows homomorphic computations on encrypted data without decrypting them. Multi-key fully homomorphic encryption (MFHE), as an extension to FHE, allows homomorphic computations on ciphertexts encrypted under different keys. However, most MFHE schemes require a Common Random/Reference String (CRS), while the few that do not are based on the Learning With Errors (LWE) problem, which means that they can only deal with single bit plaintext. Consequently, MFHE schemes based on the Ring Learning With Errors (RLWE) problem are more desirable, as they can handle polynomial plaintext. Requiring the CRS seems to weaken the semantic definition of MFHE, where all users generate their own keys independently. In this paper, we study the RLWE-based MFHE in the CRS model and propose the first RLWE-based MFHE without a CRS. To this end, we remove the CRS by designing a relinearization algorithm without a CRS. Like previous MFHE schemes, our RLWE-based MFHE without CRS has a simple 1-round threshold decryption, which implies a 3-round secure MPC protocol in the plain model from the RLWE assumption.

Computer Standards & Interfaces•Mar 24, 2023•9 citations

A secure multi-party computation protocol without CRS supporting multi-bit encryption

Zong-Wu Zhu, Ruwei Huang

To solve the problems in the existing fully homomorphic encryption (FHE)-based secure multi-party computation (SMC) protocols such as low efficiency, the FHE scheme that supports multi-bit encryption was modified during the generation of the public key so that the users could generate their public keys independently without the common random string (CRS) matrix. Further, a multi-bit Gentry-Sahai-Waters scheme (MGSW) scheme without CRS was constructed. The modified LinkAlgo algorithm was adopted to expand the single-key ciphertext into the multi-key ciphertext and simplify the way of generating the expanded ciphertext. In this way, a multi-key FHE (MFHE) scheme was achieved based on the MGSW scheme. Finally, a three-round SMC protocol without CRS was constructed using the MFHE scheme and the decisional learning with errors (DLWE) assumption, which was secure in the semi-malicious model. Compared to the existing protocols, the protocol proposed herein can support multi-bit encryption and is found with smaller ciphertext size and lower storage overhead and generate the expanded ciphertext in a simpler way. Overall performance is better than existing protocols.

PLoS ONE•Mar 18, 2022•3 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

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

Efficient SMC Protocol Based on Multi-Bit Fully Homomorphic Encryption

Zong-Wu Zhu, Ruwei Huang

Aiming at the problems of large ciphertext size and low efficiency in the current secure multi-party computation (SMC) protocol based on fully homomorphic encryption (FHE), the paper proves that the fully homomorphic encryption scheme that supports multi-bit encryption proposed by Chen Li et al. satisfies the key homomorphism. Based on this scheme and threshold decryption, a three-round, interactive, leveled, secure multi-party computation protocol under the Common Random String (CRS) model is designed. The protocol is proved to be safe under the semi-honest model and the semi-malicious model. From the non-interactive zero-knowledge proof, it can be concluded that the protocol is also safe under the malicious model. Its security can be attributed to the Decisional Learning With Errors (DLWE) and a variant of this problem (some-are-errorless LWE). Compared with the existing secure multi-party computation protocol based on fully homomorphic encryption under the CRS model, the ciphertext size of this protocol is smaller, the efficiency is higher, the storage overhead is smaller, and the overall performance is better than the existing protocol.

Applied Sciences•Nov 3, 2021•5 citations

Efficient Dynamic Multi-key FHE Scheme from LWE for Untrusted Cloud Environments

Shuchang Zeng, Ching-Fang Hsu, Jianqun Cui +2 more

Fully Homomorphic Encryption (FHE) provides a good solution to directly operate on the ciphertext, and the decryption result is equivalent to the corresponding operation on the plaintext. As a technique suitable for distributed environments, multi-key Fully Homomorphic Encryption (MKFHE) scheme is the most common variant of the FHE scheme since it allows encrypted data to be computed under different keys. Unfortunately, the existing dynamic MKFHE schemes based on learning with errors (LWE) still suffer from the inefficiency of long public keys, which typically grow cube in size along the lattice dimension. Moreover, there current constructions fail to provide reliable and fast algorithms to simultaneously expand ciphertexts with multiple additional keys. In order to solve the above problems, a new faster dynamic MKFHE scheme with shorter public key in asymmetric key setting from LWE is proposed in this paper, in which the size of the public key is further reduced from $\tilde O\left( {{n^3}{{(K + L)}^2}} \right)$ to $\tilde O\left( {{n^2}{{(K + L)}^2}} \right)$. In addition, our scheme cleverly adopts the dual-user cooperation method in distributed system to realize the ciphertext expansion locally, thereby reducing the computing overhead of the cloud server. More interestingly, we design a flexible parallel ciphertext expansion algorithm for the first time based on the basic algorithm. This algorithm realizes the ciphertext expansion when multiple keys are added at the same time, thus significantly improving the computational efficiency of ciphertext expansion in the dynamic MKFHE scheme. Finally, the CPA-secure of our scheme based on standard LWE assumptions is proven.

IEEE International Conference on Parallel and Distributed Systems (ICPADS)•Dec 17, 2023•1 citation
Abstract In dynamic multi-key Fully Homomorphic Encryption (MFHE) scheme, homomorphic operations on ciphertexts encrypted under different keys are allowed. Moreover, the resulting ciphertext can be further computed with ciphertexts under other keys. In 2016, Peikert and Shiehian presented a dynamic MFHE scheme that relies on using a Common Reference String (CRS) and circular security assumptions. Subsequently, various variants of dynamic MFHE schemes were proposed based on this scheme, but these variant schemes still rely on a CRS and circular security assumption. Therefore, constructing a MFHE GSW scheme relies solely on the LWE assumption and does not require a CRS remains a valuable challenge. This paper introduces a new dynamic MFHE scheme. Compared to existing solutions, our scheme does not require the circular security assumption and depends solely on the LWE assumption, which theoretically provides an enhanced level of security. Additionally, it eliminates the need for a shared CRS but instead replaces the CRS with each party independently generate random matrices. This decentralized approach enhances the ability of users to generate keys independently. The size of ciphertexts and public keys in our scheme is comparable to other existing solutions, thus maintaining efficiency in both computation and ciphertext extension.
Fully Homomorphic Encryption (FHE) is a powerful encryption system in cloud computing that allows homomorphic computations on encrypted data without decrypting them. Multi-key fully homomorphic encryption (MFHE), as an extension to FHE, allows homomorphic computations on ciphertexts encrypted under different keys. However, most MFHE schemes require a Common Random/Reference String (CRS), while the few that do not are based on the Learning With Errors (LWE) problem, which means that they can only deal with single bit plaintext. Consequently, MFHE schemes based on the Ring Learning With Errors (RLWE) problem are more desirable, as they can handle polynomial plaintext. Requiring the CRS seems to weaken the semantic definition of MFHE, where all users generate their own keys independently. In this paper, we study the RLWE-based MFHE in the CRS model and propose the first RLWE-based MFHE without a CRS. To this end, we remove the CRS by designing a relinearization algorithm without a CRS. Like previous MFHE schemes, our RLWE-based MFHE without CRS has a simple 1-round threshold decryption, which implies a 3-round secure MPC protocol in the plain model from the RLWE assumption.
To solve the problems in the existing fully homomorphic encryption (FHE)-based secure multi-party computation (SMC) protocols such as low efficiency, the FHE scheme that supports multi-bit encryption was modified during the generation of the public key so that the users could generate their public keys independently without the common random string (CRS) matrix. Further, a multi-bit Gentry-Sahai-Waters scheme (MGSW) scheme without CRS was constructed. The modified LinkAlgo algorithm was adopted to expand the single-key ciphertext into the multi-key ciphertext and simplify the way of generating the expanded ciphertext. In this way, a multi-key FHE (MFHE) scheme was achieved based on the MGSW scheme. Finally, a three-round SMC protocol without CRS was constructed using the MFHE scheme and the decisional learning with errors (DLWE) assumption, which was secure in the semi-malicious model. Compared to the existing protocols, the protocol proposed herein can support multi-bit encryption and is found with smaller ciphertext size and lower storage overhead and generate the expanded ciphertext in a simpler way. Overall performance is better than existing protocols.
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.
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.
Aiming at the problems of large ciphertext size and low efficiency in the current secure multi-party computation (SMC) protocol based on fully homomorphic encryption (FHE), the paper proves that the fully homomorphic encryption scheme that supports multi-bit encryption proposed by Chen Li et al. satisfies the key homomorphism. Based on this scheme and threshold decryption, a three-round, interactive, leveled, secure multi-party computation protocol under the Common Random String (CRS) model is designed. The protocol is proved to be safe under the semi-honest model and the semi-malicious model. From the non-interactive zero-knowledge proof, it can be concluded that the protocol is also safe under the malicious model. Its security can be attributed to the Decisional Learning With Errors (DLWE) and a variant of this problem (some-are-errorless LWE). Compared with the existing secure multi-party computation protocol based on fully homomorphic encryption under the CRS model, the ciphertext size of this protocol is smaller, the efficiency is higher, the storage overhead is smaller, and the overall performance is better than the existing protocol.
Fully Homomorphic Encryption (FHE) provides a good solution to directly operate on the ciphertext, and the decryption result is equivalent to the corresponding operation on the plaintext. As a technique suitable for distributed environments, multi-key Fully Homomorphic Encryption (MKFHE) scheme is the most common variant of the FHE scheme since it allows encrypted data to be computed under different keys. Unfortunately, the existing dynamic MKFHE schemes based on learning with errors (LWE) still suffer from the inefficiency of long public keys, which typically grow cube in size along the lattice dimension. Moreover, there current constructions fail to provide reliable and fast algorithms to simultaneously expand ciphertexts with multiple additional keys. In order to solve the above problems, a new faster dynamic MKFHE scheme with shorter public key in asymmetric key setting from LWE is proposed in this paper, in which the size of the public key is further reduced from O~(n3(K+L)2)\tilde O\left( {{n^3}{{(K + L)}^2}} \right)O~(n3(K+L)2) to O~(n2(K+L)2)\tilde O\left( {{n^2}{{(K + L)}^2}} \right)O~(n2(K+L)2). In addition, our scheme cleverly adopts the dual-user cooperation method in distributed system to realize the ciphertext expansion locally, thereby reducing the computing overhead of the cloud server. More interestingly, we design a flexible parallel ciphertext expansion algorithm for the first time based on the basic algorithm. This algorithm realizes the ciphertext expansion when multiple keys are added at the same time, thus significantly improving the computational efficiency of ciphertext expansion in the dynamic MKFHE scheme. Finally, the CPA-secure of our scheme based on standard LWE assumptions is proven.