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.
Metadata
- Available format(s)
- Publication info
- Published elsewhere. Major revision. The 2nd ACM ASIA Public-Key Cryptography Workshop - ASIAPKC 2014, The 18th Annual International Conference on Information Security and Cryptology - ICISC 2015
- DOI
- 10.1145/2600694.2600696, 10.1007/978-3-319-30840-1_3
- Keywords
- proof of knowledgeaccess structureattribute-basedidentificationsignaturetwo-tier keys
- Contact author(s)
- anada @ sun ac jp
- History
- 2020-06-23: last of 17 revisions
- 2016-05-20: received
- See all versions
- Short URL
- https://ia.cr/2016/483
- License
-
CC BY