5

Disclaimer: This question is of theoretical importance to me trying to educate myself better on cryptographic principles and signature schemes. I don't intend to imply that in practice schnorr signatures are less secure than current 2-2 multisig transactions / scripts.

I am currently reading the musig paper and about scriptless scripts. In my understanding an important common idea in both cases seems to be able to have a single signature produced from several private keys.

Let us assume I can brute force the private key from a public key within reasonable time let's say 1 month (for example because I have a somewhat efficient algorithm for the discrete log in ecdsa (which I don't have). Also assume I can invert the hash function of Bitcoin addresses quickly. Or assume we just know the public keys because I am the third party in an escrow service)

Wouldn't I be able to break a MuSig address within 1 month (under the above assumption) by breaking the aggregated private key to the aggregated public key whereas in the setting of a common 2-2 multisig wallet I would need 2 months in order to be able to provide two valid signatures since I'd have to bruteforce both private keys independently of each other?

5

Yes or no, depending on your definition.

You are right that the expected time to forge a 2-of-2 multisignature is twice that of a single signature, because you obviously need to use your forger algorithm twice.

However, in practice such constant factors are ignored when describing security levels. For example, typically ed25519 and secp256k1 are placed in the same group of 128-bit security, despite the fact that secp256k1 needs on average 4x more iterations of Pollard's rho algorithm to break the DLP. On the other hand, due to secp256k1's efficiently computable endomorphism, individual iterations of that algorithm are 1.7x faster than what would be expected otherwise.

Furthermore, the unit they're specified in is vague. When talking about ECDLP, the security levels is usually specified in terms of the number of elliptic curve multiplications. But an EC multiplication is not a trivial thing, nor is its performance identical across curves. However, when talking about things in the order of 2^128 a factor 10 here or there only changes the exponent by 3.3. It gets even fuzzier when you take into account specialized hardware that could be built for certain tasks, making it even hard to compare.

The point is that we don't care how long things take for an attacker. We only care that they're so long that no attacker could conceivably use them to pose a real threat.

If it takes too long to forge two signatures, it very likely also takes too long to break one.

  • 3
    Thanks for elaborating on the practical considerations too. Though it was quite clearto me that such a factor is not of practical relevance I learned a few more things from your answer! Btw expect more questions about rogue attacks, key aggregation and the musig paper over the next days (: – Rene Pickhardt Mar 6 at 19:32
  • 1
    Keep 'em coming. – Pieter Wuille Mar 6 at 19:36

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.