The knowledge complexity of interactive proof-systems

DOI10.1145/22145.22178zbMath0900.94025OpenAlexW2144752539WikidataQ56427208 ScholiaQ56427208MaRDI QIDQ4365519

Shafi Goldwasser, Silvio Micali, Charles W. Rackoff

Publication date: 13 November 1997

Published in: Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85 (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.419.8132

Mathematics Subject Classification ID

Cryptography (94A60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Witness Maps and Applications, On QA-NIZK in the BPK Model, Security analysis of discrete logarithm based cryptosystems, Multiple Usage of Random Bits in Finite Automata, Rationality Authority for Provable Rational Behavior, Constant-Round Leakage-Resilient Zero-Knowledge Argument for NP from the Knowledge-of-Exponent Assumption, Polynomial IOPs for Linear Algebra Relations, ECLIPSE: Enhanced Compiling Method for Pedersen-Committed zkSNARK Engines, Nonlocal Games with Noisy Maximally Entangled States are Decidable, Secure commitment against a powerful adversary, On Emulating Interactive Proofs with Public Coins, Complexity limitations on one-turn quantum refereed games, PrORAM, Verifiably-Extractable OWFs and Their Applications to Subversion Zero-Knowledge, Speed-stacking: fast sublinear zero-knowledge proofs for disjunctions, Spartan and bulletproofs are simulation-extractable (for free!), Ligero: lightweight sublinear arguments without a trusted setup, Sok: vector OLE-based zero-knowledge protocols, Zero-Knowledge Accumulators and Set Algebra, Zero-Knowledge Arguments for Matrix-Vector Relations and Lattice-Based Group Encryption, Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions, A Shuffle Argument Secure in the Generic Model, Indistinguishable Proofs of Work or Knowledge, Physical ZKP protocols for Nurimisaki and Kurodoko, Succinct classical verification of quantum computation, Multimodal private signatures, Physical zero-knowledge proof protocol for Topswops, Hide a liar: card-based ZKP protocol for Usowan, Obtaining simulation extractable NIZKs in the updatable CRS model generically, Efficient NIZKs from LWE via polynomial reconstruction and ``MPC in the head, Doubly adaptive zero-knowledge proofs, Efficient proof of RAM programs from any public-coin zero-knowledge system, NIWI and new notions of extraction for algebraic languages, Modal and justification logics for multi-agent systems (invited talk), Card-based ZKP protocol for Nurimisaki, Parallel repetition of \((k_1,\dots ,k_{\mu }) \)-special-sound multi-round interactive proofs, Snarky ceremonies, Lattice-based inner product argument, Nova: recursive zero-knowledge arguments from folding schemes, Steganography-free zero-knowledge, Vector commitments over rings and compressed \(\varSigma \)-protocols, On black-box constructions of time and space efficient sublinear arguments from symmetric-key primitives, Non-interactive zero-knowledge from non-interactive batch arguments, Algebraic reductions of knowledge, A note on non-interactive zero-knowledge from CDH, Publicly verifiable zero-knowledge and post-quantum signatures from VOLE-in-the-head, Cryptanalysis of Harari's identification scheme, Protocols for quantum binary voting, An Introduction to the Use of zk-SNARKs in Blockchains, Quadratic Error Minimization in a Distributed Environment with Privacy Preserving, Structure Versus Hardness Through the Obfuscation Lens, Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas, Fully Simulatable Quantum-Secure Coin-Flipping and Applications, Unnamed Item, The Arrow of Time through the Lens of Computing, Improved Zero-Knowledge Identification with Lattices, Multi-theorem preprocessing NIZKs from lattices, Extended security arguments for signature schemes, \(k\)-critical graphs in \(P_5\)-free graphs, Isolated Proofs of Knowledge and Isolated Zero Knowledge, Cryptology in the Classroom: Analyzing a Zero-Knowledge Protocol, Precise Time and Space Simulatable Zero-Knowledge, Graph isomorphism is low for PP, On Garbling Schemes with and Without Privacy, Secure Protocol Transformations, Efficient Zero-Knowledge Proof of Algebraic and Non-Algebraic Statements with Applications to Privacy Preserving Credentials, Fine-Grained Cryptography, Generalized lowness and highness and probabilistic complexity classes, Efficiency Preserving Transformations for Concurrent Non-malleable Zero Knowledge, Composition of Zero-Knowledge Proofs with Efficient Provers, Lattice-Based SNARGs and Their Application to More Efficient Obfuscation, On the concurrent composition of quantum zero-knowledge, How to construct physical zero-knowledge proofs for puzzles with a ``single loop condition, Dynamic sizing of multilayer perceptrons, Concurrent knowledge extraction in public-key models, More efficient shuffle argument from unique factorization, The knowledge complexity of quadratic residuosity languages, Tight state-restoration soundness in the algebraic group model, Model independent approach to probabilistic models, Lattice-based zero-knowledge arguments for additive and multiplicative relations, Efficient lattice-based polynomial evaluation and batch ZK arguments, A closer look at multiple forking: leveraging (in)dependence for a tighter bound, On the complexity of interactive proofs with bounded communication, The graph clustering problem has a perfect zero-knowledge interactive proof, Round optimal black-box ``commit-and-prove, On the security loss of unique signatures, Towards a unified approach to black-box constructions of zero-knowledge proofs, Compressing proofs of \(k\)-out-of-\(n\) partial knowledge, Belief, awareness, and limited reasoning, Improved identification schemes based on error-correcting codes, Partitioned encryption and achieving simultaneity by partitioning, MPC-in-multi-heads: a multi-prover zero-knowledge proof system (or: how to jointly prove any NP statements in ZK), On the design of cryptographic primitives, Survey of information security, A logic of interactive proofs, Fiat-Shamir and correlation intractability from strong KDM-secure encryption, Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes, Does co-NP have short interactive proofs ?, ZK-PCPs from leakage-resilient secret sharing, Minimum disclosure proofs of knowledge, Probabilistic quantifiers and games, Zero-knowledge proofs of identity, Mathematical problems in cryptology, Graph isomorphism is in the low hierarchy, Relativized Arthur-Merlin versus Merlin-Arthur games, Are there interactive protocols for co-NP languages?, Fiat-Shamir bulletproofs are non-malleable (in the algebraic group model), Stacking sigmas: a framework to compose \(\varSigma\)-protocols for disjunctions, On the power of rewinding simulators in functional encryption, On the complexity of collision resistant hash functions: new and old black-box separations, On some variations of two-way probabilistic finite automata models, Secure electronic bills of lading: Blind counts and digital signatures, Classical, quantum and nonsignalling resources in bipartite games, Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle, Lattice-based secret handshakes with reusable credentials, Blind key-generation attribute-based encryption for general predicates, Practical proofs of knowledge without relying on theoretical proofs of membership on languages, A pure labeled transition semantics for the applied pi calculus, Perfect implementation, Generalized proofs of knowledge with fully dynamic setup, On communication models and best-achievable security in two-round MPC, Oblivious transfer from trapdoor permutations in minimal rounds, Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?, Secret handshakes: full dynamicity, deniability and lattice-based design, A discrete logarithm implementation of perfect zero-knowledge blobs, Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption, Privacy-preserving and verifiable protocols for scientific computation outsourcing to the cloud, Cheat sensitive quantum bit commitment via pre- and post-selected quantum states, Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy, Random walks and concurrent zero-knowledge, Efficient signature generation by smart cards, Task-structured probabilistic I/O automata, On games of incomplete information, What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\), Entity authentication schemes using braid word reduction, Weakening the perfect encryption assumption in Dolev-Yao adversaries, Proving possession of arbitrary secrets while not giving them away: New protocols and a proof in GNY logic, Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits, Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs, A Transform for NIZK Almost as Efficient and General as the Fiat-Shamir Transform Without Programmable Random Oracles, Placing conditional disclosure of secrets in the communication complexity universe, A note on universal composable zero-knowledge in the common reference string model, On the amortized complexity of zero-knowledge protocols, Three-Player Entangled XOR Games are NP-Hard to Approximate, Probabilistic complexity classes and lowness, Transparent SNARKs from DARK compilers, Stacked garbling for disjunctive zero-knowledge proofs, Statistical ZAPR arguments from bilinear maps, Statistical Zaps and new oblivious transfer protocols, Boosting verifiable computation on encrypted data, On the power of interaction, Non-interactive zero knowledge from sub-exponential DDH, Order-C secure multiparty computation for highly repetitive circuits, A Lattice-Based Group Signature Scheme with Message-Dependent Opening, Round-optimal verifiable oblivious pseudorandom functions from ideal lattices, Probabilistic game automata, Proving properties of interactive proofs by a generalized counting technique, On succinct arguments and witness encryption from groups, Covert authentication from lattices, The complexity of the max word problem and the power of one-way interactive proof systems, Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs, NIZK from LPN and trapdoor hash via correlation intractability for approximable relations, Non-interactive zero-knowledge arguments for QMA, with preprocessing, Statistical zero-knowledge languages can be recognized in two rounds, Relativized perfect zero knowledge is not BPP, Decision algorithms for multiplayer noncooperative games of incomplete information, Round-optimal perfect zero-knowledge proofs, Computation of equilibria in noncooperative games, Interactive physical ZKP for connectivity: applications to Nurikabe and Hitori, Definitions and properties of zero-knowledge proof systems, Zero-knowledge proofs for committed symmetric Boolean functions