Strict polynomial-time in simulation and extraction

DOI10.1145/509907.509979zbMATH Open1192.68343OpenAlexW2075455730MaRDI QIDQ3579210FDOQ3579210

Authors: Boaz Barak, Yehuda Lindell 

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (13)

• The Knowledge Complexity of Interactive Proof Systems
• On Non-Black-Box Simulation and the Impossibility of Approximate Obfuscation
• A black-box approach to post-quantum zero-knowledge in constant rounds
• Fiat-Shamir transformation of multi-round interactive proofs (Extended version)
• Fiat-Shamir transformation of multi-round interactive proofs
• On the Implausibility of Constant-Round Public-Coin Zero-Knowledge Proofs
• On expected probabilistic polynomial-time adversaries: a suggestion for restricted definitions and their benefits
• Constant-round zero-knowledge proofs of knowledge with strict polynomial-time extractors for NP
• On Zero-Knowledge with Strict Polynomial-Time Simulation and Extraction from Differing-Input Obfuscation for Circuits
• Lower bounds for non-black-box zero knowledge
• Three-Round Public-Coin Bounded-Auxiliary-Input Zero-Knowledge Arguments of Knowledge
• A Discrete-Logarithm Based Non-interactive Non-malleable Commitment Scheme with an Online Knowledge Extractor
• Secure Two-Party Computation of Squared Euclidean Distances in the Presence of Malicious Adversaries

This page was built for publication: Strict polynomial-time in simulation and extraction

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