Helger Lipmaa's publications

On Diophantine Complexity and Statistical Zero-Knowledge Arguments

Helger Lipmaa. On Diophantine Complexity and Statistical Zero-Knowledge Arguments. In Chi Sung Laih, editor, Advances on Cryptology --- ASIACRYPT 2003, volume 2894 of Lecture Notes in Computer Science, pages 398--415, Taipei, Taiwan, November 30--December 4, 2003. Springer, Heidelberg.

File: [.ps.bz2 (105 KB), .pdf (306 KB)] ps recommended.


We show how to construct practical honest-verifier statistical zero-knowledge 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.

Keywords: Arguments of knowledge, Diophantine complexity, integer commitment scheme, statistical zero knowledge.


Supersedes: Obsoletes the next paper: Helger Lipmaa. Statistical Zero-Knowledge Proofs from Diophantine Equations, eprint 2001/086. The latter was was published on IACR eprint archive in November 2001 for time-stamping purposes. The ASIACRYPT 2003 paper is a completely revised version with many new results.

Comment: This paper contains a couple of small mistakes. Most importantly, the solution (given in appendix) of using several generators and list commitments obviously does not work (thanks for Rohe/Adelsbach for pointing it out) - but this has no implications to the rest of the paper. I plan to update it for a journal publication

More information: CiteSeer. Publisher Webpage.


Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.