Abstract
We study the problem of authenticating the content and creation time of documents generated by an organization and retained in archival storage. Recent regulations (e.g., the Sarbanes-Oxley act and the Securities and Exchange Commission rule) mandate secure retention of important business records for several years. We provide a mechanism to authenticate bulk repositories of archived documents. In our approach, a space efficient local data structure encapsulates a full document repository in a short (e.g., 32-byte) digest. Periodically registered with a trusted party, these commitments enable compact proofs of both document creation time and content integrity. The data structure, an append-only persistent authenticated dictionary, allows for efficient proofs of existence and non-existence, improving on state-of-the-art techniques. We confirm through an experimental evaluation with the Enron email corpus its feasibility in practice.
Chapter PDF
Similar content being viewed by others
References
Anagnostopoulos, A., Goodrich, M., Tamassia, R.: Persistent authenticated dictionaries and their applications. In: Davida, G.I., Frankel, Y. (eds.) ISC 2001. LNCS, vol. 2200, pp. 379–393. Springer, Heidelberg (2001)
Bayer, D., Haber, S., Stornetta, W.: Improving the efficiency and reliability of digital time-stamping. In: Sequences II: Methods in Communication, Security, and Computer Science, pp. 329–334 (1993)
Benaloh, J., de Mare, M.: Efficient broadcast time-stamping. Technical report TR-MCS-91-1, Clarkson University, Departments of Mathematics and Computer Science (1991)
Blibech, K., Gabillon, A.: CHRONOS: An authenticated dictionary based on skip lists for time-stamping systems. In: Proc. Workshop on Secure Web Services, pp. 84–90. ACM, New York (2005)
Blibech, K., Gabillon, A.: A new time-stamping scheme based on skip lists. In: Gavrilova, M.L., Gervasi, O., Kumar, V., Tan, C.J.K., Taniar, D., Laganá, A., Mun, Y., Choo, H. (eds.) ICCSA 2006. LNCS, vol. 3982, pp. 395–405. Springer, Heidelberg (2006)
Buldas, A., Laud, P.: New linking schemes for digital time-stamping. In: Proc. 1st International Conference on Information Security and Cryptology (ICISC), pp. 3–13. Korea Institute of Information Security and Cryptology, KIISC (1998)
Buldas, A., Laud, P., Lipmaa, H.: Accountable certificate management using undeniable attestations. In: Proc. 7th ACM Conference on Computer and Communication Security (CCS), pp. 9–17. ACM, New York (2000)
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., Villemson, J.: Universally composable time-stamping schemes with audit. In: Zhou, J., López, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 359–373. Springer, Heidelberg (2005)
Buldas, A., Laud, P., Schoenmakers, B.: Optimally efficient accountable time-stamping. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 293–305. Springer, Heidelberg (2000)
Camenisch, J., Lysyanskaya, A.: Dynamic accumulators and application to efficient revocation of anonymous credentials. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 61–76. Springer, Heidelberg (2002)
Cohen, W.: Enron email dataset, http://www.cs.cmu.edu/~enron
Crosby, S., Wallach, D.: Efficient data structures for tamper evident logging. In: Proc. 18th USENIX Security Symposium, USENIX (2009)
Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. Journal of Computer and System Sciences 38(1), 86–124 (1989)
EMC, Centera Compliance Edition Plus, http://www.emc.com/products/detail/hardware/centera-compliance-edition-plus.htm
Goodrich, M., Papamanthou, C., Tamassia, R.: On the cost of persistence and authentication in skip lists. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 94–107. Springer, Heidelberg (2007)
Goodrich, M., Papamanthou, C., Tamassia, R., Triandopoulos, N.: Athos: Efficient authentication of outsourced file systems. In: Proc. Information Security Conference (ISC), pp. 80–96 (2008)
Goodrich, M., Tamassia, R.: Efficient authenticated dictionaries with skip lists and commutative hashing. technical report, Johns Hopkins Information Security Institute (1991), http://www.cs.jhu.edu/~goodrich/cgc/pubs/hashskip.pdf
Goodrich, M., Tamassia, R., Hasic, J.: An efficient dynamic and distributed cryptographic accumulator. In: Bertrand, G., Imiya, A., Klette, R. (eds.) Digital and Image Geometry. LNCS, vol. 2243, pp. 372–388. Springer, Heidelberg (2002)
Goodrich, M., Tamassia, R., Schwerin, A.: Implementation of an authenticated dictionary with skip lists and commutative hashing. In: DARPA Information Survivability Conference and Exposition II (DISCEX II), pp. 68–82. IEEE Press, Los Alamitos (1991)
Haber, S., Stornetta, W.S.: How to time-stamp a digital document. Journal of Cryptology 3(2), 99–111 (1991)
Huang, L., Hsu, W.W., Zheng, F.: CIS: Content immutable storage for trustworthy record keeping. In: Proc. of the Conference on Mass Storage Systems and Technologies (MSST). IEEE Computer Society Press, Los Alamitos (2006)
Knuth, D.E.: The art of computer programming, vol. 3. Addison-Wesley, Reading (1973)
Kocher, P.: On certificate revocation and validation. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 951–980. Springer, Heidelberg (1998)
Lukose, R.M., Lillibridge, M.: Databank: An economics based privacy preserving system for distributing relevant advertising and content. Technical report HPL-2006-95, HP Laboratories (2006)
Maniatis, P., Baker, M.: Enabling the archival storage of signed documents. In: Proc. First USENIX Conference on File and Storage Technologies (FAST), pp. 31–45. USENIX (2002)
Maniatis, P., Baker, M.: Secure history preservation through timeline entanglement. In: Proc. 11th USENIX Security Symposium, pp. 297–312. USENIX (2002)
Merkle, R.: A cerified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218–238. Springer, Heidelberg (1990)
Micali, S., Rabin, M., Kilian, J.: Zero-knowledge sets. In: Proc. 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos (2003)
Naor, M., Nissim, K.: Certificate revocation and certificate update. In: Proc. 7th USENIX Security Symposium, USENIX (1998)
Oprea, A., Bowers, K.: Authentic time-stamps for archival storage (2009); Available from the Cryptology ePrint Archive
Sion, R.: Strong WORM. In: Proc. of the 28th IEEE International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society Press, Los Alamitos (2008)
Yumerefendi, A., Chase, J.: Strong accountability for network storage. In: Proc. 6th USENIX Conference on File and Storage Technologies (FAST). USENIX (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Oprea, A., Bowers, K.D. (2009). Authentic Time-Stamps for Archival Storage. In: Backes, M., Ning, P. (eds) Computer Security – ESORICS 2009. ESORICS 2009. Lecture Notes in Computer Science, vol 5789. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04444-1_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-04444-1_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04443-4
Online ISBN: 978-3-642-04444-1
eBook Packages: Computer ScienceComputer Science (R0)