skip to main content
10.1145/1103022.1103037acmconferencesArticle/Chapter ViewAbstractPublication PagesccsConference Proceedingsconference-collections
Article

CHRONOS: an authenticated dictionary based on skip lists for timestamping systems

Published: 11 November 2005 Publication History

Abstract

Skip Lists were first used as data structures for their simple implementation and optimal update and search time. Goodrich [7][8] was the first to propose an authenticated dictionary based on skip lists. More recently, Maniatis and Baker [10][11][12] have proposed an authenticated append only dictionary based on perfect skip lists. In this paper, we propose an authenticated append only dictionary which offers better performances than the previous proposals. Moreover this dictionary allows comparing the relative order of elements. Such a dictionary could be used for timestamping purposes.

References

[1]
A. Anagnostopoulos, M. T. Goodrich, and R. Tamassia. Persistent authenticated dictionaries and their applications. Lecture Notes in Computer Science, 2001.
[2]
D. Bayer, S. Haber, and W. Stornetta. Improving the efficiency and reliability of digital time-stamping. In Sequences'91: Methods in Communication, Security, and Computer Science, pages 329--334, 1992.
[3]
A. Buldas, P. Laud, and H. Lipmaa. Accountable certificate management with undeniable attestations. 7th ACM Conference on Computer and Communications Security, pages 9--18, 2000.
[4]
A. Buldas, P. Laud, H. Lipmaa, and J. Villemson. Time-stamping with Binary Linking Schemes. In H. Krawczyk, editor, Advances on Cryptology --- CRYPTO '98, volume 1462 of Lecture Notes in Computer Science, pages 486--501, Santa Barbara, USA, Aug. 1998. Springer-Verlag.
[5]
A. Buldas, H. Lipmaa, and B. Schoenmakers. Optimally efficient accountable time-stamping. In Public Key Cryptography, pages 293--305, 2000.
[6]
P. Devanbu, M. Gertz, C. Martel, and S. Stubblebine. Authentic third-party data publication, 1999.
[7]
M. Goodrich and R. Tamassia. Efficient authenticated dictionaries with skip lists and commutative hashing. Technical report, Johns Hopkins Information Security Institute, 2000.
[8]
M. Goodrich, R. Tamassia, and A. Schwerin. Implementation of an authenticated dictionary with skip lists and commutative hashing. DISCEX II, 2001.
[9]
P. C. Kocher. On certificate revocation and validation. Financial Cryptography, Second International Conference, pages 172--177, 1998.
[10]
P. Maniatis. Historic Integrity in Distributed Systems. PhD thesis, Computer Science Department, Stanford University, Stanford, CA, USA, 2003.
[11]
P. Maniatis and M. Baker. Secure history preservation through timeline entanglement. Technical Report arXiv:cs.DC/0202005, Computer Science Department, Stanford University, Stanford, CA, USA, Feb. 2002. Available at http://www.arxiv.org/abs/cs.DC/0202005.
[12]
P. Maniatis and M. Baker. Authenticated append-only skip lists, 2003.
[13]
R. C. Merkle. Protocols for public key cryptosystems. IEEE Symposium on Security and Privacy, pages 122--134, 1980.
[14]
R. C. Merkle. A certified digital signature. Advances in Cryptology, 1990.
[15]
S. Micali. Efficient certificate revocation. Technical report, MIT Laboratory for Computer Science, 1996.
[16]
M. Naor and K. Nissim. Certificate revocation and certificate update. In Proceedings 7th USENIX Security Symposium, 1998.
[17]
W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, pages 668--676, 1990.

Cited By

View all
  • (2016)FlexDPDPACM Transactions on Storage10.1145/294378312:4(1-44)Online publication date: 16-Aug-2016
  • (2015)An Everlasting Secure Non-interactive Timestamping Scheme in the Bounded Storage ModelTransactions on Petri Nets and Other Models of Concurrency X - Volume 941010.1007/978-3-662-48650-4_2(19-33)Online publication date: 1-Jul-2015
  • (2014)Authenticated Dictionary Based on FrequencyICT Systems Security and Privacy Protection10.1007/978-3-642-55415-5_24(293-306)Online publication date: 2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SWS '05: Proceedings of the 2005 workshop on Secure web services
November 2005
98 pages
ISBN:1595932348
DOI:10.1145/1103022
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 November 2005

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. authenticated dictionaries
  2. order of insertion
  3. skip lists
  4. timestamping systems

Qualifiers

  • Article

Conference

CCS05
Sponsor:

Upcoming Conference

CCS '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)FlexDPDPACM Transactions on Storage10.1145/294378312:4(1-44)Online publication date: 16-Aug-2016
  • (2015)An Everlasting Secure Non-interactive Timestamping Scheme in the Bounded Storage ModelTransactions on Petri Nets and Other Models of Concurrency X - Volume 941010.1007/978-3-662-48650-4_2(19-33)Online publication date: 1-Jul-2015
  • (2014)Authenticated Dictionary Based on FrequencyICT Systems Security and Privacy Protection10.1007/978-3-642-55415-5_24(293-306)Online publication date: 2014
  • (2010)FastADACM SIGOPS Operating Systems Review10.1145/1740390.174040144:1(45-49)Online publication date: 12-Mar-2010
  • (2009)Efficient data structures for tamper-evident loggingProceedings of the 18th conference on USENIX security symposium10.5555/1855768.1855788(317-334)Online publication date: 10-Aug-2009
  • (2009)Authentic time-stamps for archival storageProceedings of the 14th European conference on Research in computer security10.5555/1813084.1813096(136-151)Online publication date: 21-Sep-2009
  • (2008)ZerberProceedings of the 11th international conference on Extending database technology: Advances in database technology10.1145/1353343.1353380(287-298)Online publication date: 25-Mar-2008
  • (2008)Signtiming scheme based on aggregate signature2008 IEEE International Conference on Intelligence and Security Informatics10.1109/ISI.2008.4565044(145-149)Online publication date: Jun-2008
  • (2008)Trustworthy keyword search for compliance storageThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-007-0069-717:2(225-242)Online publication date: 1-Mar-2008
  • (2006)Trustworthy keyword search for regulatory-compliant records retentionProceedings of the 32nd international conference on Very large data bases10.5555/1182635.1164213(1001-1012)Online publication date: 1-Sep-2006
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media