Computing on the Edge of Chaos: Structure and Randomness in Encrypted Computation.
Craig Gentry · IACR Cryptology ePrint Archive · 2014
This survey, aimed mainly at mathematicians rather than practitioners, covers recent devel- opments in homomorphic encryption (computing on encrypted data) and program obfuscation (gen- erating encrypted but functional programs). Current schemes for encrypted computation all use es- sentially the same approach: they encrypt via a noisy encoding of the message, they decrypt using an approximate ring homomorphism, and in between they employ techniques to carefully con- trol the noise as computations are performed. This noisy approach uses a delicate balance between structure and randomness: structure that allows correct computation despite the randomness of the en- cryption, and randomness that maintains privacy against the adversary despite the structure. While the noisy approach works, we need new techniques and insights, both to improve e ciency and to better understand encrypted computation conceptually. Mathematics Subject Classification (2010). Primary 68Qxx; Secondary 68P25.