[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1109/SFCS.2005.60guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

On the Impossibility of Obfuscation with Auxiliary Input

Published: 23 October 2005 Publication History

Abstract

Barak et al. formalized the notion of obfuscation, and showed that there exist (contrived) classes of functions that cannot be obfuscated. In contrast, Canetti and Wee showed how to obfuscate point functions, under various complexity assumptions. Thus, it would seem possible that most programs of interest can be obfuscated even though in principle general purpose obfuscators do not exist. We show that this is unlikely to be the case. In particular, we consider the notion of obfuscation w.r.t. auxiliary input, which corresponds to the setting where the adversary, which is given the obfuscated circuit, may have some additional a priori information. This is essentially the case of interest in any usage of obfuscation we can imagine. We prove that there exist many natural classes of functions that cannot be obfuscated w.r.t. auxiliary input, both when the auxiliary input is dependent of the function being obfuscated and even when the auxiliary input is independent of the function being obfuscated. We also give a positive result. In particular, we show that any obfuscator for the class of point functions is also an obfuscator w.r.t. independent auxiliary input.

References

[1]
B. Barak. How to Go Beyond the Black-Box Simulation Barrier. In 42nd FOCS , pages 106-115, 2001.
[2]
B. Barak:, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, K. Yang On the (Im)possibility of Obfuscating Programs. In CRYPTO 2001 , pages 1-18.
[3]
R. Canetti. Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information. CRYPTO 1997 , pages 455-469.
[4]
R. Canetti, D. Micciancio, and O. Reingold. Perfectly One-Way Probabilistic Hash Functions. In Proceeding of STOC 1998 .
[5]
O. Goldreich. Foundations of Cryptography: Vol. 1: Basic Tools . Cambridge University Press, 2001.
[6]
O. Goldreich. Foundations of Cryptography: Vol. 2: Basic Applications . Cambridge University Press, 2004.
[7]
O. Goldrekh and L.A. Levin. A Hard-Core Predicate for all One-Way functions. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing , pages 25-32, 1989.
[8]
S. Goldwasser and S. Micali. Probabiilistic encryption. in Journal of Computer and System Sciences , 28:270-299, 1984.
[9]
G. Goldreich, S. Goldwasser, and S. Micali. How to Construct Random Functions. In Journal of the ACM , 33(4), 1984, 792-804.
[10]
S. Goldwasser, S. Micali, R. L. Rivest A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. In SIAM Journal of Computation , 17(2): 281-308 (1988).
[11]
O. Goldreich and Y. Oren. Definitions and Properties of Zero-Knowledge Proof Systems. In Journal of Cryptology , Vol. 7, No. 1, pages 1-32, 1994.
[12]
S. Hada. Zero-Knowledge and Code Obfuscation. In Advances in Cryptology - ASIACRYPT '00 .
[13]
J. Hastad, R. Impagliazzo, L.A. Levin, M. Luby. A Pseudorandom Generator from any One-Way Function. In SIAM Journal on Computing 28 (1999), pages 1364-1396 (electronic).
[14]
B. Lynn, M. Prabhakaran, and A. Sahai. Positive Results and Techniques for Obfuscation. In Proceedings of Eurocrypt , 2004.
[15]
H. Wee. On Obfuscating Point Functions. In eprint 2005/001.

Cited By

View all
  • (2021)Indistinguishability obfuscation from circular securityProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451070(736-749)Online publication date: 15-Jun-2021
  • (2021)Impossibility of Quantum Virtual Black-Box Obfuscation of Classical CircuitsAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84242-0_18(497-525)Online publication date: 16-Aug-2021
  • (2019)A survey of leakage-resilient cryptographyProviding Sound Foundations for Cryptography10.1145/3335741.3335768(727-794)Online publication date: 4-Oct-2019
  • Show More Cited By

Index Terms

  1. On the Impossibility of Obfuscation with Auxiliary Input

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image Guide Proceedings
      FOCS '05: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science
      October 2005
      645 pages
      ISBN:0769524680

      Publisher

      IEEE Computer Society

      United States

      Publication History

      Published: 23 October 2005

      Qualifiers

      • Article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 22 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2021)Indistinguishability obfuscation from circular securityProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451070(736-749)Online publication date: 15-Jun-2021
      • (2021)Impossibility of Quantum Virtual Black-Box Obfuscation of Classical CircuitsAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84242-0_18(497-525)Online publication date: 16-Aug-2021
      • (2019)A survey of leakage-resilient cryptographyProviding Sound Foundations for Cryptography10.1145/3335741.3335768(727-794)Online publication date: 4-Oct-2019
      • (2019)IND-secure quantum symmetric encryption based on point obfuscationQuantum Information Processing10.1007/s11128-019-2280-z18:6(1-16)Online publication date: 1-Jun-2019
      • (2018)Indistinguishability Obfuscation from Functional EncryptionJournal of the ACM10.1145/323451165:6(1-37)Online publication date: 19-Nov-2018
      • (2018)Protecting million-user iOS apps with obfuscationProceedings of the 40th International Conference on Software Engineering: Software Engineering in Practice10.1145/3183519.3183524(235-244)Online publication date: 27-May-2018
      • (2017)Stochastic optimization of program obfuscationProceedings of the 39th International Conference on Software Engineering10.1109/ICSE.2017.28(221-231)Online publication date: 20-May-2017
      • (2017)On the Implausibility of Differing-Inputs Obfuscation and Extractable Witness Encryption with Auxiliary InputAlgorithmica10.1007/s00453-017-0276-679:4(1353-1373)Online publication date: 1-Dec-2017
      • (2017)On Virtual Grey Box Obfuscation for General CircuitsAlgorithmica10.1007/s00453-016-0218-879:4(1014-1051)Online publication date: 1-Dec-2017
      • (2017)Obfuscating ConjunctionsJournal of Cryptology10.1007/s00145-015-9221-530:1(289-320)Online publication date: 1-Jan-2017
      • Show More Cited By

      View Options

      View options

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media