Knowledge proof of private keys from DH key exchange

Question

Given a group where the computational Diffie–Hellman (DH) assumption holds and generator G.

Say there is a set of private randomly selected keys {a, b, c, d, e,...} and corresponding public keys set {A, B, C, D, E,...} calculated as A=aG. Each public key is publicly linked to its corresponding user/owner.

Alice can use its private key a and the public key of Bob, B, to calculate K=aB. This K is used as a tag for both users, can be publicly available, as it will not be used to encrypt messages, just as a reference. Bob can verify this by knowing that Alice is making the request (assume this), calculating K'=bA and checking if K=K'. Only Alice and Bob can know that this K is related to them.

From the computational DH assumption, K is meaningless for the other users. And K is a way to track this combination for the relevant users, in this case, Alice and Bob. I am assuming for now that this K is unique per private key combination.

Is it possible to prove that K contains two different private keys from the set of private keys without revealing the private keys?

The private/public keys need to be used to create another combination, say in case Alice and Charlie, acG. Because of this, (M)LSAG, as used in Moreno, is not usable because the keys need to be reused and such a link could reveal to Charlie that Alice already made some kind of transaction with someone else from the set of public keys.

I would like to have this proof in order that every user can verify that the K is valid, (i.e., calculated using private keys from the set), to avoid spam. An evil user could just generate random K using his/her private key but would be meaningless to everybody else. A blockchain will be used to track the references.

LSAG stands for Linkable Spontaneous Anonymous Group, and M for matrix version.

Answer 1

If I understand it right, you want a way to prove, given a list $\{A, B, C, D, \cdots\}$ of public keys, that some given key $K$ is "the tag" corresponding to a pair of key from this list, without revealing which one. Let me call this a "valid tag".

For simplicity, suppose that $K$ is the tag of Alice and Bob. Either Alice or Bob can prove that $K$ is a valid tag, using standard zero-knowledge proof techniques. The intuition is as follows:

(1) If the pair $(A,B)$ was not supposed to stay hidden, then Bob could just perform a zero-knowledge proof that $(G,A,B,K)$ is a Diffie-Hellman tuple, using his witness $b$ (such that $G^b = B$ and $A^b = K$). There are standard zero-knowledge proofs for this relation, see for example my answer here.

(2) To keep the pair hidden, we change the statement: instead of proving "$(G,A,B,K)$ is a Diffie-Hellman tuple", Bob proves the statement "$(G,A,B,K)$ is a Diffie-Hellman tuple, OR $(G,A,C,K)$ is a Diffie-Hellman tuple, OR $(G,A,D,K)$ is a Diffie-Hellman tuple..." and so on (for each pair of distinct public keys). Then, using the CDS OR-trick, we can convert the zero-knowledge proof for the Diffie-Hellman relation into a zero-knowledge proof for an OR of many Diffie-Hellman relation (in particular, the resulting proof will not reveal which of the statements in the OR is the true one).

The above is the simplest, most direct solution. Of course, it is expensive: the cost of the proof grows as $n\cdot(n-1)/2$ times the cost of a single Diffie-Hellman proof (or $n$ times if we can leak the identity of one of the two parties involved in the tag $K$). There exists solutions to reduce the cost, but they use significantly more advanced cryptographic techniques. A good example are one-out-of-many proofs which enable precisely this kind of OR-proofs, but with logarithmic communication in the number of OR clauses.

Last thing: if you want everyone to check the proof and do not want to re-do the proof with everyone, then you can make the proof non-interactive in the random oracle model using the Fiat-Shamir transform; this way, it becomes publicly verifiable. Also, note that when a party sends this proof, this will always leak information: e.g. the fact that Bob sends the proof that $K$ is a valid tag always reveals that Bob could check that himself in the first place, which means that Bob's public key is one of the keys involved. It might be ok in your scenario, but you must be clear with that.

Answer 2

I never know the practical case for ECDH to be used for a group of key pairs like that. There are formal ways to split secrete for a group of people more than 2. e.g. https://en.wikipedia.org/wiki/Secret_sharing

AFAIK, ECDH should be used to create shared secrete between exactly 2 parties.

From the computational DH assumption, K is meaningless for the other users. And K is a way to track this combination for the relevant users, in this case, Alice and Bob. I am assuming for now that this K is unique per private key combination.

You might have some misunderstanding to the shared secrete, but K is also meaningless for Alice and Bob to track back each other's private key, too. The nature of ECC scalar multiplication, which you used to generate a public key, is one-way. Mathematically the way Alice can find Bob's private key is to exhaust all the points in a big space like 2^256 or bigger, which is really hard to do with current computation resource on earth.