Efficient implementation of fully homomorphic encryption

A non-transitory 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;
• and
• homomorphically 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.

A method for performing homomorphic decryption, comprising:

• executing, by one or more processors in a computer system, program code stored in a memory of the computer system to cause the computer system to perform operations, 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;
• and
• homomorphically 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-1is the same for all l.

A non-transitory 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;
• and
• homomorphically 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.

An apparatus, comprising:

• at least one memory storing program code;
• at least one processor,
• wherein the at least one processor is configured, in response to execution of the program code, to cause the apparatus to perform the following:
• 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 (y)}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 (y)} is an encryption of the product yi·σi;
• and
• homomorphically 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.

An apparatus, comprising:

• at least one memory storing program code;
• at least one processor,
• wherein the at least one processor is configured, in response to execution of the program code, to cause the apparatus to perform the following:
• 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;
• and
• homomorphically 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)}=g1, 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.