Paper 2014/567

Attribute-Based Signatures without Pairings by the Fiat-Shamir Transformation

Hiroaki Anada, Seiko Arita, and Kouichi Sakurai

Abstract

We propose the first practical attribute-based signature (ABS) scheme with attribute privacy without pairings in the random oracle model. Our strategy is in the Fiat-Shamir paradigm; we first provide a concrete construction of a $\Sigma$-protocol of \textit{boolean proof}, which is a generalization of the well-known $\Sigma$-protocol of OR-proof, so that it can treat any monotone boolean formula instead of a single OR-gate. Then, we apply the Fiat-Shamir transformation to our $\Sigma$-protocol of boolean proof and obtain a non-interactive witness-indistinguishable proof of knowledge system (NIWIPoK) which has a knowledge extractor in the random oracle model. Finally, by combining our NIWIPoK with a credential bundle scheme of the Fiat-Shamir signature, we obtain an attribute-based signature scheme (ABS) which possesses the property of attribute privacy. The series of constructions are obtained from a given $\Sigma$-protocol and can be attained without pairings.

Note: The preliminary version of this paper appeared in Proceedings in the 2nd ACM ASIA Public-Key Cryptography Workshop - ASIAPKC 2014, pp. 49-58, Keita Emura, Goichiro Hanaoka and Yunlei Zhao eds., under the title of "Attribute-Based Signatures without Pairings via the Fiat-Shamir Paradigm". This is the full version and more than a half has been rewritten.