Încerc să analizez un joc de „unicitate” în jurul semnăturilor Schnorr. Jocul este descris în $\textbf{B.}$ și încerc să prevăd $\textbf{1.}$ și $\textbf{2.}$ câteva răspunsuri incomplete pentru a o rezolva. Este posibil să o rezolvi pe deplin? Nu am folosit în analiza mea o reducere la problema DL; poate există vreo modalitate de a reduce jocul la el? Scuze pentru lipsa de rigoare criptografică și mulțumesc mult pentru lectură
$ \textbf{A. Ipoteza criptografică:}$
Vom folosi o funcție hash criptografică sigură $H$ ieșire în $\mathbb Z_n$, Unde $n$ este ordinea curbei, presupus prim. Presupunem că ordinul prim este un număr prim al $256$ cifre atunci când sunt scrise în bază $2$.
$\textbf{B. Joc criptografic:}$
Presupunând un punct de curbă eliptică $S$ a fost calculat după ce s-a ales un tuplu $\{R,X,m\}$, Unde $S := R + H(X,R,m).X$ ca și în semnătura Schnorr, putem găsi practic un tuplu $\{R',X',m'\}$ precum $\{R',X',m'\} \neq \{R,X,m\}$ (cel puțin unul dintre elemente diferă în cele două seturi) verificare $R' + H(X',R',m').X' = S = R + H(X,R,m).X$ ?
Facem presupunerea suplimentară că tuplu $\{X,R,m\}$ poate fi ales de adversar înainte de joc, adică tuplu $\{X,R,m\}$ nu îi este furnizată de către verificator.
$\textbf{1. Presupunând cunoașterea logaritmului discret la $S$:} $
Dacă jocul de mai sus necesită, de asemenea, să se furnizeze verificatorului dovada cunoașterii logaritmului discret la S (adică, cunoașterea $s$ astfel încât $s.G = S$, sau, cu alte cuvinte, după ce a început cu o semnătură Schnorr validă), se pare că răspunsul este negativ.
Presupunând temporar că $\{X,R, m\}$ si corespunzatoare $s$ sunt furnizate direct de către verificator adversarului, folosind notații naturale, adversarul trebuie să găsească $r', x'$ și $m'$ astfel încât $r' + H(X',R',m').x' = s$. Se pare că singurul mod de a face acest lucru, având în vedere că adăugarea a două numere întregi aleatorii modulo $n$ împreună (aici $r'$, ales aleatoriu și $H(X',R',m').x'$, un modulo întreg aleatoriu $n$ datorită faptului că funcția hash este sigură criptografic prin presupunere) are ca rezultat un modulo întreg aleatoriu $n$, ca rezultat al sumei a 2 numere întregi aleatoare distribuite uniform modulo $n$ este un modulo întreg aleatoriu distribuit uniform $n$. Putem ignora mesajul $m$ pentru acest joc și forțarea brută asupra intrărilor $r'$, $x'$ (sau, echivalent, doar forțarea brută $r'$) pare a fi singura soluție pentru a câștiga jocul, ceea ce îl face să se bucure de a $256$-bit de securitate și, prin urmare, să fie imposibil de tratat. Mă întreb dacă raționamentul este corect sau dacă acesta este incorect?
Revenind la ipoteza originală a $\textbf{B.}$, se pare că acest lucru este de fapt posibil să se limiteze superioare jocului $128$-bit de securitate (de asemenea, o dificultate imposibil de rezolvat, dar este doar o limită superioară aici) în loc de $256$ când $\{X, R, m\}$ poate fi ales de adversar (și nu i se oferă). Fixare $x'=x$ și $r$ și $r'$, adversarul poate rezolva problema Zilei de naștere și poate găsi câteva $m$ și $m'$ (prin aplicarea algoritmului Birthday) verificând relația de mai jos, care este o soluție pentru joc:
$H(X,R,m) - H(X,R',m') = (r' - r).x^{-1}$.
$\textbf{2. Nu presupunem cunoașterea logaritmului discret la $S$:} $
Nu sunt sigur că argumentele de mai sus în $\textbf{1.}$ au fost aproximativ corecte, dar această situație pare puțin mai dificil de studiat.
$\textit{2. a) Presupunând cunoașterea logaritmului discret la nonces:}$
Pentru a câștiga acest joc, trebuie să oferiți ambilor dovezi de cunoaștere a logaritmilor discreti $R$ și $R'$ (o astfel de dovadă a cunoștințelor este suficientă dacă $R' = R$). Pentru a încerca să rezolvăm întrebarea presupunem că cineva a câștigat jocul, ceea ce presupune, scăzând cele două relații pe care un câștigător al jocului trebuie să le cunoască $u$ astfel încât:
$$u.G = H(X, R, m).X - H(X',R', m').X'.$$
Să presupunem că jocul este câștigat cu $X = X'$, atunci, înseamnă că logaritmul discret al $X$ trebuie cunoscut deoarece trebuie să fie adevărat că $u.G = (H(X, R, m) - H(X,R', m')).X$, și suntem deci în cazul lui $\textbf{1.}$.
Dacă $R = R'$ ($X'$ poate fi egal sau nu cu $X$), apoi revenim în cazul particular în care $u=0$, și avem asta $X' = H(X, R, m).H(X',R, m')^{-1}.X$, adică logaritmul discret $a$ de $X'$ cu privire la $X$ trebuie să verifice $a = H(X, R, m).H(X',R, m')^{-1}$. Fixare $X$ și $X'$ astfel încât $X' = a.X$ pentru unii $a$, cel mai bun algoritm pentru a rezolva acest lucru pare din nou algoritmul de ziua de naștere cu introducere în jur $2^{128}$ mesaje diferite în provocări pentru a găsi în cele din urmă unele $m$ și $m'$ care verifică $a.H(X',R, m') - H(X, R, m) = 0$.
Dacă ambele $X \neq X'$, și $R \neq R'$, nu reușesc să găsesc nicio potențială concluzie. Știe cineva un răspuns sau o referință pentru acest caz?
$\textit{2. b) Presupunând cunoașterea logaritmului discret la cheile publice:}$
Se pare că ne întoarcem la caz $R = R'$ de $\textit{2. a)}$ dacă $R = R'$, dar nu reusesc sa trag concluzia daca $R \neq R'$.
$\textit{2. c) Presupunând că nu cunoaște nici logaritmul discret la nonces și chei:}$
Din nou putem concluziona dacă $R = R'$ folosind același argument ca și cazul în $\textit{2. a)}$ pentru cazul $R = R'$, dar din nou pare să fie mai dificil să tragi altfel (adică dacă $R \neq R'$).
