CryptoDB
On Diophantine Complexity and Statistical Zero-Knowledge Arguments
Authors: | |
---|---|
Download: | |
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{\aa}rd-Jurik multi-candidate voting scheme and of the Lipmaa-Asokan-Niemi $(b+1)$st-price auction scheme that work in this model. |
BibTeX
@misc{eprint-2003-11820, title={On Diophantine Complexity and Statistical Zero-Knowledge Arguments}, booktitle={IACR Eprint archive}, keywords={cryptographic protocols/Arguments of knowledge, Diophantine complexity, integer commitment scheme, statistical zero knowledge}, url={http://eprint.iacr.org/2003/105}, note={This version corresponds to the Asiacrypt 2003 publication helger@tcs.hut.fi 12300 received 25 May 2003, last revised 5 Sep 2003}, author={Helger Lipmaa}, year=2003 }