Cheapest way to prove that two different private keys are known to the same person?

Say that there are two unrelated ECC keypairs ($Pub_1$, $Priv_1$) and ($Pub_2$, $Priv_2$). Alice claims that she knows both $Priv_1$ and $Priv_2$, but Bob doesn't trust her, and thinks that $Priv_2$ is only known to Eve, Alice's friend.

Bob asks Alice to prove that she controls both private keys. Now, Bob knows that if Eve really does control $Priv_2$, she'd willing to collude with Alice to generate a proof that Alice controls both. But he also knows that Eve's trust is limited—Eve wouldn't actually be willing to tell Alice the private key $Priv_2$.

What proof could Alice give Bob that she (or at least the same person) knows both $Priv_1$ and $Priv_2$? Note that eg. a nested signature like eg. $Sig_1(Sig_2(msg))$ is insufficient, because Eve could just generate $Sig_2(msg)$ and give it to Alice to wrap in $Sig_1$ without ever revealing $Priv_2$.

Another complication: the proof needs to work efficiently on the secp256k1 curve. (I've looked into using a zkSNARK for this, but the SNARK libraries I've seen don't operate efficiently on that curve.)

This seems theoretically impossible. As far as I can tell, there's no distinction between knowing $priv_2$ and colluding with someone who knows $priv_2$.

Assume some proof protocol $\Pi$ exists between the prover (A) and the verifier (B), that satisfies the described requirements. There is always a way for $A(priv_1)$ and $E(priv_2)$ to collude to execute $\Pi$ in a way that $A$ learns nothing about $priv_2$. $A$ and $E$ just run some MPC protocol to compute the next response to $B$.

The security of the MPC protocol guarantees that $A$ learns nothing more than its own input $priv_1$ and the outputs, which are the responses to $B$, which everyone can see anyway. And if $\Pi$ is zero-knowledge to $B$ (typically desired), then $A$ learns nothing from the responses.

Disclaimer: I do not have a security proof for this scheme. Criticisms are welcome.

To simplify the notation, I'm calling the two (private, public) key pairs $(a, A = a\cdot G)$ and $(b, B = b\cdot G)$ on the base point $G$. Lowercase letters are scalars, uppercase letters are EC points. $H_s()$ means hash and reduce (mod the order of $G$) to a scalar. All operations between scalars (such as subtraction and multiplication) are mod the order of $G$.

First, declare $D = a\cdot b\cdot G$.

let $m = H_s(\text{"message being signed"})$ as a one-time message that will prevent reuse of this signature across contexts.

To prove $D$ really is constructed properly, use an extended Schnorr signature:

Signature is $(D, c, r)$ where $k$ is a random scalar, $c = H_s(m \mathbin\| k\cdot G \mathbin\| k\cdot B)$ and $r = k - c\cdot a$.

Signature is verified by checking $c \overset{?}{=} H_s(m \mathbin\| r\cdot G + c\cdot A \mathbin\| r\cdot B + c\cdot D)$ and by checking $D$ is a valid point and not the point at infinity.

This proves both that $a$ is known, and that $a$ is both the private key of the point $A$ on the generator point $G$, and also the private key of the point $D$ on the generator point $B$. Therefore $D$ is proven to be $a\cdot b\cdot G$.

Finally, we need to produce a second signature proving that someone knows both $a$ and $b$. We can do that by proving knowledge of the private key of point $D$ on the base point $G$ (thus proving knowledge of $a\cdot b$).

Signature is $(c', r')$ where $k'$ is a random scalar, $c' = H_s(m \mathbin\| k'\cdot G)$ and $r' = k' - c'\cdot a\cdot b$.

Signature is verified by checking $c' \overset{?}{=} H_s(m \mathbin\| r'\cdot G + c'\cdot D)$.

If Alice were to collude with Eve without Eve disclosing $b$, Alice would have to disclose her private key $a$ to Eve. Knowledge of $k'$ by either colluder would allow that colluder to calculate the other colluder's private key. The security of this scheme depends on it not being mathematically possible for Alice to somehow collude with Eve to construct $r'$ such that either Alice or Eve could then mathematically determine the other's private key.

The overall signature is therefore $(D, c, r, c', r')$ and is $5\cdot 32 = 160$ bytes.