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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2001/086}},
      url = {https://eprint.iacr.org/2001/086}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.