International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On Diophantine Complexity and Statistical Zero-Knowledge Arguments

Helger Lipmaa
Search ePrint
Search Google
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.
  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},
  note={This version corresponds to the Asiacrypt 2003 publication 12300 received 25 May 2003, last revised 5 Sep 2003},
  author={Helger Lipmaa},