Welcome to the resource topic for
**2012/480**

**Title:**

Short Signatures From Diffie-Hellman: Realizing Short Public Key

**Authors:**
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.

**ePrint:**
https://eprint.iacr.org/2012/480

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .