Paper 2005/230

Yet Another Short Signatures Without Random Oracles from Bilinear Pairings

Fangguo Zhang and Xiaofeng Chen

Abstract

In recent years, cryptographic protocols based on the bilinear pairings have attracted much attention. One of the most distinguished achievements in this area was the solution to design short signatures. Up to now, there exist two short signature schemes with random oracles and one without random oracles from bilinear pairings. In this paper, we describe another short signature scheme which is existentially unforgeable under a chosen message attack without using random oracles. The security of our scheme depends on a new complexity assumption we call the $k$+1 square roots assumption. We discuss the relationship between the $k$+1 square roots assumption and some related problems and give some conjectures. Further more, the $k$+1 square roots assumption gives even shorter signatures under the random oracles.