Re: [Privacy-pass] Details about PrivateStats

Dear Subodh, everyone:

Thank you for sharing your research, I find the AT-VOPRF to be a very nice construction and of independent interest. I watched your talk at RWC, but only recently had time to look at the details.

With regards to concrete efficiency in your situation, would it not be more efficient to combine Privacy Pass with a Merkle-tree to reduce communication?

Say, for simplicity, that you rotate keys every day in a year, then you could represent all attributes with N = ceil(log_2 365) = 9 bits. In my understanding, the public key then consists of 11 group elements (+ public parameters like group and generator which I ignore here) and the daily key + proof of correctness consists of 9 group elements and 9 Chaum-Pedersen proofs (+ the normal signature and C-H proof of correctness for the token). This gives you a public key of size 11*257=2827 bits and AT-VOPRF of size 9*(257+2*256) = 6921 bits when using X25519.

For the same situation, if we use a master seed to generate each daily signing key k_i = KDF(seed, date) and build a Merkle-tree with the daily keys K_i = [k_i] G as leaves, the public key is only the root of the tree of size 256 bits. The daily key can be sent over together with the path of hashes to prove that it is the correct key, and this will be of size 1 group element and 9 hashes, that is, 257+9*256 = 2561 bits. This could even be more optimized as most of the hashes in the path of two consecutive keys will be the same.

Best,
Tjerand

PS! In a joint work with Martin Stand we have designed an extension of Privacy Pass that includes public metadata that has exactly the same communication cost as plain Privacy Pass. We will email this list as soon as the ePrint is available (we uploaded on Wednesday).

On 15 Jan 2021, at 21:00, privacy-pass-request@ietf.org<mailto:privacy-pass-request@ietf.org> wrote:

From: Subodh Iyengar <subodh@fb.com<mailto:subodh@fb.com>>
Subject: [Privacy-pass] Details about PrivateStats
Date: 15 January 2021 at 16:20:37 CET
To: "privacy-pass@ietf.org<mailto:privacy-pass@ietf.org>" <privacy-pass@ietf.org<mailto:privacy-pass@ietf.org>>

We presented the PrivateStats system at Real World Crypto yesterday we've been experimenting with at Facebook.

Here's a link to the paper https://research.fb.com/privatestats and also a link to the talk https://www.youtube.com/watch?t=48&v=4eKwlSqGUi4&feature=youtu.be

The paper and talk details some of the challenges productionizing a PrivacyPass style VOPRF.
We also introduce a new construction to derive an attribute based VOPRF which is compatible with PrivacyPass VOPRFs.

TL;DR: we change the way we derive the public key for the underlying VOPRF. An attribute (eg. a day or anything) is mapped -> {bit vector}. Then an attribute specific key is derived from the bit vector. The public key can be used directly in the VOPRF. Someone could later check that the public key was correctly derived from the attribute.

An attribute based VOPRF might be a good addition to privacypass and allow binding attributes to the Public Keys used for PrivacyPass VOPRFs, and would love to chat more about developing this

Thanks,
Subodh

Privacy-pass mailing list
Privacy-pass@ietf.org<mailto:Privacy-pass@ietf.org>
https://www.ietf.org/mailman/listinfo/privacy-pass