[tor-dev] Proposal xyz : Count Unique IP addresses in an anonymous way

[Aaron Johnson]

> We should also consider how this proposal would interact with other
> proposed secure aggregation solutions, like Privcount [1] and/or some
> other kind of PrivEx [2].  I'd like to hear what the designers of
> those ideas think of this one.

As you know, PrivCount is a secure aggregation system. In particular, it allows you to count some value (i.e. compute some sum) across relays and over time such that the only output anyone learns is a noisy (and differentially-private) version of the sum.

As you also know, PCSA allows one to locally store a count of unique items in a way that provides some privacy if the machine is compromised. PrivCount isn’t designed to support such counting of unique items, but it does provide such “forward privacy" (actually it provides perfect, information-theoretic privacy).

So, it seems that PCSA and PrivCount do similar but different counting and provide similar but different kinds of forward privacy. These ideas could be combined to provide some combination of their functionality and privacy features. To do so, have each relay maintain an FM sketch as a sequence of PrivCount counters (recall that these counters are blinded and thus appear random at any given time). Represent a 0 in each counter by storing (in a blinded way) 0, and represent 1 by storing (in a blinded way) a random value (with b bits in the counter it is non-zero with probability 1-2^(-b)). Given a new item, a relay turns bits from 0 to 1 in the sketch by adding a random value. The PrivCount aggregation protocol would reveal each bit of the FM sketch aggregated across all relays, which would thus reveal the PCSA count of unique IPs seen across all relays. Note that this output would not be differentially private - it isn’t obvious how FM sketches can support differential privacy with any accuracy as some single user does cause all bits to flip to one. The output would provide whatever privacy FM sketches provide, and this idea would support the privacy-enhancement of flipping random bits proposed by Tschorsch and Scheuermann.

This scheme would provide better forward privacy than PCSA alone, because PrivCount would secure the counters perfectly during the measurement period. It would provide better unique counting than per-relay PCSA because it would be counting uniquely across all relays. Again, it wouldn’t provide the differential privacy guarantee of PrivCount, but it would provide whatever privacy is provided by PCSA.

This is an idea I had considered a while ago but gave up on because of the lack of a differential-privacy guarantee for the output and my general lack of confidence in the privacy provided by PCSA. However, it may well be an improvement on what Tor is doing currently :-)

Best,
Aaron