Great summary, Andres! Just coming back from vacation now and catching up. On Fri, Jul 31, 2015 at 10:17 AM, Trevor Perrin <[email protected]> wrote:
> On Tue, Jul 28, 2015 at 11:28 AM, Andres Erbsen <[email protected]> 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.
_______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
