Published on: 2018-07-26T02:05:05+00:00
The email conversation discusses the implementation of an M-of-N "single sig" extension of MuSig without the need for new opcodes. The solution involves using MuSig's blinding factor solution and interpolation to achieve M-of-N instead of M-of-M.Each party publishes a public key and a random nonce. The x coordinate is used for interpolation purposes, while R is derived from the interpolation of G*k1, G*k2... L is obtained from H(X1,X2,...), and X is the sum of all H(L,Xi)Xi. E (a blinding factor) is computed as H(R | M | X), with si being a share of the signature and xi being the private data. (si, e) are then published as the share signature. To prevent a birthday attack on k, e2 is introduced as a second blinding factor, and (si, e, e2) is published as the share signature. Finally, any party can derive s from m of n shares by interpolating, not adding.The author of the message expresses gratitude for assistance and provides a summary of the solution arrived at for an M of N "single sig" extension of MuSig, which involves using MuSig's blinding solution to solve the Wagner attack and interpolation to enhance MuSig to be M of N instead of M of M. The process involves each party publishing public key G*xi, computing Xi and r, and deriving e and si for each participant. Any party can derive s from m of n shares by interpolating rather than adding. The references used include MuSig and HomPrf.The conversation is discussing the musig construction and how it can be used in m of n multisig. The musig construction involves hashing all keys and summing the multiples to compute the shared blinding factor, which improves the system. This results in a nice Shamir m of n multisig with a single signature and all the same properties otherwise. In response to this, Russell O'Connor raises a concern about multiparty signature attacks where an attacker can modify more than one variable. In a coin-join protocol where every other participant could be the same attacker representing themselves as multiple participants, the attacker can get their hands on multiple variables.In a discussion on bitcoin-dev mailing list, Erik Aronesty raised the question of whether or not it is possible to use the birthday attack where there is only one variable to modify. He argued that in a multiparty signature, an attacker can have more than one variable to modify. In such cases, the attacker could be representing themselves as multiple participants and thus have access to multiple variables. This scenario can arise in coin-join protocols where every other participant in the multi-party signature might actually be the same single attacker.The context describes a discussion between individuals regarding the security of a bitcoin private key. The conversation revolves around the idea of a secure multiparty computation (SMC) of a signature being more secure overall than other methods. However, there is some uncertainty about how to do it offline and all parties need to agree on the blinding factor. The conversation then shifts towards the applicability of Wagner's algorithm in this scenario. It is mentioned that adaptively chosen public keys can be dangerous and easily exploited, but using hash(pub) as X prevents this attack. Ultimately, the discussion centers around the security of Shamir secret sharing interpolation and how it prevents attacks on the multisig construction.The discussion revolves around the security of Shamir secret sharing and the adaptability of Wagner's algorithm in the multisig construction. The writer argues that Wagner's algorithm is not applicable due to the inability to birthday attack something where there is only a single variable that can be modified. Additionally, with an additive construction adaptive attacks are possible, but there is no mechanism for a birthday attack on k in this revised solution.A new threshold multi-signature scheme has been proposed that offers a simpler mechanism compared to musig and aligns more closely with the original Schnorr construction. In this scheme, each party has a public key g*x', where x' is their private key, and rolls a random k' to compute r' = g*k'. The share of r' is broadcasted, and lagrange interpolation is used to compute g*k across shares. Verification follows the same process as Schnorr, but interpolation is used to obtain the necessary components (s, e, g*x') from shares of s', e', and g*x'. The security assumptions are based on Shamir + discrete log.The proposed construction allows for offline production of multisig signatures, with each device generating its own k-share and x-share. Only the interpolation of M out of n shares is required, eliminating the need for round trips. It is important to prove that H(M) * r does not reveal any information about k, relying on the same discrete logarithm assumptions as Bitcoin itself.
Updated on: 2023-08-01T23:39:16.191213+00:00