|
How To Go Beyond the Black-Box Simulation Barrier
Boaz Barak
Abstract
The simulation paradigm is central to cryptography. A
simulator
is an algorithm that tries to simulate the interaction of the
adversary with an honest party, without knowing the private input
of this honest party. Previously known simulators used the
adversary's algorithm as a black-box. We present the first
constructions of non-black-box simulators. Using these new
non-black-box techniques we obtain a zero-knowledge argument
system. This argument system satisfies several properties that
were previously proven to be impossible to obtain using
black-box simulators.
Specifically, assuming the existence of collision resistent hash
functions, we construct a zero-knowledge argument system for
NP that satisfies the following properties:
- This system has a constant number of rounds with
negligible soundness error.
- It remains zero knowledge even when composed concurrently
n times, where n is the security parameter.
Simultaneously obtaining 1 and 2 has been recently proven to be
impossible to achieve using black-box simulators.
- It is an Arthur-Merlin (public coins) protocol.
Simultaneously obtaining 1 and 3 was known to be impossible to
achieve with a black-box simulator.
- It has a simulator that runs in strict polynomial time,
rather than in expected polynomial time.
All previously known constant-round, negligible-error
zero-knowledge arguments utilized expected polynomial-time
simulators.
Versions
home | research | links | cv | pictures
|