zbMATH — the first resource for mathematics

Fully homomorphic encryption over the integers. (English) Zbl 1279.94130
Gilbert, Henri (ed.), Advances in cryptology – EUROCRYPT 2010. 29th annual international conference on the theory and applications of cryptographic techniques, French Riviera, May 30 – June 3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13189-9/pbk). Lecture Notes in Computer Science 6110, 24-43 (2010).
Summary: We construct a simple fully homomorphic encryption scheme, using only elementary modular arithmetic. We use C. Gentry’s technique to construct a fully homomorphic scheme from a “bootstrappable” somewhat homomorphic scheme [“Fully homomorphic encryption using ideal lattices.” In: STOC 2009, New York, N.Y.: ACM, 169–178 (2009; Zbl 1257.68017)]. However, instead of using ideal lattices over a polynomial ring, our bootstrappable encryption scheme merely uses addition and multiplication over the integers. The main appeal of our scheme is the conceptual simplicity.
We reduce the security of our scheme to finding an approximate integer gcd – i.e., given a list of integers that are near-multiples of a hidden integer, output that hidden integer. We investigate the hardness of this task, building on earlier work of N. Howgrave-Graham [Cryptography and lattices – CaLC 2001, Lect. Notes Comput. Sci. 2146, 51–66 (2001; Zbl 1006.94528)].
For the entire collection see [Zbl 1188.94008].

94A60 Cryptography
Full Text: DOI