Paper 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$.
Note: Vastly updated, obsoletes the first submitted version. Compated to the second submitted version (November 13), only the abstract was changed.
Metadata
- Available format(s)
- PS
- Category
- Foundations
- Publication info
- Published elsewhere. Submitted© Preliminary version, Nov 5 2001
- Keywords
- Diophantine equationsinteger commitment schemestatistical zero-knowledge
- Contact author(s)
- helger @ tcs hut fi
- History
- 2001-11-20: last of 5 revisions
- 2001-10-25: received
- See all versions
- Short URL
- https://ia.cr/2001/086
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2001/086,
author = {Helger Lipmaa},
title = {Statistical Zero-Knowledge Proofs from Diophantine Equations},
howpublished = {Cryptology {ePrint} Archive, Paper 2001/086},
year = {2001},
url = {https://eprint.iacr.org/2001/086}
}
