US 10,652,010 B2Granted

Fully homomorphic encrypted ciphertext query method and system

AssigneesShenzhen Fhe Technologies Co., Ltd, Heping Hu

InventorsHeping Hu, Wei Hu

Life of this patent

Estimating the term…

Loading patent…

Abstract

A fully homomorphic encrypted ciphertext query method, the method including: acquiring a first plaintext, encrypting the first plaintext using a symmetric-key algorithm or a public-key algorithm to yield a first ciphertext, and storing the first ciphertext as a queried object; receiving a second plaintext which corresponds to a query condition, encrypting the second plaintext using a symmetric-key algorithm or a public-key algorithm to yield a second ciphertext, and storing the second ciphertext as a query object; performing bitwise summation on the queried object and the query object, to acquire a ciphertext query result; and decrypting the ciphertext query result to yield a decrypted plaintext, and comparing the decrypted plaintext with the second plaintext, determining, if the decrypted plaintext is the same as the second plaintext, the ciphertext query result is correct, and the query object exists in the queried object; otherwise, determining the ciphertext query result is incorrect.

Claims15

Dependent claims

A method, comprising:

(1) acquiring a first plaintext, encrypting the first plaintext using a symmetric-key algorithm or a public-key algorithm to yield a first ciphertext, and storing the first ciphertext as a queried object;
wherein:
when the symmetric-key algorithm is employed, the following formula is used:
c=(m+s*r+p*q) mod x0, wherein c denotes a ciphertext, m denotes a digit of a plaintext conforming to a numeral system, s denotes a base of the numeral system, r denotes a random number, p denotes an encryption key, and x0 denotes an intermediate variable equal to a product of the encryption key p and another encryption key q, both p and q are odd numbers, and the encryption keys are not publicly disclosed;
and
when the public-key algorithm is employed, the following formula is used:
c=(m+s*r+s*Σ1τxi*r) mod x0, wherein c denotes a ciphertext, m denotes a digit of a plaintext conforming to a numeral system, s denotes a base of the numeral system, both r and τ denote random numbers, xi denotes a randomly generated ith number, xi=qi*p+s*r, p denotes a private key and is an odd number, and qi<<q0, 0≤i≤τ, a public key is denoted as pk=(x0, x1, . . . , xi, . . . , xτ), and the private key p is generated based on Learning With Errors (LWE), a lattice, or Approximate Greatest Common Divisor (GCD) and sparse subset sum problem (SSSP);
(2) receiving a second plaintext which corresponds to a query condition, encrypting the second plaintext using the symmetric-key algorithm or the public-key algorithm to yield a second ciphertext, and storing the second ciphertext as a query object;
(3) performing bitwise summation on the queried object acquired in (1) and the query object acquired in (2) according to a numeral system thereof, to acquire a ciphertext query result;
and
(4) decrypting the ciphertext query result acquired in (3) to yield a decrypted plaintext, and comparing the decrypted plaintext with the second plaintext in (2), determining, if the decrypted plaintext is the same as the second plaintext, the ciphertext query result is correct, and the query object exists in the queried object;
otherwise, determining the ciphertext query result is incorrect, and the query object does not exist in the queried object.

9 more elements

A method, comprising:

(1) acquiring a first plaintext, encrypting the first plaintext using a symmetric-key algorithm or a public-key algorithm to yield a first ciphertext, and storing the first ciphertext as a queried object;
wherein:
when the symmetric-key algorithm is employed, the following formula is used:
c=(m+s*r+p*q) mod x0, wherein c denotes a ciphertext, m denotes a digit of a plaintext conforming to a numeral system, s denotes a base of the numeral system, r denotes a random number, p denotes an encryption key, and x0 denotes an intermediate variable equal to a product of the encryption key p and another encryption key q, both p and q are odd numbers, and the encryption keys are not publicly disclosed;
and
when the public-key algorithm is employed, the following formula is used:
c=(m+s*r+s*Σ1τxi*r) mod x0, wherein c denotes a ciphertext, m denotes a digit of a plaintext conforming to a numeral system, s denotes a base of the numeral system, both r and τ denote random numbers, xi denotes a randomly generated ith number, xi=qi*p+s*r, p denotes a private key and is an odd number, and qi<<q0, 0≤i≤τ, a public key is denoted as pk=(x0, x1, . . . , xi, . . . , xτ), and the private key p is generated based on Learning With Errors (LWE), a lattice, or Approximate Greatest Common Divisor (GCD) and sparse subset sum problem (SSSP);
(2) receiving a second plaintext which corresponds to a query condition, encrypting the second plaintext using the symmetric-key algorithm or the public-key algorithm to yield a second ciphertext, and storing the second ciphertext as a query object;
(3) performing bitwise subtraction on the queried object acquired in (1) and the query object acquired in (2) according to a numeral system thereof, to yield a difference, and using the difference as a ciphertext query result;
and
(4) decrypting the ciphertext query result acquired in (3) to yield a decrypted plaintext, and determining whether the decrypted plaintext is equal to zero, if the plaintext is equal to zero, it indicates that the ciphertext query result is correct, and the query object exists in the queried object;
otherwise, it indicates that the ciphertext query result is incorrect, and the query object does not exist in the queried object.

9 more elements

A system, comprising:

a first module configured to acquire a first plaintext of any data type, encrypt the first plaintext using a symmetric-key algorithm or a public-key algorithm to yield a first ciphertext, and store the first ciphertext as a queried object;
wherein:
when the symmetric-key algorithm is employed, the following formula is used:
c=(m+s*r+p*g) mod x0, wherein c denotes a ciphertext, m denotes a digit of a plaintext conforming to a numeral system, s denotes a base of the numeral system, r denotes a random number, p denotes an encryption key, and x0 denotes an intermediate variable equal to a product of the encryption key p and another encryption key q, both p and q are odd numbers, and the encryption keys are not publicly disclosed;
and
when the public-key algorithm is employed, the following formula is used:
c=(m+s*r+s*Σ1τxi*r) mod x0, wherein c denotes a ciphertext, m denotes a digit of a plaintext conforming to a numeral system, s denotes a base of the numeral system, both r and r denote random numbers, xi denotes a randomly generated ith number, xi=qi*p+s*r, p denotes a private key and is an odd number, and qi<<q0, 0≤i≤τ, a public key is denoted as pk=(x0, x1, . . . , xi, . . . , xτ), and the private key p is generated based on Learning With Errors (LWE), a lattice, or Approximate Greatest Common Divisor (GCD) and sparse subset sum problem (SSSP);
a second module configured to receive a second plaintext which corresponds to a query condition, encrypt the second plaintext using the symmetric-key algorithm or the public-key algorithm to yield a second ciphertext, and store the second ciphertext as a query object;
a third module configured to perform bitwise summation on the queried object acquired by the first module and the query object acquired by the second module according to a numeral system thereof, to acquire a ciphertext query result;
and
a fourth module configured to decrypt the ciphertext query result acquired by the third module to yield a decrypted plaintext, compare the decrypted plaintext with the second plaintext acquired by the second module, and determine, if the decrypted plaintext is the same as the second plaintext, the ciphertext query result is correct, and the query object exists in the queried object;
otherwise, determine the ciphertext query result is incorrect, and the query object does not exist in the queried object.

9 more elements

A system, comprising:

a first module configured to acquire a first plaintext of any data type, encrypt the first plaintext using a symmetric-key algorithm or a public-key algorithm to yield a first ciphertext, and store the first ciphertext as a queried object;
wherein:
when the symmetric-key algorithm is employed, the following formula is used:
c=(m+s*r+p*q) mod x0, wherein c denotes a ciphertext, m denotes a digit of a plaintext conforming to a numeral system, s denotes a base of the numeral system, r denotes a random number, p denotes an encryption key, and x0 denotes an intermediate variable equal to a product of the encryption key p and another encryption key q, both p and q are odd numbers, and the encryption keys are not publicly disclosed;
and
when the public-key algorithm is employed, the following formula is used:
c=(m+s*r+s*Σ1τxi*r) mod x0, wherein c denotes a ciphertext, m denotes a digit of a plaintext conforming to a numeral system, s denotes a base of the numeral system, both r and τ denote random numbers, xi denotes a randomly generated ith number, xi=qi*p+s*r, p denotes a private key and is an odd number, and qi<<q0, 0≤i≤τ, a public key is denoted as pk=(x0, x1, . . . , xi, . . . , xτ), and the private key p is generated based on Learning With Errors (LWE), a lattice, or Approximate Greatest Common Divisor (GCD) and sparse subset sum problem (SSSP);
a second module configured to receive a second plaintext which corresponds to a query condition, encrypt the second plaintext using the symmetric-key algorithm or the public-key algorithm to yield a second ciphertext, and store the second ciphertext as a query object;
a third module configured to perform bitwise subtraction on the queried object acquired by the first module and the query object acquired by the second module according to a numeral system thereof, to yield a difference, and use the difference as a ciphertext query result;
and
a fourth module configured to decrypt the ciphertext query result acquired by the third module to yield a decrypted plaintext, and determine whether the decrypted plaintext is equal to zero, if the plaintext is equal to zero, it indicates that the ciphertext query result is correct, and the query object exists in the queried object;
otherwise, it indicates that the ciphertext query result is incorrect, and the query object does not exist in the queried object.

9 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/120,443Filed 3 Sep 2018 · continuation in part
Priority: CN 2017 1 03208259 May 2017
Published: US 2018/0367294 A120 Dec 2018
Granted: 12 May 2020
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

H04L 9/008
Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols: involving homomorphic…
G06F 21/6227
To a system of files or objects, e.g. local or distributed file system or database: where protection concerns the structure of data, e.g. records,…
H04L
Digital communication
G06F
Computing and data processing