Obfuscating Conjunctions under Entropic Ring LWE
We show how to securely obfuscate conjunctions, which are functions f(x[subscript 1], . . . , x[subscript n]) = ∧[subscript i∈I] y[superscript i] where I ⊆ [n] and each literal y[subscript i] is either just x[subscript i] or ¬x[subscript i] e.g., f(x[subscript 1], . . . , x_n) = x[subscript 1] ⊆ ¬...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2017
|
| Online Access: | http://hdl.handle.net/1721.1/112985 https://orcid.org/0000-0002-2666-0045 |
| _version_ | 1826203694016757760 |
|---|---|
| author | Brakerski, Zvika Vaikuntanathan, Vinod Wee, Hoeteck Wichs, Daniel |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Brakerski, Zvika Vaikuntanathan, Vinod Wee, Hoeteck Wichs, Daniel |
| author_sort | Brakerski, Zvika |
| collection | MIT |
| description | We show how to securely obfuscate conjunctions, which are functions f(x[subscript 1], . . . , x[subscript n]) = ∧[subscript i∈I] y[superscript i] where
I ⊆ [n] and each literal y[subscript i] is either just x[subscript i] or ¬x[subscript i] e.g., f(x[subscript 1], . . . , x_n) = x[subscript 1] ⊆ ¬ x[subscript 3] ⊆ ¬ x[subscript 7] · · · ⊆ x[subscript 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 multilinear 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. |
| first_indexed | 2024-09-23T12:41:54Z |
| format | Article |
| id | mit-1721.1/112985 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:41:54Z |
| publishDate | 2017 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/1129852022-10-01T10:33:37Z Obfuscating Conjunctions under Entropic Ring LWE Brakerski, Zvika Vaikuntanathan, Vinod Wee, Hoeteck Wichs, Daniel Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Vaikuntanathan, Vinod We show how to securely obfuscate conjunctions, which are functions f(x[subscript 1], . . . , x[subscript n]) = ∧[subscript i∈I] y[superscript i] where I ⊆ [n] and each literal y[subscript i] is either just x[subscript i] or ¬x[subscript i] e.g., f(x[subscript 1], . . . , x_n) = x[subscript 1] ⊆ ¬ x[subscript 3] ⊆ ¬ x[subscript 7] · · · ⊆ x[subscript 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 multilinear 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. 2017-12-29T19:18:44Z 2017-12-29T19:18:44Z 2016-01 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-4057-1 http://hdl.handle.net/1721.1/112985 Brakerski, Zvika, et al. "Obfuscating Conjunctions under Entropic Ring LWE." Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science - ITCS '16, 14-17 January, 2016, Cambridge, MA, ACM Press, 2016, pp. 147–56. https://orcid.org/0000-0002-2666-0045 en_US http://dx.doi.org/10.1145/2840728.2840764 Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science - ITCS '16 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery MIT Web Domain |
| spellingShingle | Brakerski, Zvika Vaikuntanathan, Vinod Wee, Hoeteck Wichs, Daniel Obfuscating Conjunctions under Entropic Ring LWE |
| title | Obfuscating Conjunctions under Entropic Ring LWE |
| title_full | Obfuscating Conjunctions under Entropic Ring LWE |
| title_fullStr | Obfuscating Conjunctions under Entropic Ring LWE |
| title_full_unstemmed | Obfuscating Conjunctions under Entropic Ring LWE |
| title_short | Obfuscating Conjunctions under Entropic Ring LWE |
| title_sort | obfuscating conjunctions under entropic ring lwe |
| url | http://hdl.handle.net/1721.1/112985 https://orcid.org/0000-0002-2666-0045 |
| work_keys_str_mv | AT brakerskizvika obfuscatingconjunctionsunderentropicringlwe AT vaikuntanathanvinod obfuscatingconjunctionsunderentropicringlwe AT weehoeteck obfuscatingconjunctionsunderentropicringlwe AT wichsdaniel obfuscatingconjunctionsunderentropicringlwe |