×

Efficient implementation of fully homomorphic encryption

  • US 8,565,435 B2
  • Filed: 08/09/2011
  • Issued: 10/22/2013
  • Est. Priority Date: 08/16/2010
  • Status: Active Grant
First Claim
Patent Images

1. 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 (σ

    )}=custom characterσ

    1

    2, . . . , σ

    Ncustom character, where for all i the bit σ

    i=1if 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)}=custom characterd1, d2, . . . , dNcustom character, 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)}=custom charactery1,y2, . . . , yNcustom character, 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)}=custom characterx1, x2, . . . , xNcustom character, 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 pi 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 all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×