Paper 2015/007

Balloon: A Forward-Secure Append-Only Persistent Authenticated Data Structure

Tobias Pulls and Roel Peeters

Abstract

We present Balloon, a forward-secure append-only persistent authenticated data structure. Balloon is designed for an initially trusted author that generates events to be stored in a data structure (the Balloon) kept by an untrusted server, and clients that query this server for events intended for them based on keys and snapshots. The data structure is persistent such that clients can query keys for the current or past versions of the data structure based upon snapshots, which are generated by the author as new events are inserted. The data structure is authenticated in the sense that the server can prove all operations with respect to snapshots created by the author. No event inserted into the data structure prior to the compromise of the author can be modified or deleted without detection due to Balloon being publicly verifiable. Balloon supports efficient (non-)membership proofs and verifiable inserts by the author, enabling the author to verify the correctness of inserts without having to store a copy of the Balloon. We formally define and prove that Balloon is a secure authenticated data structure.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. MINOR revision.ESORICS 2015
Keywords
Authenticated Data Structure
Contact author(s)
roel peeters @ esat kuleuven be
History
2015-06-26: last of 3 revisions
2015-01-05: received
See all versions
Short URL
https://ia.cr/2015/007
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/007,
      author = {Tobias Pulls and Roel Peeters},
      title = {Balloon: A Forward-Secure Append-Only Persistent Authenticated Data Structure},
      howpublished = {Cryptology ePrint Archive, Paper 2015/007},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/007}},
      url = {https://eprint.iacr.org/2015/007}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.