# Can DH be used for privacy-preserving proof of possession?

First time question poster so I hope the below is clear enough :).

Problem summary: Can a Holder and Verifier safely use ECDH for a Challenge-Response protocol where:

1. the Holder proves possession and control over a private key $$d$$ using material that a trusted Issuer signs, and
2. the Verifier learns no correlation handle (e.g., Holder public key $$Q_d= dG$$)?

Details and research: In previous posts, the Verifier either knows the Holder public key (c.f. 55195) or focuses on security properties that arguably do not apply to the proof of possession context (e.g., PTR-PAKE by Jarecki et al 2015). Here, the challenge-response protocol would be broken if:

1. The Verifier learns a correlation handle from the protocol (e.g., the public key $$dG$$).
2. The Holder can generate a proof of possession without being in control of $$d$$.
3. The Verifier successfully verifies a proof of possession that does not include $$d$$.

Protocol suggestion

Given an elliptic curve over $$GF(p)$$ with the generator $$G$$ of order $$order$$:

Issuer steps:

1. uses a PRNG to generate, $$r \in [1, order-1]$$.
2. generates the point $$Q_r=rG$$
3. multiplies the Holder public key with $$r$$ to generate $$Q_{dr}=$$ECDH$$(r, Q_d)$$.
4. issues a signature over points $$P = (Q_r, Q_{dr})$$ to the Holder

The Holder presents $$P$$ to a Verifier. After validating the Issuer signature, the Verifier continues with:

1. using a PRNG to generate scalars, $$(m,n) \in [1, order-1]$$.
2. computes the two challenge points $$C = (Q_{rm} = m \cdot Q_r, Q_{drn} = n \cdot Q_{dr})$$
3. sends $$C$$ to the Holder.

The Holder:

1. uses ECDH to generate the two x-coordinates of the points $$R = (x_{drm}=(d \cdot Q_{rm}).x, x_{d^2rn}=(d \cdot Q_{drn}).x)$$

The Verifier continues with:

1. checks that neither of the values in $$R$$ correspond to an x-coordinate of the challenge points in $$C$$.
2. computes $$(m^{-1}, n^{-1})$$
3. uses the values in $$R$$ to recover any of the two possible y coordinates (we denote recovered point as $$Q'$$) to generate the four response points for testing: $$T = (m^{-1} \cdot [Q'_{drm}, Q'_{d^2rn}], n^{-1} \cdot [Q'_{drm}, Q'_{d^2rn}])$$.
4. accept the response if exactly one x-coordinate of a point in $$T$$ is equal to a point in $$P$$

(See update below) As an additional question, and if the above is secure, would a non-interactive alternative be possible by replacing the challenge generation with a random oracle access? For instance, the Holder can generate the challenge pair from a presentation session id and $$P$$ using a cryptographic hash function e.g., c = SHA512(P || session_id) and m,n=c[:32], c[32:].

Update to the non-interactive part:

Knowing the values $$(m,n)$$ and $$P$$ seemingly allows the computation of the correct output even without possession of $$d$$. With challenge $$c_1$$ for $$Q_r$$ and $$c_2$$ is for $$Q_{dr}$$, an attacker could generate a random point $$S$$ and then flip the challenge in the response and compute the x-coordinates of the pair $$(ECDH(c_1, Q_{dr}), S)$$. Or?

And if the non-interactive part is not possible, the protocol can be simplified, as suggested in the comments, by only focusing on the ecdh input point. This would change steps 5,6,8 and the following verification steps.

The Verifier only has to generate generate scalar $$m \in [1, order-1]$$ and the challenge becomes $$C = m \cdot Q_r$$.

The Holder now only has to compute $$R=ECDH(d, C)$$ and the Verifier could compare $$R$$ with $$ECDH(m, Q_{rd})$$.

• Please can you define what you mean by a correlation handle. Also can you explain why steps 8 and 12 do not violate criterion 3 for breaking the protocol. Commented Mar 1 at 23:27
• @DanielS I was sloppy. Criterion 3 should of course say that it must not be possible to generate a proof of possession of without $d$. By correlation handle I mean material that can be used to track user behavior across presentations, e.g., a public key used to verify a signature over a nonce. I am aware of signature key blinding (e.g., datatracker.ietf.org/doc/draft-irtf-cfrg-signature-key-blinding) but cannot rely on it since my private key is in a secure hardware module (PIV card). Commented Mar 2 at 10:50
• The value $Q_{dr} = dr \cdot G$ appears to be specific to the holder. If the holder hands that (as a part of $P$) to the verifier, how is this anonymous? Commented Mar 2 at 16:56
• @sander Is correct; every attestation will have a unique $r$. As for the two points in $C$. If both $Q_r, Q_{rd}$ were multiplied with challenge $m$, the Verifier cannot tell if the User did step 8 or returned the challenge $Q_{drm}$ and a random value. But I realize now that the Issuer can just clarify that the $Q_r$ is the ECDH input. That way step 6 only requires one challenge. And steps 8-11 only need to be done with one point. Finally, ECDSA/Schnorr would be great, but I am working with PIV cards and cannot access $d$! ECDH is the only static PIV function I have access to. Commented Mar 2 at 19:43
• @sander If $m$ is kept secret and it is clear which point is the ecdh_input, then I believe it is possible yes. The user would compute the x-coordinate of $[mrd]G$ and the verifier can either remove the challenge or perform ECDH on its side. But a secret $m$ would not allow replacing the Verifier with a random oracle access, no? It would be neat if the user could send all the information for verification in one go. Commented Mar 2 at 20:18

Based on the comments I did some further reading. I think a multi-party DH key exchange (c.f., 1025) can serve as a basis for what I am after.

More specifically, in a three party DH setting, the Issuer and the Holder can share a symmetric key $$r$$, e.g., by deriving it from the Holder's public key $$Q_d=[d]G$$ using some deterministic key derivation function, $$DK()$$. I find both BIP32, and ARKG interesting.

The following should be a Proof of Possession protocol that satisfies the three requirements listed in the original post.

The Issuer steps:

1. Deterministically generate r.
2. Include ecdh_input_issuer, key_share_issuer_holder = ECDH(r, G), ECDH(r, [d]G)) in the attestation and sign it.

The Holder steps (the Verifier public key, $$Q_v = [v]G$$, is known to the Holder):

1. Computes 3 party DH key share s = ECDH(r*d, Q_v). This can be done by first computing [rv]G.x = ECDH(r, Q_v), finding a point with that x-coordinate, and then using the secure hardware to compute s = ECDH(d, [rv]G).
2. In this simple case, the Holder sends $$R=s$$ to the Verifier together with the attestation.

The Verifier steps once it receives $$R$$ and the attestation:

1. Computes a point, $$[dr]G'$$, from key_share_issuer_holder (sign of y-coordinate does not matter). Alternatively the Verifier just computes the scalar multiplication using x only.
2. Computes the 3 party DH key share s' = ECDH(v, [dr]G') or using an x coordinate only method.
3. Checks if s' == s

The shared key $$s$$ can be used to sign a challenge, or as input to a KDF. Both ways would permit linking the response $$R$$ to a presentation session_id and/or a challenge. This would be context specific.

Has anyone seen anything like the above? Would the above steps work as a basis for a secure and privacy preserving proof of possession?

• The Holder-Verifier protocol looks like the ECDH-agreed MAC authentication with the mdoc/mDL mobile security object. For deterministic generation of r, maybe also use ECDH between Holder and Issuer? What is the purpose of including ecdh_input_issuer in the attestation? Commented Mar 5 at 6:21
• I was thinking of using some deterministic key generation for r, unclear which one. ECDH would link the r value to the issuer, which may or may not be desirable. Without ecdh_input_issuer, a Holder with a PIV card cannot compute [drv]G, or? I assume you mean that the Holder can compute r and thus it does not need to be included in the issued attestation, correct? Commented Mar 5 at 7:55
• Correct. And for avoiding linking to the issuer: let the issuer generate an ephemeral ECDH key. Or mix that with a static key such as in the Noise protocol framework. Commented Mar 5 at 8:00