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 $\omega(1)$ public keys (e.g., $\log\log\lambda$), where $\lambda$ is the security parameter, and \item the standard EUF-CMA security with tighter reduction; $O(\lambda q)$ reduction loss, when ignoring negligible factors, which is less than $O(\sqrt{\frac{\lambda}{\log}}\lambda q)$ of the original security proof and almost the same as that of the Water signature scheme.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2014/138

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},
note = {\url{https://eprint.iacr.org/2014/138}},
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.