Zvika Brakerski. Fully homomorphic encryption --------------------------------------------- Additional problem (from Lecture 4) We saw in class how the noise grows in homomorphic evaluation in the approximate eigenvalue scheme, and the ideas on how the properties of the scheme allow to achieve smaller noise levels. My question to you is to come up with a way to perform homomorphic evaluation on circuits such that the noise does not go wild. Let us say that we want to evaluate circuits of size s and depth d, and that the dimension of our scheme is N (like we had in class). 1. Find a method for homomorphic evaluation such that the noise blowup is at most 2^O(d) * poly(s,N), where poly(.,.) is some fixed polynomial, and the running time is poly(s,N). As a first step, you may assume that d=O(log(N)), and then extend to general d. 2. Find a method for homomorphic evaluation such that the noise blowup is 2^O(d^0.9) * poly(s,N), and the running time is still poly(s,N). You can replace 0.9 by any number smaller than 1, the ultimate goal is to make the noise blowup just poly(s,N) (independent of depth). If you solve any part of the problem (preferably both), I'd be happy to know, please send me an email.