On the Possibility of One-Message Weak Zero-Knowledge
Boaz Barak and Rafael Pass
Abstract
We investigate whether it is possible to obtain
any meaningful type of zero-knowledge proofs using a
one-message (i.e., non-interactive) proof system. We
show that, under reasonable (although not standard) assumptions,
there exists a one-message proof system for every language in
NP that satisfies the following relaxed form of zero knowledge:
The soundness condition holds only against cheating provers
that run in uniform (rather than non-uniform) probabilistic
polynomial-time.
The zero-knowledge condition is obtained using a simulator
that runs in quasi-polynomial (rather than polynomial)
time.
We note that it is necessary to introduce both relaxations
to obtain a one-message system for a non-trivial language. We
stress that our result is in the plain model, and in particular we
do not assume any setup conditions (such as the existence
of a shared random string).
We also discuss the validity of our assumption, and show two
conditions that imply it. In addition, we show that an assumption
of a similar kind is necessary in order to obtain a
one-message system that satisfies some sort of meaningful
zero-knowledge and soundness conditions.
Versions
home | research | links | cv | pictures
|