A signature scheme as secure as the Diffle-Hellman problem

被引:0
作者
Goh, EJ [1 ]
Jarecki, S [1 ]
机构
[1] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA
来源
ADVANCES IN CRYPTOLOGY-EUROCRYPT 2003 | 2003年 / 2656卷
关键词
signature schemes; computational Diffie-Hellman; discrete logarithm; exact security; tight reductions; random oracle model;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We show a signature scheme whose security is tightly related to the Computational Diffie-Hellman (CDH) assumption in the Random Oracle Model. Existing discrete-log based signature schemes, such as ElGamal, DSS, and Schnorr signatures, either require non-standard assumptions, or their security is only loosely related to the discrete logarithm (DL) assumption using Pointcheval and Stern's "forking" lemma. Since the hardness of the CDH problem is widely believed to be closely related to the hardness of the DL problem, the signature scheme presented here offers better security guarantees than existing discrete-log based signature schemes. Furthermore, the new scheme has comparable efficiency to existing schemes. The signature scheme was previously proposed in the cryptographic literature on at least two occasions. However, no security analysis was done, probably because the scheme was viewed as a slight modification of Schnorr signatures. In particular, the scheme's tight security reduction to CDH has remained unnoticed until now. Interestingly, this discrete-log based signature scheme is similar to the trapdoor permutation based PSS signatures proposed by Bellare and Rogaway, and has a tight reduction for a similar reason.
引用
收藏
页码:401 / 415
页数:15
相关论文
共 31 条
[1]  
[Anonymous], 1996, Advances in Cryptology-CRYPTO 1996, 16th Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 1996, Proceedings
[2]  
[Anonymous], LNCS
[3]  
[Anonymous], 2001, LNCS
[4]  
Bellare M, 1998, LECT NOTES COMPUT SC, V1403, P236, DOI 10.1007/BFb0054130
[5]  
Bellare M, 1996, LECT NOTES COMPUT SC, V1070, P399
[6]  
Bellare M., 1995, P 1 ACM C COMPUTER C, P62
[7]  
Boneh D., 2001, LNCS, P514, DOI [DOI 10.1007/3-540-45682-1_30, DOI 10.1007/3-540-45682-130]
[8]  
Brickell E, 2000, LECT NOTES COMPUT SC, V1751, P276
[9]  
Brickell E. F., 1992, P EUROCRYPT, P200
[10]  
CAMENISCH J, 1997, 260 ETH ZUR I THEOR