Abstract:
We describe a 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 Strong Diffie-Hellman assumption. This
assumption has similar properties to the Strong RSA assumption,
hence the name. Strong RSA was previously used to construct signature
schemes without random oracles. However, signatures generated by our
scheme are much shorter and simpler than signatures from schemes
based on Strong RSA. Furthermore, our scheme provides a limited form
of message recovery.
Reference:
In proceedings of Eurocrypt 2004, LNCS 3027, pp. 56-73, 2004
Full paper: pdf