Opened 20 months ago

Last modified 6 months ago

#23416 assigned enhancement

Document the precision and limits of sample_laplace_distribution()

Reported by: teor Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-relay, privcount, 034-triage-20180328, 034-removed-20180328
Cc: Actual Points:
Parent ID: #25263 Points: 1
Reviewer: Sponsor: SponsorQ-can

Description

The function documentation of sample_laplace_distribution() should answer the following questions:

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

add_laplace_noise() should document, and possible enforce:

  • what is the maximum delta_f / epsilon 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 delta_f / epsilon value that can be used within the limits of double precision arithmetic?
    • (zero provides no differential privacy)

Child Tickets

Change History (12)

comment:1 Changed 19 months ago by teor

Owner: set to teor
Status: newassigned

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

comment:2 Changed 19 months ago by teor

My branch bug23414 implements part of this, we're reviewing it in #23414.

comment:3 in reply to:  2 Changed 19 months ago by teor

Replying to teor:

My branch bug23414 implements part of this, we're reviewing it in #23414.

These code and comment changes are now split off into #23523.

Edit: the related ticket is #23523

Last edited 19 months ago by teor (previous) (diff)

comment:4 Changed 19 months ago by teor

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

This is a work in progress, it can wait until 0.3.3

comment:5 Changed 18 months ago by nickm

Sponsor: SponsorQ-can

comment:6 Changed 17 months ago by teor

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.

comment:7 Changed 15 months ago by teor

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

Moving most of my assigned tickets to 0.3.4

comment:8 Changed 14 months ago by teor

Parent ID: #23061#25263

comment:9 Changed 13 months ago by nickm

Keywords: 034-triage-20180328 added

comment:10 Changed 13 months ago by nickm

Keywords: 034-removed-20180328 added

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

comment:11 Changed 12 months ago by nickm

Milestone: Tor: 0.3.4.x-finalTor: unspecified

These tickets, tagged with 034-removed-*, are no longer in-scope for 0.3.4. We can reconsider any of them, if time permits.

comment:12 Changed 6 months ago by teor

Owner: teor deleted

We should fix these issues by migrating these statistics to PrivCount in Tor.
See #25263 and its parents for details.

Note: See TracTickets for help on using tickets.