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.