Efficient Implementation Of Fully Homomorphic Encryption

• US 20120039473A1
• Filed: 08/09/2011
• Published: 02/16/2012
• Est. Priority Date: 08/16/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gentry, Craig B., Halevi, Shai
• Granted Patent: US 8,565,435 B2
• Time in Patent Office: Days
• US Class Current: 380/277
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 2209/26 Testing cryptographic entity, e.g. testing integrity of encryption key or encryption algorithm
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/0816 Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
• CPC Class Codes: H04L 9/3026 details relating to polynomials generation, e.g. generation of irreducible polynomials
• CPC Class Codes: Y04S 40/20 Information technology specific aspects, e.g. CAD, simulation, modelling, system security

Abstract

In one exemplary embodiment of the invention, a method for homomorphic decryption, including: providing a ciphertext with element c, there exists a big set B having N elements z_i so B={z₁,z₂, . . . , z_N}, there exists a small set S having n elements s_j so S={s₁, s₂, . . . , s_n}, the small set is a subset of the big set, summing up the elements of the small set yields the private key, there exists a bit vector {right arrow over (σ)} having N bits σ_i so {right arrow over (σ)}=σ₁, σ₂, . . . , σ_N, σ_i=1 if z_i ∈ S else σ_i=0, there exists an encrypted vector {right arrow over (d)} having N ciphertexts d_i so d=d₁, d₂, . . . , d_N, d_i is an encryption of σ_i; post-processing c by multiplying it by all z_i to obtain an intermediate vector {right arrow over (y)}=y₁, y₂, . . . , y_N with y_i computed y_i=c×z_i; homomorphically multiplying y_i by d_i obtaining a ciphertext vector {right arrow over (x)} having N ciphertexts x_i so z=x₁, x₂, . . . , x_N, where x_i is an encryption of the product y_i·σ_i; and homomorphically summing all x_i to obtain a resulting ciphertext that is an encryption of the at least one bit, where the big set is partitioned into n parts with each part having a plurality of different elements from the big set, where the elements of the small set are one element from each part.

Claims

1. A method for homomorphic decryption, comprising:

providing a ciphertext comprising a ciphertext element c that is obtained by encrypting at least one bit b using a public key h, where the public key h and a private key w collectively comprise an encryption key pair such that the private key w enables decryption of data that has been encrypted using the public key h to form a ciphertext, where there exists a big set B that includes N elements z_i such that B={z₁,z₂, . . . , z_N}, where there exists a small set S that includes n elements s_j such that S={s₁,s₂, . . . , s_n}, where the small set S is a subset of the big set B, where n<

N, where n is an integer greater than one, where summing up the elements s_j of the small set S yields the private key w, where there exists a bit vector ei that includes N bits σ

_i such that {right arrow over (σ

)}=σ

₁,σ

₂, . . . , σ

_N, where for all i the bit Q_i=1 if z_i∈

S else the bit σ

_i=0, where there exists an encrypted vector {right arrow over (d)} that includes N ciphertexts d_i such that {right arrow over (d)}=d₁,d₂, . . . , d_N, where for all i the ciphertext d_i of the encrypted vector {right arrow over (d)} is an encryption of the bit σ

_i;

post-processing the provided ciphertext element c by multiplying the provided ciphertext element c by all elements of the big set B to obtain an intermediate vector {right arrow over (y)}=y₁,y₂, . . . , y_N, where for all i the element y_i of the intermediate vector {right arrow over (y)} is computed as y_i=c×

z_i;

homomorphically multiplying the elements y_i of the intermediate vector {right arrow over (y)} by the ciphertexts d_i in the encrypted vector {right arrow over (d)} to obtain a ciphertext vector {right arrow over (x)} comprised of ciphertexts, where the ciphertext vector {right arrow over (x)} includes N ciphertext elements x_i such that {right arrow over (x)}=x₁,x₂, . . . , x_N, where for all i the ciphertext element x_i in the ciphertext vector {right arrow over (x)} is an encryption of the product y_i·

σ

_i; and

homomorphically summing all of the ciphertext elements x_i of the ciphertext vector z to obtain a resulting ciphertext that comprises an encryption of the at least one bit b,

where the big set B is partitioned into n parts p_j with each of the n parts p_j having a plurality of different elements from the big set B, where the elements s_j of the small set S consist of one element from each of the n parts p_j.

2. The method of claim 1, where the private key w comprises at least one of:

an integer, a vector, a matrix and an element in an algebraic ring.

3. The method of claim 1, where each of the n parts has N/n different elements from the big set B.

4. The method of claim 1, where the encrypted vector {right arrow over (d)} is represented by n partial encrypted vectors {right arrow over (e_j)}, one for each part p_j of the big set B, where for all j the partial encrypted vector {right arrow over (x_j)} comprises t_j ciphertexts, two of which are encryptions of 1 and the rest being encryptions of 0.

5. The method of claim 4, where for all j the j′

th part of the big set B has a size a_j, where the number of ciphertexts t_j in the partial encrypted vector {right arrow over (e_j)} satisfies the relation;

t_j≧

┌

√

{square root over (2a_j)}┐

.

6. The method of claim 4, where each ciphertext d_i in the encrypted vector {right arrow over (d)} is computed as a function of two ciphertexts from one of the partial encrypted vectors {right arrow over (e_j)}.

7. The method of claim 4, where each ciphertext d_i in the encrypted vector {right arrow over (d)} is computed as a product of two ciphertexts from one of the partial encrypted vectors {right arrow over (e_j)}.

8. The method of claim 4, where each of the n parts p_j comprises a geometric progression of elements z_i from the big set B.

9. The method of claim 1, where each of the n parts p_j comprises a geometric progression of elements z_i from the big set B.

10. A computer readable storage medium tangibly embodying a program of instructions executable by a machine for performing operations for homomorphic decryption, said operations comprising:

providing a ciphertext comprising a ciphertext element c that is obtained by encrypting at least one bit b using a public key h, where the public key h and a private key w collectively comprise an encryption key pair such that the private key w enables decryption of data that has been encrypted using the public key h to form a ciphertext, where there exists a big set B that includes N elements z_i such that B={z₁,z₂, . . . , z_N}, where there exists a small set S that includes n elements s_j such that S={s₁,s₂, . . . , s_n}, where the small set S is a subset of the big set B, where n<

N, where n is an integer greater than one, where summing up the elements s_j of the small set S yields the private key w, where there exists a bit vector {right arrow over (σ

)} that includes N bits σ

_i such that {right arrow over (σ

)}=σ

₁,σ

₂, . . . , σ

_N, where for all i the bit σ

_i=1 if z_i∈

S else the bit σ

_i=0, where there exists an encrypted vector {right arrow over (d)} that includes N ciphertexts d_i such that {right arrow over (d)}=d₁,d₂, . . . , d_N, where for all i the ciphertext d_i of the encrypted vector {right arrow over (d)} is an encryption of the bit σ

_i;

post-processing the provided ciphertext element c by multiplying the provided ciphertext element c by all elements of the big set B to obtain an intermediate vector {right arrow over (y)}=y₁,y₂, . . . , y_N, where for all i the element y_i of the intermediate vector {right arrow over (y)} is computed as y_i=c×

z_i;

homomorphically multiplying the elements y_i of the intermediate vector {right arrow over (y)} by the ciphertexts d_i in the encrypted vector {right arrow over (d)} to obtain a ciphertext vector {right arrow over (x)} comprised of ciphertexts, where the ciphertext vector {right arrow over (x)} includes N ciphertext elements x_i such that {right arrow over (x)}=x₁,x₂, . . . , x_N, where for all i the ciphertext element x_i in the ciphertext vector {right arrow over (x)} is an encryption of the product y_i·

σ

_i; and

homomorphically summing all of the ciphertext elements x_i of the ciphertext vector {right arrow over (x)} to obtain a resulting ciphertext that comprises an encryption of the at least one bit b,

where the big set B is partitioned into n parts p_j with each of the n parts p_j having a plurality of different elements from the big set B, where the elements s_j of the small set S consist of one element from each of the n parts p_j.

11. The computer readable storage medium of claim 10, where the private key w comprises at least one of:

an integer, a vector, a matrix and an element in an algebraic ring.

12. The computer readable storage medium of claim 10, where each of the n parts has N/n different elements from the big set B.

13. The computer readable storage medium of claim 10, where the encrypted vector {right arrow over (d)} is represented by n partial encrypted vectors {right arrow over (e_j)}, one for each part p_j of the big set B, where for all j the partial encrypted vector {right arrow over (e_j)} comprises t_j ciphertexts, two of which are encryptions of 1 and the rest being encryptions of 0.

14. The computer readable storage medium of claim 13, where for all j the j′

th part of the big set B has a size a_j, where the number of ciphertexts t_j in the partial encrypted vector {right arrow over (e_j)}satisfies the relation;

t_j≧

┌

√

{square root over (2a_j)}┐

.

15. The computer readable storage medium of claim 13, where each ciphertext d_i in the encrypted vector {right arrow over (d)} is computed as a function of two ciphertexts from one of the partial encrypted vectors {right arrow over (e_j)}.

16. The computer readable storage medium of claim 13, where each ciphertext d_i in the encrypted vector {right arrow over (d)} is computed as a product of two ciphertexts from one of the partial encrypted vectors {right arrow over (e_j)}.

17. The computer readable storage medium of claim 13, where each of the n parts p_j comprises a geometric progression of elements z_i from the big set B.

18. The computer readable storage medium of claim 10, where each of the n parts p_j comprises a geometric progression of elements z_i from the big set B.

19. A method for homomorphic decryption, comprising:

providing a ciphertext comprising a ciphertext element c that is obtained by encrypting at least one bit b using a public key h, where the public key h and a private key w collectively comprise an encryption key pair such that the private key w enables decryption of data that has been encrypted using the public key h to form a ciphertext, where there exists a big set B that includes N elements z_i such that B={z₁,z₂, . . . , x_N}, where there exists a small set S that includes n elements s_j such that S={s₁,s₂, . . . , s_n}, where the small set S is a subset of the big set B, where n<

N, where n is an integer greater than one, where summing up the elements s_j of the small set S yields the private key w, where there exists a bit vector {right arrow over (σ

)} that includes N bits σ

_i such that {right arrow over (σ

)}=σ

₁,σ

₂, . . . , σ

_N, where for all i the bit σ

_i=1 if z_i∈

S else the bit σ

_i=0, where there exists an encrypted vector {right arrow over (d)} that includes N ciphertexts d_i such that {right arrow over (d)}=d₁,d₂, . . . , d_N, where for all i the ciphertext d_i of the encrypted vector {right arrow over (d)} is an encryption of the bit σ

_i;

post-processing the provided ciphertext element c by multiplying the provided ciphertext element c by all elements of the big set B to obtain an intermediate vector {right arrow over (y)}=y₁,y₂, . . . , y_N, where for all i the element y_i of the intermediate vector {right arrow over (y)} is computed as y_i=c×

z_i;

homomorphically multiplying the elements y_i of the intermediate vector {right arrow over (y)} by the ciphertexts d_i in the encrypted vector {right arrow over (d)} to obtain a ciphertext vector {right arrow over (x)} comprised of ciphertexts, where the ciphertext vector {right arrow over (x)} includes N ciphertext elements x_i such that {right arrow over (x)}=x₁,x₂, . . . , x_N, where for all i the ciphertext element x_i in the ciphertext vector {right arrow over (x)} is an encryption of the product y_i·

σ

_i; and

homomorphically summing all of the ciphertext elements x_i of the ciphertext vector {right arrow over (x)} to obtain a resulting ciphertext that comprises an encryption of the at least one bit b,

where the big set B is comprised of m geometric progressions {right arrow over (G_k)}=g_l, where each geometric progression {right arrow over (G_k)} comprises a plurality of different elements z_i from the big set B, where m is an integer greater than zero, where for each geometric progression {right arrow over (G_k)} a ratio of successive elements g_l/g<sub>l−

1</sub> is the same for all l.

20. The method of claim 19, where the private key w comprises at least one of:

an integer, a vector, a matrix and an element in an algebraic ring.

21. The method of claim 19, where the encrypted vector {right arrow over (d)} is represented by n partial encrypted vectors {right arrow over (e_j)}, one for each part p_j of the big set B, where for all j the partial encrypted vector {right arrow over (e_j)} comprises t_j ciphertexts, two of which are encryptions of 1 and the rest being encryptions of 0.

22. A computer readable storage medium tangibly embodying a program of instructions executable by a machine for performing operations for homomorphic decryption, the operations comprising:

providing a ciphertext comprising a ciphertext element c that is obtained by encrypting at least one bit b using a public key h, where the public key h and a private key w collectively comprise an encryption key pair such that the private key w enables decryption of data that has been encrypted using the public key h to form a ciphertext, where there exists a big set B that includes N elements z_i such that B={z₁,z₂, . . . , z_N}, where there exists a small set S that includes n elements s_j such that S ={s₁,s₂, . . . s_n}, where the small set S is a subset of the big set B, where n<

N, where n is an integer greater than one, where summing up the elements s_j of the small set S yields the private key w, where there exists a bit vector {right arrow over (σ

)} that includes N bits σ

_i such that {right arrow over (σ

)}=σ

₁,σ

₂, . . . , σ

_N, where for all i the bit σ

_i=1 if z_i∈

S else the bit σ

_i=0, where there exists an encrypted vector {right arrow over (d)} that includes N ciphertexts d_i such that {right arrow over (d)}=d₁,d₂, . . . , d_N, where for all i the ciphertext d_i of the encrypted vector {right arrow over (d)} is an encryption of the bit σ

_i;

post-processing the provided ciphertext element c by multiplying the provided ciphertext element c by all elements of the big set B to obtain an intermediate vector {right arrow over (y)}=y₁,y₂, . . . , y_N, where for all i the element y_i of the intermediate vector {right arrow over (y)} is computed as y_i=c×

z_i;

homomorphically multiplying the elements y_i of the intermediate vector {right arrow over (y)} by the ciphertexts d_i in the encrypted vector {right arrow over (d)} to obtain a ciphertext vector {right arrow over (x)} comprised of ciphertexts, where the ciphertext vector {right arrow over (x)} includes N ciphertext elements x_i such that {right arrow over (x)}=x₁,x₂, . . . , x_N, where for all i the ciphertext element x_i in the ciphertext vector {right arrow over (x)} is an encryption of the product y_i·

σ

_i; and

homomorphically summing all of the ciphertext elements x_i of the ciphertext vector {right arrow over (x)} to obtain a resulting ciphertext that comprises an encryption of the at least one bit b,

where the big set B is comprised of m geometric progressions {right arrow over (G_k)}=g_l, where each geometric progression {right arrow over (G_k)} comprises a plurality of different elements z_i from the big set B, where m is an integer greater than zero, where for each geometric progression {right arrow over (G_k)} a ratio of successive elements g_l/g<sub>l−

1</sub> is the same for all l.

23. The computer readable storage medium of claim 22, where each of the n parts has N/n different elements from the big set B.

24. The computer readable storage medium of claim 22, where the encrypted vector {right arrow over (d)} is represented by n partial encrypted vectors {right arrow over (e_j)}, one for each part p_j of the big set B, where for all j the partial encrypted vector {right arrow over (e_j)} comprises t_j ciphertexts, two of which are encryptions of 1 and the rest being encryptions of 0.

25. The computer readable storage medium of claim 22, where each of the n parts p_j comprises a geometric progression of elements z_i from the big set B.