eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2007/195

Verifying Statistical Zero Knowledge with Approximate Implementations

Ling Cheung, Sayan Mitra, and Olivier Pereira


Statistical zero-knowledge (SZK) properties play an important role in designing cryptographic protocols that enforce honest behavior while maintaining privacy. This paper presents a novel approach for verifying SZK properties, using recently developed techniques based on approximate simulation relations. We formulate statistical indistinguishability as an implementation relation in the Task-PIOA framework, which allows us to express computational restrictions. The implementation relation is then proven using approximate simulation relations. This technique separates proof obligations into two categories: those requiring probabilistic reasoning, as well as those that do not. The latter is a good candidate for mechanization. We illustrate the general method by verifying the SZK property of the well-known identification protocol of Girault, Poupard and Stern.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
formal verificationstatistical zero knowledge
Contact author(s)
lcheung @ theory csail mit edu
2007-05-25: received
Short URL
Creative Commons Attribution


      author = {Ling Cheung and Sayan Mitra and Olivier Pereira},
      title = {Verifying Statistical Zero Knowledge with Approximate Implementations},
      howpublished = {Cryptology ePrint Archive, Paper 2007/195},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/195}},
      url = {https://eprint.iacr.org/2007/195}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.