Daniel Wichs
New York University

Isolated Proofs of Knowledge and Isolated Zero Knowledge

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 unbounded values of $\ell$. However, for any
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.

Ivan Damgaard and Jesper Buus Nielsen and Daniel Wichs