The impossibility of obfuscation with auxiliary input or a universal simulator

Nir Bitansky; Ran Canetti; Henry Cohn; Shafi Goldwasser; Yael Tauman Kalai; Omer Paneth; Alon Rosen

doi:10.1007/978-3-662-44381-1_5

The impossibility of obfuscation with auxiliary input or a universal simulator

Nir Bitansky, Ran Canetti, Henry Cohn, Shafi Goldwasser, Yael Tauman Kalai, Omer Paneth, Alon Rosen

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In this paper we show that indistinguishability obfuscation for general circuits implies, somewhat counterintuitively, strong impossibility results for virtual black box obfuscation. In particular, it implies: - The impossibility of average-case virtual black box obfuscation with auxiliary input for any circuit family with super-polynomial pseudo-entropy (for example, many cryptographic primitives). Impossibility holds even when the auxiliary input depends only on the public circuit family, and not which circuit in the family is being obfuscated. - The impossibility of average-case virtual black box obfuscation with a universal simulator (with or without any auxiliary input) for any circuit family with super-polynomial pseudo-entropy. These bounds significantly strengthen the impossibility results of Goldwasser and Kalai (FOCS 2005).

Original language	English (US)
Title of host publication	Advances in Cryptology, CRYPTO 2014 - 34th Annual Cryptology Conference, Proceedings
Publisher	Springer Verlag
Pages	71-89
Number of pages	19
Edition	PART 2
ISBN (Print)	9783662443804
DOIs	https://doi.org/10.1007/978-3-662-44381-1_5
State	Published - 2014
Event	34rd Annual International Cryptology Conference, CRYPTO 2014 - Santa Barbara, CA, United States Duration: Aug 17 2014 → Aug 21 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	8617 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	34rd Annual International Cryptology Conference, CRYPTO 2014
Country/Territory	United States
City	Santa Barbara, CA
Period	8/17/14 → 8/21/14

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-662-44381-1_5

Cite this

Bitansky, N., Canetti, R., Cohn, H., Goldwasser, S., Kalai, Y. T., Paneth, O., & Rosen, A. (2014). The impossibility of obfuscation with auxiliary input or a universal simulator. In Advances in Cryptology, CRYPTO 2014 - 34th Annual Cryptology Conference, Proceedings (PART 2 ed., pp. 71-89). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8617 LNCS, No. PART 2). Springer Verlag. https://doi.org/10.1007/978-3-662-44381-1_5

The impossibility of obfuscation with auxiliary input or a universal simulator. / Bitansky, Nir; Canetti, Ran; Cohn, Henry et al.
Advances in Cryptology, CRYPTO 2014 - 34th Annual Cryptology Conference, Proceedings. PART 2. ed. Springer Verlag, 2014. p. 71-89 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8617 LNCS, No. PART 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bitansky, N, Canetti, R, Cohn, H, Goldwasser, S, Kalai, YT, Paneth, O & Rosen, A 2014, The impossibility of obfuscation with auxiliary input or a universal simulator. in Advances in Cryptology, CRYPTO 2014 - 34th Annual Cryptology Conference, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 8617 LNCS, Springer Verlag, pp. 71-89, 34rd Annual International Cryptology Conference, CRYPTO 2014, Santa Barbara, CA, United States, 8/17/14. https://doi.org/10.1007/978-3-662-44381-1_5

Bitansky N, Canetti R, Cohn H, Goldwasser S, Kalai YT, Paneth O et al. The impossibility of obfuscation with auxiliary input or a universal simulator. In Advances in Cryptology, CRYPTO 2014 - 34th Annual Cryptology Conference, Proceedings. PART 2 ed. Springer Verlag. 2014. p. 71-89. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-662-44381-1_5

Bitansky, Nir ; Canetti, Ran ; Cohn, Henry et al. / The impossibility of obfuscation with auxiliary input or a universal simulator. Advances in Cryptology, CRYPTO 2014 - 34th Annual Cryptology Conference, Proceedings. PART 2. ed. Springer Verlag, 2014. pp. 71-89 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{4d3187109c5b4a34a7589848cec15dd1,

title = "The impossibility of obfuscation with auxiliary input or a universal simulator",

abstract = "In this paper we show that indistinguishability obfuscation for general circuits implies, somewhat counterintuitively, strong impossibility results for virtual black box obfuscation. In particular, it implies: - The impossibility of average-case virtual black box obfuscation with auxiliary input for any circuit family with super-polynomial pseudo-entropy (for example, many cryptographic primitives). Impossibility holds even when the auxiliary input depends only on the public circuit family, and not which circuit in the family is being obfuscated. - The impossibility of average-case virtual black box obfuscation with a universal simulator (with or without any auxiliary input) for any circuit family with super-polynomial pseudo-entropy. These bounds significantly strengthen the impossibility results of Goldwasser and Kalai (FOCS 2005).",

author = "Nir Bitansky and Ran Canetti and Henry Cohn and Shafi Goldwasser and Kalai, {Yael Tauman} and Omer Paneth and Alon Rosen",

year = "2014",

doi = "10.1007/978-3-662-44381-1_5",

language = "English (US)",

isbn = "9783662443804",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

number = "PART 2",

pages = "71--89",

booktitle = "Advances in Cryptology, CRYPTO 2014 - 34th Annual Cryptology Conference, Proceedings",

edition = "PART 2",

note = "34rd Annual International Cryptology Conference, CRYPTO 2014 ; Conference date: 17-08-2014 Through 21-08-2014",

}

TY - GEN

T1 - The impossibility of obfuscation with auxiliary input or a universal simulator

AU - Bitansky, Nir

AU - Canetti, Ran

AU - Cohn, Henry

AU - Goldwasser, Shafi

AU - Kalai, Yael Tauman

AU - Paneth, Omer

AU - Rosen, Alon

PY - 2014

Y1 - 2014

N2 - In this paper we show that indistinguishability obfuscation for general circuits implies, somewhat counterintuitively, strong impossibility results for virtual black box obfuscation. In particular, it implies: - The impossibility of average-case virtual black box obfuscation with auxiliary input for any circuit family with super-polynomial pseudo-entropy (for example, many cryptographic primitives). Impossibility holds even when the auxiliary input depends only on the public circuit family, and not which circuit in the family is being obfuscated. - The impossibility of average-case virtual black box obfuscation with a universal simulator (with or without any auxiliary input) for any circuit family with super-polynomial pseudo-entropy. These bounds significantly strengthen the impossibility results of Goldwasser and Kalai (FOCS 2005).

AB - In this paper we show that indistinguishability obfuscation for general circuits implies, somewhat counterintuitively, strong impossibility results for virtual black box obfuscation. In particular, it implies: - The impossibility of average-case virtual black box obfuscation with auxiliary input for any circuit family with super-polynomial pseudo-entropy (for example, many cryptographic primitives). Impossibility holds even when the auxiliary input depends only on the public circuit family, and not which circuit in the family is being obfuscated. - The impossibility of average-case virtual black box obfuscation with a universal simulator (with or without any auxiliary input) for any circuit family with super-polynomial pseudo-entropy. These bounds significantly strengthen the impossibility results of Goldwasser and Kalai (FOCS 2005).

UR - http://www.scopus.com/inward/record.url?scp=84905402107&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84905402107&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-44381-1_5

DO - 10.1007/978-3-662-44381-1_5

M3 - Conference contribution

AN - SCOPUS:84905402107

SN - 9783662443804

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 71

EP - 89

BT - Advances in Cryptology, CRYPTO 2014 - 34th Annual Cryptology Conference, Proceedings

PB - Springer Verlag

T2 - 34rd Annual International Cryptology Conference, CRYPTO 2014

Y2 - 17 August 2014 through 21 August 2014

ER -

The impossibility of obfuscation with auxiliary input or a universal simulator

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this