[tor-bugs] #23414 [Core Tor/Tor]: rep_hist_format_hs_stats() should add noise, then round

[Tor Bug Tracker & Wiki]

#23414: rep_hist_format_hs_stats() should add noise, then round
-------------------------+-------------------------------------------------
     Reporter:  teor     |      Owner:  (none)
         Type:  defect   |     Status:  new
     Priority:  Medium   |  Milestone:  Tor: 0.3.2.x-final
    Component:  Core     |    Version:  Tor: 0.2.6.2-alpha
  Tor/Tor                |   Keywords:  tor-relay, security-low, privcount,
     Severity:  Normal   |  031-backport, 030-backport, 029-backport, 028
                         |  -backport-maybe, 026-backport-maybe
Actual Points:           |  Parent ID:  #23061
       Points:  0.5      |   Reviewer:
      Sponsor:           |
-------------------------+-------------------------------------------------
 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 14e83e6.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/23414>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online