Paper 2007/331

Isolated Proofs of Knowledge and Isolated Zero Knowledge

Ivan Damgaard, Jesper Buus Nielsen, and Daniel Wichs

Abstract

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 $$-IPoK for \emph{unbounded} values of $$. However, for any \emph{pre-defined} threshold $$, and any relation in NP and we construct an $$-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 $$ 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 $$-IPoK that is also ZK with respect to such a verifier. As another new notion, we define $$-isolated zero knowledge ($$-IZK) where the verifier is $$-isolated. For every relation in NP and every $$, we construct an $$-IPoK protocol that is also $$-IZK. We describe several applications of $$-IPoK protocols under the physical assumption that one can $$-isolate a prover for the duration of the proof phase. Firstly, we can use a witness indistinguishable (WI) $$-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 $$-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.