Cryptology ePrint Archive: Report 2007/195

Verifying Statistical Zero Knowledge with Approximate Implementations

Ling Cheung and Sayan Mitra and Olivier Pereira

Abstract: 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.

Category / Keywords: foundations / formal verification, statistical zero knowledge

Date: received 23 May 2007

Contact author: lcheung at theory csail mit edu

Available format(s): PDF | BibTeX Citation

Version: 20070525:085630 (All versions of this report)

Short URL: ia.cr/2007/195

Discussion forum: Show discussion | Start new discussion