nach oben

Journal of Cryptology

Erschienen in:

01.04.2014

On Strong Simulation and Composable Point Obfuscation

verfasst von: Nir Bitansky, Ran Canetti

Erschienen in: Journal of Cryptology | Ausgabe 2/2014

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The Virtual Black Box (VBB) property for program obfuscators provides a strong guarantee: anything computable by an efficient adversary, given the obfuscated program, can also be computed by an efficient simulator, with only oracle access to the program. However, we know how to achieve this notion only for very restricted classes of programs.

This work studies a simple relaxation of VBB: allow the simulator unbounded computation time, while still allowing only polynomially many queries to the oracle. We demonstrate the viability of this relaxed notion, which we call Virtual Grey Box (VGB), in the context of composable obfuscators for point programs: it is known that, with respect to VBB, if such obfuscators exist, then there exist multi-bit point obfuscators (also known as “digital lockers”) and subsequently also very strong variants of encryption that are resilient to various attacks, such as key leakage and key-dependent-messages. However, no composable VBB-obfuscators for point programs have been shown. We show composable VGB-obfuscators for point programs under a strong variant of the Decision Diffie–Hellman assumption. We show that VGB (instead of VBB) obfuscation still suffices for the above applications, as well as for new applications. This includes extensions to the public key setting and to encryption schemes with resistance to certain related key attacks (RKA).

Vorheriger Artikel On the Amortized Complexity of Zero-Knowledge Protocols

Nächster Artikel Computationally Secure Pattern Matching in the Presence of Malicious Adversaries

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

Nur mit Berechtigung zugänglich

As noted by [4], the following can be replaced with the equivalent requirement that \(|\Pr[\mathcal{A}(\mathcal{O}(C))=\pi(C)]-\Pr [\mathcal{S}^{C}(1^{|C|})=\pi(C)]|\leq\frac{1}{p(n)}\), for any predicate \(\pi:\mathcal{C}_{n}\rightarrow\{0,1\}\). Also the size of the simulator can depend on p(n), namely the required simulation quality.

See the section on applications in [4] for more details.

Formally, one should also set a time out mechanism to deal with other inputs.

Note that \(k=|\mathcal{O}(F_{\alpha ,\beta, \beta'})|\geq n\) so \(\mathcal{A}\) is allowed poly(n) steps.

DI should not be confused with Indistinguishability Obfuscators of [4], which were presented in Definition 3.2.

For example, cmb _{2,5}((a,b),(c,d,e))=(c,a,d,e,b).

Any pair \((\bar {x},I)\) should be thought of as partial information on a tuple of size t with the elements of \(\bar {x}\) in the indices I.

If t≥logn then \(|G_{n}^{t}| \geq\binom{n}{\log n} \geq( \frac{n}{\log n} )^{\log n}\) and otherwise \(|G_{n}^{t}| \geq \binom{n}{t}\geq(\frac{n}{t})^{t} \geq(\frac {n}{\log n})^{\omega(1)}\).

Adding such an oracle allows the algorithm to get the encoding of any arbitrary element in ℤ_p by applying ADD _σ (in particular, it could sample random elements).

Formally, these are defined on a joint probability space, where both the original and altered interaction are executed, and it refers to the polynomials determined by the altered interaction. In particular, these polynomials are independent of \(\bar {x},\bar {u}\).

This can be equivalently formulated as an adaptive definition where the family of correlation functions is polynomially bounded.

To be more accurate, we should first note that for all large enough n∈ℕ and any z∈{0,1}^q(n) there is indeed a circuit with the required property. Then we can restrict our discussion to all large enough n’s.

[1]

B. Applebaum, D. Harnik, Y. Ishai, Semantic security under related-key attacks and applications, in ICS (2011), pp. 45–60

[2]

B. Applebaum, Fast cryptographic primitives based on the hardness of decoding random linear code. Technical Report TR-845-08, Princeton University (2008). Available at ftp://ftp.cs.princeton.edu/techreports/2008/845.pdf

[3]

B. Adida, D. Wikström, How to shuffle in public, in TCC (2007), pp. 555–574

[4]

B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S.P. Vadhan, K. Yang, On the (im)possibility of obfuscating programs, in CRYPTO (2001), pp. 1–18

[5]

D. Boneh, S. Halevi, M. Hamburg, R. Ostrovsky, Circular-secure encryption from decision Diffie–Hellman, in CRYPTO (2008), pp. 108–125

[6]

D. Boneh, The decision Diffie–Hellman problem, in ANTS (1998), pp. 48–63

[7]

J. Black, P. Rogaway, T. Shrimpton, Encryption-scheme security in the presence of key-dependent messages, in Selected Areas in Cryptography (2002), pp. 62–75

[8]

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

[9]

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

[10]

R. Canetti, Y. Tauman Kalai, M. Varia, D. Wichs, On symmetric encryption and point obfuscation, in TCC (2010), pp. 52–71

[11]

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

[12]

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

[13]

R. Canetti, M. Varia, Non-malleable obfuscation, in TCC (2009), pp. 73–90

[14]

Y. Dodis, A. Smith, Correcting errors without leaking partial information, in STOC (2005), pp. 654–663

[15]

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

[16]

O. Goldreich, L.A. Levin, A hard-core predicate for all one-way functions, in STOC ’89: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing (ACM, New York, 1989), pp. 25–32 CrossRef

[17]

S. Goldwasser, G.N. Rothblum, On best-possible obfuscation, in TCC (2007), pp. 194–213

[18]

S. Hada, Secure obfuscation for encrypted signatures, in Eurocrypt (2010)

[19]

I. Haitner, T. Holenstein, On the (im)possibility of key dependent encryption, in TCC (2009), pp. 202–219

[20]

S. Halevi, H. Krawczyk, Security under key-dependent inputs, in ACM Conference on Computer and Communications Security (2007), pp. 466–475

[21]

D. Hofheinz, M.-L. John, M. Stam, Obfuscation for cryptographic purposes, in TCC (2007), pp. 214–232

[22]

S. Hohenberger, G.N. Rothblum, A. Shelat, V. Vaikuntanathan, Securely obfuscating re-encryption, in TCC (2007), pp. 233–252

[23]

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

[24]

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

[25]

H. Wee, On obfuscating point functions, in STOC (2005), pp. 523–532

Titel: On Strong Simulation and Composable Point Obfuscation
verfasst von: Nir Bitansky
Ran Canetti
Publikationsdatum: 01.04.2014
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 2/2014
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-013-9146-9

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"

Weitere Artikel der Ausgabe 2/2014

Better Security for Deterministic Public-Key Encryption: The Auxiliary-Input Setting

Four-Dimensional Gallant–Lambert–Vanstone Scalar Multiplication

On the Amortized Complexity of Zero-Knowledge Protocols

Improved Practical Attacks on Round-Reduced Keccak

Computationally Secure Pattern Matching in the Presence of Malicious Adversaries

Premium Partner