**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

[ Cryptology ePrint archive ]