<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Hello,<div class=""><br class=""></div><div class="">I won’t be able to be at this meeting, but I would like to make some comments:</div><div class=""> 1. Prio’s zero-knowledge proofs (i.e. SNIPs) are not secure against a single malicious server. If you are using them the decide whether or not to include a given input, then a malicious server can cause good inputs to be excluded or bad inputs to be included. This could be used to exclude all good inputs except for one target one or to repeatedly exclude-then-include the input of a target party over a sequence of meaurement periods to see how much it tends to affect the aggregate. The SNIP protocols can no doubt be upgraded to provide security against malicious servers, but as of yet no such protocol has been published, implemented, or evaluated.</div><div class=""> 2. A main application for using client-provided zero-knowledge proofs is to allow Boolean inputs to be added. A client's proof would guarantee that a given input is 0 or 1, despite the input being secret-shared using shares in a larger field (say, 32-bit values) and thus impossible to otherwise learn anything about its value. The server then could add up the inputs to determine how many clients had the Boolean flag set. This may well be useful for inputs from clients directly, which is the Mozilla case. In Tor’s case, there is no plan to have clients submit statistics themselves (e.g. from Tor Browser), because it raises obvious privacy/PR concerns (I believe these could be mitigated, but that discussion has yet to even seriously start as far as I can tell). In the Tor case, the inputs are coming from relays. To the extent that relays are reporting on client activity, the Boolean input case seems less useful, as the relays should really be reporting the total amount activity they saw instead of just if they saw something ever happen. I could imagine, however, that figuring out how many relays saw some weird event (like an error, or evidence of some attack) happen might be useful. Other than Boolean inputs, I’m not sure what we would want to be proved about the inputs. Of the examples in the Prio paper (Sec. 5.2), only frequency count and variance seem to use client proofs. Frequency count is the Boolean case I discussed. I’m not sure what would justify gathering the variance of the per-relay values.</div><div class=""> 3. PrivCount is compatible with Prio’s Affine Function Encodings, as such encodings compute aggregates simply by adding inputs.</div><div class=""><br class=""></div><div class="">My overall opinion about Prio is that could be very useful to collect per-client statistics, such as from Tor Browser, but that doing so would require an upgraded version secure against malicious servers.</div><div class=""><br class=""></div><div class="">Best,</div><div class="">Aaron</div><div class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Nov 19, 2018, at 7:19 PM, teor <<a href="mailto:teor@riseup.net" class="">teor@riseup.net</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="content-type" content="text/html; charset=utf-8" class=""><div dir="auto" class=""><div dir="ltr" class=""><span class=""></span></div><div dir="ltr" class=""><meta http-equiv="content-type" content="text/html; charset=utf-8" class="">Hi all,<div class=""><br class=""></div><div class="">We are meeting to discuss PrivCount and Prio at 2200 UTC on</div><div class="">Tuesday 20 November in #tor-meeting on <a href="http://irc.oftc.net/" class="">irc.oftc.net</a>.</div><div class=""><br class=""></div><div class="">We will log the meeting, so that people who can't attend can catch</div><div class="">up later.</div><div class=""><br class=""></div><div class="">Here's some background:</div><div class=""><div class=""><br class=""></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);" class="">Henry Corrigan-Gibbs recently built a private statistics system<br class="">called Prio <<a href="https://crypto.stanford.edu/prio/" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="link" x-apple-data-detectors-result="8" class="">https://crypto.stanford.edu/prio/</a>> that is now used for<br class="">privately collecting telemetry at Mozilla<br class=""><<a href="https://hacks.mozilla.org/2018/10/testing-privacy-preserving-telemetry-with-prio/" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="link" x-apple-data-detectors-result="9" class="">https://hacks.mozilla.org/2018/10/testing-privacy-preserving-telemetry-with-prio/</a>>.<br class=""> It provides a similar functionality to PrivCount<br class=""><<a href="https://ohmygodel.com/publications/privcount-ccs2016.pdf" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="link" x-apple-data-detectors-result="10" class="">https://ohmygodel.com/publications/privcount-ccs2016.pdf</a>> that Tor is<br class="">planning to use, and also provides strong robustness against malformed or<br class="">malicious reports.</span></div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">Some questions we'll discuss:<br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""><br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">How can we design Tor's statistics to make it easy to:</span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">* defend against corruption attacks, and</span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">* support more complex aggregate statistics.</span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""><br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">How does PrivCount in Tor's design handle aggregation</span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">server failures?</span></font></div><span style="background-color: rgba(255, 255, 255, 0);" class=""><div class=""><span style="background-color: rgba(255, 255, 255, 0);" class=""><br class=""></span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);" class="">Some background:</span></div><br class=""></span><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">Here's my quick comparison of Prio and PrivCount in Tor:<br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">* Prio servers can do complex calculations using linear data structures<br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">* PrivCount is limited to additive totals (and histograms)<br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""><br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">* Prio servers can defend against corruption attacks using SNIPs</span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""> (secret non-interactive proofs)</span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">* PrivCount in Tor has an optional scheme to defend against corruption,</span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""> but it </span></font><span style="background-color: rgba(255, 255, 255, 0);" class="">requires adding additional noise</span></div><span style="background-color: rgba(255, 255, 255, 0);" class=""><br class=""></span><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">* Prio doesn't have differential privacy (yet)<br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">* PrivCount guarantees differential privacy across the entire set of<br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""> statistics<br class=""></span></font></div><span style="background-color: rgba(255, 255, 255, 0);" class=""><br class=""></span><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">* Prio increases security by failing when one server fails<br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">* PrivCount in Tor is robust to server failure, and compensates<br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""> for the decreased security by adding more noise<br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""> (The PrivCount design used for our research papers was not<br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""> robust, and failed whenever any server or client failed.)<br class=""></span></font></div><span style="background-color: rgba(255, 255, 255, 0);" class=""><div class=""><span style="background-color: rgba(255, 255, 255, 0);" class=""><br class=""></span></div><br class=""></span><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class="">Here are our latest specs, notes, and code for PrivCount in Tor:<br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""><a href="https://gitweb.torproject.org/torspec.git/tree/proposals/288-privcount-with-shamir.txt" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="link" x-apple-data-detectors-result="1" class="">https://gitweb.torproject.org/torspec.git/tree/proposals/288-privcount-with-shamir.txt</a><br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""><a href="https://trac.torproject.org/projects/tor/wiki/org/meetings/2018MexicoCity/Notes/PrivCount" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="link" x-apple-data-detectors-result="2" class="">https://trac.torproject.org/projects/tor/wiki/org/meetings/2018MexicoCity/Notes/PrivCount</a><br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""><a href="https://trac.torproject.org/projects/tor/wiki/org/meetings/2018MexicoCity/Notes/PrivCountTechnical" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="link" x-apple-data-detectors-result="3" class="">https://trac.torproject.org/projects/tor/wiki/org/meetings/2018MexicoCity/Notes/PrivCountTechnical</a><br class=""></span></font></div><div class=""><font class=""><span style="caret-color: rgb(0, 0, 0); background-color: rgba(255, 255, 255, 0);" class=""><a href="https://github.com/nmathewson/privcount_shamir" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="link" x-apple-data-detectors-result="4" class="">https://github.com/nmathewson/privcount_shamir</a><br class=""></span></font></div><div class=""><br class=""></div><div class=""><div dir="ltr" class=""><span style="background-color: rgba(255, 255, 255, 0);" class="">T</span><div class=""><span style="background-color: rgba(255, 255, 255, 0);" class=""><br class=""></span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);" class="">-- </span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);" class="">teor</span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);" class="">----------------------------------------------------------------------</span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);" class=""><br class=""></span></div></div></div></div></div></div></div>_______________________________________________<br class="">tor-dev mailing list<br class=""><a href="mailto:tor-dev@lists.torproject.org" class="">tor-dev@lists.torproject.org</a><br class="">https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev<br class=""></div></blockquote></div><br class=""></div></body></html>