Abstract
The known security proofs for hash tree time-stamping assume collision-resistance (CR). An asymptotically optimally tight proof has the security loss formula \(\frac{t'}{\delta'}\approx 14 \sqrt{C}\left(\frac{t}{\delta}\right)^{1.5}\), where \(\frac{t'}{\delta'}\) is the time-success ratio of a collision-finder, \(\frac{t}{\delta}\) is the ratio of a back-dating adversary and C is the size of the hash tree created in every time unit. Practical schemes use 256-bit hash functions that are just 2128-secure because of the birthday bound. For having a 280-secure time-stamping scheme, we have C < 103 that is insufficient for global scale solutions. Due to tightness bounds for CR, practically relevant security proofs must use assumptions stronger than CR. We show that under the random oracle (RO) assumption, the security loss is independent of C. We establish a linear-preserving security reduction under the Pre-Image Awareness (PrA) assumption. We present a new slightly stronger assumption SPrA that leads to much tighter proofs. We also show that bounds on C are necessary—based on any PrA/SPrA function, we construct a PrA/SPrA function that is insecure for unbounded time-stamping.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bayer, D., Haber, S., Stornetta, W.-S.: Improving the efficiency and reliability of digital timestamping. In: Sequences II: Methods in Communication, Security, and Computer Sci., pp. 329–334. Springer, Heidelberg (1993)
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: The 1st ACM Conference on Computer and Communications Security: CCS 1993, pp. 62–73. ACM (1993)
Bellare, M., Rogaway, P.: The exact security of digital signatures - How to sign with RSA and Rabin. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 399–416. Springer, Heidelberg (1996)
Buldas, A., Niitsoo, M.: Optimally tight security proofs for hash-then-publish time-stamping. In: Steinfeld, R., Hawkes, P. (eds.) ACISP 2010. LNCS, vol. 6168, pp. 318–335. Springer, Heidelberg (2010)
Buldas, A., Laur, S.: Do broken hash functions affect the security of time-stamping schemes? In: Zhou, J., Yung, M., Bao, F. (eds.) ACNS 2006. LNCS, vol. 3989, pp. 50–65. Springer, Heidelberg (2006)
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., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. JACM 51(4), 557–594 (2004)
Chang, D., Yung, M.: Adaptive preimage resistance analysis revisited: requirements, subtleties and implications. In: IACR Cryptology ePrint Archive 209 (2012)
Coron, J.-S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgård revisited: How to construct a hash function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (2005)
Dodis, Y., Ristenpart, T., Shrimpton, T.: Salvaging Merkle-Damgård for practical applications. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 371–388. Springer, Heidelberg (2009)
Haber, S., Stornetta, W.-S.: How to time-stamp a digital document. Journal of Cryptology 3(2), 99–111 (1991)
Luby, M.: Pseudorandomness and Cryptographic Applications. Princeton University Press, Princeton (1996)
Maurer, U., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004)
Merkle, R.C.: Protocols for public-key cryptosystems. In: Proceedings of the 1980 IEEE Symposium on Security and Privacy, pp. 122–134 (1980)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buldas, A., Laanoja, R. (2013). Security Proofs for Hash Tree Time-Stamping Using Hash Functions with Small Output Size. In: Boyd, C., Simpson, L. (eds) Information Security and Privacy. ACISP 2013. Lecture Notes in Computer Science, vol 7959. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39059-3_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-39059-3_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39058-6
Online ISBN: 978-3-642-39059-3
eBook Packages: Computer ScienceComputer Science (R0)