nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models

verfasst von : Mohammad Mahmoody, Ameer Mohammed, Soheil Nematihaji

Erschienen in: Theory of Cryptography

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The celebrated work of Barak et al. (Crypto’01) ruled out the possibility of virtual black-box (VBB) obfuscation for general circuits. The recent work of Canetti, Kalai, and Paneth (TCC’15) extended this impossibility to the random oracle model as well assuming the existence of trapdoor permutations (TDPs). On the other hand, the works of Barak et al. (Crypto’14) and Brakerski-Rothblum (TCC’14) showed that general VBB obfuscation is indeed possible in idealized graded encoding models. The recent work of Pass and Shelat (Cryptology ePrint 2015/383) complemented this result by ruling out general VBB obfuscation in idealized graded encoding models that enable evaluation of constant-degree polynomials in finite fields.

In this work, we extend the above two impossibility results for general VBB obfuscation in idealized models. In particular we prove the following two results both assuming the existence of trapdoor permutations:

There is no general VBB obfuscation in the generic group model of Shoup (Eurocrypt’97) for any abelian group. By applying our techniques to the setting of Pass and Shelat we extend their result to any (even non-commutative) finite ring.
There is no general VBB obfuscation in the random trapdoor permutation oracle model. Note that as opposed to the random oracle which is an idealized primitive for symmetric primitives, random trapdoor permutation is an idealized public-key primitive.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Impossibility of VBB Obfuscation with Ideal Constant-Degree Graded Encodings

Nächstes Kapitel Lower Bounds on Assumptions Behind Indistinguishability Obfuscation

The emulation here and in next steps would require the idealized model \({\mathcal I}\) to have an efficient “lazy evaluation” procedure. For example lazy evaluation for random oracles chooses a random answer (different from previous ones) given any new query.

More formally, using the rank argument of [Pas15] it can be shown that for the purpose of obfuscation, the two models are equivalent up to arbitrary small \(1/{\text {poly}}(n)\) completeness error.

Even though the summation is technically defined over the group elements, for simplicity we use the addition operation over the labels as well.

Note that this is even the case for \({\mathbb Z}_q\) when q is a prime power, although finite fields have prime power sizes.

In general, when the random permutation R is available in all input lengths, we can use a mixture of the above arguments by generating all the oracle queries of length \(c \log (n)\) (for a sufficiently large constant c) during the obfuscation (in the plain model) and representing this randomness in the obfuscated circuit. This issue also exists in the trapdoor permutation and the generic group models and can be handled exactly the same way.

So the oracle might return \(\bot \) even if the two labels are in the range of \(\sigma (G)\).

Note that although the sequence T grows as we proceed in learning phase 1, we already now that this sequence will not have length more than d since all of these labels that are discovered while executing the obfuscated code has to be generated by the obfuscator, due to the assumption that the sequential execution of the obfuscator followed by the obfuscated code is in generic form. Therefore we can always consider \(\mathbf {a}_i\) to be of dimension k.

Note that even though \(W(Q_B)\) could always be derived from \(Q_B\), and even T could be derived from an ordered variant of \(Q_B\) (in which the order in which \(Q_B\) has grown is preserved) we still choose to explicitly represent these elements in the obfuscated \(\widehat{B}\) to ease the description of the execution of \(\widehat{B}\).

Note that we do not have access to the set \(Q_\sigma \) that was used for consistent lazy evaluation of \(\sigma (\cdot )\).

We even allow new labels \(t_i\) to be discovered during this execution to be appended to T, even though that would indirectly lead to an abort!

Note that we do not solve a system of equations in R and rather search only integer solutions to \(\mathbf {x}W = \mathbf {a}\) as we did in Sect. 3.2.

[BGI+01]

Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001) CrossRef

[BGK+13]

Barak, B., Garg, S., Kalai, Y.T., Paneth, O., Sahai, A.: Protecting obfuscation against algebraic attacks. IACR Cryptology ePrint Archive, 2013:631 (2013)

[BGK+14]

Barak, B., Garg, S., Kalai, Y.T., Paneth, O., Sahai, A.: Protecting obfuscation against algebraic attacks. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 221–238. Springer, Heidelberg (2014) CrossRef

[BP13]

Bitansky, N., Paneth, O.: On the impossibility of approximate obfuscation and applications to resettable cryptography. In: Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 241–250. ACM, New York (2013)

[BR14]

Brakerski, Z., Rothblum, G.N.: Virtual black-box obfuscation for all circuits via generic graded encoding. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 1–25. Springer, Heidelberg (2014) CrossRef

[Can97]

Canetti, R.: Towards realizing random oracles: hash functions that hide all partial information. In: Kaliski Jr, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 455–469. Springer, Heidelberg (1997) CrossRef

[CGH04]

Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM 51(4), 557–594 (2004)MathSciNetCrossRefMATH

[CKP15]

Canetti, R., Tauman Kalai, Y.T., Paneth, O.: On obfuscation with random oracles. Cryptology ePrint Archive, Report 2015/048 (2015). http://eprint.iacr.org/

[GGH13a]

Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013) CrossRef

[GGH+13b]

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

[GKLM12]

Goyal, V., Kumar, V., Lokam, S., Mahmoody, M.: On black-box reductions between predicate encryption schemes. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 440–457. Springer, Heidelberg (2012) CrossRef

[HL02]

Horwitz, J., Lynn, B.: Toward hierarchical identity-based encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 466–481. Springer, Heidelberg (2002) CrossRef

[IR89]

Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: ACM Symposium on Theory of Computing (STOC), pp. 44–61. ACM Press (1989)

[LPS04]

Lynn, B.Y.S., Prabhakaran, M., Sahai, A.: Positive results and techniques for obfuscation. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 20–39. Springer, Heidelberg (2004) CrossRef

[McC90]

McCurley, K.S.: The discrete logarithm problem. In: Proceedings of the AMS Symposia in Applied Mathematics: Computational Number Theory and Cryptography, pp. 49–74. American Mathematical Society (1990)

[MMN+15]

Mahmoody, M., Mohammed, A., Nematihaji, S., Pass, R., Shelat, A.: Lower bounds on assumptions behind indistinguishability obfuscation (2015, in Submission)

[Pas15]

Pass, R., Shelat, A.: Impossibility of vbb obfuscation with ideal constant-degree graded encodings. Cryptology ePrint Archive, Report 2015/383 (2015). http://eprint.iacr.org/

[RTV04]

Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004) CrossRef

[Sho97]

Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997) CrossRef

[Wee05]

Wee, H.: On obfuscating point functions. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 523–532. ACM (2005)

Titel: On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models
verfasst von: Mohammad Mahmoody
Ameer Mohammed
Soheil Nematihaji
Verlag: Springer Berlin Heidelberg
Buch: Theory of Cryptography
Print ISBN: 978-3-662-49095-2

Electronic ISBN: 978-3-662-49096-9

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-49096-9_2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"