In this paper we undertake a concrete analysis of the Abe et al. claims. By properly accounting for the actual structure of the underlying groups and subgroup membership testing of group elements in signatures, we show that the schemes are not as efficient as claimed. We present natural Type 3 analogues of the Type 2 schemes, and show that the Type 3 schemes are superior to their Type 2 counterparts in every aspect. We also formally establish that in the concrete mathematical structure of asymmetric pairing, all Type 2 structure-preserving signature schemes can be converted to the Type 3 setting without any penalty in security or efficiency, and show that the converse is false. Furthermore, we prove that the Type 2 setting does not allow one to circumvent the known lower bound result for the Type 3 setting. Our analysis puts the optimality claims for Type 2 structure-preserving signature in a concrete perspective and indicates an incompleteness in the definition of a generic bilinear group in the Type 2 setting.
Category / Keywords: Original Publication (with minor differences): IACR-ASIACRYPT-2015 Date: received 18 Aug 2014, last revised 10 Sep 2015 Contact author: sanjit at csa iisc ernet in Available format(s): PDF | BibTeX Citation Version: 20150910:074328 (All versions of this report) Short URL: ia.cr/2014/635 Discussion forum: Show discussion | Start new discussion