Fully Homomorphic Encryption for Mathematicians (2013)

We give an introduction to Fully Homomorphic Encryption for mathematicians. Fully Homomorphic Encryption allows untrusted parties to take encrypted data <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper E normal n normal c left-parenthesis m 1 right-parenthesis comma ellipsis comma normal upper E normal n normal c left-parenthesis m Subscript t Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">E</mml:mi> <mml:mi mathvariant="normal">n</mml:mi> <mml:mi mathvariant="normal">c</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>m</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo stretchy="false">)</mml:mo> <mml:mo>,</mml:mo> <mml:mo> … </mml:mo> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">E</mml:mi> <mml:mi mathvariant="normal">n</mml:mi> <mml:mi mathvariant="normal">c</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>m</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {Enc}(m_1),\ldots ,\mathrm {Enc}(m_t)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and any efficiently computable function <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f"> <mml:semantics> <mml:mi>f</mml:mi> <mml:annotation encoding="application/x-tex">f</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and compute an encryption of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f left-parenthesis m 1 comma ellipsis comma m Subscript t Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>m</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mo> … </mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>m</mml:mi> <mml:mi>t</mml:mi> </mml:msub> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">f(m_1,\ldots ,m_t)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , without knowing or learning the decryption key or the raw data <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m 1 comma ellipsis comma m Subscript t Baseline"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>m</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mo> … </mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>m</mml:mi> <mml:mi>t</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">m_1,\ldots ,m_t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . The problem of how to do this was recently solved by Craig Gentry, using ideas from algebraic number theory and the geometry of numbers. In this paper we discuss some of the history and background, give examples of Fully Homomorphic Encryption schemes, and discuss the hard mathematical problems on which the cryptographic security is based.