Patent ID: 8565435

Claim:
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 z i such that B={z 1 , z 2 , . . . , z N }, where there exists a small set S that includes n elements s j such that S={s 1 , s 2 , . . . , 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 (σ)}= σ 1 ,σ 2 , . . . , σ N , where for all i the bit σ i =1if 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 1 , d 2 , . . . , 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 1 ,y 2 , . . . , 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 1 , x 2 , . . . , 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 i 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 .