Re: [Privacy-pass] Details about PrivateStats

[Ananth Raghunathan <[e-mail]>]

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 <[e-mail]> 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, [e-mail] wrote:
>
> *From: *Subodh Iyengar <[e-mail]>
> *Subject: **[Privacy-pass] Details about PrivateStats*
> *Date: *15 January 2021 at 16:20:37 CET
> *To: *"[e-mail]" <[e-mail]>
>
>
> 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
> [e-mail]
> https://www.ietf.org/mailman/listinfo/privacy-pass
>
>
> --
> Privacy-pass mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/privacy-pass
>