IACR News item: 18 July 2015
Allison Bishop, Susan Hohenberger, Brent Waters
ePrint Reportassumptions such as the Learning with Errors (LWE) problem. If it were difficult to find such counterexamples, this might bolster are confidence in using 2-circular encryption as a method of bootstrapping Fully Homomorphic Encryption systems that are based on lattice assumptions.
The results of this paper broadly expand the class of assumptions under which we can build 2-circular counterexamples. We first show for any constant k >= 2 how to build counterexamples from a bilinear group under the decision k-linear assumption. Recall that the decision k-linear assumption becomes progressively weaker as k becomes larger. This means that we can instantiate counterexamples
from symmetric bilinear groups and shows that asymmetric groups do not have any inherently special property needed for this problem.
We then show how to create 2-circular counterexamples from the Learning with Errors problem. This extends the reach of these systems beyond bilinear groups and obfuscation.
Additional news items may be found on the IACR news page.