Cryptology ePrint Archive: Report 2012/480

Short Signatures From Diffie-Hellman: 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 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.

Category / Keywords: Short Signatures, Diffie-Hellman, Short Public Key

Publication Info: 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).

Date: received 20 Aug 2012, last revised 31 Mar 2013

Contact author: jhsbhs at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20130401:051440 (All versions of this report)

Short URL: ia.cr/2012/480

Discussion forum: Show discussion | Start new discussion