We also investigate lower bounds on the size of the public verification key in the Type II setting. Previous work in structure-preserving signatures has explored lower bounds on the number of verification equations and the number of group elements in a signature but the size of the verification key has not been investigated before. We show that in the Type II setting it is necessary to have at least 2 group elements in the public verification key in a signature scheme with a single verification equation.
Our constructions match the lower bounds so they are optimal with respect to verification complexity, signature sizes and verification key sizes. In fact, in terms of verification complexity, they are the most efficient structure preserving signature schemes to date. Depending on the context in which a scheme is deployed it is sometimes desirable to have strong existential unforgeability, and in other cases full randomizability. We give two structure-preserving signature schemes with a single verification equation where both the signatures and the public verification keys consist of two group elements each. One signature scheme is strongly existentially unforgeable, the other is fully randomizable. Having such simple and elegant structure-preserving signatures may make the Type II setting the easiest to use when designing new structure-preserving cryptographic schemes, and lead to schemes with the greatest conceptual simplicity.Category / Keywords: public-key cryptography / Structure-preserving signatures, Type II pairings, strong existential unforgeability, randomizability, lower bounds Date: received 1 May 2014 Contact author: mehdi tibouchI at normalesup org Available format(s): PDF | BibTeX Citation Version: 20140501:164225 (All versions of this report) Discussion forum: Show discussion | Start new discussion