<div dir="ltr">Great summary, Andres! Just coming back from vacation now and catching up.<br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jul 31, 2015 at 10:17 AM, Trevor Perrin <span dir="ltr"><<a href="mailto:trevp@trevp.net" target="_blank">trevp@trevp.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Tue, Jul 28, 2015 at 11:28 AM, Andres Erbsen <<a href="mailto:andreser@mit.edu">andreser@mit.edu</a>> wrote:<br>
><br>
> TLDR: CONIKS doesn't usefully hide any userspace statistics either<br>
</span>> [...] And accepting the dataset size<br>
<span class="">> leak as inevitable hints at an obvious work-around: dummies. The keyserver is<br>
> free to create dummy users which do not correspond to real people and exist<br>
> solely to add noise to the measurements about the actual userbase.  This works<br>
> as long as the dummy users are indistinguishable from real ones, which is easy<br>
> to achieve in both CONIKS and the design I proposed.<br>
<br>
<br>
</span>I haven't worked out numbers here, but it feels like there's a difference:<br>
<br>
The CONIKS paper discusses the option of "Randomizing the order of<br>
directory entries" every epoch [1].  This would require the server to<br>
rebuild the tree every epoch.  But if a CONIKS system did this and<br>
also (a) added dummy users to pad the userbase out to a large constant<br>
size (e.g. 1 billion users), and (b) had reasonable rate-limiting of<br>
client queries, then I would think the size and rate-of-change of the<br>
userbase could be well-hidden?<br>
<br>
Hiding this seems harder in your system because verifiers need to<br>
check the consistency of all user entries between epochs.  So to hide<br>
the rate of change you'd have to simulate the behavior of dummy users<br>
over time, including joining, changing keys, and leaving; and add<br>
enough noise to mask underlying trends.<br>
<br>
But this is arguably a minor issue, outweighed by other benefits.<br></blockquote><div><br></div><div style="font-size:12.8000001907349px">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.</div><div style="font-size:12.8000001907349px"><br></div><div><span style="font-size:12.8000001907349px">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.</span> </div><div><br></div><div> </div></div></div></div>