Paper 2012/480

Short Signatures From Diffie-Hellman: Realizing Short Public Key

Jae Hong Seo


Efficient signature scheme whose security is relying on reliable assumptions is important. There are few schemes based on the standard assumptions such as the Diffie-Hellman (DH) in the standard model. We present a new approach for (hash-and-sign) DH-based signature scheme in the standard model. First, we combine two known techniques, programmable hashes and a tag-based signature scheme so that we obtain a short signature scheme with somewhat short public key of $\Theta(\frac{\lambda}{\log\lambda})$ group elements. Then, we developed a new technique for {\em asymmetric trade} between the public key and random tags, which are part of signatures. Roughly speaking, we can dramatically reduce the public key size by adding one field element in each signature. More precisely, our proposal produces public key of $\Theta(\sqrt{\frac{\lambda}{\log \lambda}})$ group elements, where $\lambda$ is the security parameter. The signature size is still short, requiring two elements in a group of order $p$ and two integers in $\zp$. In our approach, we can guarantee the security against adversaries that make an a-priori bounded number of queries to signing oracle (we call {\em bounded CMA}). i.e., the maximum number $q$ of allowable signing queries is prescribed at the parameter generating time. Note that for polynomial $q$, we limit ourselves to dealing with only polynomial-time reductions in all security proofs.

Available format(s)
Publication info
Published elsewhere. An extended abstract will appear at Eurocrypt 2013 in the form of the merged paper with some independent work (
Short SignaturesDiffie-HellmanShort Public Key
Contact author(s)
jhsbhs @ gmail com
2013-04-01: last of 3 revisions
2012-08-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jae Hong Seo},
      title = {Short Signatures From Diffie-Hellman: Realizing Short Public Key},
      howpublished = {Cryptology ePrint Archive, Paper 2012/480},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.