Paper 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.
Note: Manuscript, obsoletes eprint 2001-086.
Metadata
- Available format(s)
- PS
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. This version corresponds to the Asiacrypt 2003 publication
- Keywords
- Arguments of knowledgeDiophantine complexityinteger commitment schemestatistical zero knowledge
- Contact author(s)
- helger @ tcs hut fi
- History
- 2003-09-05: revised
- 2003-05-29: received
- See all versions
- Short URL
- https://ia.cr/2003/105
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2003/105,
author = {Helger Lipmaa},
title = {On Diophantine Complexity and Statistical Zero-Knowledge Arguments},
howpublished = {Cryptology {ePrint} Archive, Paper 2003/105},
year = {2003},
url = {https://eprint.iacr.org/2003/105}
}
