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

From certFHE Community KB
Jump to navigation Jump to search
Line 3: Line 3:
 
== Preliminaries ==
 
== Preliminaries ==
  
 +
For an integer <math>q </math>, write <math> \mathbb Z_q := \left(-q/2, q/2 \right] \cap \mathbb Z</math>. This is not the same with the ring <math>\mathbb Z/q \mathbb Z </math>. For any <math> x \in \mathbb Q </math>, write <math> [x]_p </math> for the unique value in <math>\left(-q/2, q/2 \right] \cap \mathbb Z </math> that is congruent to <math>x </math> modulo <math>q</math>.
 +
 +
If <math>v,w </math> are two <math>n</math>-dimensional vectors, then the tensor product <math> v \otimes w </math> is the <math> n^2</math> dimensional vector containing all elements of the form <math>v[i]w[j]</math>. Note that
 +
 +
<center><math>  <v \otimes w, x \otimes y> = <v,x> \cdot <w,y> .</math> </center>
 +
 +
== Building Blocks of a homomorphic encryption scheme ==
 +
 +
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.
  
 
==References==
 
==References==

Revision as of 14:57, 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q } , write . This is not the same with the ring . For any , write Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle [x]_p } for the unique value in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left(-q/2, q/2 \right] \cap \mathbb Z } that is congruent to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x } modulo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} .

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v,w } are two Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} -dimensional vectors, then the tensor product Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v \otimes w } is the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n^2} dimensional vector containing all elements of the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v[i]w[j]} . Note that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle <v \otimes w, x \otimes y> = <v,x> \cdot <w,y> .}

Building Blocks of a homomorphic encryption scheme

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

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
Retrieved from "https://certfhewiki.certsign.ro/wiki/index.php?title=Fully_Homomorphic_Encryption_without_Modulus_Switching&oldid=310"