International Association
for Cryptologic Research

In EUROCRYPT 2005, Waters proposed a signature scheme based on the computational Diffie-Hellman (DH) assumption without random oracles. His scheme is the first and sole signature scheme in the category of (hash-and-sign) signature schemes secure under the DH assumption in the standard model and has also been applied to the design of numerous protocols in the various cryptographic areas. However, the Waters signature scheme suffered from a large public key of $\\Theta(\\lambda)$ group elements, where $\\lambda$ is the security parameter. Realizing standard model DH-based signature scheme, in which both the signature and the public key are short, has been an open problem.

We propose short signatures from the DH assumption, which has a sublinear size public key. More precisely, our proposal produces a public key of $\\Theta(\\sqrt{\\frac{\\lambda}{\\log \\lambda}})$ group elements. Our construction is inspired from two techniques for short signatures such as using programmable hashes and using tags. From two previous techniques, we first derive a signature scheme with a somewhat short public key of $\\Theta(\\frac{\\lambda}{\\log\\lambda})$, and then we developed a new technique for {\\em asymmetric trade} between the public key size and the signature size. In particular, by adding one field element in each signature, we can reduce the public key size to $O(\\sqrt{\\frac{\\lambda}{\\log \\lambda}})$ group elements, so that the resulting signature size is two group elements and two field elements.

We also propose a variant by applying a technique for compressing tag vectors so that the resulting signatures has a shorter signature size (two group elements and one field element) by augmenting signing/verification costs and adding constant factor in public key size (that is, public key size is still $\\Theta(\\sqrt\\frac{\\lambda}{\\log\\lambda})$ group elements). Note that we limit ourselves to dealing with only polynomial-time reductions in all security proofs.