An efficient hierarchical ID-Based signature scheme

The GSHIDS scheme is the only HIDS scheme at present, however, it is not very efficient. In this paper, an efficient hierarchical ID-based signature scheme, where all efficiency parameters are independent of the hierarchy depth, is presented. We solve the problem that signature expansion factor and complexity of verification grow linearly with the number of hierarchy level in GSHIDS scheme. Signature in our scheme consists of just three group elements. In addition, verification only requires two paring operations and one multiplicative operation. Other algorithms in our scheme are nearly as efficient as those in GSHIDS scheme. Such high efficiency is thanks to the new technique adopted in extraction algorithm. We prove that our scheme is secure against adaptively chosen message and ID-tuple attack in random oracle model when GSHIDS scheme is secure. Our scheme can be extended to many aspects and constructed to other efficient schemes such as distributed PKGs scheme, hierarchical ID-based threshold signature scheme, and very efficient forward secure signature scheme.