The Knowledge Complexity of Interactive Proof Systems
From MaRDI portal
Publication:3833627
DOI10.1137/0218012zbMath0677.68062WikidataQ21694644 ScholiaQ21694644MaRDI QIDQ3833627
Shafi Goldwasser, Silvio Micali, Charles W. Rackoff
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.419.8132
94A60: Cryptography
03F07: Structure of proofs
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
A framework for polynomial-time query learnability, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE, Construction of Universal Designated-Verifier Signatures and Identity-Based Signatures from Standard Signatures, How to Achieve Perfect Simulation and A Complete Problem for Non-interactive Perfect Zero-Knowledge, General Properties of Quantum Zero-Knowledge Proofs, An Equivalence Between Zero Knowledge and Commitments, The Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization, The Complexity of Zero Knowledge, Linear Logic Proof Games and Optimization, The relativized relationship between probabilistically checkable debate systems, IP and PSPACE, The reachability problem for finite cellular automata, Locally random reductions: Improvements and applications, A language-dependent cryptographic primitive, Interactive proof systems and alternating time-space complexity, Arithmetization: A new method in structural complexity theory, Non-deterministic exponential time has two-prover interactive protocols, Applying a formal analysis technique to the CCITT X.509 strong two-way authentication protocol, Constant-round perfect zero-knowledge computationally convincing protocols, Statistical zero-knowledge languages can be recognized in two rounds, Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority, Relativized perfect zero knowledge is not BPP, \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\), Secure circuit evaluation. A protocol based on hiding information from an oracle, A discrete logarithm implementation of perfect zero-knowledge blobs, Practic zero-knowledge proofs: Giving hints and using deficiencies, An introduction to randomized algorithms, An interactive identification scheme based on discrete logarithms and factoring, Multi-oracle interactive protocols with constant space verifiers, A guide to completeness and complexity for modal logics of knowledge and belief, An almost-constant round interactive zero-knowledge proof, On being incoherent without being very hard, A uniform-complexity treatment of encryption and zero-knowledge, Graph isomorphism is low for PP, On the communication complexity of zero-knowledge proofs, A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm, On hiding information from an oracle, Self-testing/correcting with applications to numerical problems, PSPACE is provable by two provers in one round, \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs, Randomness in interactive proofs, Definitions and properties of zero-knowledge proof systems, Three systems for cryptographic protocol analysis, The power of adaptiveness and additional queries in random-self- reductions, The random oracle hypothesis is false, On the power of multi-prover interactive protocols, Probabilistically checkable proofs and their consequences for approximation algorithms, More on BPP and the polynomial-time hierarchy, On the hardness of computing the permanent of random matrices, Fully parallelized multi-prover protocols for NEXP-time, On the existence of statistically hiding bit commitment schemes and fail-stop signatures, Quantum multi-prover interactive proof systems with limited prior entanglement., On the limits of nonapproximability of lattice problems, Interactive and probabilistic proof-checking, New efficient and secure protocols for verifiable signature sharing and other applications, Clique is hard to approximate within \(n^{1-\epsilon}\), Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, Randomized proofs in arithmetic, Uniform generation of NP-witnesses using an NP-oracle, Robust threshold DSS signatures, PSPACE has constant-round quantum interactive proof systems, A one-round, two-prover, zero-knowledge protocol for NP, Practical and provably secure release of a secret and exchange of signatures, The complexity of approximating a nonlinear program, Arthur-Merlin games in Boolean decision trees, On relationships between statistical zero-knowledge proofs, The reactive simulatability (RSIM) framework for asynchronous systems, Games with zero-knowledge signaling, Novel \(\Omega\)-protocols for NP, Unifying simulatability definitions in cryptographic systems under different timing assumptions, Lower bounds for non-black-box zero knowledge, LWPP and WPP are not uniformly gap-definable, Overcoming free riding in multi-party computations -- the anonymous case, On Dinur’s proof of the PCP theorem, Information-Theoretic Conditions for Two-Party Secure Function Evaluation, The Knowledge Complexity of Interactive Proof Systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Definitions and properties of zero-knowledge proof systems
- How to construct constant-round zero-knowledge proof systems for NP
- Existence of 3-round zero-knowledge proof systems for NP
- Lower bounds for non-black-box zero knowledge
- On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge
- Strict polynomial-time in simulation and extraction
- The Knowledge Complexity of Interactive Proof Systems
- Foundations of Cryptography
- On the Composition of Zero-Knowledge Proof Systems
- Advances in Cryptology – CRYPTO 2004
- Advances in Cryptology - CRYPTO 2003
- Which Languages Have 4-Round Zero-Knowledge Proofs?
- Theory of Cryptography
