How to go beyond the black-box simulation barrier

By Boaz Barak. Proceedings IEEE International Conference on Cluster Computing, 2001

500 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/e418a05b81c1e6e2903eb7df969a630ee8377700

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation (2001, methodology): “We note, however, that [ 1 ] and [2] assume the existence of trapdoor clawfree permutations, whereas the protocols we use (with expected polynomial-time simulators and extractors) assume only the existence of one-way functions.”
Introduction to Property Testing (2017, background): “, CS-proofs [190, 207] and their applications [31, 67]), and the length of the PCP affects the complexity of those applications.”
The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols (2004, unknown): “Since [11, 12] there has been more progress with regard to the design of non-black-box simulation ZK protocols [1].”
Multi-trapdoor Commitments and Their Applications to Proofs of Knowledge Secure Under Concurrent Man-in-the-Middle Attacks (2004, background): “Barak in [3] shows a constant round non-malleable ZK proof in the non-black-box model (and thus very inefficient).”
Efficient Arguments without Short PCPs (2007, background): “In particular, the existence of interactive proof systems for NP in which the prover is laconic, in the sense that the total length of the messages it sends to the verifier is much smaller than the length of the witness, would imply a nontrivial nondeter- Twenty-Second Annual IEEE Conference on…”
On Cryptographic Assumptions and Challenges (2003, background): “This is especially acute in case of non block-box simulation [4].”
Improved Delegation of Computation using Fully Homomorphic Encryption (2010, unknown): “However, the Random Oracle Heuristic is known to be unsound in general [CGH04] and even in the context of Fiat–Shamir [ Bar01 ,GK03].”
How To Simulate It - A Tutorial on the Simulation Proof Technique (2016, background): “, the non-black uniform zero-knowledge protocol of [1]), the ability to set the random tape of the adversary does not help.”