Subject: Re: [Privacy-pass] Details about PrivateStats

From: Tjerand Silde <[email-masked]>
Date: Sat, 27 Feb 2021 16:53:31 +0000

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, [email-masked]<mailto:[email-masked]> wrote:

From: Subodh Iyengar <[email-masked]<mailto:[email-masked]>>
Subject: [Privacy-pass] Details about PrivateStats
Date: 15 January 2021 at 16:20:37 CET
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>

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
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/privacy-pass

---

From: Ananth Raghunathan <[email-masked]>
Date: Sat, 27 Feb 2021 11:50:49 -0800

Tjerand, I'm excited to see the extension with public metadata -- looking
forward to it. At a first glance, the idea of generating all attribute keys
and committing to them through a Merkle tree seems to make sense and might
offer a better tradeoff. I think where our construction is useful is when
the domain is much larger (2^64 onwards, say). I do wonder though if there
are ways to generate public keys (and corresponding secret keys)
dynamically that can be "committed to" ahead of time with a Merkle
tree-like construction. Do ideas from stateless hash-based signatures or
HIBE constructions apply here?

Ananth

On Sat, 27 Feb 2021 at 08:53, Tjerand Silde <[email-masked]> wrote:

> 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, [email-masked] wrote:
>
> *From: *Subodh Iyengar <[email-masked]>
> *Subject: **[Privacy-pass] Details about PrivateStats*
> *Date: *15 January 2021 at 16:20:37 CET
> *To: *"[email-masked]" <[email-masked]>
>
>
> 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
>
> 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
>
>
>
> [email-masked]
> --
> [email-masked]