Lower bounds for non-black-box zero knowledge

DOI10.1016/j.jcss.2005.06.010zbMath1094.68024OpenAlexW2100862778MaRDI QIDQ2490264

Yehuda Lindell, Boaz Barak, Salil P. Vadhan

Publication date: 28 April 2006

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2005.06.010

zbMATH Keywords

Argument systemsInteractive proof systemsNon-black-box simulationPseudorandom generatorsRandomness extractorsZero knowledge

Mathematics Subject Classification ID

Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Concurrent knowledge extraction in public-key models, The Journey from NP to TFNP Hardness, Three-Round Public-Coin Bounded-Auxiliary-Input Zero-Knowledge Arguments of Knowledge, A note on perfect correctness by derandomization, Standard Security Does Not Imply Indistinguishability Under Selective Opening, Fiat-Shamir and correlation intractability from strong KDM-secure encryption, Round-optimal zero-knowledge proofs of knowledge for NP, NIZKs with an Untrusted CRS: Security in the Face of Parameter Subversion, Constant-round zero-knowledge proofs of knowledge with strict polynomial-time extractors for NP, Round-optimal black-box secure computation from two-round malicious OT, Existence of 3-round zero-knowledge proof systems for NP, Multikey Fully Homomorphic Encryption and Applications, Augmented random oracles, Which languages have 4-round zero-knowledge proofs?, Post-quantum resettably-sound zero knowledge, The Knowledge Complexity of Interactive Proof Systems, Lower bounds for non-black-box zero knowledge, One-Time Programs, On the Correlation Intractability of Obfuscated Pseudorandom Functions, Strong Proofs of Knowledge, Fiat–Shamir for Highly Sound Protocols Is Instantiable, On the Implausibility of Constant-Round Public-Coin Zero-Knowledge Proofs, On the Existence of Extractable One-Way Functions, Composition of Zero-Knowledge Proofs with Efficient Provers, Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs

Cites Work

• Bit commitment using pseudorandomness
• Derandomizing Arthur-Merlin games using hitting sets
• Random generation of combinatorial structures from a uniform distribution
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Efficient signature generation by smart cards
• A uniform-complexity treatment of encryption and zero-knowledge
• Definitions and properties of zero-knowledge proof systems
• On interactive proofs with a laconic prover
• Uniform generation of NP-witnesses using an NP-oracle
• A note on negligible functions
• Randomness is linear in space
• How to construct constant-round zero-knowledge proof systems for NP
• Lower bounds for non-black-box zero knowledge
• Security Proofs for Signature Schemes
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Resettable zero-knowledge (extended abstract)
• A complete problem for statistical zero knowledge
• Strict polynomial-time in simulation and extraction
• On Approximation Algorithms for # P
• How To Prove Yourself: Practical Solutions to Identification and Signature Problems
• The Knowledge Complexity of Interactive Proof Systems
• A Pseudorandom Generator from any One-way Function
• Computing with Very Weak Random Sources
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Foundations of Cryptography
• Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack
• Foundations of Cryptography
• On the Composition of Zero-Knowledge Proof Systems
• Concurrent and resettable zero-knowledge in poly-loalgorithm rounds
• Black-box concurrent zero-knowledge requires \tilde {Ω} (log n ) rounds
• Advances in Cryptology – CRYPTO 2004
• Advances in Cryptology - CRYPTO 2003
• Advances in Cryptology - CRYPTO 2003
• Zaps and Their Applications
• Factoring Polynomials Over Large Finite Fields
• On pseudorandomness and resource-bounded measure
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item