New Signature and Multi-Signature Schemes with Tight Security Reduction Based on D-DDH Problem

Abstract:

Based on the newly introduced d-decisional Diffie-Hellman (d-DDH) intractable problem, a signature scheme and a multi-signature scheme are proposed. The main method in the constructions is a transformation of a knowledge proof on the equality of two discrete logarithms. The two schemes are proved secure in the random oracle model and the security reductions to the d-DDH problem are tight. Moreover, one can select different d for different security demand of applications. Thus the schemes are secure, efficient and practical.

• Periodical: Applied Mechanics and Materials (Volumes 263-266)
• Pages: 3052-3059
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.263-266.3052
• Online since: December 2012
• Authors: Ze Cheng Wang
• Keywords: D-Decisional Diffie-Hellman Problem, Multi-Signature Scheme, Random Oracle Model, Signature Scheme, Tight Security Reduction

References

[1] M. Bellare and P. Rogaway, in: Advances in Cryptology-Eurocrypt '96, edited by U. Maurer, volume 1070 of Lecture Notes in Computer Science, Springer (1996).

[2] S. Micali and L. Reyzin: Journal of Cryptology, Vol.15(1):1-18, (2002).

[3] S. Goldwasser, S. Micali, and R. Rivest: SIAM J. Computing, Vol. 17(2): 281-308, (1988).

[4] J.S. Coron, in: Advances in Cryptology-Eurocrypt 2002, edited by L. Knudsen, volume 2332 of Lecture Notes in Computer Science, Springer (2002).

[5] B. Chevallier-Mames: in: Advances in Cryptology-Crypto 2005, edited by L. Knudsen, volume 3621 of Lecture Notes in Computer Science, Springer (2005).

[6] E. Goh, S. Jareckiz, J. Katz and N. Wang: Journal of Cryptology, Vol.20(1):493-514, (2007).

[7] D. J. Bernstein, in: Advances in Cryptology-Eurocrypt 2008, edited by N. Smart, volume 4965 of Lecture Notes in Computer Science, Springer (2008).

[8] S. Schage, in: Advances in Cryptology-Eurocrypt 2011, edited by K. G. Paterson, volume 6632 of Lecture Notes in Computer Science, Springer (2011).

[9] M.Abdalla, P. Fouque, V. Lyubashevsky and M. Tibouchi, in: Advances in Cryptology-Eurocrypt 2012, edited by D. Pointcheval and T. Johansson, volume 7237 of Lecture Notes in Computer Science, Springer (2012).

DOI: 10.1007/978-3-642-29011-4_34

[10] D. Hofheinz and T. Jager, in: Advances in Cryptology- Crypto 2012, edited by R. Safavi-Naini and R. Canetti, volume 7417 of Lecture Notes in Computer Science, Springer (2012).

DOI: 10.1007/978-3-642-32009-5

[11] K. Itakura and K. Nakamura: NEC Research & Development, Vol.71:1-8, (1983).

[12] S. Micali, K. Ohta, and L. Reyzin: in: Proceedings of the 8th ACM Conference on Computer and Communications Security, edited by P. Samarati, ACM Press, New York (2005).

[13] A. Boldyreva, in: Public Key Cryptography-PKC 2003, edited by Y. Desmedt, volume 2567 of Lecture Notes in Computer Science, Springer (2003).

[14] S. Lu, R. Ostrovsky, A. Sahai, H. Shacham, and B.Waters, in: Advances in Cryptology- Eurocrypt 2006, edited by S. Vaudenay, volume 4004 of Lecture Notes in Computer Science, Springer (2006).

DOI: 10.1007/11761679_28

[15] T. Ristenpart and S. Yilek, in: Advances in Cryptology-Eurocrypt 2007, edited by M. Naor, volume 4515 of Lecture Notes in Computer Science, Springer (2007).

[16] Haifeng Qian, Shouhuai Xu: Inf. Process. Lett. Vol. 111(2): 82-89, (2010).

[17] Yuan Zhou, Haifeng Qian and Xiangxue Li, in: Information Security-ISC 2011, edited by X. Lai, J. Zhou, and H. Li, volume 7001 of Lecture Notes in Computer Science, Springer (2011).

[18] R. Cramer, I. Damgard, E. Kiltz, S. Zakarias, A. Zottarel, in: Public Key Cryptography-PKC 2012, edited by M. Fischlin, J. Buchmann, and M. Manulis, volume 7293 of Lecture Notes in Computer Science, Springer (2012).

DOI: 10.1007/978-3-642-30057-8_38