skip to main content
10.1145/2591796.2591859acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
research-article

On the existence of extractable one-way functions

Published: 31 May 2014 Publication History

Abstract

A function f is extractable if it is possible to algorithmically "extract," from any adversarial program that outputs a value y in the image of f; a preimage of y. When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions.
We make two headways in the study of the existence of extractable one-way functions (EOWFs). On the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length.
On the positive side, for adversarial programs with bounded auxiliary input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zero-knowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions.

Supplementary Material

MP4 File (p505-sidebyside.mp4)

References

[1]
Barak, B. How to go beyond the black-box simulation barrier. In FOCS (2001), pp. 106--115.
[2]
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S. P., and Yang, K. On the (im)possibility of obfuscating programs. In CRYPTO (2001), pp. 1--18.
[3]
Barak, B., Lindell, Y., and Vadhan, S. P. Lower bounds for non-black-box zero knowledge. J. Comput. Syst. Sci. 72, 2 (2006), 321--391.
[4]
Bellare, M., and Palacio, A. The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols. In Proceedings of the 24th Annual International Cryptology Conference (2004), pp. 273--289.
[5]
Bellare, M., and Palacio, A. Towards plaintext-aware public-key encryption without random oracles. In ASIACRYPT (2004), pp. 48--62.
[6]
Bitansky, N., Canetti, R., Chiesa, A., Goldwasser, S., Lin, H., Tromer, E., and Rubinstein, A. The haunting of the snark. Manuscript (2013).
[7]
Bitansky, N., Canetti, R., Chiesa, A., and Tromer, E. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (2012), ITCS '12, pp. 326--349.
[8]
Bitansky, N., Canetti, R., Chiesa, A., and Tromer, E. Recursive composition and bootstrapping for snarks and proof-carrying data. In STOC (2013), pp. 111--120.
[9]
Bitansky, N., Canetti, R., Cohn, H., Goldwasser, S., Kalai, Y. T., Paneth, O., and Rosen, A. The impossibility of obfuscation with auxiliary input or a universal simulator. CoRR abs/1401.0348 (2014).
[10]
Bitansky, N., and Chiesa, A. Succinct arguments from multi-prover interactive proofs and their efficiency benefits. In CRYPTO (2012), pp. 255--272.
[11]
Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., and Paneth, O. Succinct non-interactive arguments via linear interactive proofs. In TCC (2013), pp. 315--333.
[12]
Boneh, D., Segev, G., and Waters, B. Targeted malleability: homomorphic encryption for restricted computations. In ITCS (2012), pp. 350--366.
[13]
Boneh, D., and Waters, B. Constrained pseudorandom functions and their applications. IACR Cryptology ePrint Archive 2013 (2013), 352.
[14]
Boneh, D., and Zhandry, M. Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. IACR Cryptology ePrint Archive 2013 (2013), 642.
[15]
Boyle, E., Goldwasser, S., and Ivan, I. Functional signatures and pseudorandom functions. IACR Cryptology ePrint Archive 2013 (2013), 401.
[16]
Boyle, E., and Pass, R. Limits of extractability assumptions with distributional auxiliary input. IACR Cryptology ePrint Archive 2013 (2013), 703.
[17]
Canetti, R., and Dakdouk, R. R. Extractable perfectly one-way functions. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (2008), pp. 449--460.
[18]
Canetti, R., and Dakdouk, R. R. Towards a theory of extractable functions. In TCC (2009), pp. 595--613.
[19]
Chung, K.-M., and Pass, H. L. R. Constant-round concurrent zero knowledge from p-certificates. In FOCS (2013).
[20]
Coron, J.-S., Lepoint, T., and Tibouchi, M. Practical multilinear maps over the integers. In CRYPTO (1) (2013), pp. 476--493.
[21]
Damgård, I. Towards practical public key systems secure against chosen ciphertext attacks. In Proceedings of CRYPTOâĂŹ91 (1992), pp. 445--456.
[22]
Damgård, I., Faust, S., and Hazay, C. Secure two-party computation with low communication. In TCC (2012), pp. 54--74.
[23]
Di Crescenzo, G., and Lipmaa, H. Succinct NP proofs from an extractability assumption. In Proceedings of the 4th Conference on Computability in Europe (2008), pp. 175--185.
[24]
Dwork, C., and Naor, M. Zaps and their applications. SIAM J. Comput. 36, 6 (2007), 1513--1543.
[25]
Feige, U., Lapidot, D., and Shamir, A. Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29, 1 (1999), 1--28.
[26]
Garg, S., Gentry, C., and Halevi, S. Candidate multilinear maps from ideal lattices. In EUROCRYPT (2013), pp. 1--17.
[27]
Garg, S., Gentry, C., Halevi, S., and Raykova, M. Two-round secure mpc from indistinguishability obfuscation. IACR Cryptology ePrint Archive 2013 (2013), 601.
[28]
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., and Waters, B. Candidate indistinguishability obfuscation and functional encryption for all circuits. In FOCS (2013).
[29]
Gennaro, R., Gentry, C., Parno, B., and Raykova, M. Quadratic span programs and succinct nizks without pcps. In EUROCRYPT (2013), pp. 626--645.
[30]
Gentry, C., Halevi, S., and Vaikuntanathan, V. i-hop homomorphic encryption and rerandomizable yao circuits. In CRYPTO (2010), pp. 155--172.
[31]
Gentry, C., and Wichs, D. Separating succinct non-interactive arguments from all falsifiable assumptions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (2011), pp. 99--108.
[32]
Goldreich, O., Goldwasser, S., and Micali, S. How to construct random functions. J. ACM 33, 4 (1986), 792--807.
[33]
Goldreich, O., and Krawczyk, H. On the composition of zero-knowledge proof systems. SIAM J. Comput. 25, 1 (1996), 169--192.
[34]
Goldreich, O., Micali, S., and Wigderson, A. How to play any mental game. In STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing (1987), pp. 218--229.
[35]
Goldreich, O., and Oren, Y. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology 7, 1 (December 1994), 1--32.
[36]
Goldwasser, S., and Kalai, Y. T. On the impossibility of obfuscation with auxiliary input. In FOCS (2005), pp. 553--562.
[37]
Goldwasser, S., Lin, H., and Rubinstein, A. Delegation of computation without rejection problem from designated verifier CS-proofs. Cryptology ePrint Archive, Report 2011/456, 2011.
[38]
Goldwasser, S., Micali, S., and Rackoff, C. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 1 (1989), 186--208.
[39]
Groth, J. Short pairing-based non-interactive zero-knowledge arguments. In Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security (2010), pp. 321--340.
[40]
Hada, S., and Tanaka, T. On the existence of 3-round zero-knowledge protocols. In Proceedings of the 18th Annual International Cryptology Conference (1998), pp. 408--423.
[41]
Hohenberger, S., Sahai, A., and Waters, B. Replacing a random oracle: Full domain hash from indistinguishability obfuscation. IACR Cryptology ePrint Archive 2013 (2013), 509.
[42]
Kalai, Y. T., Raz, R., and Rothblum, R. D. How to delegate computations: The power of no-signaling proofs. In STOC (2014).
[43]
Kiayias, A., Papadopoulos, S., Triandopoulos, N., and Zacharias, T. Delegatable pseudorandom functions and applications. IACR Cryptology ePrint Archive 2013 (2013), 379.
[44]
Koppula, V., Ramchen, K., and Waters, B. Separations in circular security for arbitrary length key cycles. IACR Cryptology ePrint Archive 2013 (2013), 683.
[45]
Lipmaa, H. Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In TCC (2012), pp. 169--189.
[46]
Lipmaa, H. Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes. IACR Cryptology ePrint Archive 2013 (2013), 121.
[47]
Micali, S. Computationally sound proofs. SIAM Journal on Computing 30, 4 (2000), 1253--1298. Preliminary version appeared in FOCS '94.
[48]
Mie, T. Polylogarithmic two-round argument systems. Journal of Mathematical Cryptology 2, 4 (2008), 343--363.
[49]
Naor, M. On cryptographic assumptions and challenges. In Proceedings of the 23rd Annual International Cryptology Conference (2003), pp. 96--109.
[50]
Pass, R., and Wee, H. Black-box constructions of two-party protocols from one-way functions. In TCC (2009), pp. 403--418.
[51]
Sahai, A., and Waters, B. How to use indistinguishability obfuscation: Deniable encryption, and more. In STOC (2014).

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing
May 2014
984 pages
ISBN:9781450327107
DOI:10.1145/2591796
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2014

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Funding Sources

Conference

STOC '14
Sponsor:
STOC '14: Symposium on Theory of Computing
May 31 - June 3, 2014
New York, New York

Acceptance Rates

STOC '14 Paper Acceptance Rate 91 of 319 submissions, 29%;
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
June 23 - 27, 2025
Prague , Czech Republic

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)17
  • Downloads (Last 6 weeks)2
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Batching Adaptively-Sound SNARGs for NPTheory of Cryptography10.1007/978-3-031-78017-2_12(339-370)Online publication date: 28-Nov-2024
  • (2024)NIZKs with Maliciously Chosen CRS: Subversion Advice-ZK and Accountable SoundnessSecurity and Cryptography for Networks10.1007/978-3-031-71070-4_1(3-23)Online publication date: 11-Sep-2024
  • (2024)Constant-Size zk-SNARKs in ROM from Falsifiable AssumptionsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58751-1_2(34-64)Online publication date: 26-May-2024
  • (2024)Witness Semantic SecurityAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58740-5_6(155-184)Online publication date: 29-Apr-2024
  • (2023)A Simple and Efficient Framework of Proof Systems for NPAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8724-5_6(174-207)Online publication date: 19-Dec-2023
  • (2023)Non-interactive Zero-Knowledge from Non-interactive Batch ArgumentsAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38545-2_2(38-71)Online publication date: 9-Aug-2023
  • (2023)Knowledge Encryption and Its Applications to Simulatable Protocols with Low Round-ComplexityAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22969-5_12(334-362)Online publication date: 25-Jan-2023
  • (2023)Fully Succinct Batch Arguments for $$\textsf{NP}$$ from Indistinguishability ObfuscationTheory of Cryptography10.1007/978-3-031-22318-1_19(526-555)Online publication date: 1-Jan-2023
  • (2022)Weak Zero-Knowledge beyond the Black-Box BarrierSIAM Journal on Computing10.1137/20M131956552:2(STOC19-156-STOC19-199)Online publication date: 27-Jan-2022
  • (2022)Incrementally Verifiable Computation via Rate-1 Batch Arguments2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00102(1045-1056)Online publication date: Oct-2022
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media