Fully Homomorphic Encryption from Scratch
Fully Homomorphic Encryption (FHE) is a form of encryption that makes it possible to evaluate functions on encrypted inputs without access to the decryption key. For example, suppose you want to use a neural network running on an untrusted server to determine whether your image contains a cat. Since the server is untrusted, you do not want it to see your image. With FHE you can encrypt the image with your secret key and upload the encrypted image to the server. The server can then apply its neural network to the encrypted image and produce an encrypted bit. You can then download the encrypted bit and decrypt it with your secret key to obtain the result.
In other words, FHE makes it possible to leverage the computational resources of an untrusted server without having to send it any unencrypted data.
At first glance it seems like FHE is impossible. Encrypted data should be indistinguishable from random bytes to a person without access to the encryption key. So how could such a person perform a meaningful calculation on the encrypted data?
