Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19]


Journal of Information Science and Engineering, Vol. 24 No. 5, pp. 1347-1360 (September 2008)

A Generic Construction for Intrusion-Resilient Signatures from Linear Feedback Shift Register*

Zheng Gong, Xiangxue Li+, Dong Zheng and Kefei Chen
Department of Computer Science and Engineering
+School of Information Security Engineering
Shanghai Jiaotong University
Shanghai 200030, P.R. China
E-mail: {neoyan; kfchen}
+State Key Laboratory of Information Security
Graduate School of Chinese Academy of Sciences
Beijing 100039, P.R. China

With the development of various cryptographic primitives deployed on insecure devices, key exposure seems inevitable. Generalized from forward-secure signatures and key-insulated signatures, intrusion-resilient signatures (IRSs) was first introduced by Itkis and Reyzin, which help us to minimize the damage of key exposure. IRSs provide the unforgeability for the past and future time periods unless both the signer and the home base modules were compromised simultaneously (even in this worst case, IRSs preserve the unforgeability for the past periods). In this paper, we propose a practical generic construction for IRSs. By applying our proposal, one can simply transform any signature scheme to a practical intrusion-resilient signature scheme. In particular, we present a concrete paradigm from linear feedback shift register (LFSR). Our LFSR-based paradigms base and signer secret keys can be reduced to just a half length of the regular ones, which is useful to save the communication and storage costs. Moreover, if the underlying signature is unforgeable in the standard model, then our construction is also intrusion-resilient in the standard model without any extra assumptions.

Keywords: digital signature, key exposure, forward security, intrusion-resilient, linear feedback shift register

Full Text () Retrieve PDF document (200809_04.pdf)

Received November 7, 2006; revised April 10, 2007; accepted March 20, 2008.
Communicated by Wen-Guey Tzeng.
*This work was supported by NSFC (NO. 60573030, 60703030, 60703031) and the National Laboratory for Modern Communications Science Foundation of China (NO. 51436040405JW0304).