The Knowledge Complexity of Interactive Proof Systems

DOI10.1137/0218012zbMath0677.68062OpenAlexW1970606468WikidataQ21694644 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

zbMATH Keywords

cryptography quadratic residue zero-knowledge interactive proof

Mathematics Subject Classification ID

Cryptography (94A60) Structure of proofs (03F07) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The Turing Test as Interactive Proof, Minimal Assumptions and Round Complexity for Concurrent Zero-Knowledge in the Bare Public-Key Model, Unnamed Item, Off-line electronic cash based on secret-key certificates, Communication efficient Zero-knowledge Proofs of knowledge, Super-Perfect Zero-Knowledge Proofs, Constant-Round Interactive Proof Systems for AC0[2 and NC1], Complexity limitations on one-turn quantum refereed games, HyperPlonk: Plonk with linear-time prover and high-degree custom gates, A survey of elliptic curves for proof systems, On separating proofs of knowledge from proofs of membership of languages and its application to secure identification schemes, Certifying giant nonprimes, An identification system based on the explicit isomorphism problem, An accurate, scalable and verifiable protocol for federated differentially private averaging, Certified everlasting zero-knowledge proof for QMA, A more complete analysis of the signal double ratchet algorithm, Rigidity of quantum steering and one-sided device-independent verifiable quantum computation, Efficient Dynamic-Resharing “Verifiable Secret Sharing” against mobile adversary, Resumable zero-knowledge for circuits from symmetric key primitives, Sherlock Holmes zero-knowledge protocols, Physical ZKP for Makaro using a standard deck of cards, Parallelizable delegation from LWE, Improvements on non-interactive zero-knowledge proof systems related to quadratic residuosity languages, Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection, Unconditionally secure NIZK in the fine-grained setting, Efficient NIZKs from LWE via polynomial reconstruction and ``MPC in the head, Classically verifiable NIZK for QMA with preprocessing, Concurrently composable non-interactive secure computation, Knowledge encryption and its applications to simulatable protocols with low round-complexity, Speak much, remember little: cryptography in the bounded storage model, revisited, Individual cryptography, Structural complexity of rational interactive proofs, Physical zero-knowledge proof for ball sort puzzle, Faster sounder succinct arguments and \textsf{IOP}s, $\mathcal{Lunar}$: a toolbox for more efficient universal and updatable zkSNARKs and commit-and-prove extensions, Efficient NIZK arguments with straight-line simulation and extraction, Updatable NIZKs from non-interactive zaps, Orion: zero knowledge proof with linear prover time, Doubly efficient interactive proofs over infinite and non-commutative rings, Public-key encryption from homogeneous CLWE, CRS-updatable asymmetric quasi-adaptive NIZK arguments, Universal reductions: reductions relative to stateful oracles, An improved physical ZKP for nonogram and nonogram color, GUC-secure commitments via random oracles: new impossibility and feasibility, New design techniques for efficient arithmetization-oriented hash functions: \texttt{Anemoi} permutations and \texttt{Jive} compression mode, Interactions of computational complexity theory and mathematics, On the Power of Statistical Zero Knowledge, Unnamed Item, Linear Logic Proof Games and Optimization, Cryptography and cryptographic protocols, Robustness and device independence of verifiable blind quantum computing, Projective Arithmetic Functional Encryption and Indistinguishability Obfuscation from Degree-5 Multilinear Maps, Magic Adversaries Versus Individual Reduction: Science Wins Either Way, Zero-knowledge proofs for set membership: efficient, succinct, modular, Playing Savitch and Cooking Games, 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, One-message statistical Zero-Knowledge Proofs and space-bounded verifier, Debates with Small Transparent Quantum Verifiers, Verifying quantum computations at scale: A cryptographic leash on quantum devices, Constructing tree decompositions of graphs with bounded gonality, The Complexity of Zero Knowledge, Efficient verifiable delay functions, Physical zero-knowledge proof for ripple effect, Sumcheck-based delegation of quantum computing to rational server, Physical zero-knowledge proof for ripple effect, Unnamed Item, Unnamed Item, Constant-Round Nonmalleable Commitments from Any One-Way Function, Statistical Security Conditions for Two-Party Secure Function Evaluation, A Cryptographically Sound Dolev-Yao Style Security Proof of the Otway-Rees Protocol, Conditional Reactive Simulatability, QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge, A Practical Group Signature Scheme Based on Rank Metric, Relativistic (or 2-Prover 1-Round) Zero-Knowledge Protocol for $$\mathsf {NP}$$ Secure Against Quantum Adversaries, Computational Integrity with a Public Random String from Quasi-Linear PCPs, Three systems for cryptographic protocol analysis, The power of adaptiveness and additional queries in random-self- reductions, The random oracle hypothesis is false, Quantum information and the PCP theorem, One-message zero knowledge and non-malleable commitments, Round-optimal fully black-box zero-knowledge arguments from one-way permutations, On the power of multi-prover interactive protocols, Fine-grained secure computation, Pattern matching on encrypted streams, Quantum computation vs. firewalls, Probabilistically checkable proofs and their consequences for approximation algorithms, Tightly secure signatures from lossy identification schemes, More on BPP and the polynomial-time hierarchy, Bridging the gap between general probabilistic theories and the device-independent framework for nonlocality and contextuality, Toward a game theoretic view of secure computation, On the hardness of computing the permanent of random matrices, Fully parallelized multi-prover protocols for NEXP-time, Unprovable security of perfect NIZK and non-interactive non-malleable commitments, $\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}$, On the existence of statistically hiding bit commitment schemes and fail-stop signatures, Round-optimal zero-knowledge proofs of knowledge for NP, A note on constant-round zero-knowledge proofs of knowledge, On server trust in private proxy auctions, Secure electronic bills of lading: Blind counts and digital signatures, Zero-knowledge proofs of knowledge for group homomorphisms, Precise zero-knowledge arguments with poly-logarithmic efficiency, On sequential composition of precise zero-knowledge, The 2010 Benjamin Franklin Medal in Computer and Cognitive Science presented to Shafrira Goldwasser, Ph.D., Constant-round zero-knowledge proofs of knowledge with strict polynomial-time extractors for NP, Quantum multi-prover interactive proof systems with limited prior entanglement., Parallel repetition of computationally sound protocols revisited, Which languages have 4-round zero-knowledge proofs?, The hunting of the SNARK, Quantum cryptography beyond quantum key distribution, Leakproof secret sharing protocols with applications to group identification scheme, Zero-knowledge identification scheme based on Weil pairing, Secure circuit evaluation. A protocol based on hiding information from an oracle, A discrete logarithm implementation of perfect zero-knowledge blobs, Non-interactive secure computation from one-way functions, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, On the tightness of forward-secure signature reductions, Certifying algorithms, Secure computation without authentication, SZK proofs for black-box group problems, Several cryptographic applications of $\Sigma$-protocol, Efficient algorithms for secure outsourcing of bilinear pairings, Protocol completion incentive problems in cryptographic Vickrey auctions, Practic zero-knowledge proofs: Giving hints and using deficiencies, An introduction to randomized algorithms, An interactive identification scheme based on discrete logarithms and factoring, The relativized relationship between probabilistically checkable debate systems, IP and PSPACE, The reachability problem for finite cellular automata, Algebraic (trapdoor) one-way functions: constructions and applications, A framework for non-interactive instance-dependent commitment schemes (NIC), Beating the generator-enumeration bound for $p$-group isomorphism, Locally random reductions: Improvements and applications, A language-dependent cryptographic primitive, Multi-oracle interactive protocols with constant space verifiers, Non-interactive proofs of proximity, Efficient computation outsourcing for inverting a class of homomorphic functions, A guide to completeness and complexity for modal logics of knowledge and belief, A code-based group signature scheme, A black-box construction of non-malleable encryption from semantically secure encryption, Dynamic proofs of retrievability via oblivious RAM, An almost-constant round interactive zero-knowledge proof, 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, On being incoherent without being very hard, Challenging epistemology: Interactive proofs and zero knowledge, A uniform-complexity treatment of encryption and zero-knowledge, Graph isomorphism is low for PP, Leveraging possibilistic beliefs in unrestricted combinatorial auctions, Cryptography in the multi-string model, On the communication complexity of zero-knowledge proofs, A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm, Randomized proofs in arithmetic, On hiding information from an oracle, An application of quantum finite automata to interactive proof systems, Analyzing security protocols using time-bounded task-PIOAs, Handling expected polynomial-time strategies in simulation-based security proofs, Hybrid commitments and their applications to zero-knowledge proof systems, New approaches for deniable authentication, Outsourcing computation: the minimal refereed mechanism, A secure and scalable group key exchange system, 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}$, 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, Self-testing/correcting with applications to numerical problems, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority, PSPACE is provable by two provers in one round, Relativized perfect zero knowledge is not BPP, $BPP$ has subexponential time simulations unless $EXPTIME$ has publishable proofs, Randomness in interactive proofs, Definitions and properties of zero-knowledge proof systems, Concretely-Efficient Zero-Knowledge Arguments for Arithmetic Circuits and Their Application to Lattice-Based Cryptography, Cryptography from Learning Parity with Noise, Complete Problem for Perfect Zero-Knowledge Quantum Proof, The Untold Story of $$\mathsf {SBP}$$, Protocols for collusion-secure asymmetric fingerprinting, An information-theoretic treatment of random-self-reducibility, Probabilistic proof systems — A survey, On Non-Black-Box Simulation and the Impossibility of Approximate Obfuscation, A Hierarchy Theorem for Interactive Proofs of Proximity, Security of 2t-Root Identification and Signatures, Robust and Efficient Sharing of RSA Functions, Proving Without Knowing: On Oblivious, Agnostic and Blindfolded Provers, Recent results in hardness of approximation, A Lattice-Based Approach to Privacy-Preserving Biometric Authentication Without Relying on Trusted Third Parties, Three-Round Public-Coin Bounded-Auxiliary-Input Zero-Knowledge Arguments of Knowledge, 3-Message Zero Knowledge Against Human Ignorance, On the (In)Security of SNARKs in the Presence of Oracles, Implicit Zero-Knowledge Arguments and Applications to the Malicious Setting, Efficient Zero-Knowledge Proofs of Non-algebraic Statements with Sublinear Amortized Cost, Constant-Round Concurrent Zero-Knowledge from Indistinguishability Obfuscation, Interactive Oracle Proofs, Zero-Knowledge Interactive Proof Systems for New Lattice Problems, Spatial Isolation Implies Zero Knowledge Even in a Quantum World, Beyond Lamport's Happened-before, A framework for polynomial-time query learnability, Randomness-efficient non-interactive zero knowledge, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Rational Modular Encoding in the DCR Setting: Non-interactive Range Proofs and Paillier-Based Naor-Yung in the Standard Model, Card-Based Zero-Knowledge Proof for Sudoku, On Constant-Round Concurrent Zero-Knowledge from a Knowledge Assumption, Beating the Birthday Paradox in Dining Cryptographer Networks, On Zero-Knowledge with Strict Polynomial-Time Simulation and Extraction from Differing-Input Obfuscation for Circuits, How to deal with malicious users in privacy‐preserving distributed data mining, On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE, Unnamed Item, NIZKs with an Untrusted CRS: Security in the Face of Parameter Subversion, Efficient Generic Zero-Knowledge Proofs from Commitments (Extended Abstract), Complex Zero-Knowledge Proofs of Knowledge Are Easy to Use, Succinct NP Proofs from an Extractability Assumption, Unnamed Item, Unnamed Item, Black-box impossibilities of obtaining 2-round weak ZK and strong WI from polynomial hardness, Statistical ZAPs from group-based assumptions, Oblivious transfer from trapdoor permutations in minimal rounds, Card-based zero-knowledge proof protocols for graph problems and their computational model, Partial Bits Exposure Attacks on a New Commitment Scheme Based on the Zagier Polynomial, ON THE POWER OF QUANTUM TAMPER-PROOF DEVICES, Simplified Submission of Inputs to Protocols, Zero-Knowledge Proofs of Proximity, Proofs of Proximity for Distribution Testing, Secure and efficient off-line digital money (extended abstract), Evolving Perfect Hash Families: A Combinatorial Viewpoint of Evolving Secret Sharing, Generalized Quantum Arthur--Merlin Games, Identification Schemes from Key Encapsulation Mechanisms, Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications, Non-Interactive Key Exchange, New Constructions and Applications of Trapdoor DDH Groups, The Knowledge Complexity of Interactive Proof Systems, How to Verify a Quantum Computation, Information-Theoretic Conditions for Two-Party Secure Function Evaluation, One-Time Programs, Unnamed Item, Output-Compressing Randomized Encodings and Applications, A Transform for NIZK Almost as Efficient and General as the Fiat-Shamir Transform Without Programmable Random Oracles, Non-Black-Box Simulation from One-Way Functions and Applications to Resettable Security, The electronic cash system based on non-interactive zero-knowledge proofs, A General, Flexible and Efficient Proof of Inclusion and Exclusion, Dynamic Universal Accumulators for DDH Groups and Their Application to Attribute-Based Anonymous Credential Systems, On the Portability of Generalized Schnorr Proofs, Public Cloud Data Auditing with Practical Key Update and Zero Knowledge Privacy, Four-Round Zero-Knowledge Arguments of Knowledge with Strict Polynomial-Time Simulation from Differing-Input Obfuscation for Circuits, Proving Computational Ability, Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More), Strong Proofs of Knowledge, On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge, On the Complexity of Computational Problems Regarding Distributions, Randomness and Computation, On Security Preserving Reductions – Revised Terminology, Threshold Attribute-Based Signatures and Their Application to Anonymous Credential Systems, Unifying Zero-Knowledge Proofs of Knowledge, Co-sound Zero-Knowledge with Public Keys, Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions, Threshold-Optimal DSA/ECDSA Signatures and an Application to Bitcoin Wallet Security, Universally Composable Adaptive Priced Oblivious Transfer, Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model, On the Implausibility of Constant-Round Public-Coin Zero-Knowledge Proofs, On the Power of Secure Two-Party Computation, On the Existence of Extractable One-Way Functions, Spooky Interaction and Its Discontents: Compilers for Succinct Two-Message Argument Systems, On the Relationship Between Statistical Zero-Knowledge and Statistical Randomized Encodings, A NEW BATCH IDENTIFICATION SCHEME, Designated Confirmer Signatures with Unified Verification, An Efficient Parallel Repetition Theorem, Eye for an Eye: Efficient Concurrent Zero-Knowledge in the Timing Model, Composition of Zero-Knowledge Proofs with Efficient Provers, Private Coins versus Public Coins in Zero-Knowledge Proof Systems, Constant-Round Interactive Proofs for Delegating Computation, On Dinur’s proof of the PCP theorem, How to Simulate It – A Tutorial on the Simulation Proof Technique, Weak Zero-Knowledge beyond the Black-Box Barrier, A black-box approach to post-quantum zero-knowledge in constant rounds, Multi-theorem designated-verifier NIZK for QMA, An algebraic framework for universal and updatable SNARKs, Quantum alternation, Constant-round leakage-resilient zero-knowledge from collision resistance, Succinct non-interactive arguments via linear interactive proofs, A one-round, two-prover, zero-knowledge protocol for NP, Zero-knowledge proofs for set membership: efficient, succinct, modular, Practical witness-key-agreement for blockchain-based dark pools financial trading, Cross-domain attribute-based access control encryption, Subversion-resistant quasi-adaptive NIZK and applications to modular zk-SNARKs, An improved physical ZKP for Nonogram, Zero-knowledge proof protocol for cryptarithmetic using dihedral cards, Affine automata verifiers, Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems, Layering quantum-resistance into classical digital signature algorithms, Practical and provably secure release of a secret and exchange of signatures, The complexity of approximating a nonlinear program, Enhancements of trapdoor permutations, Polynomial runtime and composability, Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs, A survey on delegated computation, A PCP theorem for interactive proofs and applications, Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier, Non-interactive zero-knowledge proofs with fine-grained security, One-shot Fiat-Shamir-based NIZK arguments of composite residuosity and logarithmic-size ring signatures in the standard model, A group identification protocol with leakage resilience of secret sharing scheme, Zero knowledge and circuit minimization, Succinct arguments in the quantum random oracle model, Linear-size constant-query IOPs for delegating computation, Cryptographic algorithms for privacy-preserving online applications, A new framework for deniable secure key exchange, Blind key-generation attribute-based encryption for general predicates, Statistical concurrent non-malleable zero-knowledge from one-way functions, Non-black-box simulation in the fully concurrent setting, revisited, Existence of 3-round zero-knowledge proof systems for NP, Efficient card-based zero-knowledge proof for Sudoku, On constant-round concurrent non-malleable proof systems, Universally composable symbolic security analysis, Individual simulations, Public-coin parallel zero-knowledge for NP, Simulation-sound arguments for LWE and applications to KDM-CCA2 security, Two standard decks of playing cards are sufficient for a ZKP for Sudoku, Post-quantum resettably-sound zero knowledge, The round complexity of quantum zero-knowledge, Security models and proof strategies for plaintext-aware encryption, Concurrent zero knowledge, revisited, Arthur-Merlin games in Boolean decision trees, Cryptographic reverse firewalls for interactive proof systems, Secure sealed-bid online auctions using discreet cryptographic proofs, On relationships between statistical zero-knowledge proofs, Efficient, actively secure MPC with a dishonest majority: a survey, The reactive simulatability (RSIM) framework for asynchronous systems, Games with zero-knowledge signaling, Verification protocols with sub-linear communication for polynomial matrix operations, Novel $\Omega$-protocols for NP, Post-challenge leakage in public-key encryption, New publicly verifiable computation for batch matrix multiplication, Unifying simulatability definitions in cryptographic systems under different timing assumptions, Lower bounds for non-black-box zero knowledge, On expected probabilistic polynomial-time adversaries: a suggestion for restricted definitions and their benefits, LWPP and WPP are not uniformly gap-definable, Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles, Privacy-preserving verifiable delegation of polynomial and matrix functions, Overcoming free riding in multi-party computations -- the anonymous case, On the relationship between statistical zero-knowledge and statistical randomized encodings, Escrow free attribute-based signature with self-revealability, How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge, Compact designated verifier NIZKs from the CDH assumption without pairings, Multi-server verifiable delegation of computations: unconditional security and practical efficiency, On the power of secure two-party computation, SPARKs: succinct parallelizable arguments of knowledge, Sigma protocols for MQ, PKP and SIS, and fishy signature schemes, Compact NIZKs from standard assumptions on bilinear maps, New constructions of statistical NIZKs: dual-mode DV-NIZKs and more, Non-interactive zero-knowledge in pairing-free groups from weaker assumptions, Which languages have 4-round fully black-box zero-knowledge arguments from one-way functions?, Classical proofs of quantum knowledge, Non-interactive distributional indistinguishability (NIDI) and non-malleable commitments, Public-coin statistical zero-knowledge batch verification against malicious verifiers, Efficient range proofs with transparent setup from bounded integer commitments, Public verifiable private decision tree prediction, Protecting data privacy in publicly verifiable delegation of matrix and polynomial functions, Single-to-multi-theorem transformations for non-interactive statistical zero-knowledge, Group encryption: full dynamicity, message filtering and code-based instantiation, The hidden subgroup problem and MKTP, Hardness of learning problems over Burnside groups of exponent 3, Round-optimal black-box commit-and-prove with succinct communication, (Commit-and-prove) predictable arguments with privacy, Distributed interactive proofs for the recognition of some geometric intersection graph classes, Uniform generation of NP-witnesses using an NP-oracle, Robust threshold DSS signatures, Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata, Interactive proofs for social graphs, New techniques for zero-knowledge: leveraging inefficient provers to reduce assumptions, interaction, and trust, Shorter non-interactive zero-knowledge arguments and ZAPs for algebraic languages, On the probabilistic closure of the loose unambiguous hierarchy, TurboIKOS: improved non-interactive zero knowledge and post-quantum signatures, PSPACE has constant-round quantum interactive proof systems, Formalizing data deletion in the context of the right to be forgotten

Cites Work