Cryptology ePrint Archive: Report 2016/483

Proofs of Knowledge on Monotone Predicates and its Application to Attribute-Based Identifications and Signatures

Hiroaki Anada and Seiko Arita and Kouichi Sakurai

Abstract: We propose a concrete procedure of the $\Sigma$-protocol introduced by Cramer, Damg\r{a}rd and Schoenmakers at CRYPTO '94, which is for proving knowledge that a set of witnesses satisfies a monotone predicate in witness-indistinguishable way; that is, hiding the assignment of truth in the predicate. We provide our procedure by extending the so-called OR-proof. As applications, we point out that our $\Sigma$-protocol serves as building blocks of pairing-free attribute-based identification and signature schemes for \emph{any monotone} predicates.

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

Original Publication (with major 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 6 Oct 2018

Contact author: anada at sun ac jp

Available format(s): PDF | BibTeX Citation

Note: The preliminary version of this paper appeared in Proceedings of the 2nd ACM ASIA Public-Key Cryptography Workshop - ASIAPKC 2014, pp. 49-58, under the title ``Attribute-Based Signatures without Pairings via the Fiat-Shamir Paradigm''. This is a corrected version. We removed the proposed attribute-based identification and signature schemes because they have only one-time attribute privacy. Instead, we mentioned that our protocol serves as building blocks of pairing-free attribute-based identification and signature schemes for any monotone predicates.

Version: 20181006:162123 (All versions of this report)

Short URL: ia.cr/2016/483


[ Cryptology ePrint archive ]