Nonce generation techniques in Schnorr multi-signatures: Exploring EdDSA-inspired approaches

1.   Introduction

Digital signatures serve as a cornerstone of modern cryptographic practices, underpinning the security and trustworthiness of digital communications, financial transactions, and authentication processes.

The concept of digital signatures dates back to the 1970s, with the theoretical foundations laid by public key cryptography. Whitfield Diffie and Martin Hellman first introduced the idea in their seminal 1976 paper ^[1], paving the way for the development of various digital signature schemes. The first practical implementation, the RSA algorithm, was developed in 1977 by Rivest, Shamir, and Adleman ^[2]. It utilizes the computational difficulty of factoring large integers as the basis for security. This was followed by the introduction of the digital signature algorithm (DSA) in the early 1990s, which relies on the discrete logarithm problem ^[3]. Both schemes set the stage for subsequent advancements and adaptations in digital signature technology. The Schnorr signature scheme, introduced by Claus Schnorr ^[4], is distinguished by its simplicity and efficiency, particularly in terms of verification speed and shorter signatures. Later, the Edwards-curve digital signature algorithm (EdDSA) was developed to provide stronger security assurances and better performance using twisted Edwards curves ^[5]. Each of these developments has contributed to the robust framework within which digital signatures operate today, addressing various aspects of security and efficiency.

The evolution of digital signature schemes has been marked by a continuous quest for enhanced security, efficiency, and practical applicability. In this context, a nonce (number used once) is a random or pseudo-random number that must not be repeated with the same private key. However, the challenge of securely generating nonces (a critical component in the signature process) remains a pivotal concern that directly impacts the scheme's security and operational viability. For instance, in ECDSA (elliptic curve digital signature algorithm) and classic DSA, the uniqueness and secrecy of the nonce are crucial; if a nonce is revealed, it can lead to straightforward attacks that recover the private key. However, generating random nonces is fraught with challenges. The main vulnerability lies in the quality of the randomness. This issue was notably exploited in the PlayStation 3 firmware hack, where ECDSA nonces were predictably generated due to inadequate randomness, ultimately leading to the compromise of the private signing key.

In the digital signature schemes, the elliptic curve digital signature algorithm (ECDSA) ^[6] and the Edwards-curve digital signature algorithm (EdDSA) ^[7] have set benchmarks for security and performance. Particularly, EdDSA's approach to deterministic nonce generation has garnered attention for its ability to circumvent the pitfalls associated with random nonce generation, notably the risks of randomness failures and the subsequent exposure to attacks that could compromise the signer's private key. Therefore, the integration of deterministic nonce generation used in EdDSA's into Schnorr signatures presents a promising avenue for enhancing the robustness and efficiency of these protocols. Therefore, integrating deterministic nonce generation, as used in EdDSA, into Schnorr signatures presents a promising avenue for enhancing the robustness and efficiency of these protocols.

Previous studies have highlighted various approaches to nonce generation, emphasizing the risks associated with randomness failures. For instance, in their paper "Reusing Nonces in Schnorr Signatures (and keeping it secure...)" (2018) ^[8], Beunardeau et al. discuss the problem of nonce reuse in Schnorr signatures, which can reveal the secret signing key and compromise the security of the signature scheme. To overcome this issue, the authors propose a variant of the Schnorr signature scheme that allows for the reuse of nonces across multiple signatures while maintaining security. Their variant uses a prime modulus p such that p-1 has several different factors q_i large enough to resist birthday attacks and mutualizes exponentiation efforts to achieve faster and more resource-efficient signatures. The authors also compare the performance of their scheme with classical Schnorr signatures and present several pre-computation techniques to speed up modular exponentiation, which is often the bottleneck in implementations of cryptographic systems.

It is worth noting that a lack of specific literature addressing the issue of nonce reuse attacks in EdDSA digital signatures was identified, largely because EdDSA is resistant to such attacks when the appropriate hashing function is chosen. Nonetheless, it is crucial to acknowledge that the security of any digital signature scheme, including EdDSA, is not impervious to potential vulnerabilities. For instance, fault attacks that exploit computational errors during the signature computation process ^[9], as well as other types of attacks that are unrelated to nonce reuse, could pose significant risks.

In their paper "Non-interactive Half-Aggregation of EdDSA and Schnorr Signatures" (2021) ^[10], Chalkias K., Garillot F., Kondi, Y., and Nikolaenko, V. offer a detailed investigation into non-interactive aggregation techniques for EdDSA and Schnorr signatures, focusing on optimizing signature aggregation for improved efficiency in cryptographic applications. The study delves into the intricacies of compact signature schemes, discussing the advantages and challenges of reducing signatures. By conducting thorough implementation and benchmarking analyses, the researchers demonstrate the practicality and performance of the proposed aggregation constructions. The results highlight the feasibility of the half-aggregation scheme and provide insights into the computational overhead required to achieve provable security guarantees in signature aggregation. The authors detail a methodology that not only enhances data compactness but also maintains the integrity and security of the signatures against various cryptographic attacks, making it highly relevant to investigations into the efficiency and security of Schnorr multi-signatures.

In another study, "Two-Round Stateless Deterministic Two-Party Schnorr Signatures from Pseudorandom Correlation Functions" (2023) ^[11], Kondi, Y., Orlandi, C., & Roy, L. introduced a novel protocol for two-party threshold Schnorr signatures that not only ensures stateless and deterministic signing but also addresses the inefficiencies found in previous threshold protocols. Utilizing pseudorandom correlation functions (PCFs), the study enhances both the security and efficiency of distributed Schnorr signing. These PCFs enable the distribution of signing nonces in a distributed, stateless, and deterministic manner, reducing the bandwidth cost per participant and making the system more suitable for practical applications.

The research provides a comprehensive analysis of various techniques for distributing Schnorr signatures, assessing key factors such as the number of rounds, bandwidth requirements, underlying assumptions, and security guarantees. The proposed protocols are designed to achieve both covert and full active security, offering robust protection against malicious actors under generic cryptographic assumptions. This advancement showcases significant improvements in the field of distributed signing protocols, particularly in how Schnorr signatures can be effectively and securely implemented in a threshold setting.

The research paper titled "MuSig-DN: Schnorr Multi-Signatures with Verifiably Deterministic Nonces" authored by Jonas Nick, Tim Ruffing, Yannick Seurin, and Pieter Wuille (2020) ^[12], provides significant insights into nonce generation and its implications for digital signature algorithms. The authors introduce a novel multi-signature scheme called MuSig-DN. This scheme utilizes deterministic nonces, which are generated in a manner that effectively safeguards against virtual machine rewinding attacks and nonce reuse attacks.

One of the pivotal challenges existing in MuSig-DN is the inherent complexity associated with deploying non-interactive zero-knowledge (NIZK) proofs to ascertain the deterministic generation of nonces. These proofs, while integral for securing the protocol against specific attack vectors and ensuring the determinism of nonce generation, introduce a notable layer of computational and conceptual complexity. Specifically, the protocol necessitates the construction and verification of NIZK proofs that each nonce was generated in accordance with the deterministic protocol. This requirement not only amplifies the computational overhead but also increases the intricacy of implementation, rendering the protocol less feasible for resource-constrained environments such as hardware wallets, which are prevalent in cryptocurrency applications.

The paper "MuSig2: Simple Two-Round Schnorr Multi-Signatures" (2023) ^[13], authored by Jonas Nick, Tim Ruffing, and Yannick Seurin, introduces a novel approach to multi-signatures by proposing the MuSig2 scheme, which optimizes the digital signature process. The research conducted in this paper focuses on enhancing the efficiency and security of multi-signature schemes, particularly in the context of Schnorr signatures. By leveraging the concept of using multiple nonces in the signing process, MuSig2 achieves significant improvements in security guarantees and performance metrics.

The key contributions of the paper include:

● Introducing MuSig2 as a two-round variant of the MuSig scheme eliminates the preliminary commitment phase and enables signers to start the signing process directly with nonces.

● Utilizing a varying number of nonces (1, 2, or 4+) to cater to different security requirements and cryptographic assumptions, such as the algebraic group model (AGM) and the one-more discrete logarithm (OMDL) assumption in the random oracle model (ROM).

The results presented in the paper highlight the efficiency gains and security enhancements achieved through the implementation of MuSig2, making it a valuable contribution to the field of digital signatures and multi-signatures.

On the other hand, the novelty of this research is threefold: First, it integrates EdDSA-inspired deterministic nonce generation into Schnorr multi-signatures, effectively combining EdDSA's robustness with the flexibility and efficiency of Schnorr's signature aggregation. Second, it removes the public nonce (R) from the challenge (c) calculations to ensure the uniqueness of each signature. Third, it allows signers to directly verify possession of secret keys using the aggregated public key, thereby enhancing bandwidth efficiency by eliminating the need for NIZK. This streamlined approach significantly improves security and reduces computational complexity, particularly for devices with constrained resources.

The primary motivation for this research is to address security vulnerabilities inherent in Schnorr multi-signatures, specifically those arising from random nonce generation, such as key cancellation, rogue keys, and nonce reuse attacks. Moreover, this study aims to enhance the efficiency and practical applicability of Schnorr signatures in scenarios where computational resources, memory, and bandwidth are limited.

The research methodology employed mathematical analysis of digital signature algorithms (ECDSA, EdDSA, Schnorr, and MuSig (multi signature) and well-known attacks (such as nonce reuse attacks, virtual machine rewinding attacks, key cancellation attacks, and rogue-key attacks) to understand and assess the effectiveness of the proposed method in addressing various challenges and ascertaining its efficiency. By analyzing the strengths and weaknesses of these digital signature schemes and exploring new techniques, this study presents a novel approach that offers a level of security comparable to that of EdDSA. Consequently, this research contributes to ongoing efforts to enhance the effectiveness and security of digital signatures.

This study met its objectives by addressing critical issues related to random nonce generation, generating the nonce in a deterministic manner, reducing computational complexity, and decreasing the amount of transmitted data combined with the NIZK proof to better utilize bandwidth.

The paper is organized as follows: Section 2 delves into the fundamentals of digital signatures, covering key algorithms such as the elliptic curve digital signature algorithm (ECDSA), the Edwards-curve digital signature algorithm (EdDSA), and the Schnorr digital signature algorithm. Section 2.4 discusses signature aggregation. Section 3 describes the proposed contributions of this research, and Section 4 concludes the findings presented in this study.

2.   Digital signature basics

2.1.   Elliptic curve digital signature algorithm ECDSA

Understanding the proposed method in this study requires a thorough explanation of the ECDSA mechanism, as it is a fundamental cornerstone of our approach.

Signature generation and verification algorithms in ECDSA are as follows ^[6]:

Suppose a sender intends to send a message with a digital signature to a receiver. Initially, they must agree on the curve parameters (E, G, n) and the hashing function H, where E represents the elliptic curve equation used, G represents the elliptic curve base point (the generator point), a point on the curve that generates a subgroup of large prime order n, and n represents the order of G. This means that nG = O, where O is the identity element.

In addition to the shared parameters, the process of signature generation involves the following variables: ${\mathrm{d}}_{A}$, ${\mathrm{Q}}_{A}$, and m. Here, ${\mathrm{d}}_{A}$ represents the private key, which is randomly selected from the interval [1, n-1]); ${\mathrm{Q}}_{A}$ represents the public key, computed as ${\mathrm{d}}_{A}$G; and m represents the message to be signed and sent. Note that the letter 'A' in the variables ${\mathrm{d}}_{A}$ and ${\mathrm{Q}}_{A}$ signifies the sender, whom we assume to be Alice.

For Alice to sign a message (m), she follows these steps ^[6]:

● Calculate e = H(m);

● Select a nonce integer "k" randomly from the range [1, n-1];

● Calculate the point (${\mathrm{x}}_{1}$, ${\mathrm{y}}_{1}$) = kG;

● Calculate r $\equiv$ ${\mathrm{x}}_{1}$ (mod n);

● Calculate s = k^-1(e + r${\mathrm{d}}_{A}$);

● The signature is the pair (r, s). Thus, Alice will send the messages(m), ${\mathrm{Q}}_{A}$, r and s to Bob.

Note that it is not only required for "k" to be secret, but it is also crucial to select a different "k" for each signature.

Bob follows these steps to verify Alice's signature:

● Calculate e = H(m);

● Calculate ${\mathrm{u}}_{1}\equiv$ es^-1 (mod n) and ${\mathrm{u}}_{2}\equiv$ rs^-1 (mod n);

● Calculate the point (${\mathrm{x}}_{1}$, ${\mathrm{y}}_{1}$) = ${\mathrm{u}}_{1}$G+ ${\mathrm{u}}_{2}{\mathrm{Q}}_{A}$;

● Alice's signature is valid just if (${\mathrm{x}}_{1}$, ${\mathrm{y}}_{1}$) ≡ kG.

Proof of the correctness of the algorithm:

(${\mathrm{x}}_{1}$, ${\mathrm{y}}_{1}$) = ${\mathrm{u}}_{1}$G+ ${\mathrm{u}}_{2}{\mathrm{Q}}_{A}$, since ${\mathrm{u}}_{1}\equiv$ es^-1 (mod n) and ${\mathrm{u}}_{2}\equiv$ rs^-1 (mod n), then:

(${\mathrm{x}}_{1}$, ${\mathrm{y}}_{1}$) = es^-1G+ rs^-1${\mathrm{Q}}_{A}$ = s^-1(eG + r${\mathrm{Q}}_{A}$) = $\frac{\mathrm{e}\mathrm{G}+\mathrm{r}{\mathrm{Q}}_{A}}{s}$,

since s = k^-1(e + r${\mathrm{d}}_{A}$), then: (${\mathrm{x}}_{1}$, ${\mathrm{y}}_{1}$) = $\frac{\mathrm{e}\mathrm{G}+\mathrm{r}{Q}_{A}}{{K}^{-1}(\mathrm{e}+\mathrm{r}{d}_{A})}$ = $\frac{\mathrm{k}(\mathrm{e}\mathrm{G}+\mathrm{r}{Q}_{A})}{\mathrm{e}+\mathrm{r}{d}_{A}}$,

since ${\mathrm{Q}}_{A}$ = ${\mathrm{d}}_{A}$G, then: (${\mathrm{x}}_{1}$, ${\mathrm{y}}_{1}$) = $\frac{\mathrm{k}(\mathrm{e}\mathrm{G}+\mathrm{r}{\mathrm{d}}_{A}\mathrm{G})}{\mathrm{e}+\mathrm{r}{\mathrm{d}}_{A}}$ = $\frac{\mathrm{k}\mathrm{G}(\mathrm{e}+\mathrm{r}{\mathrm{d}}_{A})}{(\mathrm{e}+\mathrm{r}{\mathrm{d}}_{A})}$ = kG.

Note that the ECDSA is susceptible to the nonce reuse attack. This means that if Alice uses the same nonce when signing different messages, an attacker, or the opponent (whom we will refer to as Oscar), can potentially discover Alice's private key (${\mathrm{d}}_{A}$). If Alice reuses the same nonce for different message signings, Oscar can carry out the following steps to expose Alice's private key (${\mathrm{d}}_{A}$):

If Oscar, who was listening to this conversation, can perform a subtraction operation between ${\mathrm{s}}_{1}$ and ${\mathrm{s}}_{2}$, the resulting outcome will reveal Alice's private key (${\mathrm{d}}_{A}$) in the following manner:

${\mathrm{s}}_{1}$- ${\mathrm{s}}_{2}$ = k^-1(${\mathrm{e}}_{1}$+ r${\mathrm{d}}_{A}$) – (k^-1(${\mathrm{e}}_{2}$+ r${\mathrm{d}}_{A}$)) = k^-1${\mathrm{e}}_{1}$+ k^-1r${\mathrm{d}}_{A}$ - k^-1${\mathrm{e}}_{2}$- k^-1r${\mathrm{d}}_{A}$ = k^-1${\mathrm{e}}_{1}$- k^-1${\mathrm{e}}_{2}$,

${\mathrm{s}}_{1}$- ${\mathrm{s}}_{2}$ = k^-1(${\mathrm{e}}_{1}$ - ${\mathrm{e}}_{2}$) = $\frac{({\mathrm{e}}_{1}-{\mathrm{e}}_{2})}{\mathrm{k}}$, k = $\frac{{\mathrm{e}}_{1}-{\mathrm{e}}_{2}}{{\mathrm{s}}_{1}-{\mathrm{s}}_{2}}$ = (${\mathrm{e}}_{1}$ - ${\mathrm{e}}_{2}$) (${\mathrm{s}}_{1}$- ${\mathrm{s}}_{2}$)^-1.

By knowing the nonce "k", Oscar now knows (${\mathrm{s}}_{1}$, ${\mathrm{s}}_{2}$, ${\mathrm{e}}_{1}$ = H (${\mathrm{m}}_{1}$) and ${\mathrm{e}}_{2}$ = H (${\mathrm{m}}_{2}$)). By substituting them into the equations for (${\mathrm{s}}_{1}$(or)${\mathrm{s}}_{2}$), Oscar can obtain Alice's private key (${\mathrm{d}}_{A}$) as follows:

${\mathrm{s}}_{1}$ = k^-1(${\mathrm{e}}_{1}$ + r${\mathrm{d}}_{A}$), ${\mathrm{s}}_{1}$ = $\frac{({\mathrm{e}}_{1}+\mathrm{r}{\mathrm{d}}_{\mathrm{A}})}{\mathrm{k}}$, k${\mathrm{s}}_{1}$ = ${\mathrm{e}}_{1}$+ r${\mathrm{d}}_{A}$, r${\mathrm{d}}_{A}$ = k${\mathrm{s}}_{1}$ - ${\mathrm{e}}_{1}$, ${\mathrm{d}}_{A}$ = $\frac{\mathrm{k}{\mathrm{s}}_{1}-{\mathrm{e}}_{1}}{\mathrm{r}}$,

${\mathrm{d}}_{A}$ = (k${\mathrm{s}}_{1}$ - ${\mathrm{e}}_{1}$) r^-1.

A nonce reuse attack, caused by a random number generator failure, was used to extract the signing key for the PlayStation 3 gaming console ^[14]. Additionally, a failure in random number generation caused users of the Android Bitcoin Wallet to lose their funds in August 2013 ^[15]. These incidents emphasize the importance of robust and secure random number generation in cryptographic systems. Thorough testing, evaluation, and implementation of reliable random number generators are crucial to preventing such failures and associated risks.

2.2.   Edwards-curve digital signature algorithm (EdDSA)

Understanding the proposed method in this study requires a thorough explanation of the EdDSA mechanism, as it is one of the cornerstone fundamentals of our approach. The signature generation and verification algorithms in EdDSA are as follows ^[5]:

For Alice to sign a message (m), she follows these steps:

● Select a Private Key (secrete key "${\mathrm{S}}_{k}$") and calculate the public key ${\mathrm{P}}_{k}$ = ${\mathrm{S}}_{k}$G;

● Calculate h = H (${\mathrm{S}}_{k}$);

● Calculate the nonce (r) by concatenating (h) with the message (m) and calculate the hash value for them, r = H (h || m), where || means concatenating h with m;

● Calculate R = x-coordinate of (rG);

● Calculate s = r + H (R||${\mathrm{P}}_{k}$||m)${\mathrm{S}}_{k}$;

● The signature is the pair (R, s), so Alice will send the message (m), ${\mathrm{P}}_{k}$, R and s to Bob.

Bob follows these steps to verify Alice's signature:

● Calculate $\widetilde {\mathrm{s}}$ = H (R||${\mathrm{P}}_{k}$|| m);

● Calculate V₁ = sG, and V₂ = R + ${\mathrm{P}}_{k}\widetilde {\mathrm{s}}$;

● The signature is valid just if V₁ = V₂.

Proof of the correctness of the algorithm:

V₂ = R + ${\mathrm{P}}_{k}\widetilde {\mathrm{s}}$, R = rG and $\widetilde {\mathrm{s}}$ = H (R||${\mathrm{P}}_{k}$||m), then:

V₂ = rG + ${\mathrm{P}}_{k}$H (R ||${\mathrm{P}}_{k}$|| m), since ${\mathrm{P}}_{k}$ = ${\mathrm{S}}_{k}$G, then:

V₂ = rG + ${\mathrm{S}}_{k}$G H (R ||${\mathrm{P}}_{k}$|| m) = G (r + ${\mathrm{S}}_{k}$H (R ||${\mathrm{P}}_{k}$|| m)),

since s = r + H (R ||${\mathrm{P}}_{k}$|| m)${\mathrm{S}}_{k}$, then: V₂ = sG = V₁.

As observed, EdDSA chooses the nonce deterministically as the hash of a part of the private key and the message. Thus, once a private key is generated, EdDSA has no further need for a random number generator to make signatures. In other words, EdDSA is resistant to nonce reuse attacks if an appropriate hashing function is chosen.

However, it is essential to consider the implications of signing the same message multiple times, leading to the reuse of the same nonce ^[7]. Repeating the signing process with the same message multiple times utilizes the same nonce repeatedly. This occurs because neither the private key nor the message changes, and hashing them multiple times results in the same hash value.

Nonetheless, this repetition does not compromise the security of the system. The reason lies in the fact that the generated signatures remain identical. Consequently, if Oscar attempts to compare these signatures, the result will be zero, indicating that they are indistinguishable.

For a more comprehensive understanding, let us examine the steps that Oscar might follow to implement a nonce reuse attack:

Since the two signatures are identical, when Oscar subtracts (${\mathrm{s}}_{1}$) from (${\mathrm{s}}_{2}$), the result would be zero (${\mathrm{s}}_{1}$-${\mathrm{s}}_{2}$ = 0). Consequently, Oscar does not receive any benefit or information from these duplicate signatures.

2.3.   Schnorr digital signature algorithm

Understanding the proposed method in this study requires a thorough explanation of the Schnorr Digital Signature Algorithm, as it is one of the cornerstone fundamentals of our approach. The interesting aspect of Schnorr signatures lies in their linearity, which offers several advantageous properties. Schnorr signatures follow a specific structure (s = r+ck), where (s) represents the signature, (r) represents the random number, (c) represents the challenge, and (k) represents the secret key. This construction also exhibits linearity, thereby aligning harmoniously with the linear nature of elliptic curve mathematics. The linearity exhibited by Schnorr signatures adds to their appeal and suitability for signature aggregation.

The signature generation and verification algorithms in Schnorr are as follows ^[16]:

For Alice to sign a message (m), she follows these steps:

● Given a cyclic group G of prime order p with generator g. select a private key (x) such that 0 < x < p;

● Calculate the public key (X), such that X = g^x;

● Choose a private nonce (r) randomly, such that 0 < r < p;

● Calculate public nonce R = g^r;

● Calculate c = H (X, R, m);

● Calculate s$\equiv$(r + cx) mod p;

● The signature is the pair (R, s). So, Alice will send the message (m), Public Key (X), R and s to Bob.

Bob can calculate (c) since he knows Alice's public key (X), (R), and the message (m). Bob considers Alice's signature valid if g^s = R${\mathrm{X}}^{c}$.

Proof of the correctness of the algorithm:

g^s = R${\mathrm{X}}^{c}$, since R = g^r and X = g^x, then:

g^s = g^r (g^x)^c = g^r+xc = g^s, because s = r + xc.

Note that Schnorr is susceptible to the nonce reuse attack. Oscar can carry out the following steps to expose Alice's private key (x) if she reuses the same nonce for different message signings:

If Oscar performs the subtraction operation between ${\mathrm{s}}_{1}$ and ${\mathrm{s}}_{2}$, the resulting outcome will reveal Alice's private key (x) in the following manner:

${\mathrm{s}}_{1}$- ${\mathrm{s}}_{2}$ = r + ${\mathrm{c}}_{1}$x – (r + ${\mathrm{c}}_{2}$x) = r + ${\mathrm{c}}_{1}$x – r–${\mathrm{c}}_{2}$x = ${\mathrm{c}}_{1}$x –${\mathrm{c}}_{2}$x,

${\mathrm{s}}_{1}$- ${\mathrm{s}}_{2}$ = x (${\mathrm{c}}_{1}$–${\mathrm{c}}_{2}$),

x = $\frac{{\mathrm{s}}_{1}-{\mathrm{s}}_{2}}{{\mathrm{c}}_{1}-{c}_{2}}$ = (s₁- s₂) (${\mathrm{c}}_{1}$ – ${\mathrm{c}}_{2}$)^-1.

By knowing all the parameters (${\mathrm{s}}_{1}$, ${\mathrm{s}}_{2}$, ${\mathrm{c}}_{1}$ = H (X, R, ${\mathrm{m}}_{1}$) and ${\mathrm{c}}_{2}$ = H (X, R, ${\mathrm{m}}_{2}$)), Oscar can obtain Alice's private key (x).

2.4.   Signature aggregation

To comprehend the reason behind the existence of three rounds in multi-signature schemes and how the proposed methodology in this research can eliminate the second round by demonstrating the knowledge of private keys, it is necessary to explain the basic principles related to signature aggregation, its inherent weaknesses, and the potential for exploitation. First of all, it is essential to familiarize oneself with some fundamental concepts.

The process for creating signatures consistently follows this recipe:

● Generate a secret nonce (r);

● Create a public nonce R, where R = rG;

● Alice sends the message (m), R, and the public key (P = private key(k)G) to Bob.

The actual signature is created by hashing the combination of all the public information above to create a challenge, c = H(R||P||m). The hashing function is chosen so that (e) has the same range as private keys.

The actual signature is created by hashing the combination of all the public information mentioned above to create a challenge, c = H(R||P||m). The hashing function is chosen so that (e) has the same range as the private keys. Now, the signature is constructed using the private information (s = r + ck).

Bob can calculate (c), since he already knows (m), (R), and (P). However, he doesn't know the private key or the nonce.

Given the equation sG = (r+ck) G, this expression is expanded to sG = rG + ckG. It is further simplified to sG = rG + (kG)c. With R = rG and P = kG denoted, the equation simplifies to sG = R + Pc.

So, Bob needs to calculate (sG) and check if this calculated value matches the right-hand side of the equation (R + Pc). Bob already has all the necessary information to perform these steps.

After a brief explanation of the approach used to create signatures and how the receiver can verify their authenticity, let us now discuss signature aggregation:

To gain a simple understanding of this, let's explore the application of the linear property of Schnorr signatures to create a two-of-two multi-signature. In this scenario, Alice and Bob want to co-sign a message without completely trusting each other. They need a way to prove ownership of their individual keys, and the combined signature is valid only if both Alice and Bob contribute to it.

Assuming private keys are denoted ${\mathrm{k}}_{i}$ and public keys ${\mathrm{P}}_{i}$. If we ask Alice and Bob to each supply a nonce, we can try:

It appears that both Alice and Bob have the ability to contribute their own (R) values. Additionally, it is possible for anyone to create a two-of-two signature by combining these (R) values with the corresponding public keys. However, it is crucial to note that this scheme suffers from a security vulnerability known as the Key Cancellation Attack.

To understand the key cancellation attack, let us reconsider the previous scenario from a different perspective. This time, Bob has prior knowledge of Alice's public key and public nonce. He waits until she reveals them, then proceeds to deceive by claiming his public key is ${\mathrm{P}}_{\mathrm{b}}^{'}$ = ${\mathrm{P}}_{b}$ - ${\mathrm{P}}_{a}$ and his public nonce is ${\mathrm{R}}_{\mathrm{b}}^{'}$ = ${\mathrm{R}}_{b}$ - ${\mathrm{R}}_{a}$. It is important to note that Bob does not possess the private keys corresponding to these bogus values.

Despite this deception, everyone assumes that the aggregated signature expression remains ${\mathrm{s}}_{agg}$ = ${\mathrm{R}}_{a}$+${\mathrm{R}}_{\mathrm{b}}^{'}$+ c(${\mathrm{P}}_{a}$+${\mathrm{P}}_{\mathrm{b}}^{'}$) in accordance with the aggregation scheme. However, Bob has the ability to create this signature by himself.

To illustrate, we will utilize the equation (sG = R + Pc) to explain the vulnerability:

${\mathrm{s}}_{agg}$G = ${\mathrm{R}}_{a}$+${\mathrm{R}}_{\mathrm{b}}^{'}$+ c(${\mathrm{P}}_{a}$+ ${\mathrm{P}}_{\mathrm{b}}^{'}$) = ${\mathrm{R}}_{a}$+ (${\mathrm{R}}_{b}$-${\mathrm{R}}_{a}$) + c (${\mathrm{P}}_{a}$+${\mathrm{P}}_{b}$-${\mathrm{P}}_{a}$) = ${\mathrm{R}}_{b}$ + c${\mathrm{P}}_{b}$ = ${\mathrm{r}}_{b}$G + c${\mathrm{k}}_{b}$G,

${\mathrm{s}}_{agg}$G = G (${\mathrm{r}}_{b}$+ c${\mathrm{k}}_{b}$),

${\mathrm{s}}_{agg}$ = (${\mathrm{r}}_{b}$+ c${\mathrm{k}}_{b}$), Therefore, ${\mathrm{s}}_{agg}$ = ${\mathrm{s}}_{b}$.

Bob could be compelled to authenticate by signing a message, proving his knowledge of the private keys. This method works, but it requires an additional round of messaging between parties. To prevent this attack, the multi-signature method involves three rounds.

Design of the Schnorr multi-signature scheme:

The primary approach for designing a Schnorr multi-signature scheme can be described as follows:

Consider a scenario involving a group of (n) signers who intend to co-sign a given message (m). Initially, each co-signer randomly calculates and shares a unique value ${\mathrm{R}}_{i}$ = ${\mathrm{g}}^{{\mathrm{r}}_{i}}$, where (g) is the generator of the underlying group and ${\mathrm{r}}_{i}$ is a randomly chosen exponent associated with each co-signer.

Subsequently, each cosigner proceeds to compute two values: R = $\prod _{i = 1}^{\mathrm{n}}{\mathrm{R}}_{i}$ and c = H ($\widetilde {\mathrm{X}}$, R, m). Here, $\widetilde {\mathrm{X}}$ represents the product of the individual public keys, ${\mathrm{X}}_{i}$, of all the cosigners, $\widetilde {\mathrm{X}}$ = $\prod _{i = 1}^{\mathrm{n}}{\mathrm{X}}_{i}$ (aggregated public key).

Moving on, the partial signature for each cosigner is computed as ${s}_{i}$ = ${r}_{i}$+ c${x}_{i}$, where ${x}_{i}$ represents the secret key associated with cosigner i. Each cosigner independently calculates their respective partial signature.

Finally, all partial signatures are merged into a single signature using the relation s$\equiv \sum _{i = 1}^{n}{s}_{i}(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{ }\mathrm{p})$, where (p) is the group's prime modulus.

The verification process of a signature, denoted as (R, s), on a message (m), with respect to a set of public keys {${\mathrm{X}}_{1}$, ..., ${\mathrm{X}}_{n}$}, can be expressed equivalently as the equation g^s = R$\widetilde {\mathrm{X}}$.

It should be noted that this verification equation corresponds precisely to the verification equation utilized in Schnorr signatures with respect to the public key represented by $\widetilde {\mathrm{X}}$. This particular property is commonly referred to as key aggregation. However, it is essential to acknowledge that these protocols are susceptible to a rogue-key attack ^[17]. This attack occurs when a malicious signer deliberately sets their public key to ${\mathrm{X}}_{1}$ = ${\mathrm{g}}^{{x}_{1}}$($\prod _{i = 2}^{\mathrm{n}}{\mathrm{X}}_{i}$)^-1, thereby enabling the signer to generate signatures for the individual public keys {${\mathrm{X}}_{1}$, ..., ${\mathrm{X}}_{n}$} independently.

MuSig signature scheme:

MuSig is a Schnorr-based multi-signature scheme that allows a group of signers to produce a short, joint signature on a common message. MuSig is provably secure in the plain public-key model.

The signature generation and verification algorithms in MuSig are as follows ^[18]:

MuSig is parameterized by group parameters (G, p, g) and three hash functions (${\mathrm{H}}_{\mathrm{c}\mathrm{o}\mathrm{m}}$, ${\mathrm{H}}_{\mathrm{a}\mathrm{g}\mathrm{g}}$and ${\mathrm{H}}_{sig}$). These three hash functions can be either identical or distinct, with the decision depending on the desired security level. Utilizing distinct hash functions enhances the level of security.

- Round 1:

A group of (n) signers wants to co-sign a message (m). Let ${\mathrm{X}}_{1}$ and ${x}_{1}$ be the public and private keys of a specific signer, where ${\mathrm{X}}_{1}$ = ${\mathrm{g}}^{{x}_{1}}$. Let ${\mathrm{X}}_{2}$, …, ${\mathrm{X}}_{n}$ be the public keys of the other co-signers and let (L) be the multi-set of all public keys involved in the signing process.

For i$\in${1, …, n}, the signer computes ${\mathrm{a}}_{i}$ = ${\mathrm{H}}_{\mathrm{a}\mathrm{g}\mathrm{g}}$ (L, ${\mathrm{X}}_{i}$) as well as the "aggregated" public key $\widetilde {\mathrm{X}}$ = $\prod _{i = 1}^{n}{X}_{i}^{{a}_{i}}$.

- Round 2:

The signer generates a random private nonce ${\mathrm{r}}_{1}$, computes the public nonce ${\mathrm{R}}_{1}$ = ${\mathrm{g}}^{{\mathrm{r}}_{1}}$, and the commitment ${\mathrm{t}}_{1}$ = ${\mathrm{H}}_{\mathrm{c}\mathrm{o}\mathrm{m}}$(${\mathrm{R}}_{1}$), then sends ${\mathrm{t}}_{1}$ to all other cosigners.

Upon receiving the commitments ${\mathrm{t}}_{2}$, …, ${\mathrm{t}}_{n}$ from other cosigners, the signer sends ${\mathrm{R}}_{1}$ to all other cosigners. This ensures that the public nonce is not exposed until all commitments have been received.

Upon receiving ${\mathrm{R}}_{2}$, …, ${\mathrm{R}}_{n}$ from other cosigners, the signer verifies that ${t}_{i}$ = ${\mathrm{H}}_{\mathrm{c}\mathrm{o}\mathrm{m}}$(R_i) for all i$\in${2, …, n}.

By sending the commitments first, the signers can ensure that no one can change their public nonce after seeing the others. This prevents a rogue-key attack, as a malicious signer would need to know the public nonces of the other signers in advance to construct a rogue public key. If any signer detects a mismatch, they abort the protocol. This ensures that the signers are using the same set of public nonces to compute the aggregated signature, which is important for the security and correctness of MuSig.

- Round 3:

If all commitment and random challenge pairs can be verified with H_agg, the next step involves computing R = $\prod _{i = 1}^{n}{R}_{i}$, c = ${\mathrm{H}}_{sig}$($\widetilde {\mathrm{X}}$, R, m) and ${\mathrm{s}}_{1}\equiv$ ${(\mathrm{r}}_{1}$+ c${\mathrm{a}}_{1}{\mathrm{x}}_{1})$ mod p.

Signature ${\mathrm{s}}_{1}$ is sent to all other cosigners. Upon receiving ${\mathrm{s}}_{2}$, …, ${\mathrm{s}}_{\mathrm{n}}$ from other cosigners, the signer can compute s $\equiv \sum _{i = 1}^{n}{s}_{i}$(mod p). The signature is the pair (R, s).

In order to verify the aggregated signature, the message (m), multi-set of public keys (L), (R), and (s) will be sent to the receiver.

The receiver follows these steps to verify the aggregated signature:

● ${\mathrm{a}}_{i}$ = ${\mathrm{H}}_{agg}$ (L, X_i) for i$\in${1, …, n};

● $\widetilde {\mathrm{X}}$ = $\prod _{i = 1}^{n}{\mathrm{X}}_{i}^{{a}_{i}};$

● c = ${\mathrm{H}}_{sig}$ ($\widetilde {\mathrm{X}}$, R, m);

● The signature is accepted if g^s = R $\prod _{i = 1}^{n}{\mathrm{X}}_{i}^{{ca}_{i}}$ = R${\widetilde {\mathrm{X}}}^{c}$.

Proof of the correctness of the algorithm:

g^s = R ${\widetilde {\mathrm{X}}}^{c}$, since R = $\prod _{i = 1}^{n}{R}_{i}$ = $\prod _{i = 1}^{n}{g}^{{r}_{i}}$, and since $\widetilde {\mathrm{X}}$ = $\prod _{i = 1}^{n}{X}_{i}^{{a}_{i}}$ = $\prod _{i = 1}^{n}{\left({g}^{{x}_{i}}\right)}^{{a}_{i}}$, then:

g^s = $\prod _{i = 1}^{n}{g}^{{r}_{i}}\prod _{i = 1}^{n}{{({g}^{{x}_{i}}}^{{a}_{i}})}^{c}$ = $\prod _{i = 1}^{n}{\mathrm{g}}^{{\mathrm{r}}_{i}+{x}_{i}{\mathrm{a}}_{i}c}$ = ${\mathrm{g}}^{{\mathrm{r}}_{1}+{x}_{1}{\mathrm{a}}_{1}c}$+ … + ${\mathrm{g}}^{{\mathrm{r}}_{\mathrm{n}}+{x}_{\mathrm{n}}{\mathrm{a}}_{\mathrm{n}}c}$ = ${g}^{\sum _{i = 1}^{n}{s}_{i}}$ = g^s, because s = $\sum _{i = 1}^{n}{s}_{i}$.

This method is immune to key cancellation attacks and rogue key attacks, but it is vulnerable to the nonce reuse attack. To understand how MuSig is susceptible to this attack, consider the scenario where Alice, among a group of cosigners, reuses the same nonce for signing different messages. In this case, Oscar can carry out the following steps to expose Alice's private key (x):

If Oscar listens to this conversation, he can perform the subtraction operation between these two signings (${\mathrm{s}}_{1}$) and ${(s}_{1}^{⃓})$, and the resulting outcome will reveal Alice's private key (${x}_{1}$) in the following manner:

${\mathrm{s}}_{1}$ - ${s}_{1}^{⃓}$ = ${r}_{1}$ + c${\mathrm{a}}_{1}{x}_{1}$ – (${r}_{1}$+ ${c}^{⃓}{\mathrm{a}}_{1}{x}_{1}$) = ${r}_{1}$ + c${\mathrm{a}}_{1}{x}_{1}$ – ${r}_{1}$ – ${c}^{⃓}{\mathrm{a}}_{1}{x}_{1}$,

${\mathrm{s}}_{1}$ - ${s}_{1}^{⃓}$ = c${\mathrm{a}}_{1}{x}_{1}$ – ${c}^{⃓}{\mathrm{a}}_{1}{x}_{1}$ = ${\mathrm{a}}_{1}{x}_{1}$ (c – ${c}^{⃓}$),

${x}_{1}$ = (${\mathrm{s}}_{1}$-${s}_{1}^{⃓}$) (${\mathrm{a}}_{1}$(c – ${c}^{⃓}$))^-1.

Since Oscar knows (${\mathrm{s}}_{1}$, ${s}_{1}^{⃓},$ R, ${\mathrm{m}}_{1}$ and ${\mathrm{m}}_{2}$) and can calculate c = H_sig ($\widetilde {\mathrm{X}}$, R, ${\mathrm{m}}_{1}$), ${c}^{⃓}$ = ${\mathrm{H}}_{\mathrm{s}\mathrm{i}\mathrm{g}}$($\widetilde {\mathrm{X}}$, R, ${\mathrm{m}}_{2}$) and ${\mathrm{a}}_{1}$ = ${\mathrm{H}}_{\mathrm{a}\mathrm{g}\mathrm{g}}$ (L, ${\mathrm{X}}_{1}$), he can then calculate Alice's private key (${x}_{1}$).

To gain a different perspective on the problem, we can examine it from an alternative angle. It is essential to consider the following scenario where Alice and Bob try to co-sign a message (${\mathrm{m}}_{1}$):

If Oscar listens to this conversation, then he can perform the subtraction operation between Alice's two signatures. The resulting outcome will reveal Alice's private key (${x}_{1}$) in the following manner:

${\mathrm{s}}_{1}$ - ${s}_{1}^{⃓}$ = ${\mathrm{r}}_{1}$+ c${\mathrm{a}}_{1}{x}_{1}$ - ${\mathrm{r}}_{1}$ - ${c}^{⃓}{\mathrm{a}}_{1}{x}_{1}$ = c${\mathrm{a}}_{1}{x}_{1}$ - ${c}^{⃓}{\mathrm{a}}_{1}{x}_{1}$ = x₁ a₁ (c-${c}^{⃓}$),

${x}_{1}$ = $\frac{{\mathrm{s}}_{1}-{s}_{1}^{⃓}}{{\mathrm{a}}_{1}(\mathrm{c}-{c}^{⃓})}$ = (${\mathrm{s}}_{1}$ - ${s}_{1}^{⃓}$)(${\mathrm{a}}_{1}$(c-${c}^{⃓}$))^-1.

This highlights the vulnerability of the MuSig protocol to nonce reuse attacks when the same nonce is utilized in multiple signature operations.

Based on the previous explanation, the novelty in the MuSig signature scheme involves the addition of the component ${a}_{i}$ to address the issue of key cancellation attacks in key aggregation for multi-signature schemes. Additionally, the MuSig signature scheme adopts a three-round signing process to counter rogue key attacks, which represent the main drawback of this method. As a result, alternative models for multi-signature schemes that require only two rounds, such as MuSig-DN and MuSig2, have been proposed.

As mentioned in the Introduction section ^[12], the complexity of the NIZK proof in the MuSig-DN protocol renders it impractical for use on dedicated signing devices like hardware wallets, which are typically employed for storing bitcoins.

Additionally, according to the Introduction section of this study ^[13], MuSig2 can use different numbers of nonces depending on the specific configuration:

● MuSig2 can use one nonce, but this configuration may have limitations in terms of security guarantees.

● MuSig2 can use two nonces to be secure under the Algebraic One-More Discrete Logarithm (AOMDL) assumption in the ROM when AGM is additionally assumed.

● MuSig2 can use four or more nonces to be proven secure under the (OMDL) assumption in the ROM (Random Oracle Model).

Thus, each signer in MuSig2 provides a list of at least two nonces, which are then combined to form the aggregate nonce for the signing operation.

In the ROM, each ${\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\mathrm{e}\mathrm{r}}_{i}$ utilizes four or more nonces (${\mathrm{R}}_{i}^{`}, {\mathrm{R}}_{i}^{``}, {\mathrm{R}}_{i}^{```}, {\mathrm{R}}_{i}^{````}, \dots, {\mathrm{R}}_{n}^{n})$, . Then, the ${\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\mathrm{e}\mathrm{r}}_{i}$ uses a random combination ${\mathrm{R}}_{i}$ = ${\mathrm{R}}_{i}^{`}{{(\mathrm{R}}_{i}^{``})}^{b}{{(\mathrm{R}}_{i}^{```})}^{{b}^{2}}$ ${{(\mathrm{R}}_{i}^{````})}^{{b}^{3}}$, where the exponent b is set by hashing essentially the entire protocol input and transcript after the nonce exchange round (the aggregated public key, the message, and the nonces of all signers):

In the AGM, each ${\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\mathrm{e}\mathrm{r}}_{i}$ utilizes two nonces (${\mathrm{R}}_{i}^{`}, {\mathrm{R}}_{i}^{``})$. Then, the ${\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\mathrm{e}\mathrm{r}}_{i}$ uses a random combination ${\mathrm{R}}_{i}$ = ${\mathrm{R}}_{i}^{`}{{(\mathrm{R}}_{i}^{``})}^{b}$, where b = H ($\widetilde {\mathrm{X}}$, m, (${\mathrm{R}}_{1}^{`}{\mathrm{R}}_{2}^{`}$, ${\mathrm{R}}_{1}^{``}{\mathrm{R}}_{2}^{``}$)).

When using two or four nonces in the MuSig2 scheme, as compared to using a single nonce, there is some additional computational complexity involved. This is because each signer, providing two or four nonces in MuSig2, faces an overhead in combining these nonces to form the aggregate nonce. This process involves additional computations to derive the scalar b via a hash function. Additionally, the signer's complexity increases slightly due to the need to handle multiple nonces and perform the necessary calculations for nonce aggregation.

3.   Proposed contributions

This section elucidates the proposed solution for addressing the nonce generation problem existing in Schnorr's Digital Signature and Schnorr's Multi Signature schemes, as explained in Sections 2.3 and 2.4. The proposed solution includes:

● Utilizing a similar private key generation approach as seen in the digital signature algorithm (EdDSA) to generate deterministic private nonces. This study suggests generating the private nonce by combining the message with the hashed value of the private key (x).

● Excluding the public nonce (R) from the calculation of the challenge c = ${\mathrm{H}}_{sig}$(X, R, m). To ensure the uniqueness of each signature, additional context and protocol-level safeguards akin to those utilized in the EdDSA framework (which falls beyond the purview of this study) should be implemented. This includes the integration of sequence numbers, timestamps, and other session-specific data into the messages. These components, which operate externally to the digital signature mechanism, are intended to mitigate certain attacks, notably replay attacks.

● In the proposed multi-signature scheme, the aggregated public key $\widetilde {\mathrm{X}}$ has been utilized instead of a NIZK proof to demonstrate that the owner of the public keys knows the corresponding secret keys. Therefore, if the aggregated public key $\widetilde {\mathrm{X}}$ matches any of the public keys of one or more cosigners, then the signing process is rejected.

The process for implementing these solutions is described in two sections:

First: Schnorr Digital Signature algorithm:

The signature generation and verification process in Schnorr is as follows:

To sign a message (m), Alice follows these steps:

● Select a Private Key (x) such that 0 < x < p;

● Calculate the Public Key (X), such that X = g^x;

● Calculate h = H(x);

● Calculate the private nonce r = H (h||m);

● Calculate the public nonce R = g^r;

● Calculate c = H (X, m);

● Calculate s$\equiv$ (r + cx) mod p;

● The signature is the pair (R, s). Thus, Alice will send the message (m), public key (X), (R), and (s) to Bob.

Bob considers Alice's signature valid only if gs = R${\mathrm{X}}^{c}$.

Proof of the correctness of the algorithm:

g^s = R${\mathrm{X}}^{c}$, since R = g^r and X = g^x, then g^s = g^r (g^x)^c = g^r+xc = g^s, where s = r + xc.

In the current scenario, Alice is unable to sign two different messages using the same nonce. This is because the private nonce changes when the message changes. However, if Alice signs the same message twice, it implies that she is using the same nonce. This raises a concern about the potential compromise of system security. For a more comprehensive understanding, let us examine the steps that Oscar might follow to implement a nonce reuse attack:

This shows that the two signatures, ${\mathrm{s}}_{1}$ and ${\mathrm{s}}_{2}$, are identical, and subtracting one from the other results in zero (${\mathrm{s}}_{1}$-${\mathrm{s}}_{2}$ = 0). Therefore, there is no benefit or information gained from duplicate signatures. This means that the security of the system is not compromised when the same message is signed twice with the same nonce. The proposed method effectively prevents nonce reuse attacks by deterministically calculating the private nonce, ensuring it changes with each new message. Even if the same message is signed multiple times, the process remains secure.

In addition, the proposed method for signing messages does not require storing any information during the signing process. The necessary calculations can be made from the inputs and received messages, eliminating the risk of manipulation through virtual machine rewinding attacks.

To prevent potential exploitation of collision probabilities, it is recommended to use appropriate cryptographic hashing functions.

Second: Proposed multi-signature scheme:

In order to differentiate multi-signature schemes, the classification is as follows:

● Multi-signature schemes, wherein n-of-n signers are required to collectively produce a valid signature.

● Threshold signature schemes wherein any subset of size t-of-n signers out of n total signers can collectively produce a valid signature.

It should be noted that this section exclusively addresses multi-signature schemes.

The proposed multi-signature generation and verification scheme is as follows:

- Round 1:

A group of n signers want to co-sign a message m. Let ${\mathrm{X}}_{1}$ and ${x}_{1}$ be the public and private key of a specific signer, where ${\mathrm{X}}_{1}$ = ${\mathrm{g}}^{{x}_{1}}$. Let ${\mathrm{X}}_{2}$, …, ${\mathrm{X}}_{\mathrm{n}}$ be the public keys of the other co-signers, and let (L) be the hash value of the multi-set of all public keys involved in the signing process, L = H_agg (${\mathrm{X}}_{1}\left|\right|\dots \left|\right|{\mathrm{X}}_{n}$):

● For i$\in${1, …, n}, each signer computes the following: ${\mathrm{a}}_{i}$ = H_agg (L, ${\mathrm{X}}_{i}$), as well as the aggregated public key: $\widetilde {\mathrm{X}}$ = $\prod _{i = 1}^{n}{X}_{i}^{{a}_{i}}$. The signer must check if ($\widetilde {\mathrm{X}}$ = ${\mathrm{X}}_{i}^{{a}_{i}}$); if so, then the signing operation is terminated.

● The signer calculates h = ${\mathrm{H}}_{agg}$(${x}_{1}$), computes the private nonce ${\mathrm{r}}_{1}$ = ${\mathrm{H}}_{agg}$(h||m), computes the public nonce ${\mathrm{R}}_{1}$ = ${\mathrm{g}}^{{\mathrm{r}}_{1}}$, and sends ${\mathrm{R}}_{1}$ to all other co-signers and receives ${\mathrm{R}}_{2}$, …, ${\mathrm{R}}_{\mathrm{n}}$ from other co-signers.

- Round 2:

● Calculate c = ${\mathrm{H}}_{sig}$ ($\widetilde {\mathrm{X}}$, m) and ${\mathrm{s}}_{1}\equiv$ ${\mathrm{r}}_{1}$+$\mathrm{c}{\mathrm{a}}_{1}{x}_{1}$ (mod p);

● Signature ${\mathrm{s}}_{1}$ is sent to all other co-signers. Upon receiving ${\mathrm{s}}_{2}$, …, ${\mathrm{s}}_{n}$ from other co-signers, they then calculate R = $\prod _{i = 1}^{n}{R}_{i}$ and s $\equiv$ $\sum _{i = 1}^{n}{s}_{i}$(mod p). The signature will be the pair (R, s). The message (m) and signature pair (R, s) will be sent to the receiver.

The receiver follows these steps to verify the aggregated signature:

● ${\mathrm{a}}_{i}$ = ${\mathrm{H}}_{agg}$(L, ${\mathrm{X}}_{i}$) for i$\in${1, …, n};

● $\widetilde {\mathrm{X}}$ = $\prod _{i = 1}^{n}{X}_{i}^{{a}_{i}};$

● c = ${\mathrm{H}}_{sig}$ ($\widetilde {\mathrm{X}}$, m)$;$

● The signature is accepted if g^s = R ${\widetilde {\mathrm{X}}}^{c}$.

Proof of the correctness of the algorithm:

g^s = R${\widetilde {\mathrm{X}}}^{c}$, since R = $\prod _{i = 1}^{n}{R}_{i}$ = $\prod _{i = 1}^{n}{g}^{{r}_{i}}$, and since $\widetilde {\mathrm{X}}$ = $\prod _{i = 1}^{n}{X}_{i}^{{a}_{i}}$ = $\prod _{i = 1}^{n}{{(g}^{{x}_{i}})}^{{a}_{i}}$, then:

g^s = $\prod _{i = 1}^{n}{g}^{{r}_{i}}$ ${\left(\prod _{i = 1}^{n}{g}^{{x}_{i}{a}_{i}}\right)}^{c}$ = $\prod _{i = 1}^{n}{\mathrm{g}}^{{\mathrm{r}}_{i}+{x}_{i}{a}_{i}c}$ = ${\mathrm{g}}^{{\mathrm{r}}_{1}+{x}_{1}1c}$ + … + ${\mathrm{g}}^{{\mathrm{r}}_{\mathrm{n}}+{x}_{\mathrm{n}}{a}_{\mathrm{n}}c}$,

g^s = ${g}^{\sum _{i = 1}^{n}{s}_{i}}$ = g^s, because s = $\sum _{i = 1}^{n}{s}_{i}$.

To enhance comprehension of the operational mechanism of the proposed method and its resilience against the rogue key attack, a simple example is employed to elucidate it:

Suppose that Alice and Bob want to co-sign a message (m) and then send this multi-signature to Robert (the receiver). The steps for the proposed multi-signature scheme are as follows:

- Round 1:

Let ${\mathrm{X}}_{\mathrm{a}}$ and ${x}_{\mathrm{a}}$ be the public and private keys of Alice, where ${\mathrm{X}}_{\mathrm{a}}$ = ${\mathrm{g}}^{{x}_{a}}$, and let ${\mathrm{X}}_{\mathrm{b}}$ and ${x}_{\mathrm{b}}$ be the public and private keys of Bob, where ${\mathrm{X}}_{\mathrm{b}}$ = ${\mathrm{g}}^{{x}_{b}}$, then L = H_agg (${\mathrm{X}}_{\mathrm{a}}$||${\mathrm{X}}_{\mathrm{b}}$):

● Alice computes ${\mathrm{a}}_{a}$ = H_agg (L, ${\mathrm{X}}_{a}$), and because she already knows Bob's public key ${\mathrm{X}}_{\mathrm{b}}$ (which is publicly available), she can calculate ${\mathrm{a}}_{b}$ = H(L||${\mathrm{X}}_{\mathrm{b}}$). After this, Alice calculates the aggregated public key $\widetilde {\mathrm{X}}$ = ${\mathrm{X}}_{a}^{{a}_{a}}\cdot {\mathrm{X}}_{b}^{{a}_{b}}$.

If Alice finds that $\widetilde {\mathrm{X}}$ = ${\mathrm{X}}_{b}^{{a}_{b}}$, then the protocol is terminated because the public key that Bob uses is fake, equating to ${\mathrm{X}}_{\mathrm{b}}$ = ${\left({\mathrm{g}}^{{x}_{b}}\right)}^{{a}_{b}}\cdot {{(\mathrm{X}}_{a}^{{a}_{a}})}^{-1}$. This manipulation suggests Bob's attempt to execute a rogue key attack, exploiting his knowledge of Alice's public key to undermine the integrity of the aggregated public key, calculated as $\widetilde {\mathrm{X}}$ = ${\mathrm{X}}_{a}^{{a}_{a}}\cdot {\mathrm{X}}_{b}^{{a}_{b}}$ = ${\mathrm{X}}_{a}^{{a}_{a}}\cdot {\mathrm{g}}^{{x}_{b}}\cdot {{(\mathrm{X}}_{a}^{{a}_{a}})}^{-1}$ = ${\mathrm{g}}^{{x}_{b}} = {\mathrm{X}}_{b}^{{a}_{b}}$. By halting the signing process at this juncture, the protocol effectively prevents Bob from forging the signature by nullifying Alice's public key contribution, thus safeguarding against potential signature forgery by Bob.

Similarly, Bob computes ${\mathrm{a}}_{b}$ = H_agg (L, ${\mathrm{X}}_{b}$), and because he already knows Alice's public key ${\mathrm{X}}_{\mathrm{a}}$(which is publicly available), he can calculate ${\mathrm{a}}_{a}$ = H(L||${\mathrm{X}}_{\mathrm{a}}$). After this, Bob calculates the aggregated public key $\widetilde {\mathrm{X}}$ = ${\mathrm{X}}_{a}^{{a}_{a}}\cdot {\mathrm{X}}_{b}^{{a}_{b}}$.

If Bob finds that $\widetilde {\mathrm{X}}$ = ${\mathrm{X}}_{b}^{{a}_{b}}$, then the protocol is terminated, indicating that Alice might be attempting a rogue key attack.

● If neither Alice nor Bob are performing a rogue key attack, then the multi-signature steps will proceed. Alice calculates h = ${\mathrm{H}}_{agg}$(${x}_{\mathrm{a}}$), private nonce ${\mathrm{r}}_{a}$ = ${\mathrm{H}}_{agg}$(h||$\mathrm{m}$), Public nonce ${\mathrm{R}}_{\mathrm{a}}$ = ${\mathrm{g}}^{{\mathrm{r}}_{a}}$, and sends ${\mathrm{R}}_{\mathrm{a}}$ to Bob and receives ${\mathrm{R}}_{\mathrm{b}}$ from him, who calculated ${\mathrm{R}}_{\mathrm{b}}$in the same way as Alice did.

- Round 2:

● Alice calculates R = $\prod _{i = 1}^{n}{R}_{i}$, c = ${\mathrm{H}}_{sig}$($\widetilde {\mathrm{X}}$, m) and ${\mathrm{s}}_{a}\equiv$ (${\mathrm{r}}_{a}$+$c{\mathrm{a}}_{a}{x}_{a}$) mod p.

● Alice sends the signature ${\mathrm{s}}_{a}$ to Bob and receiving ${\mathrm{s}}_{b}$ from him, who calculates ${\mathrm{s}}_{\mathrm{b}}$ in the same manner as Alice did.

● The aggregated signature will be s = ${\mathrm{s}}_{a}$ +${\mathrm{s}}_{b}$ (mod p). Then, the multi-signature will be the pair (R, s). Subsequently, the message (m) and the signature pair (R, s), will be sent to Robert.

Robert will consider the multi-signature to be valid only if g^s = R ${\widetilde {\mathrm{X}}}^{c}$

When evaluating the efficacy of the proposed method against nonce reuse attacks, it should be noted that Alice is unable to sign two different messages using the same nonce. This is because the private nonce changes when the message does. However, if Alice signs the same message twice, it indicates she is using the same nonce. This raises concern about whether this compromises the security of the system.

Let us assess whether the security of the system would be compromised in instances where Alice co-signs a message (m) twice with Bob while utilizing the same nonce:

Since the two signatures (${s}_{\mathrm{a}}^{⃓}$ and ${\mathrm{s}}_{a}$) are identical, this means that when Oscar subtracts one signature (${\mathrm{s}}_{a}$) from the other (${s}_{\mathrm{a}}^{⃓}$), the result is zero (${\mathrm{s}}_{a}$-${s}_{\mathrm{a}}^{⃓}$ = 0). Consequently, this indicates that the system's security remains uncompromised when signing the same message with the same nonce multiple times, as the duplicate signatures yield no new information.

Now, the effectiveness of the proposed method in addressing the issue explained in the second scenario in Section 2.4 will be assessed as follows:

In the suggested approach, Bob cannot choose different nonces for the same message. Even if Bob attempts to do so intentionally, Alice will still sign the same message with the same unique nonce, resulting in identical signatures. Specifically, the signatures (${s}_{\mathrm{a}}^{⃓}$ and ${\mathrm{s}}_{a}$) are identical because we excluded the public nonce from the challenge calculations. Consequently, subtracting one signature from the other results in zero (${\mathrm{s}}_{a}$-${s}_{\mathrm{a}}^{⃓}$ = 0). This means that Oscar gains no benefit or information from these duplicate signatures.

Thus, the proposed method effectively thwarts nonce reuse attacks by deterministically calculating and changing the private nonce for each new message. Additionally, the method does not require storing any information during the signing process, as all necessary calculations can be derived from the inputs and received messages. This eliminates the risk of manipulation through virtual machine rewinding attacks. To mitigate the potential exploitation of collision probabilities, employing suitable cryptographic hashing functions is recommended.

4.   Conclusions

The method proposed to enhance the Schnorr digital signature and two-round MuSig shows promise in achieving several important objectives. First, it improves the Schnorr digital signature by combining the private key and the message through hashing, then it hashes the result again to generate a private nonce, inspired by the method used in EdDSA.

The proposed method excludes the public nonce (R) from the challenge calculations (c = ${\mathrm{H}}_{sig}$(X, R, m)), ensuring the uniqueness of each signature. Moreover, removing (R) from these calculations reduces the computational complexity, a crucial factor in constrained resources devices where every computational step matters. A significant advantage of this method is that it ensures the private nonce will be different for each new message. Even if the same message is signed multiple times with the same nonce, it will not make the system insecure, thus effectively solving the issue of random number generation failures.

In multi-signature schemes, the proposed method compares to the MuSig signature scheme. While MuSig is resistant to key cancellation and rogue key attacks, it involves three rounds and is susceptible to nonce reuse attacks. In contrast, the proposed method is a two-round scheme that is immune to key cancellation, rogue key, and nonce reuse attacks, offering enhanced security with lower computational complexity.

When compared to MuSig-DN, it is clear that MuSig-DN introduces inherent complexity due to the necessity of deploying NIZK proofs to validate the deterministic generation of nonces. This requirement not only increases computational overhead but also adds complexity to the implementation, making the protocol less practical for devices with constrained resources. In contrast, the proposed method utilizes the aggregated public key $\widetilde {\mathrm{X}}$ to demonstrate ownership of the corresponding secret keys. This approach eliminates the need to compute and send NIZK proofs along with signatures, leading to reduced computational complexity and bandwidth usage. Thus, the proposed method is more efficient in terms of computational complexity and bandwidth utilization, especially for devices with constrained resources.

Comparing the proposed method to MuSig2, the key difference lies in how they handle nonces. MuSig2 allows for the use of multiple nonces based on a configured set where each signer needs to provide at least two nonces. These nonces are then combined to create an aggregated nonce for the signing process. Thus, generating and using multiple nonces in MuSig2 adds computational complexity, particularly in deriving the scalar "b" using a hash function. Also, sending multiple nonces in MuSig2 leads to higher bandwidth usage. In contrast, the proposed method employs only a single nonce. This streamlined approach eliminates additional computational tasks and minimizes bandwidth requirements, making the process more efficient and straightforward compared to MuSig2.

Although this study does not definitively assert superiority over the established and proven MuSig-DN and MuSig2 methods, it represents a valuable contribution to ongoing efforts to improve digital signature technology. In the proposed method, the public nonce (R) serves the receiver's verification process to ensure the signature's validity. Additionally, the proposed method removes the need to store any information between signing rounds, meaning signers don't have to remember details such as the nonce or partial signature. They can generate these values again using public inputs and messages. This benefit reduces storage and computational requirements for signers and enhances resistance against virtual machine rewinding attacks. As a result, this approach prevents cheating in the public keys, reduces computational complexity, and minimizes the amount of information sent combined with NIZK proof, leading to better utilization of bandwidth.

Author contributions

Nawras H. Sabbry: Conceptualization, methodology, formal analysis, investigation, writing (original draft preparation and visualization); Alla Levina: Supervision, writing (review and editing), project administration, funding acquisition. All authors have read and agreed to the published version of the manuscript.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This research was funded by the Ministry of Science and Higher Education of the Russian Science Foundation (Project "Goszaadanie" No.075-00003-24-02, FSEE-2024-0003).

Conflict of interest

The authors declare that there are no conflicts of interest regarding the publication of this article.