Welcome to the resource topic for 2014/138
Title:
Short Signatures from Diffie-Hellman, Revisited: Sublinear Public Key, CMA Security, and Tighter Reduction
Authors: 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.
ePrint: https://eprint.iacr.org/2014/138
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 .