Paper 2007/019
Fast Digital Signature Schemes as Secure as Diffie-Hellman Assumptions
Changshe Ma, Jian Weng, and Dong Zheng
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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Public-key cryptographysignature schemesdiscrete logarithm problemDiffie-Hellman problemtight reduction
- Contact author(s)
- changshema @ gmail com
- History
- 2007-01-26: received
- Short URL
- https://ia.cr/2007/019
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2007/019,
author = {Changshe Ma and Jian Weng and Dong Zheng},
title = {Fast Digital Signature Schemes as Secure as Diffie-Hellman Assumptions},
howpublished = {Cryptology {ePrint} Archive, Paper 2007/019},
year = {2007},
url = {https://eprint.iacr.org/2007/019}
}
