# US 2021/0243005 A1 · Fully homomorphic encryption method and device and computer readable storage medium

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0243005 A1
- Document ID: US20210243005A1
- Status: Published application
- Kind: A1
- Application number: 17/255,671
- Filed: 2018-07-04
- Published: 2021-08-05
- Earliest claimed: 2018-07-04
- Assignees: Shenzhen University
- Applicants: Shenzhen University
- Inventors: Peng ZHANG; Xiaoqiang SUN
- Web page: https://patentgrep.com/patent/US20210243005A1

## CPC

- H04L 9/008: {involving homomorphic encryption}
- H04L 9/0618: {Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation}
- H04L 9/3026: {details relating to polynomials generation, e.g. generation of irreducible polynomials}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L 2209/12: Details relating to cryptographic hardware or logic circuitry
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Provided are a fully homomorphic encryption method and device and a computer readable storage medium capable of enhancing efficiency of a homomorphic multiplication operation in a fully homomorphic encryption method. The method comprises: Step S1: generating a prime modulus qj=qj(λ, L), according to an input security parameter λ and a number of encryption layers L, wherein qj mod n≡1, n is an integer power of 2, j=0, 1, . . . , L−1, and q0<q1< . . . <qL-1; Step S2: generating a private key sk and a public key pk according to the prime modulus qj; Step S3: encrypting plaintext m according to the public key pk; and Step S4: performing a homomorphic operation on two ciphertexts associated with the same private key, the homomorphic operation includes a homomorphic addition operation FHE.Add(c′, c″) and a homomorphic multiplication operation FHE.Mul(c′, c″).

## Claims

### Claim 1

A fully homomorphic encryption method, comprising:
Step S1: generating a prime modulus qj=qj (λ, L), according to an input security parameter λ and a number of encryption layers L, wherein qj mod n≡1, n is an integer power of 2, j=0, 1, . . . , L−1, and q0<q1< . . . <qL-1;
Step S2: generating a private key sk and a public key pk according to the prime modulus qj;
Step S3: encrypting plaintext m according to the public key pk; and
Step S4: performing a homomorphic operation on two ciphertexts associated with the same private key, the homomorphic operation includes a homomorphic addition operation FHE.Add (c′, c″) and a homomorphic multiplication operation FHE.Mul(c′, c″), wherein the process of the homomorphic multiplication operation FHE.Mul(c′, c″) is as follows:
calculating a result ciphertext cmul=(cmul,0, cmul,1, cmul,2) according to the following processes, for two ciphertexts c′=(c′0, c′1) and c″=(c″0,c″1) associated with the same given private key:
cmul,0=[c′0·c″0]qj, cmul,1=[c′0·c″1+c′1·c″0]qj, cmul,2=[c′1·c″1]qj
outputting cmul directly, if cmul undergoes addition homomorphism in a next operation or no operation;
if cmul undergoes multiplication homomorphism in a next operation, reducing the size of the ciphertext of cmul from three ring elements to two ring elements by using the aforementioned key exchange technology, to obtain a new ciphertext c*mul=(c*mul,0,c*mul,1),
wherein c*mul,1=[p·cmul,1+cmul,2·wL-1,1]p·qj, and j∈[0, L−1].

### Claim 2 (depends on 1)

The fully homomorphic encryption method of claim 1, wherein, in step S4, the process of the homomorphic addition operation FHE.Add(c′,c″) is as follows:
for two given ciphertexts c′=(c′0, c′1, . . . , c′r) and c″=(c″0, c″1, . . . , c″k) associated with the same private key, wherein r,k∈{1, 2}, and r≤k,
if r=1 and k=1, the homomorphic addition ciphertext is cadd=([c′0+c″0]qj, [c′1+c″1]qj)
if r=1 and k=2, the homomorphic addition ciphertext is cadd=([c′0+c″0]qj, [c′1+c″1]qj, c″2)
if r=2 and k=2, the homomorphic addition ciphertext is cadd=([c′0+c″0]qj, [c′1+c″1]qj, [c′2+c″2]qj),
wherein j∈[0, L−1].

### Claim 3 (depends on 1)

The fully homomorphic encryption method of claim 1, wherein, in step S2, the specific process of generating a private key sk and a public key pk according to the prime modulus qj is as follows:
using χ⊂Rqj to represent error distribution, and Rqj to represent an integer polynomial ring of modulo xn+1 and qj, and assuming params=(qj=0, 1, . . . , L-1, χ), and performing the following operation in the key generation function FHE.KeyGen(params):
entering the parameter params, to randomly and uniformly generate s∈R2, wherein R2 is the integer polynomial ring of modulo xn+1 and 2 to obtain b=[−(a·s+t·e)]qL-1, wherein a∈RqL-1, error e∈χ, t is a plaintext space modulus, [ ]qL-1 represents a modulo qL-1 operation; and given an integer p and using an exchange matrix wL-1=(bL-1, aL-1), wherein bL-1=[−aL-1·s+t·eL-1−p·s2]p·qL-1, aL-1∈RqL-1 and eL-1∈χ, to obtain the private key sk=s and the public key pk=(b, a, wL-1).

### Claim 4 (depends on 3)

The fully homomorphic encryption method of claim 3, wherein, Step S3 specifically comprises:
given m∈Rt in an encryption function FHE.Enc(pk, m), wherein Rt is an integer polynomial ring of modulo x″+1 and 2, randomly selecting u and ei from χ, where i=0, 1, and generating ciphertext c according to the following formula:
c=([m+b·u+t·e1]qL-1,[a·u+t·e2]qL-1).

### Claim 5 (depends on 1)

The fully homomorphic encryption method of claim 1, further comprising a decryption operation FHE.Dec(c, sk), wherein the ciphertext defined as c=(c0, c1, . . . , ck), and if k=1, then m=[[c0+c1·s]qj]t, if k=2, then m=[[c0+c1·s+c2·s2]qj]t.

### Claim 6 (depends on 1)

The fully homomorphic encryption method of claim 1, wherein Step S1 is performed by a prime modulus generating function FHE.Setup(1l, L).

### Claim 7 (depends on 1)

A fully homomorphic encryption device, comprising at least one processor, memory, and an interface which are connected through a bus;
the memory stores computer execution instructions;
the at least one processor executes computer execution instructions stored in the memory, to cause the fully homomorphic encryption device to perform the steps of the method of claim 1.

### Claim 8 (depends on 1)

A computer-readable storage medium storing a computer program, wherein the computer program, when executed by a processor, performs the steps of the method of claim 1.

### Claim 9 (depends on 2)

The fully homomorphic encryption method of claim 2, further comprising a decryption operation FHE.Dec(c, sk), wherein the ciphertext is defined as c=(c0, c1, . . . , ck), and if k=1,then m=[[c0+c1·s]qj]t, if k=2, then m=[[c0+c1·s+c2·s2]qj]t.

### Claim 10 (depends on 3)

The fully homomorphic encryption method of claim 3, further comprising a decryption operation FHE.Dec(c, sk), wherein the ciphertext is defined as c=(c0, c1, . . . , ck), and if k=1,then m=[[c0+c1·s]qj]t, if k=2, then m=[[c0+c1·s+c2·s2]qj]t.

### Claim 11 (depends on 4)

The fully homomorphic encryption method of claim 4, further comprising a decryption operation FHE.Dec(c, sk), wherein the ciphertext is defined as c=(c0, c1, . . . , ck), and if k=1, then m=[[c0+c1·s]qj]t, if k=2, then m=[[c0+c1·s+c2·s2]qj]t.

### Claim 12 (depends on 2)

The fully homomorphic encryption method of claim 2, wherein Step S1 is performed by a prime modulus generating function FHE.Setup(1l, L).

### Claim 13 (depends on 3)

The fully homomorphic encryption method of claim 3, wherein Step S1 is performed by a prime modulus generating function FHE.Setup(1l, L).

### Claim 14 (depends on 4)

The fully homomorphic encryption method of claim 4, wherein Step S1 is performed by a prime modulus generating function FHE.Setup(1l, L).

### Claim 15 (depends on 2)

A fully homomorphic encryption device, comprising at least one processor, memory, and an interface which are connected through a bus;
the memory stores computer execution instructions;
the at least one processor executes computer execution instructions stored in the memory, to cause the fully homomorphic encryption device to perform the steps of the method of claim 2.

### Claim 16 (depends on 3)

A fully homomorphic encryption device, comprising at least one processor, memory, and an interface which are connected through a bus;
the memory stores computer execution instructions;
the at least one processor executes computer execution instructions stored in the memory, to cause the fully homomorphic encryption device to perform the steps of the method of claim 3.

### Claim 17 (depends on 4)

A fully homomorphic encryption device, comprising at least one processor, memory, and an interface which are connected through a bus;
the memory stores computer execution instructions;
the at least one processor executes computer execution instructions stored in the memory, to cause the fully homomorphic encryption device to perform the steps of the method of claim 4.

### Claim 18 (depends on 5)

A fully homomorphic encryption device, comprising at least one processor, memory, and an interface which are connected through a bus;
the memory stores computer execution instructions;
the at least one processor executes computer execution instructions stored in the memory, to cause the fully homomorphic encryption device to perform the steps of the method of claim 5.

### Claim 19 (depends on 6)

A fully homomorphic encryption device, comprising at least one processor, memory, and an interface which are connected through a bus;
the memory stores computer execution instructions;
the at least one processor executes computer execution instructions stored in the memory, to cause the fully homomorphic encryption device to perform the steps of the method of claim 6.

### Claim 20 (depends on 2)

A computer-readable storage medium storing a computer program, wherein the computer program, when executed by a processor, performs the steps of the method of claim 2.