Fast Digital Signature Schemes as Secure as Diffie-Hellman Assumptions

Abstract: This paper presents two fast digital signature schemes based on Diffie-Hellman assumptions. In the random oracle model, the first scheme S1 has a tight security reduction to the computational Diffie-Hellman (CDH) problem; and the second scheme S2 has a tight security reduction to the decisional Diffie-Hellman (DDH) problem. Comparing with existing signature schemes (whose security is tightly related to CDH problem) like EDL signature schemes, the signature generation of S1 is about 27 % faster, and the verification is about 35 % faster, if without considering the hash function evaluations. Comparing with existing signature schemes (whose security is tightly related to DDH problem) like KW-DDH signature scheme, the signing of S2 is about 40 % faster and the verification is about 35 % faster. The high efficiency of the proposed schemes is attributed to a new protocol EDL mwz which implements the proof of equality of discrete logarithm. The EDL mwz protocol outperforms its counterpart, the Chaum and Pedersen protocol, as its computation is about 38 % faster and its bandwidth is |G | bits shorter. This new protocol may be of independent interests