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.