Computer Science – Cryptography and Security
Scientific paper
2003-02-07
Computer Science
Cryptography and Security
24 pages
Scientific paper
In this work we describe, design and analyze the security of a tamper-evident, append-only data structure for maintaining secure data sequences in a loosely coupled distributed system where individual system components may be mutually distrustful. The resulting data structure, called an Authenticated Append-Only Skip List (AASL), allows its maintainers to produce one-way digests of the entire data sequence, which they can publish to others as a commitment on the contents and order of the sequence. The maintainer can produce efficiently succinct proofs that authenticate a particular datum in a particular position of the data sequence against a published digest. AASLs are secure against tampering even by malicious data structure maintainers. First, we show that a maintainer cannot ``invent'' and authenticate data elements for the AASL after he has committed to the structure. Second, he cannot equivocate by being able to prove conflicting facts about a particular position of the data sequence. This is the case even when the data sequence grows with time and its maintainer publishes successive commitments at times of his own choosing. AASLs can be invaluable in reasoning about the integrity of system logs maintained by untrusted components of a loosely-coupled distributed system.
Baker Mary
Maniatis Petros
No associations
LandOfFree
Authenticated Append-only Skip Lists does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Authenticated Append-only Skip Lists, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Authenticated Append-only Skip Lists will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-294734