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 $\ell$IPoK for \emph{unbounded} values of $\ell$. However, for any \emph{predefined} 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 ``maninthemiddle'' 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.
Metadata
 Available format(s)
 PDF PS
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. This is the full version of a paper accepted to Eurocrypt 2008
 Keywords
 zero knowledgeproof of knowledgeisolationuniversal composability
 Contact author(s)
 danwichs @ gmail com
 History
 20080121: last of 2 revisions
 20070822: received
 See all versions
 Short URL
 https://ia.cr/2007/331
 License

CC BY
BibTeX
@misc{cryptoeprint:2007/331, author = {Ivan Damgaard and Jesper Buus Nielsen and Daniel Wichs}, title = {Isolated Proofs of Knowledge and Isolated Zero Knowledge}, howpublished = {Cryptology ePrint Archive, Paper 2007/331}, year = {2007}, note = {\url{https://eprint.iacr.org/2007/331}}, url = {https://eprint.iacr.org/2007/331} }