reading assignment (for 4/1/2011), exercise, and more

[עודד גולדרייך‎]

[Subject: reading assignment (for 4/1/2011), exercise, and more]

Please note all *four* parts of this post.


PART 1: READING ASSIGNMENT FOR 4/1/2011
---------------------------------------


Read all of Section 4.3.
This includes the basic definitions (Sec 4.3.1),
an example (i.e., ZK for GI -- Sec 4.3.2),
the augmentation by auxiliary-inputs (Sec 4.3.3),
and the sequential composition theorem (sec 4.4.4).
The latter is very important; please read it carefully
rather than assuming that this is straightforward
(as it is not -- compare, e.g., parallel composition...).


PART 2: EXERCISE TO BE SUBMITTED ON 11/1/2011
---------------------------------------

1. Prove that if $S$ has a zero-knowledge NP-proof system,
then $S$ is in BPP. (You *may* generalize this to any ZKIP
in which the communication is uni-directional; that is,
in the generalized system the prover sends a single message,
but the verifier decided probabilistically whether to accept.)

2. Prove that if $S$ has a zero-knowledge interactive proof system
in which the verifier is deterministic, then $S$ is in BPP.


PART 3: TWO ADVANCED TOPICS DISCUSSED IN TODAYS'S MEETING
---------------------------------------

[1st topic]
In the meeting somebody (I'll not risk providing names...)
asked about a variant of the definition of zero-knowledge
that is obtained by considering only verifiers that output a single
bit
(i.e., take the standard definition that refers to the output of the
verifier
and restrict to verifiers that output a single bit).
My on-line impression was that this is as strong as the standard
definition,
but currently I'm not sure. Furthermore, I have a vague recall that
sombody has suggested this variant and studied it; I will try to find
out...


[2nd topic]
At the end of the meeting, I outlined a strategy $P$
that is zero-knowledge (wrt the "bare" definition)
but is not zero-knowledge *w.r.t auxiliary inputs*
(and yields knowsledge when executed twice, sequentially).

The description refers to a sequence of sets $\{S_n\}$
such that (1) [pseudorandomness] a uniformly distributed
element in $S_n$ is computationally indistinguishable from
a uniformly distributed $n$-bit long strong, and (2) [evasiveness]
for every probabilistic polynomial-time $A$ the proabbility that
$A(1^n)$
hits $S_n$ is negligible (in $n$).

On input $x$, where $n=|x|$, the strategy $P$ behaves as follows:
Upon receiving an $n$-bit string, denoted $r$, from the verifier,
if $r$ is in $S_n$, then $P$ answers with $K(x)$,
where $K$ is a hard to compute function,
and otherwise (i.e,., $r\not\in S_n$) $P$ answers
with a uniformly selected element of $S_n$.

Clearly, $P$ is not auxiliary-input zero-knowledge
(e.g., when the auxiliary input is in $S_n$,
the verifier can easily gets knowledge by sending this aux).
Note that $P$ is *bare* zero-knowledge by virtue of a simulator
that just outputs a uniformly distributed $n$-bit string
(which is comput' indist' from a random element of $S_n$),
because it is infeasible for the *bare* verifier to send
a string that hits $S_n$.


PART 4: FOR THOSE RUSHING FORWARD
---------------------------------------


The last two assignments will be devoted to the
construction of zero-knowledge proof systems for
any set in NP (Sec 4.4).
After seeing the abstract outline of this proof system,
you will be well motivated to learn a new tool --
commitment schemes (in Sec 4.4.1). Next, turn to the
digital implementation of the ZKIP for NP (in Sec 4.4.2).