Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12]


Journal of Information Science and Engineering, Vol. 28 No. 3, pp. 571-586 (May 2012)

Non-Interactive Forward-Secure Threshold Signature without Random Oracles*

1College of Information Engineering
Qingdao University
Qingdao, 266071 P.R. China
2Institute of Network Security
Shandong University
Jinan, 250100 P.R. China
3School of Computer and Information Engineering
Shandong University of Finance
Jinan, 250014 P.R. China
4Department of Computer Science
National University of Singapore
117590 Singapore

Forward-secure threshold signature is one kind of important distributed signatures. In a (t, n) forward-secure threshold signature, if an adversary attacks fewer than t players, she cannot forge any valid signature; even if an adversary attacks t or more players in some time period, she cannot forge the signatures of previous time periods. At present, all forward-secure threshold schemes are at most proven to be secure in the random oracle model. However, security in the random oracle model does not imply security in the real world. In this work, we proposed the first forward-secure threshold signature scheme that can be proven secure without random oracles. In this scheme, the complexity of any performance parameter is at most log-squared in terms of the total number of time periods T. Another important point that differentiates our scheme from previous schemes is that our scheme does not need any interaction among the players in key update and signing algorithms. Therefore, the players can update their shares and sign the message, possibly in a completely decentralized fashion, which is very valuable in ad-hoc circumstances.

Keywords: forward security, digital signature, threshold signature, provable security, key exposure, standard model

Full Text () Retrieve PDF document (201205_09.pdf)

Received November 3, 2009; revised January 6 & April 27, 2011; accepted July 6, 2011.
Communicated by Wen-Guey Tzeng.
* This paper was partially supported by the National Natural Science Foundation of China (No. 60703089), the Shandong Province Natural Science Foundation of China (No. ZR2010FQ019, ZR2009GQ008, ZR2010FQ015).