Should "noise" be added during "updates"

[OR13]

changing 1 bit, reveals timing information.

[msporny]

Another thing we need to consider is that adding noise in the beginning also gives an adversary information.

If you know that, on day 1, a revocation list was published with half of the bit positions set to one, then you have a high liklihood that the population size can't be more than half the size of the list.... so: herd size < (bitstring size / 2) right off of the bat.

[msporny]

Adding noise in a predictable way also gives an adversary information. That is, if you always flip 5 bits at a time, or you can calculate a mean at 5 bits, then you can reduce herd size by that multiplier.

If we add noise, we'll need a mechanism that does it in a way that prevents distribution predictability. The ideal would be to add 3 bits of noise, then 15, then 2, then 300, (or something that gives you the widest distribution probability given other restrictions)... and doing that, of course, actively harms compression.

Perhaps we should also consider flipping bits at random times? That actively harms caching (and compression!).

So perhaps breaking the bit-space up by N and then running Lévy, Brownian, or other IID processes (initialized using cryptographically random numbers) over each IID bit-space and counting on collisions (or misfiring of bit flips in the "junk space") to add the randomness necessary to confuse any sort of statistical analysis on herd size.

We would, of course, need mathematical proofs of the above to make sure we're actually doing something useful wrt. privacy. That said, this could be viewed as an "implementation detail" -- we don't define how you set the bit string, just that it exists and VCs map to a bit in the bit string.

[dlongley]

Any threats here should be more clearly documented (including concrete examples) before proceeding to possible mitigations.

[OR13]

a few protocols that already have noise added, for comparison:

• https://github.com/vuvuzela/vuvuzela
• https://github.com/libp2p/specs/tree/master/noise

Similar systems such as CT, notably don't have noise:

• https://certificate.transparency.dev/howctworks/

[iherman]

The issue was discussed in a meeting on 2023-09-15

• no resolutions were taken

View the transcript

1.8. Should "noise" be added during "updates" (issue vc-status-list-2021#40)

See github issue vc-status-list-2021#40.

Manu Sporny: decoys or noise when the initial publication happens and when you see updates.
… concern is, adversary looking at the list, watching bits flip, downloading the list every 5 mins, they can see what percentage of your population is having things revoked or changed or modified and gives them insights into your population.
… ... are operating ... they would undrestand ... 30% of the population broke the law in some way ....
… they can figure out what the population is doing ....
… one way to address this is to add noise to the list.

Kristina Yasuda: describing the problem is sufficient in privacy considerations.

Manu Sporny: implementor specific ... publisher of the list decides on how to add noise and in what order .... creates variation ... there is no one algorithm to add noise ... the downside is taht the implementor may not have privacy experts ...
… so easy for them get wrong and reveal more information.
… do we want to tackle noise generation or do we want to leave that to implementors?

Brent Zundel: this exists because of the architecture itself .... strongly in favor of option 2 ... even if we find a good way to do this, in a few weeks a better one would come up ...
… there are going to be confusion, but it doesn't feel like we have enough information in the group ...
… so, a note somewhere on how to go about noise.

Kristina Yasuda: yeah, in general agree ... what mechanisms are currently used?

Kristina Yasuda: it is hard.

Manu Sporny: they are not doing this at all, as far as we can tell. we heard it is on the roadmap, but no one is doing it.
… e.g. revocation status list, you'd never want to flip a revocation bit, because that would give away that that entry is a decoy.
… so you have to be careful. it becomes even more important with multi-bits.

Kristina Yasuda: well, driving licenses can be temporarily revoked for 30/60 days etc so flipping back is fine.

Manu Sporny: +1 to agree with everything that has been said so far, we don't have enough implementation experience to decide,.

Kristina Yasuda: no advising, just describing the problem is sufficient.

Manu Sporny: no specific recommendation for the path, but htings that implementors should be worried about.

Brent Zundel: post cr and move on.

Joe Andrieu: not to advise, really we haven't figured outk, but things to consider.

[OR13]

I suggest closing, given the recommendation made in #41