Short Signatures from Diffie-Hellman, Revisited: Sublinear Public Key, CMA Security, and Tighter Reduction

Abstract. Designing efficient signature scheme based on the standard assumption such as the Com-putational 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 EURO-CRYPT 2013). The Waters signature scheme achieves the 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 1. asymptotically (almost) compact parameters; short signatures (two group elements and one expo-nent) and ω(1) public keys (e.g., log log λ), where λ is the security parameter, and 2. the standard EUF-CMA security with tighter reduction; O(λq) reduction loss, when ignoring neg-ligible factors, which is less than O( λ log λq) of the original security proof and almost the same as that of the Water signature scheme.