[messaging] Another Take At Public Key Distribution

[Trevor Perrin]

On Tue, Jul 28, 2015 at 11:28 AM, Andres Erbsen <andreser at mit.edu> wrote:
>
> TLDR: CONIKS doesn't usefully hide any userspace statistics either
> [...] And accepting the dataset size
> leak as inevitable hints at an obvious work-around: dummies. The keyserver is
> free to create dummy users which do not correspond to real people and exist
> solely to add noise to the measurements about the actual userbase.  This works
> as long as the dummy users are indistinguishable from real ones, which is easy
> to achieve in both CONIKS and the design I proposed.


I haven't worked out numbers here, but it feels like there's a difference:

The CONIKS paper discusses the option of "Randomizing the order of
directory entries" every epoch [1].  This would require the server to
rebuild the tree every epoch.  But if a CONIKS system did this and
also (a) added dummy users to pad the userbase out to a large constant
size (e.g. 1 billion users), and (b) had reasonable rate-limiting of
client queries, then I would think the size and rate-of-change of the
userbase could be well-hidden?

Hiding this seems harder in your system because verifiers need to
check the consistency of all user entries between epochs.  So to hide
the rate of change you'd have to simulate the behavior of dummy users
over time, including joining, changing keys, and leaving; and add
enough noise to mask underlying trends.

But this is arguably a minor issue, outweighed by other benefits.

---

My bigger question is whether it's realistic to have 3rd-party
verifiers who provide keyservers with auditing and signatures in
real-time (responding within a few seconds), while also providing
clients a diverse set of trust options.

I haven't thought about this that much, but I wonder if there are ways
to keep the benefits of frequent epochs (every few seconds) while
being tolerant of less-reliable / slower verifiers, or verifiers
chosen by clients without involving the keyserver?


Trevor

[1] http://www.jbonneau.com/doc/MBBFF15-coniks.pdf