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 $\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.