sample_laplace_distribution() should take multiple random inputs

changed milestone to %Tor: unspecified

added 026-backport-maybe 031-unreached-backport 034-removed-20180328 034-triage-20180328 component::core tor/tor milestone::Tor: unspecified parent::25263 points::0.5 priority::medium privcount security-low severity::normal sponsor::Q-can status::new tor-relay type::defect version::tor 0.2.8.1-alpha labels

Trac:
Status: new to needs_review
Description: Currently, sample_laplace_distribution() takes a random double as input, and then extracts the following random values:

a random sign
a random value in (0.0, 1.0]

This reduces the precision of the result. For details, see: https://trac.torproject.org/projects/tor/ticket/23061#comment:32

Instead, the function could take a random boolean sign and p, and the transform becomes: {{ result = mu - b * (sign ? 1.0 : -1.0) * tor_mathlog(1.0 - p); }}

This would increase the precision by one bit, plus whatever precision is lost in 2.0 * fabs(p - 0.5).

This may have been introduced in dad5eb7.

to

Currently, sample_laplace_distribution() takes a random double as input, and then extracts the following random values:

a random sign
a random value in (0.0, 1.0]

This reduces the precision of the result. For details, see: https://trac.torproject.org/projects/tor/ticket/23061#comment:32

Instead, the function could take a random boolean sign and p, and the transform becomes:

result = mu - b * (sign ? 1.0 : -1.0)
                * tor_mathlog(1.0 - p);

This would increase the precision by one bit, plus whatever precision is lost in 2.0 * fabs(p - 0.5).

This may have been introduced in dad5eb7.

Should this be in needs_review? I see a suggestion for writing a patch, but I don't see the actual patch itself.

Wouldn't it be better to have a function that outputs a random double in (-1.0, +1.0)? If you're only using 53 bits of entropy from a RNG call that generates 64, there are spare bits to use for generating the sign.

Replying to catalyst:

Wouldn't it be better to have a function that outputs a random double in (-1.0, +1.0)? If you're only using 53 bits of entropy from a RNG call that generates 64, there are spare bits to use for generating the sign.

sample_laplace_distribution() takes the log of a strictly positive floating point number, and then applies a random sign.

We could use sgn() and abs() to decompose [-1.0, 1.0] into {+, -} and [0.0, 1.0], but we'd still have to reject 0.0 before doing the log, and then apply the sign. So it seems more complex than the alternative.

Trac:
Status: needs_review to needs_revision

I meant that the new function would exclude -1.0 and +1.0, so 1 - fabs(x) would still be nonzero.

That works, too: it costs us another random double function, but saves us an argument, and some complexity in the callers. Want to write the patch, or should I?

Produces random values in the range (-1.0, 1.0), with similar semantics to my other routine. Timing characteristics depend on how copysign() is implemented, though I expect most libms to use bit twiddling of some sort.

double
uint64_to_dbl_neg1_1(uint64_t x) {
#if DBL_MANT_DIG > 63
#error System double mantissa is unexpectedly large.
#endif
  return copysign(uint64_to_dbl_0_1(x), 0.0 - (x >> 63));
}

Edit: The routine can produce both 0.0 and -0.0, which is probably not what you want. If that's a problem the caller should re-sample entropy on either 0 or 1 << 63 depending on which zero you want it to return.

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

Trac:
Owner: N/A to teor
Status: needs_revision to assigned

This can wait until 0.3.3

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

Trac:
Sponsor: N/A to SponsorQ-can

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.

0.2.8 is EOL, so we won't be backporting to it.

Trac:
Keywords: 028-backport-maybe deleted, N/A added

Moving most of my assigned tickets to 0.3.4

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

Remove 030-backport from all open tickets that have it: 0.3.0 is now deprecated.

Trac:
Keywords: 030-backport deleted, N/A added

Remove 026-backport from all open tickets that have it: 0.2.6 has been deprecated for some while.

Trac:
Parent: #23061 (moved) to #25263 (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

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

Trac:
Milestone: Tor: 0.3.4.x-final to Tor: unspecified

0.3.1 is end of life, there are no more backports. Tagging with 031-unreached-backport instead.

Trac:
Keywords: 031-backport deleted, 031-unreached-backport added

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

Trac:
Owner: teor to N/A

0.2.9 is no longer maintained as of 1 January 2020. Therefore, we won't be backporting anything to it.

(None of these tickets are merge_ready, so we can just delete the backport tag.)

Trac:
Keywords: 029-backport deleted, N/A added

Change tickets that are assigned to nobody to "new".

Trac:
Status: assigned to new

changed time estimate to 4h

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

sample_laplace_distribution() should take multiple random inputs

Child items ...

Activity