Lecture Notes in Computer Science, 2002, Volume 2551/2002, 79-92, DOI: 10.1007/3-540-36231-2_8

Never Trust Victor: An Alternative Resettable Zero-Knowledge Proof System

Olaf Müller and Michael Nüsken

View Related Documents

Abstract

We present a new resettable zero-knowledge proof system for graph 3-colorability with round complexity O(u(n) log2 n), where u: ℕ → ℝ>0 is any unbounded function and n denotes the number of vertices in the graph. Furthermore, we present a new formulation of the definition of resettable zero-knowledge and define and implement a knowledgeable commitment scheme: after the commitment phase the receiver is convinced that the sender knows a valid decommitment. This remains true even if the receiver is resettable, albeit with the drawback of non-constant round complexity. This is achieved by appending a resettable perfect witness-indistinguishable proof of knowledge of a decommitment to the original commit phase. We base all our constructions on a standard intractability assumption: the hardness of one of the many variants of the discrete logarithm problem.

Fulltext Preview

Image of the first page of the fulltext document