Paper 2012/480
Short Signatures From DiffieHellman: Realizing Short Public Key
Jae Hong Seo
Abstract
Efficient signature scheme whose security is relying on reliable assumptions is important. There are few schemes based on the standard assumptions such as the DiffieHellman (DH) in the standard model. We present a new approach for (hashandsign) DHbased signature scheme in the standard model. First, we combine two known techniques, programmable hashes and a tagbased 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 apriori 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 polynomialtime reductions in all security proofs.
Metadata
 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 (http://eprint.iacr.org/2013/171).
 Keywords
 Short SignaturesDiffieHellmanShort Public Key
 Contact author(s)
 jhsbhs @ gmail com
 History
 20130401: last of 3 revisions
 20120821: received
 See all versions
 Short URL
 https://ia.cr/2012/480
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/480, author = {Jae Hong Seo}, title = {Short Signatures From DiffieHellman: Realizing Short Public Key}, howpublished = {Cryptology ePrint Archive, Paper 2012/480}, year = {2012}, note = {\url{https://eprint.iacr.org/2012/480}}, url = {https://eprint.iacr.org/2012/480} }