#23147 closed enhancement (wontfix)

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

Reported by: nickm Owned by: teor
Priority: Medium Milestone: Tor: 0.3.4.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: prop288, prop280, rust, privcount, 034-triage-20180328, 034-removed-20180328
Cc: Actual Points:
Parent ID: #22898 Points:
Reviewer: Sponsor: SponsorQ

Description

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.

Child Tickets

Change History (16)

comment:1 Changed 22 months ago by teor

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

comment:2 Changed 22 months ago by 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.

comment:3 Changed 22 months ago by teor

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

comment:4 Changed 22 months ago by 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.

comment:5 in reply to:  4 Changed 22 months ago by teor

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.)

comment:6 Changed 22 months ago by nickm

Milestone: Tor: 0.3.2.x-finalTor: 0.3.3.x-final

comment:7 in reply to:  2 Changed 22 months ago by teor

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()).

comment:8 Changed 22 months ago by teor

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 253.
  • what is the minimum stddev value that can be used within the limits of double precision arithmetic?
    • (zero provides no differential privacy)

comment:9 Changed 22 months ago by teor

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.

comment:10 Changed 17 months ago by nickm

Milestone: Tor: 0.3.3.x-finalTor: 0.3.4.x-final
Type: defectenhancement

comment:11 Changed 17 months ago by teor

Keywords: prop288 prop280 added
Summary: prop280: Merge privcount-in-tor data collector backend implementationprop288: Merge privcount-in-tor data collector backend implementation

This is now prop288.

comment:12 Changed 17 months ago by teor

Keywords: rust privcount added
Owner: set to teor
Status: newassigned

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

comment:13 Changed 16 months ago by teor

Parent ID: #22898

comment:14 Changed 15 months ago by nickm

Keywords: 034-triage-20180328 added

comment:15 Changed 15 months ago by nickm

Keywords: 034-removed-20180328 added

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

comment:16 Changed 15 months ago by nickm

Resolution: wontfix
Status: assignedclosed

This is now planned for rust, via #25669

Note: See TracTickets for help on using tickets.