A novel short signature without random oracles

We present a new short signature provably secure under the standard model. The proposed signature is equipped with attractive properties: (1) The signature can be generated without learning the message content; (2) The signature can be re-randomized and the resulting signature has the same distribution as the original one; (3) Without knowledge of the original signature and even the message content, one can be convinced that a signature holder has obtained the correct signature from the signer. We note that these properties are useful to construct many cryptographic protocols such as pseudonym systems. To the best of our knowledge, this is the first short signature scheme that is equipped with these properties. Our signature is proven to be Existentially unforgeable under a Chosen message attack (EUF-CMA) in the standard definition without using random oracles. The signature length is as short as the state-of-the-art Boneh-Boyen short signature.