Zvika Brakerski
ABSTRACT
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.
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.
- Miklós Ajtai. Generating hard instances of the short basis problem. In ICALP, pages 1--9, 1999. Google Scholar
Digital Library
- Saikrishna Badrinarayanan, Eric Miles, Amit Sahai, and Mark Zhandry. Post-zeroizing obfuscation: The case of evasive circuits. Cryptology ePrint Archive, Report 2015/167, 2015. http://eprint.iacr.org/.Google Scholar
- Boaz Barak, Nir Bitansky, Ran Canetti, Yael Tauman Kalai, Omer Paneth, and Amit Sahai. Obfuscation for evasive functions. In TCC, pages 26--51, 2014.Google ScholarCross Ref
- Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. J. ACM, 59(2):6, 2012. Google ScholarDigital Library
- Zvika Brakerski and Guy N. Rothblum. Obfuscating conjunctions. In CRYPTO (2), pages 416--434, 2013.Google Scholar
- Ran Canetti. Towards realizing random oracles: Hash functions that hide all partial information. In CRYPTO, pages 455--469, 1997. Google ScholarDigital Library
- Ran Canetti, Guy N. Rothblum, and Mayank Varia. Obfuscation of hyperplane membership. In TCC, pages 72--89, 2010. Google ScholarDigital Library
- Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu, and Damien Stehlé. Cryptanalysis of the multilinear map over the integers. In EUROCRYPT, 2015. Also, Cryptology ePrint Archive, Report 2014/906.Google Scholar
- Jung Hee Cheon, Changmin Lee, and Hansol Ryu. Cryptanalysis of the new CLT multilinear maps. Cryptology ePrint Archive, Report 2015/934, 2015. http://eprint.iacr.org/.Google Scholar
- Jean-Sebastien Coron. Cryptanalysis of GGH15 multilinear maps. Cryptology ePrint Archive, Report 2015/1037, 2015. http://eprint.iacr.org/.Google Scholar
- Jean-Sébastien Coron, Craig Gentry, Shai Halevi, Tancrède Lepoint, Hemanta K. Maji, Eric Miles, Mariana Raykova, Amit Sahai, and Mehdi Tibouchi. Zeroizing without low-level zeroes: New MMAP attacks and their limitations. In CRYPTO I, pages 247--266, 2015.Google ScholarCross Ref
- Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Practical multilinear maps over the integers. In CRYPTO (1), pages 476--493, 2013.Google Scholar
- Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. New multilinear maps over the integers. In CRYPTO I, pages 267--286, 2015.Google ScholarCross Ref
- Yevgeniy Dodis, Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan. Public-key encryption schemes with auxiliary inputs. In TCC, pages 361--381, 2010. Google ScholarDigital Library
- Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Comput., 38(1):97--139, 2008. Google ScholarDigital Library
- Yevgeniy Dodis and Adam Smith. Correcting errors without leaking partial information. In STOC, pages 654--663, 2005. Google ScholarDigital Library
- Léo Ducas and Alain Durmus. Ring-LWE in polynomial rings. In Public Key Cryptography - PKC 2012, pages 34--51, 2012. Google ScholarDigital Library
- Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps from ideal lattices. In EUROCRYPT, pages 1--17, 2013.Google ScholarCross Ref
- Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In FOCS, pages 40--49, 2013. Also, Cryptology ePrint Archive, Report 2013/451. Google ScholarDigital Library
- Craig Gentry, Sergey Gorbunov, and Shai Halevi. Graph-induced multilinear maps from lattices. In TCC, pages 498--527, 2015.Google ScholarCross Ref
- Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197--206, 2008. Google ScholarDigital Library
- Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan. Robustness of the learning with errors assumption. In Innovations in Computer Science - ICS, pages 230--240, 2010.Google Scholar
- Shafi Goldwasser and Guy N. Rothblum. On best-possible obfuscation. In TCC, pages 194--213, 2007. Google ScholarDigital Library
- Satoshi Hada. Zero-knowledge and code obfuscation. In ASIACRYPT, pages 443--457, 2000. Google ScholarDigital Library
- Shai Halevi. Graded encoding, variations on a scheme. Cryptology ePrint Archive, Report 2015/866, 2015. http://eprint.iacr.org/.Google Scholar
- Dennis Hofheinz, John Malone-Lee, and Martijn Stam. Obfuscation for cryptographic purposes. In TCC, pages 214--232, 2007. Google ScholarDigital Library
- Susan Hohenberger, Guy N. Rothblum, Abhi Shelat, and Vinod Vaikuntanathan. Securely obfuscating re-encryption. In TCC, pages 233--252, 2007. Google ScholarDigital Library
- Yupu Hu and Huiwen Jia. Cryptanalysis of GGH map. Cryptology ePrint Archive, Report 2015/301, 2015. http://eprint.iacr.org/.Google Scholar
- Ben Lynn, Manoj Prabhakaran, and Amit Sahai. Positive results and techniques for obfuscation. In EUROCRYPT, pages 20--39, 2004.Google ScholarCross Ref
- Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. J. ACM, 60(6):43, 2013. Google ScholarDigital Library
- Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In EUROCRYPT, pages 700--718, 2012. Google ScholarDigital Library
- Brice Minaud and Pierre-Alain Fouque. Cryptanalysis of the new multilinear map over the integers. Cryptology ePrint Archive, Report 2015/941, 2015. http://eprint.iacr.org/.Google Scholar
- Damien Stehlé and Ron Steinfeld. Making NTRU as secure as worst-case problems over ideal lattices. In EUROCRYPT, pages 27--47, 2011. Google ScholarDigital Library
- Hoeteck Wee. On obfuscating point functions. In STOC, pages 523--532, 2005. Google ScholarDigital Library
Index Terms
- Obfuscating Conjunctions under Entropic Ring LWE
Recommendations
Obfuscating Conjunctions
We show how to securely obfuscate the class of conjunction functions (functions like $$f(x_1, \ldots , x_n) = x_1 \wedge \lnot x_4 \wedge \lnot x_6 \wedge \cdots \wedge x_{n-2}$$f(x1,ź,xn)=x1ź x4ź x6źźźxn-2). Given any function in the class, we produce ...
Verifiably encrypted signatures with short keys based on the decisional linear problem and obfuscation for encrypted VES
Verifiably encrypted signatures (VES) are encrypted signatures under a public key of a trusted third party. We can verify their validity without decryption. VES has useful applications such as online contract signing and optimistic fair exchange. We ...
Lossiness and Entropic Hardness for Ring-LWE
Theory of CryptographyAbstractThe hardness of the Ring Learning with Errors problem (RLWE) is a central building block for efficiency-oriented lattice-based cryptography. Many applications use an “entropic” variant of the problem where the so-called “secret” is not distributed ...
Comments