Cryptology ePrint Archive: Report 2005/386

A New Short Signature Scheme Without Random Oracles from Bilinear Pairings

Fangguo Zhang, Xiaofeng Chen, Willy Susilo and Yi Mu

Abstract: In this paper, we propose a new signature scheme that is existentially unforgeable under a chosen message attack without random oracle. The security of our scheme depends on a new complexity assumption called the $k$+1 square roots assumption. We also discuss the relationship between the $k$+1 square roots assumption and some related problems and provide some conjectures. Moreover, the $k$+1 square roots assumption can be used to construct shorter signatures under the random oracle model. As some applications, a new chameleon hash signature scheme and a on-line/off-line signature scheme and a new efficient anonymous credential scheme based on the proposed signature scheme are presented.

Category / Keywords: Short signature, Bilinear pairings,Standard model, Random oracle, Anonymous credential

Date: received 24 Oct 2005, last revised 14 Jul 2006

Contact author: isszhfg at mail sysu edu cn

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: We reorganized the paper and added an anonymous credential scheme as another application of the proposed signature scheme.

Version: 20060714:131711 (All versions of this report)

Short URL: ia.cr/2005/386

Discussion forum: Show discussion | Start new discussion