Cryptology ePrint Archive: Report 2016/483

A Concrete Procedure of the $\Sigma$-protocol on Monotone Predicates

Hiroaki Anada and Seiko Arita and Kouichi Sakurai

Abstract: We propose a concrete procedure of the $\Sigma$-protocol introduced by Cramer, Damgård and Schoenmakers at CRYPTO '94, which is for proving knowledge that a set of witnesses satisfies a monotone predicate in witness-indistinguishable way. We provide the concrete procedure by extending the so-called OR-proof.

Category / Keywords: proof system, sigma-protocol, OR-proof, witness indistinguishability

Original Publication (with minor differences): Proceedings of the 2nd ACM ASIA Public-Key Cryptography Workshop - ASIAPKC 2014, pp. 49-58
DOI: 10.1145/2600694.2600696

Date: received 19 May 2016, last revised 8 Mar 2018

Contact author: anada at sun ac jp

Available format(s): PDF | BibTeX Citation

Note: Explanation on the witness indistinguishability was corrected.

Version: 20180308:090839 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]