Re: [Privacy-pass] Details about PrivateStats

[Tjerand Silde <[e-mail]>]

Dear Ananth, Subodh, all:

I agree with Ananth that the underlying assumptions are a bit different, and that the q-hardness requirement would impact the parameters. I see that Privacy Pass are standardising curve options with 192 bits of security instead of 128 bits to deal with this issue, and we might have to update our parameters accordingly in the final version of the paper.

The new construction with public metadata use the exact same DLEQ proof as earlier, but with updated public key and changed order of T’ and W’ to prove the correct relation. So I would say that the structure and communication is the same, but with some small differences in computation. We had to do some slightly bigger changes in the protocol with both public and private metadata, where we have to do two AND-proofs and publish two group elements before we can compute the OR-proof as in the original protocol.

Best,
Tjerand

On 11 Mar 2021, at 23:02, Subodh Iyengar <[e-mail]<mailto:[e-mail]>> wrote:

Thank Tjerand, read your paper and it's quite clever in its use of the DLEQ proof. In addition to Ananth's questions, if I understand correctly, this new construction will change the DLEQ proof in the existing l VOPRF evaluation as well. Is that correct?

Subodh
________________________________
From: Ananth Raghunathan <[e-mail]<mailto:[e-mail]>>
Sent: Tuesday, March 9, 2021 11:17 AM
To: Tjerand Silde <[e-mail]<mailto:[e-mail]>>
Cc: Subodh Iyengar <[e-mail]<mailto:[e-mail]>>; [e-mail]<mailto:[e-mail]> <[e-mail]<mailto:[e-mail]>>
Subject: Re: [Privacy-pass] Details about PrivateStats

Thanks Tjerand! I read the paper and I think the idea of using the Dodis-Yampolskiy PRF construction with f(x) = g^(1/(sk+x)) on the attributes is a really neat idea. One thing to think about comparing different constructions is the relative strength of the hardness of the underlying assumptions. If I'm not mistaken, in this construction there is a q-hardness requirement from the Diffie-Hellman inversion problem where q is the # of attribute queries, whereas the Naor-Reingold construction can get away with a n-hardness requirement from the Diffie-Hellman exponent problem where n is the log (size of attribute set). I think there are some selective-security and full-security notions that also need discussion but it's nice to see these alternatives with compact sizes.

Best,
Ananth

On Mon, 1 Mar 2021 at 10:55, Tjerand Silde <[e-mail]<mailto:[e-mail]>> wrote:
Dear Ananth, Subodh, all:

I agree that the AT-VOPRF is more useful for large domains, and that it guarantees fresh and unpredictable keys for each attribute. As I mentioned earlier, I like the construction a lot, and this is just a comment on the concrete efficiency in PrivateStats.

I also agree that one must publicly agree on which attribute is the correct one in each situation, for example by going through the leaf nodes in sequence left to right from a given date. But as far as I can understand, this is also needed in the AT-VOPRF construction. When you prove inclusion in the three you at the same time prove at which leaf node the public key is placed, and this would avoid the attack you mention.

The attribute public keys does indeed not have to be generated from the same master key, this is just to make it easier to store private keys on the server side. It does, as far as I can see, not affect security in any way.

It definitely makes sense to look into hash-based signatures and HIBE to see if the Merkle-tree approach can be extended to large domains, without having to generate all keys in advance. Very interesting idea.

Our paper is now available on ePrint, see new thread about the topic.

Best,
Tjerand

On 1 Mar 2021, at 17:48, Subodh Iyengar <[e-mail]<mailto:[e-mail]>> wrote:

I'm excited to read this paper as well. Please do share the eprint when it is available.

Putting the attribute keys on a merkle tree does make sense. One thing we need to be careful about is at least having 1 unique key per attribute on the merkle tree and not just proving inclusion in the tree.
For example, one could give (K1, attr1) to a user1 and (K2, attr1) to user2 in a regular tree. One nice part of having the AB-VOPRF as a PRF in privatestats is that we inherently get that property.

One open question, which I'm not sure whether it affects the security of the protocol itself, and could use further analysis,
is that having all attribute keys grouped in a merkle tree does prove that they are all related to the root, however, doesn't prove that they are derived from the master key.  However, that
might or might not matter to the security of privacypass, vs the security of the VOPRF.  Very interesting indeed.

Subodh
________________________________
From: Privacy-pass <[e-mail]<mailto:[e-mail]>> on behalf of Ananth Raghunathan <[e-mail]<mailto:[e-mail]>>
Sent: Saturday, February 27, 2021 11:50 AM
To: Tjerand Silde <[e-mail]<mailto:[e-mail]>>
Cc: [e-mail]<mailto:[e-mail]> <[e-mail]<mailto:[e-mail]>>
Subject: Re: [Privacy-pass] Details about PrivateStats

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]<mailto:[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]<mailto:[e-mail]> wrote:

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

--
Privacy-pass mailing list
[e-mail]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/privacy-pass