log in  |  register  |  feedback?  |  help
Append-only Authenticated Dictionaries (AADs) and Their Applications
Alin Tomescu - MIT
Friday, October 27, 2017, 12:00-1:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)

We study "append-only" authenticated dictionaries (AADs) in a different setting where not one but multiple, mutually-distrusting clients update the dictionary via an untrusted server. This model, sometimes described as the n-party model, differs from the 2-party and 3-party models as it cannot assume a trusted source to compute authentication information.

Our clients' goal is to maintain a fork-consistent or "append-only" view of the dictionary, as they transition from an arbitrarily old authenticated digest of the dictionary to a newer one. Specifically, each client wants to ensure key-value pairs were only added to the new dictionary and old pairs were not removed nor changed.

Thus, the server should be able to compute an "append-only" proof that convinces clients this "append-only" property holds. The challenge is to construct a small-sized proof between arbitrary versions i and j of the dictionary.

We show a bandwidth-efficient but computationally-intensive construction based on constant-sized polynomial commitments (by Kate et al).

The main application for AADs is secure public-key distribution, where a public-key directory should not be able to remove public-key bindings from the directory, or else it can impersonate users without (efficient) detection. 

We believe AADs could have other applications in authenticated logging-based systems such as encrypted file systems or cryptocurrencies.


Alin is a PhD candidate at MIT focusing on public-key distribution for secure communication.

His interests lie at the intersection of theory and practice: he enjoys applied cryptography, distributed systems and writing code. 

In the past, Alin has worked on privacy-preserving file systems, private social networking and secure email.

This talk is organized by Octavian Suciu