Short Signatures from Diffie-Hellman: Realizing Almost Compact Public Key

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 80-bit security. Note that the Waters signature scheme, which is the previous best digital signature scheme in the same category (CDH assumption, standard model), requires linear-sized public keys in the security parameter, particularly those with 164 group elements for 80-bit security. To achieve our goal, we revisited the CDH-based 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 prefix-guessing technique for random tags. Note that the prefix-guessing technique was first introduced by Hohenberger and Waters (CRYPTO 2009) and was originally used for message queries.