Difference between revisions of "GSW - Bootstrapping"

From certFHE Community KB
Jump to navigation Jump to search
Line 16: Line 16:
  
 
<b> A randomized decomposition function.</b> There is a randomized, efficiently computable function <math> \mathfrak g^{-1}: \mathbb Z_q \to \mathbb Z^l </math> such that <math> x \leftarrow \mathfrak g^{-1}(a) </math> is "subgaussian" with parameter <math> O(1)</math>, and always satisfies <math> \langle g,x \rangle =a </math>. <ref> D. Micciancio and C. Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In
 
<b> A randomized decomposition function.</b> There is a randomized, efficiently computable function <math> \mathfrak g^{-1}: \mathbb Z_q \to \mathbb Z^l </math> such that <math> x \leftarrow \mathfrak g^{-1}(a) </math> is "subgaussian" with parameter <math> O(1)</math>, and always satisfies <math> \langle g,x \rangle =a </math>. <ref> D. Micciancio and C. Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In
EUROCRYPT, pages 700–718. 2012</ref>
+
EUROCRYPT, pages 700–718. 2012 https://www.iacr.org/archive/eurocrypt2012/72370695/72370695.pdf</ref>
  
 
In particular <math>x </math> is randomized and has low entries with very large probability.
 
In particular <math>x </math> is randomized and has low entries with very large probability.
  
 
== References ==
 
== References ==

Revision as of 07:40, 15 June 2020

Gentry's bootstrapping theorem allows for converting a “somewhat homomorphic” encryption scheme (which supports only a bounded number of homomorphic operations) into a fully homomorphic encryption one (which has no such bound). The bounded nature of all known somewhat homomorphic schemes cannot be avoided due to “error” terms in their ciphertexts, which are necessary for security. The error grows as a result of performing homomorphic operations, and if it grows too large, the ciphertext will no longer decrypt correctly.

Bootstrapping the error of a ciphertext so that it can support more homomorphic operations, by homomorphically evaluating the decryption function on the ciphertext. The result is a ciphertext that still encrypts the original encrypted message. If the error coming from the homomorphic evaluation is smaller than the error in the original ciphertext, we say that the ciphertext is “refreshed”. To date, bootstrapping is the only known way of obtaining an unbounded FHE scheme, i.e., one that can homomorphically evaluate any efficient function using keys and ciphertexts of a fixed size.

Here we present an efficient bootstrapping method for a variant of the GSW scheme, as presented in the paper of Alperin-Sheriff and Peikert [1].

A "simpler" variant of the GSW cryptosystem

The authors present a variant of the GSW scheme which permits a tighter analysis of its error growth under homomorphic operations.

Given a modulus , let us denote by and define the "gadget" (we will think of it as column) vector

Remark that , according to our choice of .

A randomized decomposition function. There is a randomized, efficiently computable function such that is "subgaussian" with parameter , and always satisfies . [2]

In particular is randomized and has low entries with very large probability.

References

  1. J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer). https://eprint.iacr.org/2014/094
  2. D. Micciancio and C. Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In EUROCRYPT, pages 700–718. 2012 https://www.iacr.org/archive/eurocrypt2012/72370695/72370695.pdf