More Efficient Structure-Preserving Signatures: Or Bypassing the Lower Bounds

Structure-preserving signatures are an important cryptographic primitive that is useful for the design of modular cryptographic protocols. In this work, we show how to bypass most of the existing lower bounds in the most efficient Type-III bilinear group setting. We formally define a new variant of structure-preserving signatures in the Type-III setting and present a number of fully secure schemes with signatures half the size of existing ones. We also give different constructions including constructions of optimal one-time signatures. In addition, we prove lower bounds and provide some impossibility results for the variant we define. Finally, we show some applications of the new constructions.