rep_hist_format_hs_stats() should add noise, then round

In order to guarantee differential privacy, we need to:

• sample at the scale of the noise (not unit scale)
• add the noise to the signal
• round the noisy signal

This is the "snapping" mitigation from "On Significance of the Least Significant Bits For Differential Privacy" by Ilya Mironov https://pdfs.semanticscholar.org/2f2b/7a0d5000a31f7f0713a3d20919f9703c9876.pdf

rep_hist_format_hs_stats() rounds once to the bin size, then adds noise which has been rounded to the nearest integer. This isn't ideal, because it makes the least significant bits of the noise meaningless.

Instead, we should:

• round the noise to integer precision
• add the signal to the noise
• round the noisy signal to the bin size

I think this was introduced in 14e83e62.

changed milestone to %Tor: unspecified in legacy/trac

added 031-unreached-backport in Legacy / Trac 034-removed-20180328 in Legacy / Trac 034-triage-20180328 in Legacy / Trac actualpoints::1.0 in Legacy / Trac component::core tor/tor in Legacy / Trac milestone::Tor: unspecified in Legacy / Trac parent::25263 in Legacy / Trac points::0.5 in Legacy / Trac priority::medium in Legacy / Trac privcount in Legacy / Trac security-low in Legacy / Trac severity::normal in Legacy / Trac sponsor::Q in Legacy / Trac status::new in Legacy / Trac tor-relay in Legacy / Trac type::defect in Legacy / Trac version::tor 0.2.6.2-alpha in Legacy / Trac labels

I'll do these in 0.3.2, some of them are security-low.

Trac:
Status: new to assigned
Owner: N/A to teor

See my branch bug23414 for a fix to this, and the additions to add_laplace_noise() that are required to make it safe. They're part of legacy/trac#23416 (moved), and there is no changes file for them yet.

Trac:
Status: assigned to needs_review

This needs another fix: if we treat signal INT_MIN and INT_MAX as if they are infinite (saturating arithmetic), then the security guarantees are much easier to reason about. And the explanations are shorter, too :-)

Also, the code would be simpler, and the explanations shorter, if we added the noise when we reset the counter. I opened legacy/trac#23501 (moved) for this.

Trac:
Status: needs_review to needs_revision

I made a new branch at bug23414-v4, and split off some unrelated changes into legacy/trac#23523 (moved).

It needs a working round_int64_to_next_multiple_of(), which also needs to be backported to 0.2.8 and later. There is a possible fix in legacy/trac#19130 (moved) (which we closed by deleting the buggy function).

Edit: the related ticket is legacy/trac#23523 (moved)

Trac:
Keywords: 028-backport-maybe, 026-backport-maybe deleted, 028-backport added

See my branches bug23414-029 and bug23414-028, which are security-low because the current code leaks the low bits of the noise. (And it biases the result upwards by an average of the bin size divided by 2, because it rounds first, then adds noise.)

bug23414-028 has the following changes:

• the context is different due to legacy/trac#19130 (moved) going into 0.2.9 (but we replace the code from 0.2.8 and 0.2.9 with the same code)
• there's no BUG macro in 0.2.8
• the existing unit tests for round_int64_to_next_multiple_of() were based on the old implementation, which had the same upwards bias as the 0.2.9 implementation, due to the rounding function itself, rather than the order of operations

Trac:
Actualpoints: N/A to 1.0
Status: needs_revision to needs_review

Oops, the original tests were right: the only thing worse than a consistent bias is one that is inconsistent (it changes when the noised signal is negative).

Good news is that round_int64_to_next_multiple_of() becomes a two-liner:

const uint64_t bias = (uint64_t)INT64_MAX + 1;
return round_uint64_to_next_multiple_of(number + bias, divisor) - bias;

Bad news is that it's my weekend, so it will be Monday before I get to this.

Edit: I bet there's also some adjustment based on bias % divisor. Which also means there's some chance of overflow. So it's not quite this easy.

Trac:
Status: needs_review to needs_revision

I don't think I'll have time to fix round_int64_to_next_multiple_of until the end of the week. So if anyone else wants to do it, please feel free to grab this ticket. (Or split it off into its own ticket.)

Trac:
Sponsor: N/A to SponsorQ

We also need to implement a scaling/sensitivity mechanism to guarantee differential privacy. See https://trac.torproject.org/projects/tor/ticket/23523#comment:12 for details.

We're still working out the best way to do this in the PrivCount in Tor spec. Let's revisit this issue when that's been reviewed on tor-dev@.

Trac:
Milestone: Tor: 0.3.2.x-final to Tor: 0.3.3.x-final

We should revise or close these tickets based on Appendix C in the latest privcount-shamir spec:

https://github.com/teor2345/privcount_shamir/blob/noise-limits/doc/xxx-privcount-with-shamir.txt

The good news is that we probably don't need to care about extreme values or binning, because properly implemented noise has known limits, and doesn't need binning.

0.2.8 is EOL, so we won't be backporting to it.

Trac:
Keywords: 028-backport deleted, N/A added

Moving most of my assigned tickets to 0.3.4

Trac:
Milestone: Tor: 0.3.3.x-final to Tor: 0.3.4.x-final

Remove 030-backport from all open tickets that have it: 0.3.0 is now deprecated.

Trac:
Keywords: 030-backport deleted, N/A added

Trac:
Parent: legacy/trac#23061 (moved) to legacy/trac#25263 (moved)

Trac:
Keywords: N/A deleted, 034-triage-20180328 added

Per our triage process, these tickets are pending removal from 0.3.4.

Trac:
Keywords: N/A deleted, 034-removed-20180328 added

These needs_revision, tickets, tagged with 034-removed-*, are no longer in-scope for 0.3.4. We can reconsider any of them, if somebody does the necessary revision.

Trac:
Milestone: Tor: 0.3.4.x-final to Tor: unspecified

0.3.1 is end of life, there are no more backports. Tagging with 031-unreached-backport instead.

Trac:
Keywords: 031-backport deleted, 031-unreached-backport added

We should fix these issues by migrating these statistics to PrivCount in Tor. See legacy/trac#25263 (moved) and its parents for details.

Trac:
Status: needs_revision to assigned
Owner: teor to N/A

0.2.9 is no longer maintained as of 1 January 2020. Therefore, we won't be backporting anything to it.

(None of these tickets are merge_ready, so we can just delete the backport tag.)

Trac:
Keywords: 029-backport deleted, N/A added

Change tickets that are assigned to nobody to "new".

Trac:
Status: assigned to new

changed time estimate to 4h

added 8h of time spent

mentioned in issue legacy/trac#23416 (moved)

mentioned in issue legacy/trac#23501 (moved)

moved from legacy/trac#23414 (moved)

added Bug label and removed 1 deleted label

added Privcount Relay + 1 deleted label and removed 1 deleted label

added 1 deleted label

removed milestone

closed

added Deferred label

added BugSmashFund label

added Security label and removed 1 deleted label

added Technical Debt label and removed 1 deleted label