Cryptology ePrint Archive: Report 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\"ohl 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\"ohl 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\"ohl 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.

Category / Keywords: public-key cryptography / Diffie-Hellman, Short Signatures, Standard Model, Tighter Reduction

Date: received 22 Feb 2014, last revised 12 Mar 2014

Contact author: jhsbhs at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140312:131424 (All versions of this report)

Short URL: ia.cr/2014/138

Discussion forum: Show discussion | Start new discussion