Statistical Zero-Knowledge Proofs from Diophantine Equations

Helger Lipmaa

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} ⟺ (\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 belongs to . 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 .

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
Keywords: Diophantine equations integer commitment scheme statistical 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}
}