Fast parallelizable multi-key fully homomorphic encryption based on ntru

Patent metadata

Field	Value
Publication number	US-2025385780-A1
Application number	US-202519315768-A
Country	US
Kind code	A1
Filing date	Sep 1, 2025
Priority date	Sep 1, 2025
Publication date	Dec 18, 2025
Grant date	—

Abstract

The present application describes a multi-key fully homomorphic encryption (MK-FHE) scheme that enables secure and efficient multi-party computation by integrating learning with errors (LWE), ring learning with errors (RLWE), and NTRU-based encryption primitives. The scheme supports dynamic key management, parallelizable bootstrapping, and low-overhead homomorphic operations. Key innovations include a hybrid product mechanism for merging ciphertexts across cryptographic structures, a single-key blind rotation algorithm optimized for Fourier domain operations, and a noise-refreshing procedure that bounds error growth during homomorphic evaluations. This scheme achieves quasi-linear time complexity relative to the number of participating parties, making it suitable for resource-constrained environments such as federated learning and secure cloud-based AI inference.

First claim

What is claimed is,:

1 . A computer-implemented method for multi-key fully homomorphic encryption, comprising:
generating a unified set of public parameters defining operational moduli and dimensions for learning with errors (LWE), ring learning with errors (RLWE), and NTRU-based encryption schemes; producing, for each participant in a plurality of participants, independent cryptographic keys comprising a secret key pair for encryption and decryption operations, and a hybrid product key enabling merging of ciphertexts across LWE and RLWE structures; transforming plaintext data into an initial encrypted form under a participant's secret key, yielding a participant-specific ciphertext compatible with LWE structures; aggregating participant-specific ciphertexts from the plurality of participants to form a composite ciphertext operable under multiple keys; conducting homomorphic evaluation of a logical operation on at least two composite ciphertexts, incorporating a noise-refreshing procedure that: integrates single-element LWE-based encrypted structures with multi-element RLWE-based encrypted structures through a gadget decomposition and tensor product-based multiplication process to generate an updated composite ciphertext; and recovering the evaluated plaintext from the updated composite ciphertext by collaboratively applying the secret keys of all relevant participants.

2 . The method of claim 1 , wherein 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.

3 . The method of claim 1 , wherein the secret key pair comprises an LWE secret vector

s
i

∈

ℤ
q
n

and an 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

←

𝒳

σ
β

d
hp

,

computing

d

i
,
0

=

r
i

·
a

+

f
i

·
𝔤

+

e

i
,
0

∈

R
Q

d
hp

,

computing

d

i
,
2

=

-

z
i

·

d

i
,
1

+

r
i

·
𝔤

+

e

i
,
1

∈

R
Q

d
hp

,

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

nksk
i

=

NTRU

f
,
Q

′

(

B
i

)

.

4 . The method of claim 1 , wherein the step of transforming plaintext data into an initial encrypted form under a participant's secret key comprises sampling a random vector

a
i

←

Z
q
n

and noise term e←χ σ computing a ciphertext component

b
=

-

〈

a
i

,

s
i

〉

+

q
4

⁢
m

Assignees

• Univ Jinan

Inventors

• Weng Jian
• Han Zhen
• Ji Yuan
• Song Zikai
• Wang Yuteng
• Lai Junzuo
• Liu Zhiquan
• Li Ming
• Feng Bingwen
• Weng Jiasi

Classifications

• H04L9/008

  involving homomorphic encryption · CPC title

• H04L9/0618 Primary

  Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation · CPC title

• H04L9/0861 Primary

  Generation of secret information including derivation or calculation of cryptographic keys or passwords · CPC title