Paper 2017/1116

A Constant-Size Signature Scheme with a Tighter Reduction from the CDH Assumption

Kaisei Kajita, Kazuto Ogawa, and Eiichiro Fujisaki

Abstract

We present a signature scheme with the tightest security-reduction among known constant-size signature schemes secure under the computational Diffie-Hellman (CDH) assumption. It is important to reduce the security-reduction loss of a cryptosystem, which enables choosing of a smaller security parameter without compromising security; hence, enabling constant-size signatures for cryptosystems and faster computation. The tightest security reduction far from the CDH assumption is $\mathcal{O}(q)$, presented by Hofheinz et al., where $q$ is the number of signing queries. They also proved that the security loss of $\mathcal{O}(q)$ is optimal if signature schemes are ``re-randomizable". In this paper, we revisit the non-re-randomizable signature scheme proposed by Bohl et al. Their signature scheme is the first that is fully secure under the CDH assumption and has a compact public key. However, they constructed the scheme with polynomial-order security-reduction loss. We first constructed a new existentially unforgeable againt extended random-message attack (EUF-XRMA) secure scheme based on Bohl et al.'s scheme, which has tighter security reduction of $\mathcal{O}(q/d)$ to the CDH assumption, where $d$ is the number of group elements in a verification key. We then transformed the EUF-XRMA secure signature scheme into an existentially unforgeable against adaptively chosen-message attack (EUF-CMA) secure one using Abe et al.'s technique. In this construction, no pseudorandom function, which results in increase of reduction loss, is used, and the above reduction loss can be achieved. Moreover, a tag can be generated more efficiently than Bohl et al.'s signature scheme, which results in smaller computation. Consequently, our EUF-CMA secure scheme has tighter security reduction to the CDH assumption than any previous schemes.

Note: We removed the non-math Latex commands (\etal, \, Böhl, etc.) from the abstract.