Abstract
We present a Universally Composable (UC) time-stamping scheme based on universal one-way hash functions. The model we use contains an ideal auditing functionality, the task of which is to check that the rounds’ digests are correctly computed. Our scheme uses hash-trees and is just a slight modification of the known schemes of Haber-Stornetta and Benaloh-de Mare, but both the modifications and the audit functionality are crucial for provable security. We prove that our scheme is nearly optimal – in every UC time-stamping scheme, almost all time stamp requests must be communicated to the auditor.
This paper is an extended abstract. Proofs of the results are presented in the full version [8].
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Backes, M.: Cryptographically Sound Analysis of Security Protocols. PhD thesis, Universit ät des Saarlandes (2002)
Backes, M., Pfitzmann, B.: Symmetric Encryption in a Simulatable Dolev-Yao Style Cryptographic Library. In: 17th IEEE Computer Security Foundations Workshop, Pacific Grove, CA (June 2004)
Backes, M., Pfitzmann, B., Waidner, M.: Symmetric authentication within a simulatable cryptographic library. In: Snekkenes, E., Gollmann, D. (eds.) ESORICS 2003. LNCS, vol. 2808, pp. 271–290. Springer, Heidelberg (2003)
Backes, M., Pfitzmann, B., Waidner, M.: A Universally Composable Cryptographic Library. In: Proceedings of the 10th ACM Conference on Computer and Communications Security, October 2003, ACM Press, Washington (2003)
Bayer, D., Haber, S., Stornetta, W.-S.: Improving the efficiency and reliability of digital time-stamping. In: Sequences II: Methods in Communication, Security, and Computer Science, pp. 329–334. Springer, New York (1993)
Benaloh, J., de Mare, M.: Efficient broadcast time-stamping. Tech. report 1, Clarkson Univ. Dep. of Mathematics and Computer Science (August 1991)
Buldas, A., Laud, P., Lipmaa, H., Villemson, J.: Time-Stamping with Binary Linking Schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 486–501. Springer, Heidelberg (1998)
Buldas, A., Laud, P., Saarepera, M., Willemson, J.: Universally Composable Time-Stamping Schemes with Audit. IACR ePrint Archive 2005/198 (2005)
Buldas, A., Saarepera, M.: On provably secure time-stamping schemes. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 500–514. Springer, Heidelberg (2004)
Canetti, R.: A unified framework for analyzing security of protocols. Electronic Colloquium on Computational Complexity (ECCC) 8(16) (2001)
Canetti, R.: Security and composition of multi-party cryptographic protocols. Journal of Cryptology 13(1), 143–202 (2000)
Canetti, R.: Universally Composable Security: A New Paradigm for Cryptographic Protocols. In: 42nd FOCS, pp. 136–145 (2001)
Canetti, R., Fischlin, M.: Universally Composable Commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001)
Dolev, D., Yao, A.C.: On the security of public key protocols. IEEE Transactions on Information Theory 29(2), 198–208 (1983)
Haber, S., Stornetta, W.-S.: How to time-stamp a digital document. Journal of Cryptology 3(2), 99–111 (1991)
Haber, S., Stornetta, W.-S.: Secure Names for Bit-Strings. In: ACM Conference on Computer and Communications Security, pp. 28–35 (1997)
Lindell, Y.: Composition of Secure Multi-Party Protocols. In: Lindell, Y. (ed.) Composition of Secure Multi-Party Protocols. LNCS, vol. 2815, pp. 21–43. Springer, Heidelberg (2003)
Luby, M.: Pseudorandomness and cryptographic applications. Princeton University Press, Princeton (1996)
Merkle, R.C.: Protocols for public-key cryptosystems. In: Proceedings of the 1980 IEEE Symposium on Security and Privacy, pp. 122–134 (1980)
Moran, T., Shaltiel, R., Ta-Shma, A.: Non-interactive timestamping in the bounded storage model. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 460–476. Springer, Heidelberg (2004)
Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, Seattle, May 15–17, 1989, pp. 33–43. ACM Press, New York (1989)
Pfitzmann, B., Schunter, M., Waidner, M.: Cryptographic Security of Reactive Systems. In: Schneider, S., Ryan, P. (eds.) Workshop on Secure Architectures and Information Flow, Royal Holloway, University of London. Electronic Notes in Theoretical Computer Science, vol. 32, Elsevier Science, Amsterdam (2000)
Pfitzmann, B., Waidner, M.: Composition and integrity preservation of secure reactive systems. In: CCS 2000, Proceedings of the 7th ACM Conference on Computer and Communications Security, Athens, Greece, November 2000, pp. 245–254. ACM Press, New York (2000)
Pfitzmann, B., Waidner, M.: A Model for Asynchronous Reactive Systems and its Application to Secure Message Transmission. In: 2001 IEEE Symposium on Security and Privacy, Oakland, California, May 2001, pp. 184–200. IEEE Computer Society Press, Los Alamitos (2001)
Russell, A.: Necessary and sufficient conditions for collision-free hashing. Journal of Cryptology 8, 87–99 (1995)
Homepage of Surety, http://www.surety.com
Homepage of Authentidate, http://www.authentidate.com
Homepage of Digistamp, http://www.digistamp.com
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buldas, A., Laud, P., Saarepera, M., Willemson, J. (2005). Universally Composable Time-Stamping Schemes with Audit. In: Zhou, J., Lopez, J., Deng, R.H., Bao, F. (eds) Information Security. ISC 2005. Lecture Notes in Computer Science, vol 3650. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11556992_26
Download citation
DOI: https://doi.org/10.1007/11556992_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29001-8
Online ISBN: 978-3-540-31930-6
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.