Strict polynomial-time in simulation and extraction
From MaRDI portal
Publication:3579210
DOI10.1145/509907.509979zbMath1192.68343OpenAlexW2075455730MaRDI QIDQ3579210
Publication date: 5 August 2010
Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/509907.509979
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
A black-box approach to post-quantum zero-knowledge in constant rounds, On Non-Black-Box Simulation and the Impossibility of Approximate Obfuscation, Three-Round Public-Coin Bounded-Auxiliary-Input Zero-Knowledge Arguments of Knowledge, On Zero-Knowledge with Strict Polynomial-Time Simulation and Extraction from Differing-Input Obfuscation for Circuits, Constant-round zero-knowledge proofs of knowledge with strict polynomial-time extractors for NP, Fiat-Shamir transformation of multi-round interactive proofs (Extended version), Fiat-Shamir transformation of multi-round interactive proofs, The Knowledge Complexity of Interactive Proof Systems, Lower bounds for non-black-box zero knowledge, On expected probabilistic polynomial-time adversaries: a suggestion for restricted definitions and their benefits, Secure Two-Party Computation of Squared Euclidean Distances in the Presence of Malicious Adversaries, A Discrete-Logarithm Based Non-interactive Non-malleable Commitment Scheme with an Online Knowledge Extractor, On the Implausibility of Constant-Round Public-Coin Zero-Knowledge Proofs
