FAST PARALLELIZABLE MULTI-KEY FULLY HOMOMORPHIC ENCRYPTION BASED ON NTRU

TECHNICAL FIELD

[0001]The present disclosure relates to the field of homomorphic encryption, particularly to a multi-key fully homomorphic encryption (MK-FHE) scheme. The disclosure provides a system and method for secure multi-party computation with parallelizable bootstrapping mechanisms. This enables efficient processing of encrypted data under multiple independent keys while reducing computational and hardware resource requirements.

BACKGROUND

[0002]Fully Homomorphic Encryption (FHE) allows computations on encrypted data without decryption, enabling privacy-preserving applications such as cloud computing, federated learning, and secure artificial intelligence (AI) inference. Traditional FHE schemes assume a single public key for encryption, which limits their applicability in multi-party scenarios where participants use independent keys. Two approaches address this limitation: Threshold FHE and Multi-Key FHE (MK-FHE). Threshold FHE uses a shared public key with distributed secret keys but is restricted to static participant sets, lacking flexibility. MK-FHE, conversely, allows each participant to generate independent key pairs, supporting dynamic participation and joint evaluation of ciphertexts under different keys.

[0003]Prior MK-FHE schemes, such as those by López-Alt et al., demonstrated feasibility but were limited by static keys and bounded participant counts. Later advancements, like those by Peikert and Shiehian, introduced dynamic key support but incurred high computational overhead. NTRU-based MK-FHE schemes, valued for compact ciphertexts, faced vulnerabilities like sublattice attacks, necessitating large moduli that increased resource demands. Recent TFHE-based MK-FHE schemes improved efficiency but relied on large bootstrapping keys, making them impractical for resource-constrained environments, such as edge devices or low-power servers.

[0004]Existing MK-FHE frameworks struggle with inefficient bootstrapping for multi-key ciphertexts, failing to balance security (e.g., avoiding overstretched parameters) and performance. Bootstrapping, a critical process for refreshing ciphertexts to manage noise growth, is computationally intensive in multi-key settings, often requiring significant memory and processing power. These limitations hinder scalability and deployment in real-world applications, particularly those involving dynamic participant sets or constrained hardware.

[0005]There remains an unmet need for an MK-FHE scheme that supports dynamic key inclusion, provides efficient parallelizable bootstrapping, and maintains robust security under standard cryptographic assumptions while minimizing hardware requirements.

SUMMARY

[0006]The present disclosure addresses these challenges by providing a novel MK-FHE scheme based on NTRU, incorporating parallelizable bootstrapping and hybrid ciphertext merging. The present disclosure provides the following schemes.

[0014]Preferably, the step of generating a unified set of public parameters defining operational moduli and dimensions for LWE, RLWE, and NTRU comprises specifying an integer modulus q for LWE operations and a polynomial ring modulus Q for RLWE and NTRU operations; specifying a vector dimension n for LWE secrets and a polynomial ring dimension N for RLWE/NTRU secrets; and specifying noise distributions, gadget decomposition bases, and error bounds for all three encryption schemes.

[0015]Preferably, the secret key pair comprises an LWE secret vector

$s_i\in {\mathbb{Z}}_q^n$

and an

[0016]RLWE secret key z_i ∈ R_Q; the hybrid product key is generated by sampling random elements r_i←χ_σβ and noise vector

$e_{i,0}\leftarrow {𝒳}_{{\sigma }_{\beta }}^{d_{\mathrm{hp}}},$

computing

$d_{i,0}=r_i·a+f_i·𝔤+e_{i,0}\in R_Q^{d_{\mathrm{hp}}},$

computing

$d_{i,2}=-z_i·d_{i,1}+r_i·𝔤+e_{i,1}\in R_Q^{d_{\mathrm{hp}}},$

and outputting a product key pair (d_i,1, d_i,2), a ciphertext merging key set is NKSK={nksk_i}_{0≤i≤d−1}, where

${\mathrm{nksk}}_i={\mathrm{NTRU}}_{f,Q}^{\prime }\left(B^i\right).$

[0017]Preferably, the step of transforming plaintext data into an initial encrypted form under a participant's secret key comprises sampling a random vector

$a_i\leftarrow {\mathbb{Z}}_q^n$

and noise term e from a distribution χ_σ, computing a ciphertext component

$b=-\langle a_i,s_i\rangle +\frac{q}{4}m+e,$

and outputting the ciphertext as a pair

$\left(b,a_i\right)\in {\mathbb{Z}}_q\times {\mathbb{Z}}_q^n,$

wherein s_i is the participant's LWE secret key.

[0018]Preferably, aggregating participant-specific ciphertexts from a plurality of participants by: receiving single-party LWE ciphertexts

$c_j=\left(b_j,a_j\right)\in {\mathbb{Z}}_q^{n+1}$

for 1≤j≤k, where each c_j is encrypted under a distinct participant's secret key; computing a joint offset term

$b_{\mathrm{sum}}={\sum }_{j=1}^k{b}_j\in {\mathbb{Z}}_q,$

concatenating ciphertext vectors to form

$a_{\mathrm{joint}}=\left(a_1,\dots ,a_k\right)\in {\mathbb{Z}}_q^{\mathrm{kn}};$

outputting a composite ciphertext

$\stackrel{\_}{\mathrm{ct}}=\left(b_{\mathrm{sum}},a_{\mathrm{joint}}\right)\in {\mathbb{Z}}_q^{\mathrm{kn}+1};$

wherein the composite ciphertext is operable under a combination of all participants' secret keys for homomorphic evaluation or decryption.

[0019]Preferably, the noise-refreshing procedure during homomorphic evaluation comprises: computing decomposed components for each index j from 0 to d−1:v_j=c⊙nksk_j, constructing a gadget vector v=(v₀, v₁, . . . , v_d−1), computing

$c_j^{\prime }={𝔤}^{-1}\left(c_j\right)·v\mathrm{mod}Q$

and forming intermediate ciphertext

$\hat{c}=\left(c_0^{\prime },c_1^{\prime },\dots ,c_k^{\prime }\right),$

applying HybridProduct to ê using public keys {b_j}_j∈[k].

[0020]Preferably, recovering the evaluated plaintext comprises: computing an inner product between the updated composite ciphertext

$\stackrel{\_}{\mathrm{ct}}=\left({\sum }_{j=1}^k{b}_j,a_1,\dots ,a_k\right)\in {\mathbb{Z}}_q^{\mathrm{kn}+1}$

and the aggregated secret key vector (1, s), where s=(s₁, . . . s_k) is the concatenation of all participants' secret keys, scaling and discretizing the result to recover a plaintext bit

$m=\lfloor \frac{2}{q}\left(\langle \overline{\mathrm{ct}},\left(1,\overline{s}\right)\rangle \right)\rceil \in \left\{0,1\right\}.$

[0021]Preferably, the noise-refreshing procedure comprises: initializing an accumulator ACC, executing blind rotation BREval in a Fourier domain, and merging ciphertexts via HybridProduct with noise variance bounded by: σ²≤k·d_hp·N²·V_hp·σ_β², where k denotes the number of participants, d_hp denotes gadget decomposition dimension, N denotes ring dimension of RLWE/NTRU (R_Q=Z_Q[X]/(X^N+1)), V_hp denotes variance bound of gadget base B, σ_β² denotes variance of RLWE noise distribution.

[0022]Preferably, the blind rotation algorithm BREval comprises: scaling coefficients

$a_i^{\prime }=\frac{2N}{q}{a}_i,$

initializing ACC=X^a0⊙evk₀, iteratively updating

$\mathrm{ACC}\odot \left[g+\left(X^{a_i^{\prime }}-1\right)·{\mathrm{evk}}_i\right]$

for 1≤i≤n−1.

[0023]Preferably, the noise-refreshing procedure executes in quasi-linear time relative to the number of parties k.

[0024]Preferably, the noise-refreshing procedure further comprises a ModSwitch operation comprising: receiving a multi-key LWE ciphertext

$c=\left(c_0,\dots ,c_{\mathrm{kn}}\right)\in {\mathbb{Z}}_Q^{\mathrm{kn}+1},$

applying randomized rounding to each component: [x]_q:Q=└qx/Q┘+B, and outputting a refreshed ciphertext

$c^{\prime }={\left({\left[c_i\right]}_{q:Q}\right)}_{0\le i\le \mathrm{kn}}\in {\mathbb{Z}}_q^{\mathrm{kn}+1}.$

[0025]Preferably, the noise-refreshing procedure further comprises a KeySwitch operation comprising: receiving a multi-key LWE ciphertext

$\stackrel{\_}{\mathrm{ct}}=\left(b,a_1,\dots ,a_k\right)\in {\mathbb{Z}}_q^{\mathrm{kn}+1},$

for each participant j, 1≤j≤k, computing

$\left(b_j^{\prime },a_j^{\prime }\right)={\sum }_{i=0}^{N-1}{𝔤}^{-1}\left(a_{i,j}\right)·{\mathrm{lsks}}_j,$

then outputting a transformed ciphertext

$\stackrel{\_}{{\mathrm{ct}}^{\prime }}=\left(b+{\sum }_{i=1}^k{b}_i^{\prime },a_1^{\prime },\dots ,a_k^{\prime }\right).$

[0029]Preferably, each participant node executes the noise-refreshing procedure by: performing tensor product-based multiplication with decomposition and vector assembly to bound error growth.

[0030]Preferably, the central node distributes parameters defining a noise distribution χ and gadget base B.

[0031]Preferably, each participant node performs the tensor product-based multiplication by constructing a vector v=(v₀, . . . , v_ {d−1}) via linear combinations of decomposed ciphertext components.

[0032]According to another aspect of the present disclosure, a non-transitory computer-readable storage medium storing instructions, when executed by one or more processors, cause the processors to perform the methods described above.

[0039]The present disclosure has the following technical advantages. The disclosure leverages gadget decomposition and NTRU-based encryption to minimize noise growth during computations. The parallelizable bootstrapping algorithm reduces time complexity to quasi-linear in the number of parties, enabling faster processing compared to prior MK-FHE schemes that scale poorly with participant count. By optimizing ciphertext sizes through NTRU's compact structure and minimizing bootstrapping key sizes via blind rotation in the Fourier domain, the disclosure reduces memory and processing demands. This enables deployment on resource-constrained devices, such as edge devices or low-power servers, without sacrificing security. The scheme supports on-the-fly key addition, allowing new parties to join computations without reconfiguring the system, enhancing flexibility for applications like federated learning. Built on standard cryptographic assumptions (e.g., decisional KDM-form NTRU problem), the scheme avoids vulnerabilities like sublattice attacks by using carefully selected parameters, ensuring security without requiring oversized moduli.

BRIEF DESCRIPTION OF THE DRAWINGS

[0040]FIG. 1 is a flowchart of the overall MK-FHE (Multi-Key Fully Homomorphic Encryption) process according to an embodiment of the present disclosure. It starts with the setup phase (MKHE.Setup) that calls sub-procedures for LWE, RLWE, and NTRU setup to generate public parameters. Then, it proceeds to key generation (MKHE.KeyGen) where LWE and RLWE secret keys are sampled, product keys and keyswitching keys are generated, and the keys are published. The encryption step (MKHE.Enc) samples random parameters and outputs an LWE ciphertext. The expansion step (MKHE.Expand) converts the LWE ciphertext to a multi-key ciphertext (MK-LWE). The NAND gate evaluation (MKHE.NAND) takes two MK-LWE ciphertexts, evaluates the NAND gate, and refreshes the result via multi-key bootstrapping. Finally, the decryption step (MKHE.Dec) uses the MK-LWE ciphertext and the secret key to compute the plaintext.

[0041]FIG. 2 illustrates a process involving multiple BREval (Blind Rotation Evaluation) operations and a subsequent merge. Each BREval block (two are shown, indexed 1 and k) processes a sequence of operations (brk_1,0 to brk_1.n−1 and brk_k,0 to brk_k,n−1) and produces an output (ACC′₁ and ACC′_k). These outputs are then merged (Merge) into an accumulator (ACC), which is then processed to form an MK-RLWE ciphertext and finally transformed into an MK-LWE ciphertext.

[0042]FIG. 3 shows the detailed steps of the NAND gate operation in a multi-key FHE scheme. Two MK-LWE ciphertexts (each in

${\mathbb{Z}}_Q^{n+1}$

are input to a NAND gate. The output of the NAND is an MK-LWE ciphertext (in

${\mathbb{Z}}_Q^{kn+1}).$

This ciphertext then undergoes accumulator operations (ACC operations) to become an MK-RLWE ciphertext (in

$R_Q^{k+1}).$

The MK-RLWE is then processed by a “Merge+Extract” step to form an MK-LWE ciphertext in

${\mathbb{Z}}_Q^{\mathrm{kN}+1}.$

This is then processed by Key Switch to another MK-LWE ciphertext in

${\mathbb{Z}}_Q^{\mathrm{kn}+1}.$

Finally, Mod Switen is applied to output the last MK-LWE ciphertext in

${\mathbb{Z}}_q^{\mathrm{kn}+1}.$

[0043]FIG. 4 is a schematic diagram of a computing system according to an embodiment of the present disclosure.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0044]The present disclosure enables secure multi-party computation by performing homomorphic operations on encrypted data under multiple independent keys, with a parallelizable noise-refreshing procedure that leverages Fourier transform-based rotation, gadget decomposition, and tensor product-based multiplication. The description details of some embodiments of the method's steps, the system's architecture, and the hardware configuration required for implementation, emphasizing efficiency improvements and suitability for resource-constrained environments.

[0045]The following detailed description, in conjunction with the accompanying drawings, elaborates the MK-FHE scheme based on NTRU, focusing on its technical implementation and improvements over prior art. The scheme integrates cryptographic primitives such as LWE, RLWE, and NTRU-based GSW-like encryption, with a focus on parallelizable bootstrapping to enable efficient multi-party computations. Some embodiments of the detailed algorithms are described below, incorporating specific operational steps, noise management techniques, and references to the illustrative figures.

[0046]A fast parallelizable multi-key fully homomorphic encryption based on NTRU according to some embodiments of the present disclosure is described below. The MK-FHE scheme includes cryptographic primitives, bootstrapping mechanisms, and core algorithms.Setup: Generates public parameters for LWE, RLWE, and NTRU.KeyGen: Each party generates LWE/RLWE/NTRU keys, plus evaluation keys for bootstrapping. Enc: Encrypts a bit into an LWE ciphertext using the party's secret key. Expand: Combines single-party LWE ciphertexts into a multi-key LWE ciphertext. Dec: Decrypts a multi-key ciphertext using all participants secret keys. NAND: Evaluates a NAND gate on two multi-key ciphertexts and refreshes via bootstrapping.

[0047]The server generates public parameters for LWE, RLWE and NTRU, taking the security parameter λ, and returns a public parameter set pp. In particular, generate the parameter pp^LWE=(n, χ, σ_α, B, d, q), generate the parameter pp^RLWE=(N, χ, σ_β, B, d, a, Q), and generate the parameter pp^NTRU=(N, χ, σ_e, B, d, Q). Finally, return the generated public parameters pp^MKHE=(pp^LWE, pp^RLWE, pp^NTRU).

[0048]Each party generates LWE/RLWE/NTRU keys, plus evaluation keys for bootstrapping. Specifically, each party samples an LWE secret key

$s_i=\left(s_{i,0},\dots ,s_{i,n-1}\right)\in {\mathbb{Z}}_q^n,$

a PLWE secret key z_i ∈ R_Q, and a noice vector

$e_i\leftarrow {𝒳}_{{\sigma }_{\beta }}^d$

and compute

$b_i=-a·z_i+e_i\in R_Q^d.$

[0049]Generate the product key for NKSK product MK-RLWE: Firstly, using a RLWE secret key z_j ∈ R_Q and a NTRU secret key f_i ∈R_Q of party i. Sample r_i←ω_σβ and a noise vector

$e_{i,0}\leftarrow {𝒳}_{{\sigma }_{\beta }}^{d_{\mathrm{hp}}},$

output the vector

$d_{i,0}=r_i·a+f_i·𝔤+e_{i,0}\in R_Q^{d_{\mathrm{hp}}}.$

Sample

$d_{i,1}\leftarrow R_Q^{d_{\mathrm{hp}}}$

and a noise vector

$e_{i,1}\leftarrow {𝒳}_{{\sigma }_{\beta }}^{d_{\mathrm{hp}}},$

compute

$d_{i,2}=-z_i·d_{i,1}+r_i·𝔤+e_{i,1}\in R_Q^{d_{\mathrm{hp}}}$

and output(d_i,1,d_i,2).

${\mathrm{nksk}}_i={\mathrm{NTRU}}_{f,Q}^{\prime }\left(B^i\right)$

and return NKSK={nksk_i}_{0≤i≤d−1}.

[0051]The evaluation key for Single-key blind rotation uses a secret key

$s=\left(s_0,\dots ,s_{n-1}\right)\in {\mathbb{Z}}_q^n$

for the first-layer LWE encryption, and a secret key ƒ ∈ R_Q (aligning with the NTRU setup where fis sampled from the key distribution χ_s over R and projected to R_Q for the second-layer NTRU-based GSW-like encryption. When computing a set of ciphertexts:

${\mathrm{evk}}_0={\mathrm{NTRU}}_{Q,f}^{\prime }\left(s_0/f\right),{\mathrm{evk}}_i={\mathrm{NTRU}}_{Q,f}^{\prime }\left(s_i\right)$

for 1≤i≤n, with these NTRU encryption operations adhering to the KDM-form NTRU assumption's mathematical space (i.e., within the ring R_Q and using distributions χ_s, χ_e to ensure hardness properties as per the decisional KDM-form NTRU_N,Q,χs,χe problem, where distinguishing the constructed ciphertext distributions from random ones in R_Q is computationally hard for PPT algorithms.

$A_i\leftarrow {\mathbb{Z}}_q^{d\times n}$

and noise

$e_i\leftarrow {\chi }_{\sigma }^d$

for 0≤i≤N−1, then compute

$b_i=-A_i·s+e_i+z_i·𝔤\in {\mathbb{Z}}_q^d$

and output the keyswitch key lksk={(b_i, A_i)}_{0≤j≤N−1}.

[0053]After key Generation, Each party Publish(b_i, hpk_i, NKSK_i, EVK_i, lksk_i).

[0054]Each party encrypts a bit into an LWE ciphertext using the party's secret key. Using a plaintext m ∈ {0,1}, party i sample

$a_i\leftarrow {\mathbb{Z}}_q^n,e\leftarrow {\chi }_{\sigma }$

to output a LWE ciphertext

$c_i=\left(-\langle a_i,s_i\rangle +\frac{q}{4}m+e,a_i\right)\in {\mathbb{Z}}_q\times {\mathbb{Z}}_q^n.$

[0055]Each party Combines single-party LWE ciphertexts into a multi-key LWE ciphertext. Given

$c_j=\left(b_j,a_j\right)\in {\mathbb{Z}}_q^{n+1}$

for 1≤j≤k, return the MK-LWE ciphertext

$\stackrel{\_}{\mathrm{ct}}=\left({\sum }_{j=1}^k{b}_j,a_1,\dots ,a_k\right)\in {\mathbb{Z}}_q^{kn+1}.$

[0056]Evaluates a NAND gate on two multi-key ciphertexts and refreshes via bootstrapping. This algorithm operates on a Multi-key LWE ciphertext

$\stackrel{\_}{{\mathrm{ct}}^{\prime }}\in {\mathbb{Z}}_q^{kn+1}.$

First, it initializes ACC as

$\left(-\lfloor \frac{Q}{8}\rfloor ·X^{\frac{2N}{q}b}·{\sum }_{-\frac{N}{2}<i<\frac{N}{2}}{X}^i,0\right)\in R_Q^{k+1}.$

Then, for j from 1 to k, it invokes the BREval algorithm.

[0057]BREval((b, a),EVK) works as follows: First, iterate over i from 0 to n−1, and in each iteration, set

$a_i^{\prime }=\frac{2N}{q}{a}_i.$

Then, initialize ACC as ACC=X^a0⊙evk₀. Next, iterate over i from 1 to n−1, and in each iteration, update ACC as

$\mathrm{ACC}\odot \left[g+\left(X^{a_i^{\prime }}-1\right)·{\mathrm{evk}}_i\right].$

Finally, return ACC.

[0058]After that, for j from 1 to k again, the Merge algorithm is used to update ACC. The Merge algorithm functions as follows: It first iterates j from 0 to d−1, computing v_j=c⊙nksk_j.

[0059]Then, it constructs v=(v₀, v₁, . . . , v_d−1). Next, for j from 0 to k, it computes

$c_j^{\prime }={𝔤}^{-1}\left(c_j\right)·v\mathrm{mod}Q,$

forms

$\hat{c}=\left(c_0^{\prime },c_1^{\prime },\cdots ,c_k^{\prime }\right),$

and finally computes c via HybridProduct(ĉ,hpk_i,{b_j}_j∈[k]) and returns ĉ.

[0060]It constructs v=(v₀, v₁, . . . , v_d−1). Next, for j from 0 to k, it computes

$c_j^{\prime }={𝔤}^{-1}\left(c_j\right)·v\mathrm{mod}Q,$

forms

$\hat{c}=\left(c_0^{\prime },c_1^{\prime },\cdots ,c_k^{\prime }\right).$

To compute c, given the MK-RLWE ciphertext

$\hat{c}=\left(,\dots ,\right)\in R_Q^{k+1}),$

$v={\sum }_{j=0}^k\langle {𝔤}^{-1}\left(\widehat{c_J}\right),b_j\rangle ;$

next, construct the MK-RLWE ciphertext

$\overline{c}=\left(c_0^{\prime },c_1^{\prime },\dots ,c_k^{\prime }\right)\in R_Q^{k+1}\mathrm{where}(c_0^{\prime }=u_0+({𝔤}^{-1}\left(v\right),d_{i,1}\rangle ),c_i^{\prime }=u_i+({𝔤}^{-1}\left(v\right),d_{i,2}\rangle ,\mathrm{and}{c}_j^{\prime }=u_j\mathrm{for}j\in \left[k\right]\setminus \left\{i\right\}.$

${\sigma }_{\mathrm{hp}}^2,$

satisfying

${\sigma }_{\mathrm{hp}}^2\le {\mathrm{kd}}_{\mathrm{hp}}{N}^2{V}_{\mathrm{hp}}{\sigma }_{\beta }^2.$

Finally, it returns ĉ.

[0061]Next, ACC is updated by adding

$\left(\lfloor \frac{Q}{8}\rfloor ,0\right).$

Subsequently, ct′ is obtained by applying Extract(ACC) to get an element in

${\mathbb{Z}}_Q^{\mathrm{kN}+1}.$

[0062]Then, the KeySwitch algorithm is performed. The KeySwitch (ct′, {lsks_j}_j∈[k]) works as follows: Given a MK-LWE ciphertext

$\stackrel{\_}{\mathrm{ct}}=\left(b,a_1,\dots ,a_k\right)\in {\mathbb{Z}}_q^{\mathrm{kn}+1}\mathrm{where}{a}_j=\left(a_{0,j},\dots ,a_{n-1,j}\right)\in {\mathbb{Z}}_q^n$

and a set of key-switch keys {lsks_j}_j∈[k]. For 1≤j≤k, it computes

$\left(b_j^{\prime },a_j^{\prime }\right)={\sum }_{i=0}^{N-1}{𝔤}^{-1}\left(a_{i,j}\right)·{\mathrm{lsks}}_j.$

[0063]Then it outputs the ciphertext

$\stackrel{\_}{{\mathrm{ct}}^{\prime }}=\left(b+{\sum }_{i=1}^k{b}_i^{\prime },a_1^{\prime },\dots ,a_k^{\prime }\right).$

after Extract, KeySwitch is performed on ct′ with {lsks_j}_j∈[k] to get an element in

${\mathbb{Z}}_Q^{\mathrm{kn}+1}.$

[0064]Finally, the ModSwitch algorithm is applied. The ModSwitch(c) algorithm: Given a MK-LWE ciphertext

$c=\left(c_0,\dots ,c_{\mathrm{kn}}\right)\in {\mathbb{Z}}_Q^{\mathrm{kn}+1},$

$c^{\prime }={\left({\left[c_i\right]}_{q:Q}\right)}_{0\le i\le \mathrm{kn}}\in {\mathbb{Z}}_q^{\mathrm{kn}+1}.$

After KeySwitch, ModSwitch is applied to ct′ to obtain the result in

${\mathbb{Z}}_q^{\mathrm{kn}+1}.$

[0065]Decrypts a multi-key ciphertext using all participants' secret keys. Given a MK-LWE ciphertext

$\stackrel{\_}{\mathrm{ct}}=\left({\sum }_{j=1}^k{b}_j,a_1,\dots ,a_k\right)\in {\mathbb{Z}}_q^{\mathrm{kn}+1}$

and secret key s=(s₁, . . . . s_k), compute

$m=\lfloor \frac{2}{q}\left(\langle \stackrel{\_}{\mathrm{ct}},\left(1,\overline{s}\right)\rangle \right)\rceil \in \left\{0,1\right\}.$

[0066]The principle of the technical schemes is further detailed below.

${\mathbb{Z}}_q^n\times \mathbb{Z}.$

In the second distribution, one first samples

$a\leftarrow {\mathbb{Z}}_q^n$

[0068]The decisional LWE_n,q,χ assumption says that it is hard for any PPT algorithms to solve decisional LWE_n,q,χ with non-negligible advantage over a random guess.

[0070]The decisional RLWE_N,Q,χ assumption says that it is hard for any PPT algorithms to solve decisional RLWE_N,Q,χ with non-negligible advantage over a random guess.

$-\left\{\left(g_0/f,\dots ,g_{d-1}/f\right)|f\leftarrow {\chi }_s,g_0,\dots ,g_{d-1}\leftarrow {\chi }_e\right\},-\left\{\left(u_1,\dots ,u_d\right)|u_1,\dots ,u_d\leftarrow R_Q\right\}.$

[0072]The decisional NTRU assumption (in the vector form) says that it is hard for any PPT algorithms to solve decisional NTRU_N,Q,χs,χe with non-negligible advantage over a random guess.

$-\left\{\left(\left(g_0+B^0·m\right)/f,\dots ,\left(g_{d-1}+B^{d-1}·m\right)/f\right)|f\leftarrow {\chi }_s,g_0,\dots ,g_{d-1}\leftarrow {\chi }_e\right\},-\left\{\left(u_1,\dots ,u_d\right)|u_1,\dots ,u_d\leftarrow R_Q\right\}.$

[0074]The decisional KDM-form NTRU_N,Q,χs,χe assumption says that it is hard for any PPT algorithms to solve decisional KDM-form NTRU_N,Qχs,χe with non-negligible advantage over a random guess.

Gadget Decomposition

$\left[B^0,\dots ,B^d-1\right]\in {\mathbb{Z}}_q^d.$

$a_i\in (-\frac{B}{2},\frac{B}{2}]$

${𝔤}^{-1}\left(f\right):={\sum }_{i=0}^{N-1}{𝔤}^{-1}\left(f_i\right)X^i.$

It is clear that

${𝔤}^{-1}\left(f\right)·𝔤=\sum _{i=0}^{N-1}{𝔤}^{-1}\left(f_i\right)·𝔤·X^i=\sum _{i=0}^{N-1}{f}_i·X^i=f$

NTRU-Based GSW-Like Encryption

[0078]Building upon the concept of gadget decomposition described in the previous subsection, we now turn to an encryption scheme that leverages this structure in a homomorphic setting.

[0079]Definition 1 (scalar NTRU ciphertexts). Our scalar NTRU encryption of u ∈ R_Q under a secret keyf ∈ R_Q (that is invertible in R_Q) is defined as:

${\mathrm{NTRU}}_{Q,f}\left(u\right)=g/f+u/f\in R_Q$

where both f, g ∈ R_Q are polynomials with small coefficients, which are usually taken from a ternary distribution in practice. Note that we don't multiple Δ to u in scalar NTRU encaryption different from [XZD⁺23](g/ƒ+Δ·u/ƒ), which is important for us to ensure the correctness of multi-key bootstrapping.

${\mathrm{NTRU}}_{Q,f}^{\prime }\left(v\right)=g/f+v·𝔤\in R_Q^d$

where g are noise vector with small coefficients, and d=┌log_BQ┐. The external product ⊙:

$R_Q\times R_Q^d\to R_Q$

between scalar NTRU ciphertexts c=NTRU_Qf(u) and vector NTRU ciphertexts

$c={\mathrm{NTRU}}_{Q,f}^{\prime }\left(v\right)$

is define as:

${\mathrm{NTRU}}_{Q,f}\left(u\right)\odot {\mathrm{NTRU}}_{Q,f}^{\prime }\left(v\right)={𝔤}^{-1}\left(c\right)·c$

[0081]Lemma 3: External Product. Let c=NTRU_Q,f(u) ∈R_Q with noise variance Var(g), and

$c={\mathrm{NTRU}}_{Q,f}^{\prime }\left(v\right)\in R_Q^d$

$\mathrm{Var}\left(\hat{g}\right)\le {\mathrm{dNV}}_B\mathrm{Var}\left(g^{\prime }\right)+{❘v❘}_2^2·\mathrm{Var}\left(g\right)$

$\mathrm{Var}\left(\hat{g}\right)\le {\mathrm{dNV}}_B\mathrm{Var}\left(g^{\prime }\right)+\mathrm{Var}\left(g\right).$

[0082]The NTRU-based GSW-like encryption framework offers a compact and efficient mechanism for encoding both scalar and vector messages in a homomorphic context. Its carefully bounded noise growth, especially under external product operations, is critical for enabling deeper circuit evaluations without compromising correctness. This structure forms the cryptographic backbone of our blind rotation mechanism. In the next section, we leverage these components to construct a single-key blind rotation procedure, which serves as the foundational layer of our full multi-key bootstrapping pipeline.

Multi-key Fully Homomorphic Encryption

[0089]We adopt an extended form of (R)LWE-based encryption adapted for multi-key scenarios.

$\stackrel{\_}{\mathrm{ct}}=\left(b,a_1,\dots ,a_k\right)\in {\mathbb{Z}}_q^{\mathrm{kn}+1}\mathrm{and}\overline{s}=\left(s_1,\dots ,s_k\right)\in {\mathbb{Z}}_q^{\mathrm{kn}}.$

If the following holds:

$\langle \stackrel{\_}{\mathrm{ct}},\left(1,\stackrel{\_}{s}\right)\rangle =\lfloor \frac{q}{t}\rceil ·m+e\in {\mathbb{Z}}_q,$

then ct is said to be a MK-LWE ciphertext encrypting m under the concatenated secret key s, with error term e.

[0091]In the RLWE case, for a message μ∈R_q and secre−keys z₁, . . . , z_k ∈ R, define

$\overline{c}=\left(c_0,\dots ,c_k\right)\in R_Q^{k+1}\mathrm{and}\overline{z}=\left(1,z_1,\dots ,z_k\right)\in R_Q^{k+1}.$

If

$\langle \overline{c},\overline{z}\rangle =\mu +e^{\prime }\in R_Q,$

then c is a MK-RLWE ciphertext representing encryption of μ under the combined secret key z, with noise e′.

Multi-key Bootstrapping Supporting Parallelization

[0092]In the previous section, we introduced the fundamental building blocks of our construction, including multi-key FHE, gadget decomposition, and NTRU-based GSW-like encryption. With these tools in place, we now present our complete bootstrapping framework that supports multi-party computation and parallel homomorphic evaluation.

[0093]This chapter details the design of our multi-key bootstrapping procedure. We begin by describing a single-key blind rotation algorithm, which serves as the basis for manipulating encrypted data in the Fourier domain. We then extend this to the multi-key setting through ciphertext merging and transformation operations. Finally, we integrate all components into a unified multi-key bootstrapping algorithm that enables ciphertext refresh under multiple keys without compromising correctness or efficiency.

Single-key Blind Rotation

[0094]We design the single-key blind rotation algorithm to output a NTRU encrytion of

$X^{\frac{2N}{q}{\sum }_{i=0}^{n-1}{a}_i{s}_i}.$

[0095]BRKGen(s,f): Given a secret key

$s=\left(s_0,\dots ,s_{n-1}\right)\in {\mathbb{Z}}_q^n$

for the first-layer LWE encryption, and a secret key θ ∈ R_Q for the second-layer NTRU-based GSWlike encryption, the algorithm first computes a set of ciphertexts:

${\mathrm{evk}}_0={\mathrm{NTRU}}_{Q,f}^{\prime }\left(s_0/f\right),{\mathrm{evk}}_i={\mathrm{NTRU}}_{Q,f}^{\prime }\left(s_i\right)\mathrm{for}1\le i<n.$

[0096]Then, the algorithm outputs EVK=(evk₀, . . . , evk_n) as the evaluation key for blind rotation.

[0097]BREval ((b, a), EVK): Given an LWE-based ciphertext

${\mathrm{LWE}}_{q,s}\left(m\right)=\left(b,a\right)\in {\mathbb{Z}}_q^n\times {\mathbb{Z}}_q,$

and an evaluation key EVK at inputs, computes and returns ACC as described in algorithm 1. The algorithm output a NTRU encrytion of

$X^{\frac{2N}{q}{\sum }_{i=0}^{n-1}{a}_i{s}_i}.$

[0098]Lemma 4 (Single-key Blind Rotation): Let LWE-based ciphertext

${\mathrm{LWE}}_{q,s}\left(m\right)=\left(b,a\right)\in {\mathbb{Z}}_q^n\times {\mathbb{Z}}_q$

under secret key s ∈

${\mathbb{Z}}_q^n,\mathrm{where}a=\left(a_0,\dots ,a_{n-1}\right)\in {\mathbb{Z}}_q^n.$

Let N be a power of 2 and q|N. Let f ∈ R_Q be a polynomial that is invertible in R_Q. Then for any EVK=BRKGen(s,f), we have that

$\mathrm{BREval}\left(\left(b,a\right),\mathrm{EVK}\right)=\mathrm{NTRU}\left(X^{\frac{2N}{q}{\sum }_{i=0}^{n-1}{a}_i{s}_i}\right)=\hat{g}/f+X^{\frac{2N}{q}{\sum }_{i=0}^{n-1}{a}_i{s}_i}/f.$

[0099]The variance of ĝ satisfies

$\mathrm{Var}\left(\hat{g}\right)\le \left(2n-1\right){\mathrm{dNV}}_B{\sigma }_e^2,\mathrm{where}{\sigma }_e^2$

is the noise variance for the second-layer NTRU encrytion. We denote

${\sigma }_{\mathrm{BR}}^2$

as the variance of ĝ. We denote

${\sigma }_e^2$

be the noise variance for the evk_i for 0≤i≤n−1. In line 4 of Algorithm 1, We have the value of ACC equals

$X^{a_0^{\prime }}\odot {\mathrm{evk}}_0=X^{a_0^{\prime }}\odot {\mathrm{NTRU}}_{Q,f}^{\prime }\left(s_0/f\right)={\mathrm{NTRU}}_{Q,f}\left(X^{a_0^{\prime }{s}_0}\right)$

with noise variance

$dN{V}_B{\sigma }_e^2$

by Lemma 3. In line 6, it is easy to see that

$𝔤+\left(X^{a_i^{\prime }}-1\right)·$

${\mathrm{evk}}_i={\mathrm{NTRU}}_{Q,f}^{\prime }\left(X^{a_i^{\prime }{s}_i}\right)$

with noise variance bounded by

${❘X^{a_i^{\prime }}-1❘}_2^2·{\sigma }_e^2\le 2{\sigma }_e^2.$

[0100]Let c_i be the value of ACC after evaluating the i-th loop in line 5-7, we have

$\begin{array}{c}{c}_i=\mathrm{ACC}\odot \left[𝔤+\left(X^{a_i^{\prime }}-1\right)·{\mathrm{evk}}_i\right]\\ ={\mathrm{NTRU}}_{Q,f}\left(X^{{\sum }_{j=0}^{i=1}{a}_j^{\prime }{s}_j}\right)\odot \backslash {\mathrm{omathrmNTRU}}_{Q,f}^{\prime }\left(X^{a_i^{\prime }{s}_i}\right)\\ ={\mathrm{NTRU}}_{Q,f}\left(X^{{\sum }_{j=0}^i{a}_j^{\prime }{s}_j}\right)\end{array}.$

[0101]Based on Lemma 3, the increased noise of each iteration has variance dNV_B·2σ_e. After the loop from line 5 to 7, the output ciphertext ACC equals

$\mathrm{NTRU}\left(X^{\frac{2N}{q}{\sum }_{i=0}^{n-1}{a}_i{s}_i}\right)$

with variance bounded by

$dN{V}_B{\sigma }_e^2+\left(n-1\right)dN{V}_B·2{\sigma }_e^2=\left(2n-1\right)dN{V}_B{\sigma }_e^2.$

Merge NTRU Ciphertext into MK-RLWE Ciphertext

[0102]To support homomorphic multiplication in the multi-key setting, we introduce a new operation that merges a scalar NTRU ciphertext with a multi-key RLWE ciphertext. This operation is crucial for enabling key-consistent evaluations across ciphertexts encrypted under different keys.

[0103]We define a two-step multiplication process. First, we outline the construction of the HybridProduct and the associated noise key-switching keys (nksk), which form the foundation for our ciphertext merging mechanism. These components will be integrated into our overall bootstrapping procedure to ensure correct and efficient message multiplication.

[0104]HPKGen(z_i,θ_i): Given a RLWE secret key z_i ∈ R_Q and a NTRU secret key θ_i ∈ R_Q of party i, it generates and returns the hpk_i=(d_i,0, d_i,1, d_i,2) as follows:

[0105]Sample r_i←χ_σβ and a noise vector

$e_{i,0}\leftarrow {\chi }_{{\sigma }_{\beta }}^{d_{hp}},$

output the vector

$d_{i,0}=r_i·a+f_i·𝔤+e_{i,0}\in R_Q^{d_{hp}}.$

[0106]Sample

$d_{i,1}\leftarrow R_Q^{d_{hp}}$

and a noise vector

$e_{i,1}\leftarrow {\chi }_{{\sigma }_{\beta }}^{d_{hp}},$

compute

$d_{i,2}=-z_i·d_{i,1}+r_i·𝔤+e_{i,1}\in R_Q^{d_{hp}}$

and output(d_i,1,d_i,2)

[0107]HybridProduct (c, hpk_i, {b_j}_j∈[k]): Given an MK-RLWE ciphertext

$\stackrel{\_}{c}=\left(c_0,\dots ,c_k\right)\in R_Q^{k+1},{\mathrm{hpk}}_i=\left(d_{i,0},d_{i,1},d_{i,2}\right)$

of party i and the public keys {b_j}_j∈[k] of parties associated with c, return an MK-RLWE ciphertext c′ as follows: for 0≤j≤k compute

$u_j=\langle {𝔤}^{-1}\left(c_j\right),d_{i,0}\rangle .$

[0108]Then compute

$v={\sum }_{j=0}^k\langle {𝔤}^{-1}\left(c_j\right),b_j\rangle ,$

return an MK-RLWE ciphertext

${\stackrel{\_}{c}}^{\prime }=\left(c_0^{\prime },c_1^{\prime },\dots ,c_k^{\prime }\right)\in R_Q^{k+1},$

where

$c_0^{\prime }=u_0+\langle {𝔤}^{-1}\left(v\right),d_{i,1}\rangle ,c_i^{\prime }=u_i+\langle {𝔤}^{-1}\left(v\right),d_{i,2}\rangle ,c_j^{\prime }=u_j\mathrm{for}\in \left[k\right]\setminus i.$

[0109]The output ciphertext c′ satisfies:

$\langle {\overline{c}}^{\prime },\overline{z}\rangle =f·\langle \overline{c},\stackrel{\_}{z}\rangle +e^{\prime }.$

[0110]Let

${\sigma }_{\mathrm{hp}}^2$

denotes the vanance or me noise term e′, we have

${\sigma }_{\mathrm{hp}}^2\le {\mathrm{kd}}_{\mathrm{hp}}{N}^2{V}_{\mathrm{hp}}{\sigma }_{\beta }^2.$

[0111]NKSKGen(ƒ,B): Given a NTRU secret key ƒ and gadget base B, the algorithm compute a set of ciphertexts

${\mathrm{nksk}}_i={\mathrm{NTRU}}_{f,Q}^{\prime }\left(B^i\right)\in R_Q^d$

for 0≤i≤d−1 and return NKSK={nksk_i}_{0≤i≤d−1}.

[0112]Correctness of Algorithm 2: We show that if NTRU_{θi, Q}(m)=c is a scalar NTRU ciphertext that encrypts m under secret key ƒ_i and c=(c₀, c₁, . . . , c_k) is a MK-RLWE ciphertext that encrypts uunder secret key z=(z₀, z₁, . . . , z_k), then the output ciphertext c′ is a MK-RLWE ciphertext that encrypts m·μ.

[0113]The algorithm first compute v_i for (0≤i≤d−1) in line 1-2, we have

$\left(v_j=c\odot {\mathrm{nksk}}_j={\mathrm{NTRU}}_{f_i,Q}\left(m\right)\odot {\mathrm{NTRU}}_{f_i,Q}^{\prime }\left(B^i\right)={\mathrm{NTRU}}_{f_i,Q}\left(m·B^j\right)\right).$

Then in line 4, we have

$v=\left(v_0,v_1,\dots ,v_{d-1}\right)=\left(\frac{g_0^{\prime }}{f_i}+B^0·\frac{m}{f_i},\dots ,\frac{g_{d-1}^{\prime }}{f_i}+B^{d-1}·\frac{m}{f_i}\right)=\frac{g^{\prime }}{f_i}+\frac{m·𝔤}{f_i}\in R_Q^d$

where

$g^{\prime }=\left(g_0^{\prime },\dots ,g_{d-1}^{\prime }\right)\in R_Q^d\mathrm{and}{\left\{g_j^{\prime }\right\}}_{j\in \left[d\right]}$

are noise polynomials with small coefficients. Then the algorithm compute

$\left(c_j^{\prime }={𝔤}^{-1}\left(c_j\right)·v\sim \left(\mathrm{mod}Q\right)=\frac{{𝔤}^{-1}\left(c_j\right)·g^{\prime }}{f_i}+\frac{c_j·m}{f_i}\right)$

for 0≤j≤d−1) Let

$\hat{c}=\left(c_0^{\prime },c_1^{\prime },\dots ,c_k^{\prime }\right),$

we have that

$\hat{c}=\left(c_0^{\prime },c_1^{\prime },\dots ,c_k^{\prime }\right)=\left(\frac{{𝔤}^{-1}\left(c_0\right)·g^{\prime }}{f_i}+\frac{c_0·m}{f_i},\dots ,\frac{{𝔤}^{-1}\left(c_k\right)·g^{\prime }}{f_i}+\frac{c_k·m}{f_i}\right)\in R_Q^{k+1}.$

[0114]After HybridProduct in line 9, we finally have the output ciphertext c′ satisfies that

$\langle {\overline{c}}^{\prime },\overline{z}\rangle \approx f_i·\langle \hat{c},\overline{z}\rangle =\langle f_i·\hat{c},\overline{z}\rangle \approx \langle m·\overline{c},\overline{z}\rangle =m·\langle \overline{c},\overline{z}\rangle \approx m·\mu .$

[0115]So c′ is a MK-RLWE ciphertext that encrypts m·μ.

Lemma 5 (Merge)

${\sigma }_{pd}^2$

be the variance of noise term e′, we have that

${\sigma }_{pd}^2\le \left(1+\mathrm{kN}/2\right)\left(d^2{N}^2{V}_B^2{\sigma }_e^2+dN{V}_B\mathrm{Var}\left(g\right)\right)+k{d}_{hp}{N}^2{V}_{hp}{\sigma }_{\beta }^2.$

where

$\mathrm{Var}\left(g\right),{\sigma }_e^2$

are the noise vanance of c and the noise variance of nksk, respectively.

[0117]By definition, we have c=g/ƒ_i+m/ƒ_i=NTRU_ƒi,Q(m) ∈ R_Q with noise polynomial g, and

${\mathrm{nksk}}_j={\mathrm{NTRU}}_{f,Q}^{\prime }\left(B^j\right)\in R_Q^d$

with noise variance

${\sigma }_e^2.$

The algorithm first compute v_j for (0≤j≤d−1) in line 1-2, we have that

$v_j=c\odot {\mathrm{nksk}}_j={\mathrm{NTRU}}_{f_i,Q}\left(m\right)\odot {\mathrm{NTRU}}_{f_i,Q}^{\prime }\left(B^i\right)=\frac{g_j^{\prime }}{f_i}+B^j·\frac{m}{f_i}$

where

$\mathrm{Var}\left(g_j^{\prime }\right)\le dN{V}_B{\sigma }_e^2+\mathrm{Var}\left(g\right)$

by lemma 3.

[0118]Then in line 4, we have

$v=\left(v_0,v_1,\dots ,v_{d-1}\right)=\left(\frac{g_0^{\prime }}{f_i}+B^0·\frac{m}{f_i},\dots ,\frac{g_{d-1}^{\prime }}{f_i}+B^{d-1}·\frac{m}{f_i}\right)=\frac{g^{\prime }}{f_i}+\frac{m·𝔤}{f_i}\in R_Q^d$

where

$g^{\prime }=\left(g_0^{\prime },\dots ,g_{d-1}^{\prime }\right)\in R_Q^d.$

Then the algorithm compute

$c_j^{\prime }={𝔤}^{-1}\left(c_j\right)·v\sim \left(\mathrm{mod}Q\right)={𝔤}^{-1}\left(c_j\right)·g^{\prime }/f_i+c_j·m/f_i)\mathrm{for}\left(0\le j\le d-1\right).$

[0119]Let

$\hat{c}=\left(c_0^{\prime },c_1^{\prime },\dots ,c_k^{\prime }\right),$

we have that

$\hat{c}=\left(c_0^{\prime },c_1^{\prime },\dots ,c_k^{\prime }\right)=\left(\frac{{𝔤}^{-1}\left(c_0\right)·g^{\prime }}{f_i}+\frac{c_0·m}{f_i},\dots ,\frac{{𝔤}^{-1}\left(c_k\right)·g^{\prime }}{f_i}+\frac{c_k·m}{f_i}\right)\in R_Q^{k+1}.$

$\mathrm{Var}\left(\hat{g}\right)=dN{V}_B\mathrm{Var}\left(g^{\prime }\right)\le d^2{N}^2{V}_B^2{\sigma }_e^2+dN{V}_B\mathrm{Var}\left(g\right).$

[0121]Let e″ be the noise introduced by the HybridProduct with variance

$\mathrm{Var}\left(e^{″}\right)\le k{d}_{hp}{N}^2{V}_{hp}{\sigma }_{\beta }^2.$

[0122]After HybridProduct in line 9, we finally have the output ciphertext c′ satisfies that

$\langle \overline{c^{\prime }},\overline{z}\rangle =f_i\langle \hat{c},\overline{z}\rangle +e^{″}=\langle \left(\hat{g}+\overline{c}·m\right),\overline{z}\rangle +e^{″}=\langle \hat{g},\overline{z}\rangle +m·\langle \overline{c},\overline{z}\rangle +e^{″}=m·\langle \overline{c},\overline{z}\rangle +e^{\prime }$

${\sigma }_{pd}^2$

as the variance of e′, it is bounded by

${\sigma }_{pad}^2=\left(1+\mathrm{kN}/2\right)\mathrm{Var}\left(\tilde{g}\right)+\mathrm{Var}\left(e^{″}\right)\le \left(1+\mathrm{KN}/2\right)\left(d^2{N}^2{V}_B^2{\sigma }_e^2+dN{V}_{\mathrm{BVar}}\left(g\right)\right)+k{d}_{hp}{N}^2{V}_{hp}{\sigma }_{\beta }^2.$

The Multi-key Bootstrapping Algorithm

[0123]We first define the LWE-based Multi-key modswitch and multi-key keyswitch that will used in Multi-key Bootstrapping as follows.

$A_i\leftarrow {\mathbb{Z}}_q^{d\times n}$

and noise

$e_i\leftarrow {\chi }_{{\sigma }_{\alpha }}^d$

for 0≤i≤N−1, then compute

$b_i=-A_i·s+e_i+z_i·𝔤\in Z_q^d.$

and output the key-swithch key lksk={(b_i,A_i)}_{0≤j≤N−1}.

[0125]KeySwitch(ct,{lksk_j}_j∈[k]): Given a MK-LWE ciphertext

$\overline{ct}=\left(b,a_1,\dots ,a_k\right)\in Z_q^{\mathrm{kn}+1}\mathrm{for}{a}_j=\left(a_{0,j},\dots ,a_{n-1,j}\right)\in {\mathbb{Z}}_q^n,$

and a set of key-switch key {lksk_j}_j∈[k]. For 1≤j≤k, the algorithm compute

$\left(b_j^{\prime },a_j^{\prime }\right)=\sum _{i=0}^{N-1}{\mathrm{fg}}^{-1}\left(a_{i,j}\right)·{\mathrm{lksk}}_j.$

[0126]Then output the ciphertext

$\stackrel{\_}{{\mathrm{ct}}^{\prime }}=\left(b+{\sum }_{i=1}^k{b}^{\prime },a_1^{\prime },\dots ,a_k^{\prime }\right).$