CSAIL Event Calendar: Previous Series

Isolated Proofs of Knowledge and Isolated Zero Knowledge

Speaker: Daniel Wichs , NYU
Date: April 4 2008
Time: 10:30AM to 12:00PM
Location: 32-449 Patil/Kiva
Host: Prof. Y. Dodis, MIT/NYU

Authors: Ivan Damgaard and Jesper Buus Nielsen and Daniel Wichs

We introduce a new notion called $\ell$-isolated proofs of
knowledge ($\ell$-IPoK). These are proofs of knowledge where a
cheating prover is allowed to exchange up to $\ell$ bits of
communication with some external adversarial environment during the
run of the proof.

Without any additional setup assumptions, no witness hiding protocol
can be an $\ell$-IPoK for \emph{unbounded} values of $\ell$. However,
for any \emph{pre-defined} threshold $\ell$, and any relation in NP
and we construct an $\ell$-IPoK protocol for that relation. The
resulting protocols are zero knowledge (ZK) in the standard sense,
i.e., w.r.t. a verifier that communicates only with the prover during
the proof. The cost of having a large threshold $\ell$ is a large
communication complexity of the constructed protocol. We analyze these
costs and present a solution that is asymptotically optimal.

If a cheating verifier is allowed to communicate arbitrarily with an
external environment, it is not possible to construct an $\ell$-IPoK
that is also ZK with respect to such a verifier. As another new
notion, we define $\ell$-isolated zero knowledge ($\ell$-IZK) where
the verifier is $\ell$-isolated. For every relation in NP and every
$\ell$, we construct an $\ell$-IPoK protocol that is also $\ell$-IZK.

We describe several applications of $\ell$-IPoK protocols under the
physical assumption that one can $\ell$-isolate a prover for the
duration of the proof phase. Firstly, we can use a witness
indistinguishable (WI) $\ell$-IPoK to prevent ``man-in-the-middle''
attacks on identification schemes. Prior results for this scenario
required all verifiers to register keys under a PKI, or the ability to
fully isolate the prover. Secondly, a partially isolated prover can
register a public key and use a WI $\ell$-IPoK to prove knowledge of
the corresponding secret key to another party acting as a verifier.
This allows us to set up a PKI where the key registrant does not need
to trust the Certificate Authority. The PKI is not perfect since the
proof is only witness indistinguishable and not zero knowledge. In a
companion paper, we show how to set up such a PKI and use it to
implement arbitrary multiparty computation securely in the UC
framework without relying on any trusted third parties.

See other events that are part of Cryptography and Information Security Seminars 2007/2008

See other events happening in April 2008