Hard languages in NP coNP and NIZK proofs from unstructured hardness

DOI10.1145/3564246.3585119MaRDI QIDQ6499301zbMATH OpenWikidataFDO

Authors Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai

Publication date 8 May 2024

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

zbMATH Keywords

complexity theory separationnon-interactive zero knowledge proofsrandom oracles

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A subexponential randomized algorithm for the simple stochastic game problem
• An average-case depth hierarchy theorem for Boolean circuits
• Can PPAD hardness be based on standard cryptographic assumptions?
• Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation
• Certifying trapdoor permutations, revisited
• Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility
• Feistel structures for MPC, and more
• Fiat-Shamir: from practice to theory
• Hardness vs randomness
• How To Prove Yourself: Practical Solutions to Identification and Signature Problems
• scientific article; zbMATH DE number 3814972 (Why is no real title available?)
• scientific article; zbMATH DE number 3921977 (Why is no real title available?)
• scientific article; zbMATH DE number 1256721 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 4185033 (Why is no real title available?)
• Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency
• MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity
• Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions
• Non-interactive Zaps and New Techniques for NIZK
• Non-interactive zero knowledge \textit{proofs} in the random oracle model
• Non-interactive zero knowledge from sub-exponential DDH
• Noninteractive zero knowledge for NP from (Plain) Learning With Errors
• On constructing 1-1 one-way functions
• On Invertible Sampling and Adaptive Security
• On succinct non-interactive arguments in relativized worlds
• Perfect structure on the edge of chaos. Trapdoor permutations from indistinguishability obfuscation
• Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativized cryptography
• Structure versus hardness through the obfuscation lens
• Substitution-permutation networks, pseudorandom functions, and natural proofs
• The complexity of approximating a nonlinear program
• The complexity of stochastic games
• The journey from NP to TFNP hardness
• The random oracle hypothesis is false
• The random oracle methodology, revisited.
• Theory of Cryptography
• Unconditional Characterizations of Non-interactive Zero-Knowledge
• ZAPs and non-interactive witness indistinguishability from indistinguishability obfuscation

Cited in

(3)

• (Inefficient prover) ZAPs from hard-to-invert functions
• The black-box simulation barrier persists in a fully quantum world
• Random permutations in computational complexity

This page was built for publication: Hard languages in NP \(\cap\) coNP and NIZK proofs from unstructured hardness

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