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:
Cover of the book

2016 | OriginalPaper | Chapter

Impossibility of VBB Obfuscation with Ideal Constant-Degree Graded Encodings

Authors : Rafael Pass, Abhi Shelat

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

A celebrated result by Barak et al. (Crypto’01) shows the impossibility of general-purpose virtual black-box (VBB) obfuscation in the plain model. A recent work by Canetti, Kalai, and Paneth (TCC’15) extends this impossibility result to the random oracle model (assuming trapdoor permutations).
In contrast, Brakerski-Rothblum (TCC’14) and Barak et al. (EuroCrypt’14) show that in idealized graded encoding models, general-purpose VBB obfuscation indeed is possible; these constructions require graded encoding schemes that enable evaluating high-degree (polynomial in the size of the circuit to be obfuscated) polynomials on encodings.
We show a complementary impossibility of general-purpose VBB obfuscation in idealized graded encoding models that enable only evaluation of constant-degree polynomials (assuming trapdoor permutations).

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
next chapter On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models
Footnotes
1
A similar simulation-based, but even stronger, notion of security was previously defined by Hada [Had00]. Even earlier, Canetti [Can97] considered a similar notion of security (without explicitly referring to obfuscation) for the special case of what is now referred to as point-function obfuscation.
 
2
The construction of [GGH+13b] was proved to satisfy the weaker notion of indistinguishability obfuscation in an idealized “matrix-multiplication” model.
 
3
The constructions in [BR14, BGK+14] require certain additional “set-based” restrictions on polynomials; we return to this in Sect. 2.2.
 
4
That is, whose circuit size is bounded by \(T(n) = poly(2^{n^{\alpha }})\) for any \(0<\alpha <1\).
 
5
That is, security holds against all circuits whose size is bounded by \(T(n) = poly(2^{n^{\alpha }})\) for any \(0<\alpha <1\).
 
6
In particular, even if the same value v is encoded twice (under the same label), independently random handles are returned for the two encodings. This model thus considers randomized graded encodings. Our results also apply to deterministic randomized encodings where the oracle keeps state also during the encoding phase and always returns the same handle for an encoding of the value v under the label l.
 
7
To make this argument it is important that we allow adaptive encodings during the initialization phase, as opposed to a single non-adaptive encoding query as in the definition of [BGK+14].
 
8
For this emulation with “bogus” random handles to work, it is important that we consider a model of randomized graded encodings (where multiple encodings of the same value are given fresh random handles). In case the encoding is deterministic (and thus encodings of the same value need to be given the same handle) the simulation fails: if the result of the operation yields a value that was previously encoded we should output that handle instead. Nevertheless, as we point out at the end of Sect. 3, our results extend to deal also with deterministic encodings where players can perform operations on the encodings.
 
9
[BGK+14] present unconditionally secure obfuscators for NC1; the LWE assumption is needed to bootstrap up to polynomial-size circuits.
 
10
The only non-uniform advice needed is the prime \(q_n\).
 
11
1 / |k| can be replaced by any inverse polynomial by appropriately adjusting the parameters in our proof.
 
12
The non-uniformity in our construction is to encode the sequence of primes \(q_1,q_2,\ldots \) that is implicit in the oracle \(M^g\). If we model the oracle M with a uniform algorithm that picks the field for each security parameter, then our construction below can also be uniform.
 
13
Step 2 (i.e., checking whether the initial encoding queries have been made) can be simulated by making a “dummy” enc(0, 0) query and checking whether M returns \(\bot \).
 
Literature
[AB15]
Applebaum, B., Brakerski, Z.: Obfuscating circuits via composite-order graded encoding. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 528–556. Springer, Heidelberg (2015) CrossRef
[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+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: STOC 2013 (2013)
[BR93]
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, CCS 1993, 3–5 November 1993, Fairfax, Virginia, USA, pp. 62–73 (1993)
[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
[BS03]
[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
[CKP15]
Canetti, R., Kalai, Y.T., Paneth, O.: On obfuscation with random oracles. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 456–467. Springer, Heidelberg (2015) CrossRef
[CV13]
[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: Proceedings of FOCS 2013 (2013)
[Had00]
Hada, S.: Zero-knowledge and code obfuscation. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 443–457. Springer, Heidelberg (2000) CrossRef
[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
[MMN15]
Mahmoody, M., Mohammed, A., Nematihaji, S.: More on impossibility of virtual black-box obfuscation in idealized models. In: TCC 2016 (2015, to appear)
[PST14]
Pass, R., Seth, K., Telang, S.: Indistinguishability obfuscation from semantically-secure multilinear encodings. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 500–517. Springer, Heidelberg (2014) CrossRef
[Rot13]
Rothblum, R.D.: On the circular security of bit-encryption. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 579–598. Springer, Heidelberg (2013) 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
Metadata
Title
Impossibility of VBB Obfuscation with Ideal Constant-Degree Graded Encodings
Authors
Rafael Pass
Abhi Shelat
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_1

Premium Partner

    Image Credits