# Two-Party Schnorr ## Schnorr Signature Scheme Notation: - $[n] = \{0,...,n-1\}$ - Public Parameters: - A group $\mathcal{G}$ of prime size $n$ with generator $G$. - A hash function $H:\{0,1\}^*\rightarrow [n]$ - $a\stackrel{?}{\leftarrow}S$ is used to denote $a$ is randomly-in-uniform picked from a set $S$. - Lowercase latin letters are elements in $[n]$. - Uppercase letters are elements in $\mathcal{G}$ - $\text{KeyGen}()$: - Let $x\stackrel{?}{\leftarrow}[n]$ - $Y \leftarrow x\cdot G$. - Private key: $x$. - Public key: $Y$. ---- - $\text{Sign}(m,x)$: - $r \stackrel{?}{\leftarrow}[n]$ - $R \leftarrow r\cdot G$ - $e \leftarrow H(m || R)$ - $s \leftarrow r + x\cdot e$ - The signature is the tuple: $(R,s)$. ---- - $\text{Verify}(R,s,m,Y)$: - $e \leftarrow H(m||R)$ - Check: $s\cdot G \stackrel{?}{=} R+e\cdot Y$ ---- ## The Two-Party Case Given a set of $n$ signers (not necessarily two), those collaborating signers generate some joint signature which can be verified against a **joint public key**. Thus, given the set of public keys of those signers $y_1,...,y_n$ they agree on a joint public key, representing the public-key, $y$, corresponding to their join signature. We denote the function which takes the individual public keys and generates a joint public key by $f:G^n \rightarrow G$. A naive approach which would yield a very efficient scheme is choosing $y=f(y_1,...,y_n)=\sum y_i$. Therefore, by summing the public keys, the join signature $(R,s)$ will simply be the sum of all signatures by all private keys of all co-signers $R=\sum R_i$ and $s=\sum s_i$. While this works very gently, there is a major issue with this approach known as **rogue key attack**. The problem is that parties may cosign with some malicious parties who have specially crafted their keys so they will cancel out the key of their victim party. So if the victim has a public key $y_v$ and the malicious party has a private key $x_a$ and public key $y_a$, the malicious party can reports its public key to be $y_a - y_v$. Therefore, their joint public key will be $y_a -y_v + y_v = y_a$ and using $x_a$ the malicious party could sign in the name of both parties. One simple solution to this problem is that each party publishes with its public key a proof-of-knowledge-of-discrete-logarithm for its public key. While this sounds good, it just doesn't meet the standard of the present, where public keys do not have such proof attached to them. At this point we have two options: 1. Tackle the problem of rogue-public-key by preventing it and leaving $f(y_1,...,y_n)=\sum y_i$. 2. Choosing another pubkey-joining function $f$. ### Public Verifiability of Joint Addresses Let's add a little bit more complexity at this point. The pubkey deriviation function $f$ can actually depend on both public values (e.g. public keys) and private values (e.g. private keys). Let's distinguish between those cases. Let's say we have a set of parties $P_1,...,P_n$ (we don't restrict the discussion to the 2-party cases at the moment). Those parties have public keys $y_1,...,y_n$. If the address only depends on the public keys then any other party can send this group of $n$ parties some funds / message without any of those parties ever being aware of the other parties. This is possible because anyone who has access to the public keys of each party can derive on its own their joint address $f(y_1,...,y_n)$. However, if $f$ depends on some non-public data (e.g. private keys), then at least of the on the $n$ parties has to manually derive the address and publish it. Not only that, but the published address can't be trusted without trusting the publisher because no-one besides the publisher (and the rest of the parties) can compute $f$. In the case of $f=\sum y_i$ anyone can verify that a given address was derived properly because it only relies on public data. ### Unforgeability of Joint Addresses Given $n$ parties, the rouge-key-attack is possible because given a value $k$, one of the parties $P_i$ could have computed some public key $y_i$ such that $f(y_1,...,y_n)=k$. Thus, with either the function $f$ being publicly verifiable or not, we want it to be *non-forgeable*. So an attack controlling $t$ parties' public keys $y_1,...,y_k$ will not be able to determine the resulting joint address $f(y_1,..,y_n)=k$. Since $y_1,...,y_n$ are group-elements, they have only one operation to aggregate them, which is the group operation $(+)$. So, to make $f$ unforgeable we have to employ other functions that take group elements, those could be: 1. Negation of some of the public keys. 2. Hash function can be applied to group elements. ### Linearity of Joint Addresses A joint public key derivation function $f$ is said to be linear each party $P_i$ generates locally some signature of the message $(R_i,s_i)$ such that the join signature of all participants is $(\sum R_i, \sum s_i)$. ### Personal Pubkey Derivation Given some party $P$ with public key $Y$, private key $x$ and some function $h:\mathcal{G}\rightarrow [n]\backslash\{0\}$, we can also pay to address $h(Y)\cdot Y$ and only $P$ would be able to spend those coins. A major benefit we get by doing so is the ability to prevent $P$ from forcing a specific public key $k$ to which we shall pay. In other words, $P$ can't come up with some value $K\in G$ such that we will end up sending our coins to $K$ because by doing so it has to set $Y$ such that $Y\cdot h(Y)=K$ which is considered computationally hard. Notice that $P$ can still easily derive the private key that corresponds to $h(Y)\cdot Y$. This is simply $h(Y)\cdot x$. Also notice that known the new private key implies knowing the original private key. Assuming $h$ is random oracle then $y\cdot h(y)$ uniformly distributed in $G$. ### MuSig Original Scheme In MuSig we have a set of $n$ parties $P_1,...,P_n$ with public keys $Y_1,...,Y_n$ and private keys $x_1,...,x_n$. Denote $L=\{Y_1,...,Y_n\}$ To jointly sign a message $m$ each party $P_i$ will derive a new public key from its existing public key: $Y'_i = H_{derive}(L || Y_i)\cdot Y_i$. Therefore the joint public key is $\widetilde{Y}=\sum Y'_i$. Along the signing procedure party $P_i$ samples a random nonce $R_i$ and broadcasts it. The joint nonce is $R=\sum R_i$. Each party $P_i$ will sign the message where the challenge is $H_{sig}(\widetilde{Y}||R||m)$ with the key corresponding to $Y'_i$. To be explicit this is what happens in signing a message $m$: 1. Each party samples a random $r_i \stackrel{?}{\leftarrow}[n]$ 2. $R_i \leftarrow r_i \cdot G$. 3. Broadcast $R_i$. 4. $R \leftarrow \sum R_j$ where $R_j$ is the nonce of party $P_j$. 5. $\widetilde{Y}=\sum H_{derive}(L||Y_i)\cdot Y_i$ 6. $e_i \leftarrow H_{sig}(\widetilde{Y} || R|| m)$ 7. $x'_i \leftarrow x_i \cdot H_{derive}(L ||Y_i)$ 8. $s_i \leftarrow r_i + e_i\cdot x_i$ 9. Broadcast $s_i$. The joint signature is $(\sum R_i, \sum s_i)$ This has two communication rounds, which sounds good in theory but the signing method is vulnerable to an attack presented in [[DEF+19]](https://eprint.iacr.org/2018/417.pdf). ### Wagner's Algorithm and DEF+19 Attack The attack that was presented relates to the MuSig algorithm ,which will from now on be referred to as the InsecureMuSig algorithm. Informally and in very high-level using the attack, the attacker can forge a valid signature of the victim on a chosen plain-text message $m^*$. The attack exploits the ability to perform parallel signing events with the victim such that ==the sum of the challenges in the signing instances is equal the a target valid challenge of some other message $m^*$==. Next by summing the challenges and the signatures from all the parallel instances, we get a valid signature of $m^*$. Finding such nonces to send in each parallel instance such that the sum of the resulting challenges will result in the target hash is done using **Wagner's Algorithm**, solving the generalized birthday-paradox problem in [[Wag02]](https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf). Let's try and give some more precise information about the attack. For simplicity the attack is taking place in a two-party setting. So there are two parties $P_1, P_2$ such that $P_2$ will be the attacker and $P_1$ will be the victim. The attacker has some message $m^*$ which he wants to get signed by him and by the victim together. The attacker has a public key $Y_2$ and private key $x_2$. The victim has a public key $Y_1$ and private key $x_1$. Their joint public key is $\widetilde{Y}=\sum a_i \cdot Y_i$, such that $a_i = H_{derive}(L || Y_i)$. The attacker initiates $k$ sessions with the victim. In session $i$ they will sign some message $m^{(i)}$. First, the victim ($P_1$) sends in each session a nonce, so in session $i$ it sends the nonce $R_1^{(i)}=r_1^{(i)}\cdot G$. Next, the attacker denotes the sum of all those nonces $R^*=\sum_{i=1}^kR_1^{(i)}$. Now, the attacker finds (using Wagner's Algorithm) a set of $k$ nonces $R_2^{(i)}$ for $i=1,...,k$ such that: $$\sum_{i=1}^k\overbrace{H(\widetilde{Y} || (R_1^{(i)} + R_2^{(i)}) || m^{(i)} ) }^{c^{(i)}}= \overbrace{H(\widetilde{Y} || R^* || m^*)}^{c^*}$$ Thus, by responding for each challenge $R_1^{(i)}$ with $R_2^{(i)}$ the attacker forces the fiat-shamir-challenge of session $i$ to be $c^{(i)}$ such that $\sum_{i=1}^k c^{(i)} = c^*$. At this point the victim computes for each session $i$ the value $s^{(i)}=r_1^{(i)} + c^{(i)}\cdot a_1 \cdot x_1$. First, denote $r^* = \sum_{i=1}^{k}r_1^{(i)}$. So, we get that: $R^* = r^* \cdot G$. Next, we get: $$\begin{align} \sum_{i=1}^ks_i &= \overbrace{\sum_{i=1}^k r_1^{(i)}}^{=r^*} + a_1\cdot x_1 \cdot \overbrace{\sum_{i=1}^k c^{(i)}}^{=c^*}\\ \sum_{i=1}^ks_i &= r^* + a_1\cdot x_1 \cdot c^*\\ \end{align}$$ By adding the term $c^* \cdot a_2 \cdot x_2$ to both sides we get: $$ \sum_{i=1}^ks_i + c^* a_2 x_2= r^* + (a_1\cdot x_1 + a_2 \cdot x_2) \cdot c^* $$ Define $s^* = \sum_{i=1}^k s_i + c^*\cdot a_2\cdot x_2$ (this is the LHS of previous equation) and we get: $$ s^*= r^* + (a_1\cdot x_1 + a_2 \cdot x_2) \cdot c^* $$ Notice that $(R^*,s^*)$ is computable by the attacker and is a valid signature of both parties on message $m^*$ because: $$\begin{align} s^* \cdot G &= \overbrace{r^* \cdot G}^{=R^*} + c^* (a_1 \cdot \overbrace{x_1 \cdot G}^{=Y_1} + a_2 \overbrace{\cdot x_2 \cdot G}^{=Y_2}) \\ s^* \cdot G &= R^* + c^* \cdot \overbrace{\sum a_i Y_i}^{=\widetilde{Y}} \\ s^* \cdot G &= R^* + \overbrace{c^*}^{=H(\widetilde{Y}||R^* || m^*)} \cdot \widetilde{Y} \\ s^* \cdot G &= R^* + H(\widetilde{Y}||R^* || m^*) \cdot \widetilde{Y} \\ \end{align}$$ Which is **exactly** the verification done on Schnorr's Signature Scheme. ### Playing Reminder: $a_i$ is used to prevent rogue key. $$\begin{align} s_i \leftarrow r_i + c_i a_i x_i \\ \end{align}$$ If instead we multiply /add $r_i$ by/to some factor $\alpha_i$ then: $$\begin{align} s_i \leftarrow \alpha_i \cdot r_i + c_i a_i x_i \\ s_i \leftarrow \alpha_i + r_i + c_i a_i x_i \\ \end{align}$$ In both cases it is possible to break. Let's try something else. $$\begin{align} s_i \leftarrow r_i + (c_i+1)\cdot a_i x_i \\ \end{align}$$ ### A n-on-n Scheme Given a set of $n$ parties with public keys $y_1,...,y_n$ their joint public key address will be derived using: $$ f(Y_1,...,Y_n) = \sum h(Y_i)\cdot Y_i $$ - $\text{LocalSign}(m,x_i,i, [Y_1,...,Y_n])$: - $J \leftarrow f(Y_1,...,Y_n)$ - $x'_i \leftarrow H(Y_i)\cdot x_i$ - $Y'_i \leftarrow H(Y_i)\cdot Y_i$ - $r_i \stackrel{?}{\leftarrow} [n]$ - $R_i \leftarrow r_i \cdot G$ - $r'_i \leftarrow H(R_i)\cdot r_i$ - $R'_i \leftarrow H(R_i)\cdot R_i$ - $s_i \leftarrow r'_i + H(J || m || R'_i)\cdot x'_i$ - Return: $((R'_i, s_i),r_i)$ - $\text{LocalVerify}(m, Y_i,R_i,s_i, [Y_1,...,Y_n])$: - $J \leftarrow f(Y_1,...,Y_n)$ - $R'_i \leftarrow H(R_i) \cdot R_i$ - $Y'_i \leftarrow H(Y_i) \cdot Y_i$ - Check: $s_i\cdot G \stackrel{?}{=}R'_i+H(J||m||R'_i)\cdot Y'_i$ - $\text{MultiPartySign}(m,x_i,i)$: - $((R'_i, s_i),r_i) \leftarrow \text{LocalSign}(m,x_i,i)$ - $\text{Broadcast}: (r_i\cdot G,s_i)$ - $\text{Receive}: (R_j,s_j)$ from each party $j$. - For each $j\in [n]- \{i\}$ - $\text{LocalVerify}(m, Y_j, R_j, s_j)$ - Set: $R'_j = H(R_j)\cdot R_j$ - Joint signature is: $(\sum R'_j, \sum s_j)$