I am trying to analyse a "uniqueness" game around Schnorr signatures. The game is described in $\textbf{B.}$ and I try to provide in $\textbf{1.}$ and $\textbf{2.}$ some incomplete answers to resolve it. Is it possible to fully solve it? I have not used in my analysis a reduction to the DL problem; maybe is there a way to reduce the game to it? Apologies for the lack of cryptographic rigour and thanks a lot for reading
$ \textbf{A. Cryptographic hypothesis:}$
We will use a secure cryptographic hash function $H$ outputing in $\mathbb Z_n$, where $n$ is the curve's order, assumed prime. We assume the prime order is a prime number of $256$ digits when written in base $2$.
$\textbf{B. Cryptographic game:}$
Assuming an elliptic-curve point $S$ has been computed after having chosen a tuple $\{R,X,m\}$, where $S := R + H(X,R,m).X$ as in Schnorr signature, can we practically find a tuple $\{R',X',m'\}$ such as $\{R',X',m'\} \neq \{R,X,m\}$ (at least one of the elements differ in the two sets) verifying $R' + H(X',R',m').X' = S = R + H(X,R,m).X$ ?
We make the additional assumption that the tuple $\{X,R,m\}$ can be chosen by the adversary before the game, i.e. the tuple $\{X,R,m\}$ is not provided to him by the verifier.
$\textbf{1. Assuming knowledge of the discrete logarithm to $S$:} $
If the above game also requires to provide proof of knowledge of the discrete logarithm to S to the verifier (i.e, knowledge of $s$ such that $s.G = S$, or, in other words, having started with one valid Schnorr signature), it seems like the answer is negative.
Temporarily supposing that $\{X,R, m\}$ and the corresping $s$ are directly provided by the verifier to the adversary, using natural notations, the adversary needs to find $r', x'$ and $m'$ such that $r' + H(X',R',m').x' = s$. It seems the only way to do this, given that adding two random integer modulo $n$ together (here $r'$, chosen randomly, and $H(X',R',m').x'$, a random integer modulo $n$ due to the hash function being a cryptographicly secure by assumption) results in a random integer modulo $n$, as the result of the sum of 2 uniformly distributed random integers modulo $n$ is a uniformaly distributed random integer modulo $n$. We can ignore the message $m$ for this game, and brute forcing on inputs $r'$, $x'$ (or equivalently just brute forcing on $r'$) seems to be the only solution to win the game, which makes it enjoying a $256$-bit security and hence to be untractable. I wonder if the reasoning is correct or if this is incorrect?
Going back to the original hypothesis of $\textbf{B.}$, it seems that this is in fact possible to upper bound the game to $128$-bit security (also an untractable difficulty, but it is only an upper bound here) instead of $256$ when $\{X, R, m\}$ can be chosen by the adversary (and not provided to him). Fixing $x'=x$ and $r$ and $r'$, the adversary can solve the Birthday problem and find some $m$ and $m'$ (by applying the Birthday algorithm) verifying the below relation, which is a solution to the game:
$H(X,R,m) - H(X,R',m') = (r' - r).x^{-1}$.
$\textbf{2. Not assuming knowledge of the discrete logarithm to $S$:} $
I am not sure that the above arguments in $\textbf{1.}$ were approximatively correct, but this situation seems a little bit more difficult to study.
$\textit{2. a) Assuming knowledge of the discrete logarithm to the nonces:}$
To win this game, one must also provide proofs of knowledge of the discrete logarithms to both $R$ and $R'$ (one such proof of knowledge suffices if $R' = R$). To try to solve the question we suppose that someone won the game, which implies, by subtracting the two relations that a winner of the game must know $u$ such that:
$$u.G = H(X, R, m).X - H(X',R', m').X'.$$
Suppose that the game is won with $X = X'$, then, it means that the discrete logairthm of $X$ must be known since it must be true that $u.G = (H(X, R, m) - H(X,R', m')).X$, and we are hence in the case of $\textbf{1.}$.
If $R = R'$ ($X'$ can be equal, or not, to $X$), then we fall back in the particular case where $u=0$, and we have that $X' = H(X, R, m).H(X',R, m')^{-1}.X$, i.e. the discrete logarithm $a$ of $X'$ with respect to $X$ must verify $a = H(X, R, m).H(X',R, m')^{-1}$. Fixing $X$ and $X'$ such that $X' = a.X$ for some $a$, the best algorithm to solve this seems again the Birthday algorithm with inputing around $2^{128}$ different messages in the challenges in order to eventually find some $m$ and $m'$ that verify $a.H(X',R, m') - H(X, R, m) = 0$.
If both $X \neq X'$, and $R \neq R'$, I do not manage to find any potential conclusion. Does anyone would know an answer or a reference for this case?
$\textit{2. b) Assuming knowledge of the discrete logarithm to the public keys:}$
We seem to fall back to the case $R = R'$ of $\textit{2. a)}$ if $R = R'$, but I do not manage to conclude if $R \neq R'$.
$\textit{2. c) Assuming knowledge of neither the discrete logarithm to the nonces and the keys:}$
We again can conclude if $R = R'$ by using the same argument as the case in $\textit{2. a)}$ for the case $R = R'$, but it again looks like to be more difficult to conclude otherwise (i.e. if $R \neq R'$).
