Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Impossibility of VBB Obfuscation with Ideal Constant-Degree Graded Encodings Read chapter Read first chapter

2016 | OriginalPaper | Chapter

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

Authors : Mohammad Mahmoody, Ameer Mohammed, Soheil Nematihaji

Published in: Theory of Cryptography

Publisher: Springer Berlin Heidelberg

Log in

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

search-config
loading …

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.

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
previous chapter Impossibility of VBB Obfuscation with Ideal Constant-Degree Graded Encodings
next chapter Lower Bounds on Assumptions Behind Indistinguishability Obfuscation
Footnotes
1
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.
 
2
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.
 
3
Even though the summation is technically defined over the group elements, for simplicity we use the addition operation over the labels as well.
 
4
Note that this is even the case for \({\mathbb Z}_q\) when q is a prime power, although finite fields have prime power sizes.
 
5
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.
 
6
So the oracle might return \(\bot \) even if the two labels are in the range of \(\sigma (G)\).
 
7
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.
 
8
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}\).
 
9
Note that we do not have access to the set \(Q_\sigma \) that was used for consistent lazy evaluation of \(\sigma (\cdot )\).
 
10
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!
 
11
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.
 
12
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.
 
Literature
[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]
[CKP15]
[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]
[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)
Metadata
Title
On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models
Authors
Mohammad Mahmoody
Ameer Mohammed
Soheil Nematihaji
Copyright Year
2016
Publisher
Springer Berlin Heidelberg
Book
Theory of Cryptography

Print ISBN: 978-3-662-49095-2

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

Copyright Year: 2016

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

Premium Partner

    Image Credits