research-article

Non-black-box simulation from one-way functions and applications to resettable security

Authors:

Karn SethAuthors Info & Claims

STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

Pages 231 - 240

https://doi.org/10.1145/2488608.2488638

Published: 01 June 2013 Publication History

Abstract

The simulation paradigm, introduced by Goldwasser, Micali and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak (FOCS'01) introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably-sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques. The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions.

In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional benefit of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.

References

[1]

B. Barak. How to go beyond the black-box simulation barrier. In FOCS '01, pages 106--115, 2001.

Digital Library

[2]

B. Barak and O. Goldreich. Universal arguments and their applications. In Computational Complexity, pages 162--171, 2002.

Digital Library

[3]

B. Barak, O. Goldreich, S. Goldwasser, and Y. Lindell. Resettably-sound zero-knowledge and its applications. In FOCS'02, pages 116--125, 2001.

Digital Library

[4]

B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, and K. Yang. On the (im)possibility of obfuscating programs. J. ACM, 59(2):6, 2012.

Digital Library

[5]

N. Bitansky and O. Paneth. On the impossibility of approximate obfuscation and applications to resettable cryptography. In STOC, 2011.

Digital Library

[6]

N. Bitansky and O. Paneth. From the impossibility of obfuscation to a new non-black-box simulation technique. In FOCS, 2012.

Digital Library

[7]

J. Camenisch and A. Lysyanskaya. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. Advances in Cryptology, pages 93--118, 2001.

[8]

R. Canetti, O. Goldreich, S. Goldwasser, and S. Micali. Resettable zero-knowledge (extended abstract). In STOC '00, pages 235--244, 2000.

Digital Library

[9]

R. Canetti, O. Goldreich, and S. Halevi. On the random-oracle methodology as applied to length-restricted signature schemes. In TCC, pages 40--57, 2004.

[10]

R. Canetti, J. Kilian, E. Petrank, and A. Rosen. Black-box concurrent zero-knowledge requires ~! (log n) rounds. In STOC '01, pages 570--579, 2001.

Digital Library

[11]

Y. Deng, V. Goyal, and A. Sahai. Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 251--260. IEEE, 2009.

Digital Library

[12]

O. Goldreich. Foundations of Cryptography | Basic Tools. Cambridge University Press, 2001.

Digital Library

[13]

O. Goldreich and A. Kahan. How to construct constant-round zero-knowledge proof systems for NP. Journal of Cryptology, 9(3):167--190, 1996.

Digital Library

[14]

O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. J. ACM, 38(3):691--729, 1991.

Digital Library

[15]

O. Goldreich and Y. Oren. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology, 7:1--32, 1994.

Digital Library

[16]

S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186--208, 1989.

Digital Library

[17]

J. Håstad, R. Impagliazzo, L. Levin, and M. Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28:12--24, 1999.

Digital Library

[18]

H. Lin and R. Pass. Constant-round non-malleable commitments from any one-way function. In STOC, pages 705--714, 2011.

Digital Library

[19]

R. Merkle. Digital signature system and method based on a conventional encryption function, Nov. 14 1989. US Patent 4,881,264.

[20]

S. Micali. Computationally sound proofs. SIAM Journal on Computing, 30(4):1253--1298, 2000.

Digital Library

[21]

M. Naor. Bit commitment using pseudorandomness. Journal of Cryptology, 4(2):151--158, 1991.

Digital Library

[22]

M. Naor and M. Yung. Universal one-way hash functions and their cryptographic applications. In STOC '89, pages 33--43, 1989.

Digital Library

[23]

R. Ostrovsky and A. Wigderson. One-way functions are essential for non-trivial zero-knowledge. In Theory and Computing Systems, 1993, pages 3--17, 1993.

[24]

R. Pass. Bounded-concurrent secure multi-party computation with a dishonest majority. In STOC '04, pages 232--241, 2004.

Digital Library

[25]

R. Pass and A. Rosen. New and improved constructions of non-malleable cryptographic protocols. In STOC '05, pages 533--542, 2005.

Digital Library

[26]

R. Pass, W.-L. D. Tseng, and D. Wikstrom. On the composition of public-coin zero-knowledge protocols. SIAM J. Comput., 40(6):1529--1553, 2011.

Digital Library

[27]

J. Rompel. One-way functions are necessary and sufficient for secure signatures, 1990.

Cited By

VISCONTI IPointcheval D(2022)Zero‐Knowledge ProofsAsymmetric Cryptography10.1002/9781394188369.ch3(63-84)Online publication date: 30-Nov-2022
https://doi.org/10.1002/9781394188369.ch3
Bitansky NKellner MShmueli O(2021)Post-quantum Resettably-Sound Zero KnowledgeTheory of Cryptography10.1007/978-3-030-90459-3_3(62-89)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90459-3_3
Garg SLiang XPandey OVisconti I(2020)Black-Box Constructions of Bounded-Concurrent Secure ComputationSecurity and Cryptography for Networks10.1007/978-3-030-57990-6_5(87-107)Online publication date: 7-Sep-2020
https://doi.org/10.1007/978-3-030-57990-6_5
Show More Cited By

Index Terms

Non-black-box simulation from one-way functions and applications to resettable security
1. Theory of computation
  1. Models of computation
    1. Interactive computation

Recommendations

Non-Black-Box Simulation from One-Way Functions and Applications to Resettable Security

The simulation paradigm, introduced by Goldwasser, Micali, and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak [FOCS 2001, IEEE Computer Society, Los Alamitos, CA, 2001, pp. 106--115] introduced a novel ...
On Non-Black-Box Simulation and the Impossibility of Approximate Obfuscation

The introduction of a non-black-box simulation technique by Barak (FOCS 2001) has been a major landmark in cryptography, breaking the previous barriers of black-box impossibility. Barak's technique has given rise to various powerful applications and is a ...
Black-Box Constructions of Two-Party Protocols from One-Way Functions
TCC '09: Proceedings of the 6th Theory of Cryptography Conference on Theory of Cryptography
We exhibit constructions of the following two-party cryptographic protocols given only black-box access to a one-way function:
- constant-round zero-knowledge arguments (of knowledge) for any language in NP;
- constant-round trapdoor commitment schemes;
- ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

June 2013

998 pages

ISBN:9781450320290

DOI:10.1145/2488608

General Chairs:
Dan Boneh
Stanford University, USA
,
Tim Roughgarden
Stanford University, USA
,
Program Chair:
Joan Feigenbaum
Yale University, USA

Copyright © 2013 ACM.

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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'13

Sponsor:

SIGACT

STOC'13: Symposium on Theory of Computing

June 1 - 4, 2013

California, Palo Alto, USA

Acceptance Rates

STOC '13 Paper Acceptance Rate 100 of 360 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
169
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

VISCONTI IPointcheval D(2022)Zero‐Knowledge ProofsAsymmetric Cryptography10.1002/9781394188369.ch3(63-84)Online publication date: 30-Nov-2022
https://doi.org/10.1002/9781394188369.ch3
Bitansky NKellner MShmueli O(2021)Post-quantum Resettably-Sound Zero KnowledgeTheory of Cryptography10.1007/978-3-030-90459-3_3(62-89)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90459-3_3
Garg SLiang XPandey OVisconti I(2020)Black-Box Constructions of Bounded-Concurrent Secure ComputationSecurity and Cryptography for Networks10.1007/978-3-030-57990-6_5(87-107)Online publication date: 7-Sep-2020
https://doi.org/10.1007/978-3-030-57990-6_5
Badrinarayanan SJain AOstrovsky RVisconti I(2019)UC-Secure Multiparty Computation from One-Way Functions Using Stateless TokensAdvances in Cryptology – ASIACRYPT 201910.1007/978-3-030-34621-8_21(577-605)Online publication date: 22-Nov-2019
https://doi.org/10.1007/978-3-030-34621-8_21
Damgård IKazana TObremski MRaj VSiniscalchi L(2018)Continuous NMC Secure Against Permutations and Overwrites, with Applications to CCA Secure CommitmentsTheory of Cryptography10.1007/978-3-030-03810-6_9(225-254)Online publication date: 8-Nov-2018
https://doi.org/10.1007/978-3-030-03810-6_9
Chongchitmate WOstrovsky RVisconti I(2017)Resettably-Sound Resettable Zero Knowledge in Constant RoundsTheory of Cryptography10.1007/978-3-319-70503-3_4(111-138)Online publication date: 5-Nov-2017
https://doi.org/10.1007/978-3-319-70503-3_4
Ciampi MOstrovsky RSiniscalchi LVisconti I(2017)Four-Round Concurrent Non-Malleable Commitments from One-Way FunctionsAdvances in Cryptology – CRYPTO 201710.1007/978-3-319-63715-0_5(127-157)Online publication date: 29-Jul-2017
https://doi.org/10.1007/978-3-319-63715-0_5
Chung KLin HPass R(2015)Constant-Round Concurrent Zero-Knowledge from Indistinguishability ObfuscationAdvances in Cryptology -- CRYPTO 201510.1007/978-3-662-47989-6_14(287-307)Online publication date: 1-Aug-2015
https://doi.org/10.1007/978-3-662-47989-6_14
Pandey OPrabhakaran MSahai A(2015)Obfuscation-Based Non-black-box Simulation and Four Message Concurrent Zero Knowledge for NPPublic-Key Cryptography -- PKC 201510.1007/978-3-662-46497-7_25(638-667)Online publication date: 2015
https://doi.org/10.1007/978-3-662-46497-7_25
Chung KLui EPass R(2015)From Weak to Strong Zero-Knowledge and ApplicationsTheory of Cryptography10.1007/978-3-662-46494-6_4(66-92)Online publication date: 2015
https://doi.org/10.1007/978-3-662-46494-6_4
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents