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 a sigma-protocol proving knowledge that a set of witnesses satisfies a monotone predicate in witness-indistinguishable manner. Inspired by the high-level proposal by Cramer, Damgard and Schoenmakers at CRYPTO '94, we construct the concrete procedure by extending the so-called OR-proof. Next, using as a witness a signature-bundle of the Fiat-Shamir signatures, we provide an attribute-based identification scheme (ABID). Then, applying the Fiat-Shamir transform to our ABID, we obtain an attribute-based signature scheme (ABS). These generic schemes are constructed from a given sigma-protocol, and the latter scheme has a feature of linkable signatures. Applying the two-tier technique proposed at PKC 2007 by Bellare and Shoup to our ABID, we obtain an attribute-based two-tier signature scheme (ABTTS). The scheme has a feature to attain attribute-privacy paying expense of the secondary-key issuing. We provide two directions of instantiation. One is to use the Guillou-Quisquater and the Schnorr sigma-protocols, which produce ABID, ABS and ABTTS schemes with a loose security reduction in the random oracle model without pairing computation. The other is to use the Camenisch-Lysyanskaya sigma-protocols in the RSA setting and discrete-logarithm setting, which produce ABTTS schemes with a tighter security reduction in the standard model.

Note: Witness-indistinguishability was emphasized.