Sketching an architecture that uses issuer blinding

[bvandersloot-mozilla]

The PACT problem statement hints at techniques to hide the issuer of a credential among a group of issuers as being one way to provide desired properties. I'm not a PrivacyPass native, so I sketched out a shape that allows that mechanism to be of use for my own understanding. Feedback encouraged.

Architectural assumptions:

1. We have two new functions: navigator.pact.issue(issueOptions) and navigator.pact.redeem(redeemOptions). We could hide these inside of FetchOptions, but for now we can keep these as explicit calls.
2. Attestation is done in a first-party web context, then issue is called.
3. The issuer and attestor may be different origins, but they are in the same informational context.
4. We store unified, unpartitioned state for the tokens.
5. Challenges are made by the Origin's client-side script via redeem.
6. We have the messages from PrivacyPass architecture (TokenChallenge, etc.). Swapping these for ACT messages isn't too hard.
7. We have a new operation IssuerHide, that hides the issuer of a credential
8. We can reliably obtain a set of all other issuers a credential may be mutually hidden as from an issuer
9. We have a magical BlindedOriginator message that the Client can give to the Origin. The properties of this message are undefined, but it could be useful to help enable the feedback mechanism.

Actors

1. Originating Issuer
2. Verifying Issuer
3. Attester
4. Origin
5. Client Script (from Origin, running in the browser)
6. Browser (behind the API)

Note: The Client Script and Browser are both running on the client.
An Issuer and Attester may be sharing information.
There are two Issuers invlolved, the originating issuer (at issuance time) and the verifying issuer (at redemption time).

Feedback:

The maximally effective feedback mechanism I see is has two properties:

1. the Verifying Issuer learns failure rates for (Originating Issuer, Origin) pairs
2. the Origin learns failure rates for Verifying Issuers on its own Origin.

We can get the latter for "free".

The former is hard!
The client should assume the Origin and Verifying Issuer are colluding.
I think this means that the magical BlindedOriginator message can't be something the Verifying Issuer can unblind themselves, otherwise the Origin can bring them into the loop before accepting a Token, defeating issuer blinding.
Even if we move a reveal at the end of each epoch to allow a once-per-epoch computation of reputation, we allow users to have their issuer blinded at the end of the first epoch. That also isn't good.

What could work is some (handwave mpc?) solution where every issuer in the group gets together with their own feedback on failures from the Origins, including the BlindedOriginator messages, and computes the desired feedback.

Message flow diagrams

Issuance

sequenceDiagram 
box Client
participant C as Client Script (Provider)
participant B as Browser
end
participant P as Originating Issuer
C<<->>P: Attestation in webpage
C->>B: navigator.pact.issue({tokenChallenge})
B->>P: TokenRequest, request peer issuer list
P->>B: TokenResponse, return peer issuer list
B->>C: Token (many)

Loading

Redemption

sequenceDiagram 
box Client
participant C as Client Script (Origin)
participant B as Browser
end;
participant P as Validating Issuer
participant O as Origin
O->>C: Token requirement communicated 
C->>B: navigator.pact.redeem(listOfAcceptedIssuers)
break with small probability
B->>C: wait randomly and return error
end
B->>B: Join issuer list against peer lists in storage,<br/> selecting one (Validating Issuer, Originating Issuer) pair,<br/> returning a Token from that Originating issuer.
B->>P: request peer issuer list
P->>B: return peer issuer list
B->>B: IssuerHide(Validating Issuer, Token)
B->>C: return Token, BlindedIssuer
C->>O: Use Token, BlindedIssuer
O->>P: Report abuse or not w/ BlindedIssuer

Loading

Computing feedback

All of the issuers get together on occasion and compute total abuse rates for originating issuers using all BlindedIssuers they receive as feedback from origins.

[wbl]

Minor crypto details: Major practical improvement coming to that paper, can provide draft on request but it is not ready for broader circulation yet (removes a verification key, better proof method). It isn't that the token changes when the issuer is hidden. Rather the redemption proof is a one out of many proof (morally) showing an issuer in the trusted set issued it.

More conceptual confusion on my part: I'm not sure I follow what the Peer Issuer list is doing. Guess there are conversations I should be catching up on.

The feedback I think can be solved in an MPC way via Distributed Point Functions, but this also means multiplying the number of parties involved and I think complicating the proofs of showing or create an anonymity issue. One important bit is the origins contribution to feedback is knowable by both participants in the MPC, so applying that is pretty clean. We use this model in the W3C Attribution solution/PPM in the IETF.

[wbl]

Actually I think I can solve the VDAF issue with a little cut and choose at issuance time. Will present details somewhere (given its crypto maybe privacy pass at ietf). Sadly this assumes single use tokens, but I think that's inherent in some of these designs using state counters. Will work on a resuseable one, but as I mentioned on the proposals issue, feedback seems tricky.

[bvandersloot-mozilla]

Minor crypto details: Major practical improvement coming to that paper, can provide draft on request but it is not ready for broader circulation yet (removes a verification key, better proof method). It isn't that the token changes when the issuer is hidden. Rather the redemption proof is a one out of many proof (morally) showing an issuer in the trusted set issued it.

Ah, neat. Then in that case I suppose the IssuerHide operation would produce a proof and the proof would then be forwarded to the Client Script and Origin?

More conceptual confusion on my part: I'm not sure I follow what the Peer Issuer list is doing. Guess there are conversations I should be catching up on.

Peer might be a bad choice of words I made up for this. Functionally it is the set of issuers an issuer would permit a potential redemption from. This maps to P in the SetPolicy of Issuer-Hiding Anonymous Credentials. I chose "peer" here because I was imagining issuers to be mutually redeemable. Any group of n>1 issuers that agrees to this arrangement would then return the same set of issuers that "peer" with one another.

[wbl]

IssuerHide produces a proof (at least in the systems we've been discussing). Really it's a kind of presentation. Whether it's a rerandomized credential as in PS, or a proof as in BBS ought to be immaterial to the API especially as we add more bells and whistles on.

One of the downfalls of designated verifier systems is that the verification keys need to be shared amongst verifiers (and aren't public). This presents some thorny issues since as the old saw goes, two can share a secret if one is dead. It's a lot cleaner security model when a public key is all they need, but that means updates are messier. Plus there might need to be some global lists of anti-double spend amounts if we're relying on token exchange as counters are updated.

[wbl]

Actually I think if issuers are mutually redeemable, and we have to share private keys everywhere, issuer hiding ends up not mattering much: they can all use the same key, except for transitivity failure reasons, and I think your idea of the grouping implies transitivity, or maybe I don't quite get it.

I'm still thinking through what this means with issuer misbehavior. My sense is that we end up in a pretty vulnerable spot where a misbehaving or compromised issuer has a lot of power, and it might not be possible to tell who it is. It certainly means some complexities for openness of the resulting system.

Interestingly public verifiability alone isn't a panacea: ensuring reporting of who the issuer is is honest, even if the party with a credential is not, is a bit complicated.

[wbl]

Reporting the issuer in zero knowledge is doable: if we use the idea from my forthcoming paper, then it's a matter of proving something additional about commitments to bits used in the GK proof, namely that they then get shared in a certain way across data that's then encrypted. This then produces an index in the list, and the origin can turn that into an issuer. Doing so with the encryption PQ is I think doable, but still hunting in the literature for exactly the right scheme (hard to prove random coins picked honestly, so have to make sure zero failure probability and that a range proof is all you need for correct encryption).

Even more promising is making the encryption somewhat FHE ciphertext, in which case doing the multiparty computations for measurement is a lot easier.

Will try to get a comprehensive proposal together in the new year early but there are many moving parts, so might be a bit.

[bvandersloot-mozilla]

I think your idea of the grouping implies transitivity

That is the way I was envisioning it.

My sense is that we end up in a pretty vulnerable spot where a misbehaving or compromised issuer has a lot of power, and it might not be possible to tell who it is. It certainly means some complexities for openness of the resulting system.

Yes, there is a requirement here to be able to get feedback on which originating issuer is actually misbehaving. So shared private keys preclude that, assuming the client is untrusted.