| Title | Obfuscating Conjunctions Under Entropic Ring LWE |
| Publication Type | Conference Paper |
| Year of Publication | 2016 |
| Authors | Brakerski, Zvika, Vaikuntanathan, Vinod, Wee, Hoeteck, Wichs, Daniel |
| Conference Name | Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-4057-1 |
| Keywords | Asymmetric Encryption, compositionality, Human Behavior, Metrics, obfuscation, pubcrawl, Resiliency |
| Abstract | We show how to securely obfuscate conjunctions, which are functions f(x1,...,xn) = iI yi where I [n] and each literal yi is either just xi or ! xi e.g., f(xi,...,x\_n) = xi ! x3 ! x7 ... x\\textbackslashvphantom\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. Our scheme satisfies virtual black box (VBB) security, meaning that the obfuscated program reveals nothing more than black-box access to f as an oracle, at least as long as (essentially) the conjunction is chosen from a distribution having sufficient entropy. |
| URL | http://doi.acm.org/10.1145/2840728.2840764 |
| DOI | 10.1145/2840728.2840764 |
| Citation Key | brakerski_obfuscating_2016 |
Obfuscating Conjunctions Under Entropic Ring LWE