Paper 2003/105 Original: eprint.iacr.org/2003/105 ↗
On Diophantine Complexity and Statistical Zero-Knowledge Arguments
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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2003-09-05: last updated
- 2003-05-29: published
- Short URL
- https://ia.cr/2003/105
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}