Paper 2014/138

Short Signatures from Diffie-Hellman, Revisited: Sublinear Public Key, CMA Security, and Tighter Reduction

Jae Hong Seo

Abstract

Designing efficient signature scheme based on the standard assumption such as the Computational Diffie-Hellman (CDH) assumption is important both from a practical and a theoretical point of view. Currently, there are only three standard model CDH-based signature schemes with short signatures due to Waters (EUROCRYPT 2005), and Seo and Böhl et al. (the merged paper in EUROCRYPT 2013). The Waters signature scheme achieves the {\em Existentail UnForgeability against Chosen Message Attack (EUF-CMA)} with nearly optimal reduction. However, this scheme suffers from large public keys. To shorten public key size, Seo and Böhl et al. proposed new approaches, respectively, but each approach has a weak point rather than the Waters signature scheme; Seo's approach could prove only a rather weak security, called the bounded CMA security, and Böhl et al.'s approach inherently accompanies a loose reduction. In this paper, we aim at stepping towards efficient CDH-based EUF-CMA secure signature scheme with tighter reduction. To this end, we revisit the Seo signature scheme and devise an alternative security proof. The resulting security proof leads \item {\em asymptotically} (almost) compact parameters; short signatures (two group elements and one exponent) and public keys (e.g., ), where is the security parameter, and \item the standard EUF-CMA security with tighter reduction; reduction loss, when ignoring negligible factors, which is less than of the original security proof and almost the same as that of the Water signature scheme.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Diffie-HellmanShort SignaturesStandard ModelTighter Reduction
Contact author(s)
jhsbhs @ gmail com
History
2014-03-12: revised
2014-02-24: received
See all versions
Short URL
https://ia.cr/2014/138
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/138,
      author = {Jae Hong Seo},
      title = {Short Signatures from Diffie-Hellman, Revisited: Sublinear Public Key, {CMA} Security, and Tighter Reduction},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/138},
      year = {2014},
      url = {https://eprint.iacr.org/2014/138}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.