Short Signatures From Diffie-Hellman: Realizing Short Public Key.

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 Θ ( λ log λ) group elements. Then, we developed a new technique for 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 Θ( λ log λ) group elements, where λ 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 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. 1