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

Category / Keywords: proof of knowledge, access structure, attribute-based, identification, signature, two-tier keys

Original Publication (with major differences): The 2nd ACM ASIA Public-Key Cryptography Workshop - ASIAPKC 2014, The 18th Annual International Conference on Information Security and Cryptology - ICISC 2015
10.1145/2600694.2600696, 10.1007/978-3-319-30840-1_3

Date: received 19 May 2016, last revised 12 Jan 2017

Contact author: anada at sun ac jp

Available format(s): PDF | BibTeX Citation

Note: Witness-indistinguishability was emphasized.

Version: 20170112:105033 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]