Cryptology ePrint Archive: Report 2003/105

On Diophantine Complexity and Statistical Zero-Knowledge Arguments

Helger Lipmaa

Abstract: We show how to construct practical honest-verifier statistical zero-knowledge \emph{Diophantine} arguments of knowledge (HVSZK AoK) that a committed tuple of integers belongs to an arbitrary language in bounded arithmetic. While doing this, we propose a new algorithm for computing the Lagrange representation of nonnegative integers and a new efficient representing polynomial for the exponential relation. We apply our results by constructing the most efficient known HVSZK AoK for non-negativity and the first constant-round practical HVSZK AoK for exponential relation. Finally, we propose the outsourcing model for cryptographic protocols and design communication-efficient versions of the Damgård-Jurik multi-candidate voting scheme and of the Lipmaa-Asokan-Niemi $(b+1)$st-price auction scheme that work in this model.

Category / Keywords: cryptographic protocols/Arguments of knowledge, Diophantine complexity, integer commitment scheme, statistical zero knowledge

Publication Info: This version corresponds to the Asiacrypt 2003 publication

Date: received 25 May 2003, last revised 5 Sep 2003

Contact author: helger at tcs hut fi

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Note: Manuscript, obsoletes eprint 2001-086.

Version: 20030905:082109 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]