prop288: Merge privcount-in-tor data collector backend implementation

I've got implementations that match the current prop280, but we'll need to make some additional fixes, including:

• Whatever changes we make in prop280.
• Actually initializing the privcount subsytem
• Collecting initial statistics.

The current implementations are in privcount_nm_v2_032 and privcount_nm_v2_shake_032.

changed milestone to %Tor: 0.3.4.x-final

added 034-removed-20180328 034-triage-20180328 component::core tor/tor milestone::Tor: 0.3.4.x-final owner::teor parent::22898 priority::medium privcount prop280 prop288 resolution::wontfix rust severity::normal sponsor::Q status::closed type::enhancement labels

T1: sample_unit_gaussian() should use crypto_rand_double() to generate x and y. See #23061 (moved).

T2. sample_unit_gaussian() can't use both r * sin(theta) and r * cos(theta) unless they are independent samples. And I'm not sure if they are.

T3. We should update the comments to say that y must be strictly less than 1.0, or log() produces infinity.

T4. We should update the comments to say that x must be strictly less than 1.0, or sin(TWO_PI*x) would produce three zeroes, and two of every other value.

Replying to teor:

T4. We should update the comments to say that x must be strictly less than 1.0, or sin(TWO_PI*x) would produce three zeroes, and two of every other value.

(This isn't strictly true, because of the granularity of floating-point numbers. But using x < 1.0 is correct.)

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

Replying to teor:

T2. sample_unit_gaussian() can't use both r * sin(theta) and r * cos(theta) unless they are independent samples. And I'm not sure if they are.

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

I think we're ok here, because the results are the same as the ones we'd get by snapping.

But if there's a transform that takes stddev and yields more precision, we should probably use it (rather than just multiplying stddev * r * sin(theta)).

See also https://trac.torproject.org/projects/tor/ticket/23061#comment:33 for the output values from this function (if it used crypto_rand_double()).

T5. The function documentation of sample_unit_gaussian() should answer the following questions:

• what is the range of outputs?
• what is the precision of the outputs?

sample_gaussian() should document, and possible enforce:

• what is the maximum stddev value that can be used within the limits of double precision arithmetic?
  • to preserve differential privacy, the low bits have to be obscured by the noise. So this can be at most 2^53^.
• what is the minimum stddev value that can be used within the limits of double precision arithmetic?
  • (zero provides no differential privacy)

T6. sample_unit_gaussian() and sample_gaussian() belong with sample_laplace() (or whatever it's called). I may end up doing this when I fix all the random double stuff.

Trac:
Type: defect to enhancement
Milestone: Tor: 0.3.3.x-final to Tor: 0.3.4.x-final

This is now prop288.

Trac:
Summary: prop280: Merge privcount-in-tor data collector backend implementation to prop288: Merge privcount-in-tor data collector backend implementation
Keywords: N/A deleted, prop280, prop288 added

I think our current plan is that I will end up (re)writing PrivCount in Tor in Rust.

Trac:
Status: new to assigned
Owner: N/A to teor
Keywords: N/A deleted, rust, privcount added

Trac:
Parent: N/A to #22898 (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

This is now planned for rust, via #25669 (moved)

Trac:
Resolution: N/A to wontfix
Status: assigned to closed

closed

moved to tpo/core/tor#23147 (closed)