Spookily Homomorphic Encryption

Homomorphic encryption schemes enable computation over encrypted data. In this talk, we will consider settings where multiple users encrypt their data under different individually chosen keys. We will show that several meaningful notions of homomorphic computation are achievable in this setting. Interestingly, even though information can never flow from one key to another one, we can achieve surprising correlations between data encrypted under different keys, reminiscent of "spooky action at a distance" in quantum mechanics.