Paper 2014/610
Computing on the Edge of Chaos: Structure and Randomness in Encrypted Computation
Craig Gentry
Abstract
This survey, aimed mainly at mathematicians rather than practitioners, covers recent developments in homomorphic encryption (computing on encrypted data) and program obfuscation (generating encrypted but functional programs). Current schemes for encrypted computation all use essentially the same "noisy" 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 control 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 encryption, 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 efficiency and to better understand encrypted computation conceptually.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. International Congress of Mathematicians (ICM) 2014
- Keywords
- homomorphic encryptionobfuscationlearning with errors
- Contact author(s)
- cbgentry @ us ibm com
- History
- 2014-08-13: received
- Short URL
- https://ia.cr/2014/610
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2014/610,
author = {Craig Gentry},
title = {Computing on the Edge of Chaos: Structure and Randomness in Encrypted Computation},
howpublished = {Cryptology ePrint Archive, Paper 2014/610},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/610}},
url = {https://eprint.iacr.org/2014/610}
}
