Paper 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å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.

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.