Welcome to the resource topic for 2007/331
Title:
Isolated Proofs of Knowledge and Isolated Zero Knowledge
Authors: Ivan Damgaard, Jesper Buus Nielsen, 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{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.
ePrint: https://eprint.iacr.org/2007/331
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .