Plausibly deniable proof of association

[sander]

To meet the ARF Topic 18 requirements, we need a proof of association (PoA) method that is:

• compatible with HDKeys, in particular distributed WSCA
• plausibly deniable

This will require three protocol steps:

1. prover shares commitment involving the right keys
2. verifier shares challenge
3. prover shares response

After these steps, the verifier can verify whether the prover knows, for example in elliptic curve cryptography, the discrete logarithm of one public key respective to another public key as base point.

The W3C Digital Credentials (DC) API proposal only supports two requests: a credential request and a credential response. So in particular there is no way to directly include protocol step 1, since the prover cannot yet know which are the right keys to use.

One solution is to add a second PoA-HTTP protocol on top:

1. RP website shares DC credential request, including an RP PoA-HTTP endpoint
2. User authenticates to WSCA
3. WSCA shares commitment at PoA-HTTP endpoint
4. PoA-HTTP endpoint returns challenge
5. User returns to RP website
6. RP website receives DC credential response, including a response to the PoA challenge

Are there other feasible solutions?

Note this will likely be relevant to ARF discussion topic C.

[emlun]

I saw this comment in eu-digital-identity-wallet/eudi-doc-architecture-and-reference-framework#354 (reply in thread):

We are still looking for an efficient plausibly deniable PoA, but no luck so far: #78

Could this be done using a proof of knowledge of the blinding factor?

We've discussed a simple proof of association in HDK and ARKG which boils down to revealing the blinding factor. If the user can prove that (using ECC as an example)

$$ pk_1 = pk_0 + b_1 * G$$

then by the EC homomorphy the issuer also knows that $sk_1 = sk_0 + b_1$, therefore knowledge of $(sk_1, b_1)$ is equivalent to knowledge of $sk_0$.

The easy solution is to simply reveal $b_1$ to the issuer, who can then recompute $pk_1$ and be convinced of the association. But this also makes the PoA non-repudiable.

But it should be possible to prove all this by instead revealing $B_1 = b_1 * G$ and proving knowledge of $(sk_0, b_1)$, right?

• The issuer receives: $(pk_0, pk_1, B_1)$ where $pk_1 = pk_0 + B_1$ and $B_1 = b_1 * G$. The issuer can verify that $pk_1 = pk_0 + B_1$ and thus be convinced that knowledge of $(sk_1, b_1)$ is equivalent to knowledge of $sk_0$.
• The user proves knowledge of $sk_0$ and $b_1$, for example using ECDSA (non-repudiable) or ECDH-MAC (repudiable).
• The $sk_0$ PoK needs to be done by the WSCD, but can be cached long term by the issuer. The $b_1$ PoK can be done in the userspace wallet client software since the client knows $b_1$.

Could that work?