  We propose VAMS, a system that enables transparency for audits of access to
data requests without compromising the privacy of parties in the system. VAMS
supports audits on an aggregate level and an individual level, by relying on
three mechanisms. A tamper-evident log provides integrity for the log entries
that are audited. A tagging scheme allows users to query log entries that
relate to them, without allowing others to do so. MultiBallot, a novel
extension of the ThreeBallot voting scheme, is used to generate a synthetic
dataset that can be used to publicly verify published statistics with a low
expected privacy loss. We evaluate two implementations of VAMS, and show that
both the log and the ability to verify published statistics are practical for
realistic use cases such as access to healthcare records and law enforcement
access to communications records.

Cryptography and Security