Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

From MaRDI portal

Publication:4302852

Jump to:navigation, search

DOI10.1145/116825.116852zbMath0799.68101OpenAlexW2011112377WikidataQ55879618 ScholiaQ55879618MaRDI QIDQ4302852

Oded Goldreich, Avi Wigderson, Silvio Micali

Publication date: 24 November 1994

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/116825.116852

zbMATH Keywords

interactive proofs zero-knowledge proofs information hiding graph isomorphism graph nonisomorphism secure encryption

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data encryption (aspects in computer science) (68P25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes., A black-box approach to post-quantum zero-knowledge in constant rounds, Concurrent knowledge extraction in public-key models, The random oracle hypothesis is false, Detecting almost symmetries of graphs, The knowledge complexity of quadratic residuosity languages, Computational hardness of optimal fair computation: beyond Minicrypt, Fast approximate probabilistically checkable proofs, On the complexity of interactive proofs with bounded communication, The graph clustering problem has a perfect zero-knowledge interactive proof, Round-optimal fully black-box zero-knowledge arguments from one-way permutations, On the power of multi-prover interactive protocols, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Practical witness-key-agreement for blockchain-based dark pools financial trading, MPC-in-multi-heads: a multi-prover zero-knowledge proof system (or: how to jointly prove any NP statements in ZK), An improved physical ZKP for Nonogram, Rate-limited secure function evaluation, Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems, Privacy-preserving algorithms for distributed mining of frequent itemsets, Complexity results in graph reconstruction, Enforcing input correctness via certification in garbled circuit evaluation, Round-optimal zero-knowledge proofs of knowledge for NP, Practical non-interactive publicly verifiable secret sharing with thousands of parties, A PCP theorem for interactive proofs and applications, Practical post-quantum signature schemes from isomorphism problems of trilinear forms, On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography, Online-extractability in the quantum random-oracle model, Zero knowledge and circuit minimization, A black-box construction of fully-simulatable, round-optimal oblivious transfer from strongly uniform key agreement, General linear group action on tensors: a candidate for post-quantum cryptography, Long-term security and universal composability, A note on constant-round zero-knowledge proofs of knowledge, On using probabilistic Turing machines to model participants in cryptographic protocols, Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle, On sequential composition of precise zero-knowledge, Practical proofs of knowledge without relying on theoretical proofs of membership on languages, A pure labeled transition semantics for the applied pi calculus, 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, Which languages have 4-round zero-knowledge proofs?, The hunting of the SNARK, Universally composable symbolic security analysis, Public-coin parallel zero-knowledge for NP, Quantum cryptography beyond quantum key distribution, Authentication schemes from actions on graphs, groups, or rings, Practical graph isomorphism. II., Possibility and impossibility results for selective decommitments, Concurrent zero knowledge, revisited, Cheat sensitive quantum bit commitment via pre- and post-selected quantum states, Knottedness is in NP, modulo GRH, Inverting onto functions., Cryptographic reverse firewalls for interactive proof systems, Adaptive zero-knowledge proofs and adaptively secure oblivious transfer, SZK proofs for black-box group problems, Functional approach to the Hamiltonian circuit and graph isomorphism problems, Practic zero-knowledge proofs: Giving hints and using deficiencies, Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification, 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, A black-box construction of non-malleable encryption from semantically secure encryption, An almost-constant round interactive zero-knowledge proof, On the expression complexity of equivalence and isomorphism of primitive positive formulas, A uniform-complexity treatment of encryption and zero-knowledge, Quantum protocols for zero-knowledge systems, Lower bounds for non-black-box zero knowledge, Obfuscation for cryptographic purposes, On expected probabilistic polynomial-time adversaries: a suggestion for restricted definitions and their benefits, Basing cryptographic protocols on tamper-evident seals, Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles, Proving possession of arbitrary secrets while not giving them away: New protocols and a proof in GNY logic, On the relationship between statistical zero-knowledge and statistical randomized encodings, Leveraging possibilistic beliefs in unrestricted combinatorial auctions, Non-interactive and non-malleable commitment scheme based on \(q\)-one way group homomorphisms, Placing conditional disclosure of secrets in the communication complexity universe, Accountable authority identity-based broadcast encryption with constant-size private keys and ciphertexts, How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge, A note on universal composable zero-knowledge in the common reference string model, On the communication complexity of zero-knowledge proofs, A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm, Stacked garbling for disjunctive zero-knowledge proofs, Which languages have 4-round fully black-box zero-knowledge arguments from one-way functions?, Non-interactive distributional indistinguishability (NIDI) and non-malleable commitments, Handling expected polynomial-time strategies in simulation-based security proofs, Zero knowledge and the chromatic number, Reducing complexity assumptions for statistically-hiding commitment, New approaches for deniable authentication, On the limits of nonapproximability of lattice problems, Interactive and probabilistic proof-checking, Determining whether a given cryptographic function is a permutation of another given cryptographic function -- a problem in intellectual property, Black-box use of one-way functions is useless for optimal fair coin-tossing, Distributed interactive proofs for the recognition of some geometric intersection graph classes, Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs, New techniques for zero-knowledge: leveraging inefficient provers to reduce assumptions, interaction, and trust, Randomness in interactive proofs, TurboIKOS: improved non-interactive zero knowledge and post-quantum signatures, Quantum commitments from complexity assumptions, Interactive physical ZKP for connectivity: applications to Nurikabe and Hitori, Cryptography from Learning Parity with Noise, Probabilistic proof systems — A survey, On Non-Black-Box Simulation and the Impossibility of Approximate Obfuscation, Recent results in hardness of approximation, Minimum Circuit Size, Graph Isomorphism, and Related Problems, Geometry and Combinatorics via Right-Angled Artin Groups, 3-Message Zero Knowledge Against Human Ignorance, A cryptographic primitive based on hidden-order groups, Spatial Isolation Implies Zero Knowledge Even in a Quantum World, Randomness-efficient non-interactive zero knowledge, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Card-Based Zero-Knowledge Proof for Sudoku, Signatures and Efficient Proofs on Committed Graphs and NP-Statements, Super-Perfect Zero-Knowledge Proofs, PrORAM, Unnamed Item, Proving knowledge of isogenies: a survey, On separating proofs of knowledge from proofs of membership of languages and its application to secure identification schemes, NIZKs with an Untrusted CRS: Security in the Face of Parameter Subversion, Efficient Generic Zero-Knowledge Proofs from Commitments (Extended Abstract), An identification system based on the explicit isomorphism problem, On-line/off-line DCR-based homomorphic encryption and applications, (Nondeterministic) hardness vs. non-malleability, Statistical security in two-party computation revisited, SIDH proof of knowledge, Short-lived zero-knowledge proofs and signatures, Graph-theoretic algorithms for the alternating trilinear form equivalence problem, Physical zero-knowledge proof for ball sort puzzle, Public-coin 3-round zero-knowledge from learning with errors and keyless multi-collision-resistant hash, Quantum computationally predicate-binding commitments with application in quantum zero-knowledge arguments for NP, Universal reductions: reductions relative to stateful oracles, An improved physical ZKP for nonogram and nonogram color, On the Power of Statistical Zero Knowledge, An Almost-Optimally Fair Three-Party Coin-Flipping Protocol, Unnamed Item, Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks, Post-quantum resettably-sound zero knowledge, Classical binding for quantum commitments, Somewhere statistical soundness, post-quantum security, and SNARGs, Card-based zero-knowledge proof protocols for graph problems and their computational model, Unnamed Item, ON THE POWER OF QUANTUM TAMPER-PROOF DEVICES, Quantum Cryptography: Key Distribution and Beyond, Pseudo-deterministic Proofs, Cryptography and cryptographic protocols, Zero-Knowledge Proofs of Proximity, An Introduction to the Use of zk-SNARKs in Blockchains, Structure Versus Hardness Through the Obfuscation Lens, Quantum Commitments from Complexity Assumptions, Unclonable Group Identification, Minimum Circuit Size, Graph Isomorphism, and Related Problems, One-Time Programs, Compression from Collisions, or Why CRHF Combiners Have a Long Output, Collusion-Free Protocols in the Mediated Model, Unnamed Item, 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, Non-Black-Box Simulation from One-Way Functions and Applications to Resettable Security, A note on the feasibility of generalised universal composability, The Complexity of Zero Knowledge, Physical zero-knowledge proof for ripple effect, Physical zero-knowledge proof for ripple effect, Strong Proofs of Knowledge, On the Complexity of Computational Problems Regarding Distributions, Randomness and Computation, Unnamed Item, Threshold Attribute-Based Signatures and Their Application to Anonymous Credential Systems, Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions, A new generic construction of anonymous designated confirmer signature for privacy-preserving fair exchange, $$P\mathop{ =}\limits^{?}NP$$, On the Implausibility of Constant-Round Public-Coin Zero-Knowledge Proofs, On Garbling Schemes with and Without Privacy, Network Oblivious Transfer, A New Spin on Quantum Cryptography: Avoiding Trapdoors and Embracing Public Keys, Designated Confirmer Signatures with Unified Verification, Efficiency Limitations for Σ-Protocols for Group Homomorphisms, Composition of Zero-Knowledge Proofs with Efficient Provers, Private Coins versus Public Coins in Zero-Knowledge Proof Systems, Unnamed Item, Constant-Round Interactive Proofs for Delegating Computation, Constant-Round Nonmalleable Commitments from Any One-Way Function, An algebraic characterization of 𝑘–colorability, How to Simulate It – A Tutorial on the Simulation Proof Technique, QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge, Weak Zero-Knowledge beyond the Black-Box Barrier

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:4302852&oldid=18239914"