Efficient Implementation Of Fully Homomorphic Encryption
First Claim
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 zi such that B={z1,z2, . . . , zN}, where there exists a small set S that includes n elements sj such that S={s1,s2, . . . , sn}, 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 sj 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 (σ
)}=σ
1,σ
2, . . . , σ
N, where for all i the bit Qi=1 if zi∈
S else the bit σ
i=0, where there exists an encrypted vector {right arrow over (d)} that includes N ciphertexts di such that {right arrow over (d)}=d1,d2, . . . , dN, where for all i the ciphertext di 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)}=y1,y2, . . . , yN, where for all i the element yi of the intermediate vector {right arrow over (y)} is computed as yi=c×
zi;
homomorphically multiplying the elements yi of the intermediate vector {right arrow over (y)} by the ciphertexts di 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 xi such that {right arrow over (x)}=x1,x2, . . . , xN, where for all i the ciphertext element xi in the ciphertext vector {right arrow over (x)} is an encryption of the product yi·
σ
i; and
homomorphically summing all of the ciphertext elements xi 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 pj with each of the n parts pj having a plurality of different elements from the big set B, where the elements sj of the small set S consist of one element from each of the n parts pj.
1 Assignment
0 Petitions
Accused Products
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 zi so B={z1,z2, . . . , zN}, there exists a small set S having n elements sj so S={s1, s2, . . . , sn}, 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 (σ)}=σ1, σ2, . . . , σN, σi=1 if zi ∈ S else σi=0, there exists an encrypted vector {right arrow over (d)} having N ciphertexts di so d=d1, d2, . . . , dN, di is an encryption of σi; post-processing c by multiplying it by all zi to obtain an intermediate vector {right arrow over (y)}=y1, y2, . . . , yN with yi computed yi=c×zi; homomorphically multiplying yi by di obtaining a ciphertext vector {right arrow over (x)} having N ciphertexts xi so z=x1, x2, . . . , xN, where xi is an encryption of the product yi·σi; and homomorphically summing all xi 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.
-
Citations
25 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 zi such that B={z1,z2, . . . , zN}, where there exists a small set S that includes n elements sj such that S={s1,s2, . . . , sn}, 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 sj 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 (σ
)}=σ
1,σ
2, . . . , σ
N, where for all i the bit Qi=1 if zi∈
S else the bit σ
i=0, where there exists an encrypted vector {right arrow over (d)} that includes N ciphertexts di such that {right arrow over (d)}=d1,d2, . . . , dN, where for all i the ciphertext di 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)}=y1,y2, . . . , yN, where for all i the element yi of the intermediate vector {right arrow over (y)} is computed as yi=c×
zi;homomorphically multiplying the elements yi of the intermediate vector {right arrow over (y)} by the ciphertexts di 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 xi such that {right arrow over (x)}=x1,x2, . . . , xN, where for all i the ciphertext element xi in the ciphertext vector {right arrow over (x)} is an encryption of the product yi·
σ
i; andhomomorphically summing all of the ciphertext elements xi 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 pj with each of the n parts pj having a plurality of different elements from the big set B, where the elements sj of the small set S consist of one element from each of the n parts pj. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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 zi such that B={z1,z2, . . . , zN}, where there exists a small set S that includes n elements sj such that S={s1,s2, . . . , sn}, 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 sj 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 (σ
)}=σ
1,σ
2, . . . , σ
N, where for all i the bit σ
i=1 if zi∈
S else the bit σ
i=0, where there exists an encrypted vector {right arrow over (d)} that includes N ciphertexts di such that {right arrow over (d)}=d1,d2, . . . , dN, where for all i the ciphertext di 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)}=y1,y2, . . . , yN, where for all i the element yi of the intermediate vector {right arrow over (y)} is computed as yi=c×
zi;homomorphically multiplying the elements yi of the intermediate vector {right arrow over (y)} by the ciphertexts di 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 xi such that {right arrow over (x)}=x1,x2, . . . , xN, where for all i the ciphertext element xi in the ciphertext vector {right arrow over (x)} is an encryption of the product yi·
σ
i; andhomomorphically summing all of the ciphertext elements xi 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 pj with each of the n parts pj having a plurality of different elements from the big set B, where the elements sj of the small set S consist of one element from each of the n parts pj. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
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 zi such that B={z1,z2, . . . , xN}, where there exists a small set S that includes n elements sj such that S={s1,s2, . . . , sn}, 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 sj 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 (σ
)}=σ
1,σ
2, . . . , σ
N, where for all i the bit σ
i=1 if zi∈
S else the bit σ
i=0, where there exists an encrypted vector {right arrow over (d)} that includes N ciphertexts di such that {right arrow over (d)}=d1,d2, . . . , dN, where for all i the ciphertext di 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)}=y1,y2, . . . , yN, where for all i the element yi of the intermediate vector {right arrow over (y)} is computed as yi=c×
zi;homomorphically multiplying the elements yi of the intermediate vector {right arrow over (y)} by the ciphertexts di 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 xi such that {right arrow over (x)}=x1,x2, . . . , xN, where for all i the ciphertext element xi in the ciphertext vector {right arrow over (x)} is an encryption of the product yi·
σ
i; andhomomorphically summing all of the ciphertext elements xi 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 (Gk)}=gl, where each geometric progression {right arrow over (Gk)} comprises a plurality of different elements zi from the big set B, where m is an integer greater than zero, where for each geometric progression {right arrow over (Gk)} a ratio of successive elements gl/gl−
1 is the same for all l. - View Dependent Claims (20, 21)
-
-
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 zi such that B={z1,z2, . . . , zN}, where there exists a small set S that includes n elements sj such that S ={s1,s2, . . . sn}, 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 sj 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 (σ
)}=σ
1,σ
2, . . . , σ
N, where for all i the bit σ
i=1 if zi∈
S else the bit σ
i=0, where there exists an encrypted vector {right arrow over (d)} that includes N ciphertexts di such that {right arrow over (d)}=d1,d2, . . . , dN, where for all i the ciphertext di 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)}=y1,y2, . . . , yN, where for all i the element yi of the intermediate vector {right arrow over (y)} is computed as yi=c×
zi;homomorphically multiplying the elements yi of the intermediate vector {right arrow over (y)} by the ciphertexts di 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 xi such that {right arrow over (x)}=x1,x2, . . . , xN, where for all i the ciphertext element xi in the ciphertext vector {right arrow over (x)} is an encryption of the product yi·
σ
i; andhomomorphically summing all of the ciphertext elements xi 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 (Gk)}=gl, where each geometric progression {right arrow over (Gk)} comprises a plurality of different elements zi from the big set B, where m is an integer greater than zero, where for each geometric progression {right arrow over (Gk)} a ratio of successive elements gl/gl−
1 is the same for all l. - View Dependent Claims (23, 24, 25)
-
Specification