Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers

摘要

We describe several contribution to the study of fully homomorphic encryption schemes over the integers, as introduced by van Dijk, Gentry, Halevi and Vaikuntanathan (Eurocrypt 2010), and later improved by Coron, Mandal, Naccache and Tibouchi (Crypto 2011). Our first result is a simple compression technique that reduces the public key size of fully homomorphic encryption schemes over the integers from the previous O(λA7) mark obtained at Crypto 2010 to O(λ~5), for λ bits of security. The idea is to generate most of the public key bits in a pseudorandom way. The new variant of the scheme remains semantically secure, but in the random oracle model. We obtain an implementation of the full scheme with a10.1 MB public key, down from 802 MB previously.