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
}