Partnering with Fastly–Oblivious HTTP relay for FLEDGE's 𝑘-anonymity server

I'm calling bullshit on the unlinkability asserted in the Github reading here. Sure, you can make it so the API in question can't relink, but that doesn't mean you can't use extraneous unmentioned metadata to do it. Without proof that no other systems are siphoning off or tracking individual token state, this just looks like more "Lets use dubious cryptography to get pressure off our backs til a credible researcher we haven't hired/paid to be quiet blows the whistle".

The having to be logged in to Chrome bit is exactly what has me thinking something about that arrangement allows them to deanonymize, otherwise, they wouldn't even be able to measure the difference between real and fake. They'd also be more than happy to make an explicit business related contractual obligation of not sharing logs with them, because they don't need them, 1 and 2, to the uninitiated, it looks like they are trying to make an active attempt to anonymize things in spite of the fact they have enough extra OOB telemetry that they can continue with business as usual.

K-anonymity isn't anonymity at all, and is at best, less identifiable internal to the dataset.

other comment explained the deal, but here's the answer you wanted:

"technologically, nothing is preventing that."

You bring up an excellent point, and it’s something we really should discuss in our explainer: https://github.com/WICG/turtledove/blob/main/FLEDGE_k_anonym...

We’ve been calling this problem key consistency, basically the risk that Google (or any OHTTP gateway operator) gives out unique keys to different users and builds a {user -> request} mapping based on the keys used to encrypt requests. The OHTTP authors published a draft spec discussing exactly this problem. https://datatracker.ietf.org/doc/draft-ietf-privacypass-key-...

Frankly, none of the technical solutions we considered were satisfying enough given the added complexity. It’s actually kind of tricky to form a convincing distribution model. The designs we looked at mostly involve multi-party schemes where there’s trust required either that parties don’t collude with each other or between the user and one party explicitly. Admittedly OHTTP is also premised on multiple parties not colluding, but we decided to punt on the key consistency problem for the sake of simplicity. We also recognize that it’s possible for savvy users to fetch the keys from the endpoints we’re serving them on, compare those keys with other users, and fact check our claims. We honestly have nothing to hide about this; everyone is receiving the same key.

To specifically address the two proposals you made:

1) Shipping the key with the client: it’s not clear this is any better than fetching it right from Google. Chrome updates and our experiment framework (known as Chrome Variations) are both Google-managed distribution mechanisms, not terribly different from fetching the key at a Google API endpoint.

2) Having the relay serve the keys: these keys are actually designed to protect data from the relay. If the relay could change the public key Chrome uses to something the relay knows the private key for it would undermine the purpose of HPKE encryption. You suggested the relay could serve a key signed by Google. The issue with that is it complicates the process of key revocation. We expect to rotate the key we use, and we want to maintain the ability to revoke keys if needed (say the relay learned of a private key). Sure we could serve a signing key revocation list, but then we’re back in into the world of complicating the multi-party relationships.

All this being said, addressing key consistency issue is on our radar, and we hope to improve the distribution model in the future. We welcome feedback of course; and we’ll take it into consideration as we continue to evolve the designs used here. There is a general blog post on Privacy Sandbox feedback at [1] and you can take a look at specifically how Chrome is fetching keys in [2]. In case you're curious the key we’re serving today has a cipher suite of (DHKEM_X25519_HKDF_SHA256, HKDF_SHA256, AES_256_GCM) and at the moment we have two gateways (one for read traffic and one for write traffic) each using their own single keypair.

[1]: https://developer.chrome.com/docs/privacy-sandbox/feedback/

[2]: https://source.chromium.org/chromium/chromium/src/+/main:chr....

That's the general idea. We're trying to limit the amount of abuse a single Google Account, device, or other first-party identity can cause. We have some more ideas and details we hope to share over time, but the goal is to keep writes to the API anonymous while preventing, the best we can, sybil attacks. We're willing to ignore/sacrifice some writes to achieve this (since any writes above ~k recent ones don't contribute directly to the utility of the system).

Beyond Private State Tokens we also have new cryptography we're researching that should let us improve unlinkability between issuance and redemption further.

https://github.com/WICG/turtledove/blob/main/FLEDGE_k_anonym...

https://eprint.iacr.org/2023/320

Thank you for the comprehensive reply!