4
$\begingroup$

I'm looking for a way for a single individual to sign or otherwise provide proof of ownership of two private keys from keypairs $A$ & $B$.

Simultaneous ownership is important. Alice can't do part of the proof with $A$, then pass the proof to Bob to finish with $B$. The proof requires both keys in a single step. E.g. Signing a message with $A$ then $B$ does not work, as this work could be split between two actors.

Both $A$ & $B$ keypairs are normal, independent keypairs. I.e. this isn't about splitting a single private key into multiple parts to be reconstructed.

Any hints are appreciated, though eventually I'd want to implement this using RSA or ECDSA.

Update: Some further boundaries:

  • This doesn't have to be a single step, or a single signature. As long as it can't be colluded on by two parties without exposing their private keys, any process is acceptable.
Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I don't think you can. If Bob's going to assist Alice in attesting ownership of private keys A and B, then he could just give her his private key B, rendering moot any such attempt at proof. $\endgroup$
    – Myria
    Commented Aug 30, 2022 at 23:22
  • 2
    $\begingroup$ The point is to ensure that if two people collude, they HAVE to share private keys. (Or at least, I want to ensure that there is no way that A + B could be proven together without one party knowing both keys). The intention is for a single party who owns two keys to prove ownership. Bob should not be involved, as he does not want to share his private key. $\endgroup$
    – AlexHeeton
    Commented Aug 31, 2022 at 7:50
  • 2
    $\begingroup$ Does this answer your question? Cheapest way to prove that two different private keys are known to the same person? $\endgroup$
    – Myath
    Commented Sep 7, 2022 at 4:40

2 Answers 2

Reset to default
4
$\begingroup$

Alice has the (private, public) EC key pair $(a, A=aG)$, and Bob has $(b, B=bG)$.

Let's say that Alice starts the signature, and gives it to Bob to complete (or somehow collaborates with Bob to complete it). This would mean that either:

  1. You need to ensure that whatever Alice gives to Bob will reveal $a$ to Bob, with no possible way for any scheme to be devised that would prevent Bob from learning $a$ through some form of blinded collaboration.

  2. The signature is not zero-knowledge, and will reveal one of the private keys to the holder of the other private key.

An easy way to achieve option 2 would be to provide a signature by either $A$ or $B$, and to include the value $d=a-b$. A verifier can easily check that $dG\overset{?}{=}A-B$. This means that knowledge of $d$ would allow someone with knowledge of either $a$ or $b$ to recover the value of $b$ or $a$ respectively.

Normally, Alice would not want anyone else to know $d$, as certain signature schemes that do not properly bind to the intended public key would be malleable by someone that wanted to make a signature signed by $A$ look like it was actually signed by $B$. But, this can be avoided as long as the signature scheme is secure against this attack, and this threat may not matter if it is public knowledge that $A$ and $B$ are owned by the same person.

Since this is not a zero-knowledge proof, there is the risk that knowledge of $d$ could have adverse consequences in certain scenarios that I have not imagined.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is precisely the information I was looking for, thankyou for explaining some of the potential risks, I can proceed from here. "Proceed" does not mean put this in to practice ;) I'm aware the potential risk of malleability attack or another attack warrant a lot more work. $\endgroup$
    – AlexHeeton
    Commented Sep 1, 2022 at 9:12
  • $\begingroup$ @AlexHeeton: If I understand correctly, $b-a\bmod n$ (where $n$ is the order of $G$) is made public. Importantly, that allows Alice to sign as Bob, and vice versa. $\endgroup$
    – fgrieu ♦
    Commented Sep 5, 2022 at 10:10
  • $\begingroup$ @fgrieu To rephrase your issue, you're saying that if b-a mod n is public, then the owner of b will know a? If so, that is desirable. $\endgroup$
    – AlexHeeton
    Commented Sep 6, 2022 at 11:39
1
$\begingroup$

One solution for the ECDSA case is to have the owner sign with the key a+b (that is adding the private keys together mod the order of the curve).

This is straightforward to verify since the public key is also A+B (that is adding the public keys together).

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ The obvious problem with your proposed RSA solution is that the holders could generate the padded message $m$ (padded to the length of $n_1n_2$), and then they individually generate $m^{e^{-1}} \bmod n_1, m^{e^{-1}} \bmod n_2$, and then it's easy to combine those two signatures to form $m^{e^{-1}} \bmod n_1 n_2$, generating a signature where neither side knew both private keys. I believe that a similar approach can be done with ECDSA; however it's a little trickier to do without an internal value leaking anything $\endgroup$
    – poncho
    Commented Aug 30, 2022 at 17:59
  • $\begingroup$ As usual, I should not be writing things about RSA. I will have to think more about the ECDSA case. $\endgroup$
    – Aman Grewal
    Commented Aug 30, 2022 at 19:10
  • $\begingroup$ Good idea, and thanks poncho for pointing out the weakness. $\endgroup$
    – AlexHeeton
    Commented Aug 31, 2022 at 7:52
  • 1
    $\begingroup$ Addition: that ECDSA solution might translate to many signature systems where the private key is the discrete logarithm of the public key in some (fixed) public group, including DSA, EdDSA, and various Schnorr signatures. [update] But I'm still wondering if B could post-process a signature made by A into one that verifies, without knowing A's private key… $\endgroup$
    – fgrieu ♦
    Commented Aug 31, 2022 at 8:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.