Short Signatures from Diffie–Hellman Realizing Al

Authors: Jae Hong Seo

Publish Date: 2016/08/10

Volume: 30, Issue: 3, Pages: 735-759

PDF Link

Abstract

In this paper we present a new digital signature scheme based on the computational Diffie–Hellman CDH assumption in the standard model The proposed signature scheme is not only asymptotically almost compact but also practical for concrete parameters in the sense that the public key has 29 group elements and the signature consists of two group elements and two exponents for 80bit security Note that the Waters signature scheme which is the previous best digital signature scheme in the same category CDH assumption standard model requires linearsized public keys in the security parameter particularly those with 164 group elements for 80bit security To achieve our goal we revisited the CDHbased signature scheme proposed by Hohenberger and Waters EUROCRYPT 2009 which is a stateful signature scheme but achieves asymptotically compact parameters in the sense that its public key and signature consist of constant group elements We modify the Hohenberger–Waters signature scheme to remove the state information from the signatures More precisely we use programmable hashes and random tags instead of counters which is the state information maintained by a signer To prove the security of the proposed signature scheme we developed prefixguessing technique for random tags Note that the prefixguessing technique was first introduced by Hohenberger and Waters CRYPTO 2009 and was originally used for message queriesThe author would like to thank Dennis Hofheinz for insightful discussions about the asymptotic security of the proposed signature scheme Shota Yamada for helpful comments on the early version of this paper and anonymous reviewers of the Journal of Cryptology for invaluable comments and constructive suggestions This work was supported by 2014 Research Fund of Myongji UniversityThe result in Lemma 2 is similar as the lemma given in 30 called “generalized birthday bound” Note that Lemma 2 is more general than “generalized birthday bound” eg if we set i=1 and j=1 then the result in Lemma 2 provides a more tighter upper bound than “generalized birthday bound” given in 30

Keywords: