Obfuscating Conjunctions under Entropic Ring LWE
Zvika Brakerski, Vinod Vaikuntanathan, Hoeteck Wee, Daniel Wichs · 2016
We show how to securely obfuscate conjunctions, which are functions f(x1,...,xn) = ∧i∈I yi where I ⊆ [n] and each literal yi is either just xi or ¬ xi e.g., f(xi,...,x_n) = xi ⊆ ¬ x3 ⊆ ¬ x7 ... ⊆ x{n-1. Whereas prior work of Brakerski and Rothblum (CRYPTO 2013) showed how to achieve this using a non-standard object called cryptographic multilinear maps, our scheme is based on an "entropic" variant of the Ring Learning with Errors (Ring LWE) assumption. As our core tool, we prove that hardness assumptions on the recent multilinear map construction of Gentry, Gorbunov and Halevi (TCC 2015) can be established based on entropic Ring LWE. We view this as a first step towards proving the security of additional mutlilinear map based constructions, and in particular program obfuscators, under standard assumptions.