[messaging] Another Take At Public Key Distribution

[Joseph Bonneau]

Great summary, Andres! Just coming back from vacation now and catching up.

On Fri, Jul 31, 2015 at 10:17 AM, Trevor Perrin <trevp at trevp.net> wrote:

> 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.
>

Yes, I think in CONIKS it is possible to completely obfuscate user size and
rate-of-change at the cost described above. This could also be done at a
faster epoch rate, but the costs of re-randomization get quite high.

The real issue, as Trevor identified, is that having verifiers check
signature chains seems to prevent effective re-randomization. This was a
tradeoff we recognized and (I beileve) footnoted somewhere in the CONIKS
paper.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150802/6cb5b0c8/attachment.html>