×

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
First Claim
Patent Images

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

    )}=custom-characterσ

    1

    2, . . . , σ

    Ncustom-character, 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)}=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 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 all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×