Cryptology ePrint Archive: Report 2001/086

Statistical Zero-Knowledge Proofs from Diophantine Equations

Helger Lipmaa

Abstract: A family $(S_t)$ of sets is $p$-bounded Diophantine if $S_t$ has a representing $p$-bounded polynomial $R_{S,t}$, s.t. $x\in S_t \iff (\exists y)[R_{S}(x;y)=0]$. We say that $(S_t)$ is unbounded Diophantine if additionally, $R_{S,t}$ is a fixed $t$-independent polynomial. We show that $p$-bounded (resp., unbounded) Diophantine set has a polynomial-size (resp., constant-size) statistical zero-knowledge proof system that a committed tuple $x$ belongs to $S$. We describe efficient SZK proof systems for several cryptographically interesting sets. Finally, we show how to prove in SZK that an encrypted number belongs to $S$.

Category / Keywords: foundations/Diophantine equations, integer commitment scheme, statistical zero-knowledge

Publication Info: Submitted© Preliminary version, Nov 5 2001

Date: received 25 Oct 2001, last revised 20 Nov 2001

Contact author: helger at tcs hut fi

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Note: Vastly updated, obsoletes the first submitted version. Compated to the second submitted version (November 13), only the abstract was changed.

Version: 20011120:231307 (All versions of this report)

Short URL: ia.cr/2001/086

Discussion forum: Show discussion | Start new discussion