Paper 2014/138
Short Signatures from DiffieHellman, 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 DiffieHellman (CDH) assumption is important both from a practical and a theoretical point of view. Currently, there are only three standard model CDHbased 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 (EUFCMA)} 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 CDHbased EUFCMA 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 EUFCMA 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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 DiffieHellmanShort SignaturesStandard ModelTighter Reduction
 Contact author(s)
 jhsbhs @ gmail com
 History
 20140312: revised
 20140224: received
 See all versions
 Short URL
 https://ia.cr/2014/138
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/138, author = {Jae Hong Seo}, title = {Short Signatures from DiffieHellman, 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} }