New forward-secure signature schemes with untrusted update

Abstract

In this paper, we present two forward-secure signature schemes (FSS) with untrusted update. Our constructions use ideas from the work of Abdalla et al. [1] and Kozlov and Reyzin [2] in their forward-secure digital signature schemes. Our schemes are proven to be forward-secure based on the hardness of factoring in the random oraclemodel. Both schemes use the same method to encrypt the private key and are more efficient than Libert scheme [3] without adding any burden to the original forward-secure schemes.

Keywords

forward-secure / digital signature / untrusted update

References

[1] Abdalla M, Miner S, Namprempre C. Forward-secure threshold signature schemes. In: Naccache D ed. Topics in Cryptology—CT-RSA, 2001, LNCS, 2001, 2020: 441-456

[2] Kozlov A, Reyzin L. Forward-secure signatures with fast key update. Security in Communication Networks, 2003, 241-256

[3] Libert B, Quisquater J J, Yung M. Key evolution systems in untrusted update environments. ACM Transactions on Information and System Security (TISSEC), 2010, 13(4): 37

[4] Anderson R. Invited lecture. In: The 4th ACM Annual Conference on Computer and Communications Security. 1997

[5] Bellare M, Miner S. A forward-secure digital signature scheme. In: Proceedings of the 19th Annual International Cryptology Conference: Advances in Cryptology. 1999, 431-448

[6] Itkis G, Reyzin L. Forward-secure signatures with optimal signing and verifying. In: Proceedings of the 21st Annual International Cryptology Conference: Advances in Cryptology. 2001, 332-354

[7] Abdalla M, Reyzin L. A new forward-secure digital signature scheme. In: Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology. 2000, 116-129

[8] Nakanishi T, Hira Y, Funabiki N. Forward-secure group signatures from pairings. Pairing-Based Cryptography-Pairing, 2009, 171-186

[9] Libert B, Yung M. Efficient traceable signatures in the standard model. In: Proceedings of the 3rd International Conference on Pairing-Based Cryptography. 2009, 187-205

[10] Malkin T, Micciancio D, Miner S. Efficient generic forward-secure signatures with an unbounded number of time periods. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology (Eurocrypt 2002). 2002, 400-417

[11] Krawczyk H. Simple forward-secure signatures from any signature scheme. In: Proceedings of the 7th ACM Conference on Computer and Communications Security. 2000, 108-115

[12] Boyen X, Shacham H, Shen E, Waters B. Forward-secure signatures with untrusted update. In: Proceedings of the 13th ACM Conference on Computer and Communications Security. 2006, 191-200

[13] Bellare M, Rogaway P. Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security. 1993, 62-73

[14] Micali S, Reyzin L. Improving the exact security of digital signature schemes. Journal of Cryptology, 2002, 15(1): 1-18

[15] Fiat A, Shamir A. How to prove yourself: practical solutions to identi-fication and signature problems. In: Proceedings of Advances in Cryptology (Crypto’86). 1987, 186-194

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg