[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [tor-bugs] #23061 [Core Tor/Tor]: crypto_rand_double() should produce all possible outputs on platforms with 32-bit int
#23061: crypto_rand_double() should produce all possible outputs on platforms with
32-bit int
-------------------------------------------------+-------------------------
Reporter: teor | Owner: teor
Type: defect | Status:
| assigned
Priority: Medium | Milestone: Tor:
| 0.3.6.x-final
Component: Core Tor/Tor | Version: Tor:
| 0.2.2.14-alpha
Severity: Normal | Resolution:
Keywords: tor-relay, security-low, privcount, | Actual Points: 0.5
029-backport, review-group-22, |
034-triage-20180328, 034-removed-20180328, |
031-unreached-backport, 035-roadmap-subtask, |
035-triaged-in-20180711 |
Parent ID: #26637 | Points: 0.1
Reviewer: | Sponsor:
| SponsorV-can
-------------------------------------------------+-------------------------
Comment (by riastradh):
I should add about `sample_uniform_01` vs `sample_uniform_01_open` that,
generally, the only reason you should use `sample_uniform_01_open` is as a
drop-in replacement for the current `crypto_rand_double` to avoid breaking
downstream code that assumes it can't get the floating-point number 1.
If you want to take the log of the sample without getting -infinity, for
instance to generate an exponential sample, you want a floating-point
number in (0, 1], not a floating-point number in [0, 1). (Even better,
for an exponential sample, you can use -log(p/2) if a fair coin toss turns
up heads, and -log1p(-p/2) if it turns up tails -- then the sampler
supports high precision negative and positive outputs; flip another coin
to pick the sign, for a Laplace sampler.) If for some reason you are
tempted to compute log1p(-p) or 1/(1 - p) downstream where p is uniform in
[0, 1), better to change what happens downstream to compute log(p) or 1/p
where p is in (0, 1] -- log1p and 1/(1 - p) are ill-conditioned near 1, so
it's always better to avoid relying on computations involving such
intermediate quantities.
The Mironov paper analyzes the use of (a) a correct uniform distribution
like I provided (actually, sometimes he vacillates between (0,1) and (0,1]
but I don't think it matters for the proof except maybe requiring a small
adjustment to Eq. (7)), together with (b) a correctly rounded natural
logarithm, and proves a differential privacy result, Theorem 1, under
those assumptions.
The system's libm is unlikely to have a correctly rounded log, with
maximum 0.5ulp error, corresponding to 2^-53^ relative error, but it is
likely to have something very close to that -- almost certainly much
better than 1ulp or 2^-52^ relative error. As a rough approximation, I
think you can just take eta in Sec. 5.2 of the paper to be 2^-52^ instead
of 2^-53^, and instead of the (1/lambda + 2^-49^B/lambda)-differential
privacy asserted in Theorem 1, you get (1/lambda +
2^-48^B/lambda)-differential privacy.
P.S. If in your Laplace sampler you use the exponential sampler I
described above -- toss a fair coin to decide whether to use -log(p/2) or
-log1p(-p/2), instead of the standard unconditional -log(p) -- I bet
you'll get a slightly better differential privacy bound. But it would
take a bit of work to identify the better bound and prove it, and really,
most of this is just to get confidence that the bound doesn't explode and
is reasonably small in concrete parameters, not to prove the bestest most
tightest bound possible.
--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/23061#comment:70>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online
_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs