3
$\begingroup$

Given two (or more) algorithms:

  • ed25519
    • private key is random blob of 32 bytes
    • public key is encoded point on Edwards 25519 curve.
  • ECDSA with secp256k1
    • private key is random blob of 32 bytes
    • public key is encoded point on secp256k1 curve.

Lets say, we have a message M and we sign it with both algorithms, with the same private key (public keys are calculated deterministically based on private key). Adversary is able to see both signatures, collect history of such signatures for different messages, messages are unencrypted.

Are there any security implications for this scheme?

$\endgroup$
  • 2
    $\begingroup$ Note that you could also store 128 bits of data or more and derive the two keys from that using a KDF with two labels. $\endgroup$ – Maarten Bodewes Jan 13 '18 at 21:55
  • 1
    $\begingroup$ Why do you want to do that? Reusing a key-pair on the same curve can be useful. But on different curves, I don't see any advantage at all over using different private keys (since the public key is already different). $\endgroup$ – CodesInChaos Jan 14 '18 at 15:35
  • $\begingroup$ @CodesInChaos I am building 2-way-peg and considering usage of the same private key for different blockchains. I think I will stick to Maarten Bodewes's answer. Thanks for your help! $\endgroup$ – warchantua Jan 22 '18 at 14:56
4
$\begingroup$

In general, using the same key in different algorithms is bad practice, and indeed having two public keys on different curves with the same private key could reveal information. I don't know how, but I am sure that you cannot prove a reduction from one to another (unless you can map one group to another, which is doubtful).

Having said the above, if you use the same curve, but just different algorithms for signing, then I believe that one could prove security (but I won't do all the details). This is because EdDSA is actually a Schnorr signature, and so it is a zero-knowledge proof of knowledge of the secret key, secure in the random oracle model. Thus, one could proof that if you can break ECDSA given ECDSA and EdDSA signing oracles, then you could break ECDSA given only an ECDSA signing oracle (by simulating the EdDSA signing oracle yourself in the random oracle model). Thus, if ECDSA is secure then using the same key for Schnorr doesn't harm anything.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure if your security argument actually holds, considering the OP intends to use different curves. (Though it is likely stills secure in practice) $\endgroup$ – CodesInChaos Jan 13 '18 at 20:18
  • 1
    $\begingroup$ The security argument should hold because the entire Schnorr part can be simulated as zero knowledge (in the ROM) and so it doesn't matter what the other signature does. However, I will never say that I'm sure of something until a full proof has been written. $\endgroup$ – Yehuda Lindell Jan 14 '18 at 5:38
  • $\begingroup$ My doubts are related to the key generation part, and not the signature part. I don't find it obvious that publishing public-keys computed over different curves but sharing the private scalar is reducible to the DL being hard in all groups. $\endgroup$ – CodesInChaos Jan 14 '18 at 11:57
  • $\begingroup$ Oh, I'm sorry. I didn't notice the different curves. You are right. This could be very problematic. $\endgroup$ – Yehuda Lindell Jan 14 '18 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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