Zero knowledge and circuit minimization

DOI10.1016/J.IC.2017.04.004MaRDI QIDQ2407082zbMATH OpenOpenAlexFDO

Authors Eric Allender, Bireswar Das

Publication date 28 September 2017

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2017.04.004

zbMATH Keywords

graph isomorphismminimum circuit size problemNP-intermediate problemstatistical zero knowledge

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Zero knowledge and circuit minimization
• Minimum circuit size, graph isomorphism, and related problems
• Minimum circuit size, graph isomorphism, and related problems
• On the power of statistical zero knowledge
• A complete problem for statistical zero knowledge

Cites work

• scientific article; zbMATH DE number 5845490 (Why is no real title available?)
• scientific article; zbMATH DE number 2134025 (Why is no real title available?)
• scientific article; zbMATH DE number 5605063 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 2196514 (Why is no real title available?)
• scientific article; zbMATH DE number 4185024 (Why is no real title available?)
• A Pseudorandom Generator from any One-way Function
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• A framework for non-interactive instance-dependent commitment schemes (NIC)
• A study of statistical zero-knowledge proofs (to appear)
• Circuit minimization problem
• Computational Complexity
• Does co-NP have short interactive proofs ?
• Graph isomorphism in quasipolynomial time (extended abstract)
• IP = PSPACE
• Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model
• NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
• Natural proofs
• On the Complexity of Learning Minimum Time-Bounded Turing Machines
• Power from Random Strings
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• SZK proofs for black-box group problems
• Statistical zero-knowledge languages can be recognized in two rounds
• The Knowledge Complexity of Interactive Proof Systems
• The complexity of theorem-proving procedures
• Trading help for interaction in statistical zero-knowledge proofs

Cited in

(15)

• scientific article; zbMATH DE number 7561759 (Why is no real title available?)
• Discrete logarithm and minimum circuit size
• The hidden subgroup problem and MKTP
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• Local zero knowledge
• On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
• On nonadaptive reductions to the set of random strings and its dense subsets
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• Zero knowledge and circuit minimization
• The non-hardness of approximating circuit size
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• Minimum circuit size, graph isomorphism, and related problems
• Minimum circuit size, graph isomorphism, and related problems

This page was built for publication: Zero knowledge and circuit minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2407082)