Top

Journal of Cryptology

Published in:

23-11-2015

Obfuscating Conjunctions

Authors: Zvika Brakerski, Guy N. Rothblum

Published in: Journal of Cryptology | Issue 1/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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}\)). Given any function in the class, we produce an obfuscated program which preserves the input–output functionality of the given function, but reveals nothing else. Our construction is based on multilinear maps, and can be instantiated using the recent candidates proposed by Garg, Gentry and Halevi (EUROCRYPT 2013) and by Coron et al. (CRYPTO 2013). We show that the construction is secure when the conjunction is drawn from a distribution, under mild conditions on the distribution. Security follows from multilinear entropic variants of the Diffie–Hellman assumption. We conjecture that our construction is secure for any conjunction, regardless of the distribution from which it is drawn. We offer supporting evidence for this conjecture, proving that our obfuscator is secure for any conjunction against generic adversaries.

previous article An Algebraic Framework for Diffie–Hellman Assumptions

next article Efficient One-Sided Adaptively Secure Computation

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

We use the asymmetric variant of the encoding scheme, where there are several distinct “source groups.”

We remark that in this case nothing at all can be learned from black box access to the function since it is infeasible to find an accepting input. We also remark that, for example, the conjunctions used for the k-resource application above naturally satisfy this condition, because of the entropy in each password.

This assumption is actually known to be false for the construction and formulation of [21]. However, we show a more careful definition of the scheme and the assumption for which no attack is known. Also, no attack is known for the recent construction of Coron et al. [14].

For the candidate of [21], the encodings are randomized, but there is a procedure for testing equality between encoded elements in the target group.

Wee [35] showed that these types of assumptions (hardness given only super-logarithmic entropy) are essential even for obfuscating point functions.

The “zero testing” parameter \({\mathbf {pzt}}\) defined in [21] is a part of \({ evparams }\).

This functionality is not explicitly provided by Garg et al. [21]; however, it can be obtained by combining their encoding and re-randomization procedures.

Recall that, as discussed in Remark 5.1, for security proofs in the random graded encoding scheme model, we assume that the encoding of each indexed ring element is unique.

The only dependence is that if for \(i \in [n]\) any of the \(\vec {\alpha }_{i,\vec {x}[i]}\) variables are 0, then \(\alpha _{n+1}\) is also 0.

B. Applebaum, Z. Brakerski, Obfuscating circuits via composite-order graded encoding, in Y. Dodis, J. B. Nielsen, editors, Theory of Cryptography—12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23–25, 2015, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9015 (Springer, 2015), pp. 528–556

B. Adida, D. Wikström, How to shuffle in public, in Vadhan [34], pp. 555–574

B. Barak, N. Bitansky, R. Canetti, Y. T. Kalai, O. Paneth, A. Sahai, Obfuscation for evasive functions, in Y. Lindell, editor, Theory of Cryptography—11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24–26, 2014. Proceedings. Lecture Notes in Computer Science, vol. 8349 (Springer, 2014), pp. 26–51

N. Bitansky, R. Canetti, On strong simulation and composable point obfuscation, in CRYPTO (2010), pp. 520–537

A. Boldyreva, S. Fehr, A. O’Neill, On notions of security for deterministic encryption, and efficient constructions without random oracles, in D. Wagner, editor, CRYPTO. Lecture Notes in Computer Science, vol. 5157 (Springer, 2008), pp. 335–359

B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, K. Yang, On the (im)possibility of obfuscating programs. J. ACM, 59(2), 6 (2012). Preliminary version in CRYPTO 2001

Z. Brakerski, G. N. Rothblum, Black-box obfuscation for d-cnfs, in Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12–14, 2014 (2014), pp. 235–250

Z. Brakerski, G. N. Rothblum, Virtual black-box obfuscation for all circuits via generic graded encoding, in Theory of Cryptography—11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24–26, 2014. Proceedings (2014), pp. 1–25

D. Boneh, A. Silverberg, Applications of multilinear forms to cryptography. IACR Crypt. ePrint Arch. 2002, 80 (2002)MATH

10.

R. Canetti, Towards realizing random oracles: Hash functions that hide all partial information. in CRYPTO (1997), pp. 455–469

11.

R. Canetti, R. R. Dakdouk, Obfuscating point functions with multibit output, in EUROCRYPT (2008), pp. 489–508

12.

J.-S. Coron, C. Gentry, S. Halevi, T. Lepoint, H. K. Maji, E. Miles, M. Raykova, A. Sahai, M. Tibouchi, Zeroizing without low-level zeroes: new MMAP attacks and their limitations. IACR Crypt. ePrint Arch. 2015, 596 (2015)MathSciNetMATH

13.

J. H. Cheon, K. Han, C. Lee, H. Ryu, D. Stehlé, Cryptanalysis of the multilinear map over the integers, in E. Oswald, M. Fischlin, editors, Advances in Cryptology—EUROCRYPT 2015—34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26–30, 2015, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9056 (Springer, 2015), pp. 3–12

14.

J.-S. Coron, T. Lepoint, M. Tibouchi, Practical multilinear maps over the integers, in R. Canetti, J. A. Garay, editors, Advances in Cryptology—CRYPTO 2013—33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2013. Proceedings, Part I. Lecture Notes in Computer Science, vol. 8042 (Springer, 2013), pp. 476–493

15.

J.-S. Coron, T. Lepoint, M. Tibouchi, New multilinear maps over the integers. IACR Crypt. ePrint Arch. 2015, 162 (2015)MathSciNetMATH

16.

R. Canetti, D. Micciancio, O. Reingold, Perfectly one-way probabilistic hash functions (preliminary version), in STOC (1998), pp. 131–140

17.

R. Canetti, G. N. Rothblum, M. Varia. Obfuscation of hyperplane membership, in TCC (2010), pp. 72–89

18.

Y. Dodis, R. Ostrovsky, L. Reyzin, A. Smith, Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97–139 (2008). Preliminary version in Eurocrypt 2004

19.

Y. Dodis, A. Smith, Correcting errors without leaking partial information, in Gabow and Fagin [20], pp. 654–663

20.

H. N. Gabow, R. Fagin, editors. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22–24, 2005. ACM (2005)

21.

S. Garg, C. Gentry, S. Halevi, Candidate multilinear maps from ideal lattices, in T. Johansson, P. Q. Nguyen, editors, EUROCRYPT. Lecture Notes in Computer Science, vol. 7881 (Springer, 2013) pp. 1–17. See also Cryptology ePrint Archive, Report 2012/610

22.

S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, B. Waters, Candidate indistinguishability obfuscation and functional encryption for all circuits, in 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26–29 October, 2013, Berkeley, CA, USA IEEE Computer Society (2013) pp. 40–49

23.

S. Goldwasser, Y. T. Kalai, On the impossibility of obfuscation with auxiliary input, in FOCS (2005) pp. 553–562

24.

S. Goldwasser, G. N. Rothblum, On best-possible obfuscation, in Vadhan [34], pp. 194–213

25.

Y. Hu, H. Jia, Cryptanalysis of ggh map. Crypt. ePrint Arch. Report 2015/301 (2015). http://eprint.iacr.org/

26.

D. Hofheinz, J. Malone-Lee, M. Stam, Obfuscation for cryptographic purposes. J. Cryptol. 23(1), 121–168 (2010)MathSciNetCrossRefMATH

27.

S. Hohenberger, G. N. Rothblum, A. Shelat, V. Vaikuntanathan. Securely obfuscating re-encryption. J. Cryptol. 24(4), 694–719 (2011)MathSciNetCrossRefMATH

28.

M. J. Kearns, U. V. Vazirani, An Introduction to Computational Learning Theory (MIT Press, Cambridge, MA, USA, 1994)

29.

B. Lynn, M. Prabhakaran, A. Sahai, Positive results and techniques for obfuscation, in EUROCRYPT (2004), pp. 20–39

30.

U. M. Maurer, Abstract models of computation in cryptography, in IMA International Conference (2005), pp. 1–12

31.

R. Rothblum, On the circular security of bit-encryption, in TCC (2013), pp. 579–598

32.

R. Renner, S. Wolf, Smooth renyi entropy and applications, in IEEE International Symposium on Information Theory, IEEE International Symposium on Information Theory (2004), p. 233

33.

V. Shoup, Lower bounds for discrete logarithms and related problems, in EUROCRYPT (1997), pp. 256–266

34.

S. P. Vadhan, editor. Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21–24, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4392 (Springer, 2007)

35.

H. Wee, On obfuscating point functions, in Gabow and Fagin [20], pp. 523–532

Title: Obfuscating Conjunctions
Authors: Zvika Brakerski
Guy N. Rothblum
Publication date: 23-11-2015
Publisher: Springer US
Published in: Journal of Cryptology / Issue 1/2017
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-015-9221-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2017

Weak Locking Capacity of Quantum Channels Can be Much Larger Than Private Capacity

Non-malleable Coding Against Bit-Wise and Split-State Tampering

Dynamic Proofs of Retrievability Via Oblivious RAM

An Algebraic Framework for Diffie–Hellman Assumptions

Bounded Tamper Resilience: How to Go Beyond the Algebraic Barrier

A Full Proof of the BGW Protocol for Perfectly Secure Multiparty Computation

Premium Partner