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

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

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

• A framework for non-interactive instance-dependent commitment schemes (NIC)
• A Pseudorandom Generator from any One-way Function
• A study of statistical zero-knowledge proofs (to appear)
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Circuit minimization problem
• Computational Complexity
• Does co-NP have short interactive proofs ?
• Graph isomorphism in quasipolynomial time (extended abstract)
• 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?)
• Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model
• IP = PSPACE
• Natural proofs
• NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
• 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
• Statistical zero-knowledge languages can be recognized in two rounds
• SZK proofs for black-box group problems
• The complexity of theorem-proving procedures
• The Knowledge Complexity of Interactive Proof Systems
• Trading help for interaction in statistical zero-knowledge proofs

Cited in

(23)

• The hidden subgroup problem and MKTP
• Discrete logarithm and minimum circuit size
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• Zero knowledge and circuit minimization
• Local zero knowledge
• Minimum circuit size, graph isomorphism, and related problems
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• 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
• Minimum circuit size, graph isomorphism, and related problems
• scientific article; zbMATH DE number 7561759 (Why is no real title available?)
• On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
• The non-hardness of approximating circuit size
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• NP-hardness of approximating meta-complexity: a cryptographic approach
• NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
• A meta-complexity characterization of quantum cryptography
• Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
• NP-hardness of approximating meta-complexity: a cryptographic approach
• On p-group isomorphism: search-to-decision, counting-to-decision and nilpotency class reductions via tensors
• On the complexity of isomorphism problems for tensors, groups, and polynomials. I: Tensor isomorphism-completeness
• SAT reduces to the minimum circuit size problem with a random oracle
• Kolmogorov complexity characterizes statistical zero knowledge

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)