Difference between revisions of "Fully Homomorphic Encryption without Modulus Switching"

From certFHE Community KB
Jump to navigation Jump to search
Line 13: Line 13:
 
We start by presenting Regev's <ref name='Regev'> O. Regev. On lattices, learning with errors, random linear codes, and cryptography.
 
We start by presenting Regev's <ref name='Regev'> O. Regev. On lattices, learning with errors, random linear codes, and cryptography.
 
In Harold N. Gabow and Ronald Fagin, editors, STOC, pages 84–93. ACM, 2005 </ref> basic public-key encryption scheme.
 
In Harold N. Gabow and Ronald Fagin, editors, STOC, pages 84–93. ACM, 2005 </ref> basic public-key encryption scheme.
 +
 +
=== The Regev scheme ==
  
 
Let <math> q= q(n) </math> be an integer function and let <math>\chi(n) </math> be a distribution over <math>\mathbb Z </math>. The scheme 'Regev' is defined as follows:
 
Let <math> q= q(n) </math> be an integer function and let <math>\chi(n) </math> be a distribution over <math>\mathbb Z </math>. The scheme 'Regev' is defined as follows:

Revision as of 13:28, 18 January 2021

This scheme proposed by Brakerski [1] has a number of advantages over previous candidates such as BGV. In particular, it uses the same modulus throughout the evaluation process, so there's no need for modulus switching. Security of these scheme is baed on the hardness of the GapSVP problem.

Preliminaries

For an integer , write . This is not the same with the ring . For any , write for the unique value in that is congruent to modulo .

If are two -dimensional vectors, then the tensor product is the dimensional vector containing all elements of the form . Note that

Building Blocks of a homomorphic encryption scheme

We start by presenting Regev's [2] basic public-key encryption scheme.

= The Regev scheme

Let be an integer function and let be a distribution over . The scheme 'Regev' is defined as follows:

  • Regev.SecretKeygen( ): Sample uniformly. Output .
  • Regev.PublicKeygen(): Let . Sample uniformly then sample . Compute . Here we apply to every entry in the -dimensional vector and define
.

Output .

  • Regev.Enc(): To encrypt a message using , sample uniformly and output the ciphertext

where .

  • Regev.Dec(): To decrypt using the secret key , compute

In order to prove corectness, the author first shows (Lemma 3.1 in [1]) that if and - -bounded are parameters for the 'Regev' scheme described above and if is the fresh encryption of some message , then

for some with .

Then, Lemma 3.2 in the same article asserts that if is some vector and is such that

with and , then

Regev.Dec( )= .

Brakerski claims that the security of this scheme reduces to the hardness of (a decisional variant of) LWE problem by classical arguments (originally due to Regev [2]).

References

  1. Z. Brakerski, Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In: Safavi-Naini R., Canetti R. (eds) Advances in Cryptology – CRYPTO 2012. CRYPTO 2012. Lecture Notes in Computer Science, vol 7417. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32009-5_50
  2. O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, STOC, pages 84–93. ACM, 2005