Paper 2017/1116

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

Kaisei Kajita, Kazuto Ogawa, and Eiichiro Fujisaki


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.

Available format(s)
Publication info
Published elsewhere. Minor revision. ISC 2017
digital signaturesthe CDH assumptiontrapdoor commitmentsa tight security reduction
Contact author(s)
kajita k-bu @ nhk or jp
2017-11-21: received
Short URL
Creative Commons Attribution


      author = {Kaisei Kajita and Kazuto Ogawa and Eiichiro Fujisaki},
      title = {A Constant-Size Signature Scheme with a Tighter Reduction from the CDH Assumption},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1116},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.