Hârtie de semnătură a inelului trasabil de la Fujisaki și Suzuki, care permite semnătura unei chei private dintr-un inel de chei publice și pentru oricine să verifice dacă un membru al inelului a semnat, fără a dezvălui care membru al inelului a semnat, cu excepția cazului în care același membru al inelului semnează două mesaje diferite sub aceeași etichetă („cheltuieli duble”), caz în care este posibil să se identifice cel care cheltuiește dublu.
Pentru un inel de $n$ semnatari, de care depinde atât protocolul de semnare, cât și protocolul de verificare $\sigma_j$ pentru $i \în [1..n]$. Unde $i$ este poziția adevăratului semnatar în ring, $\sigma_i$ este determinată pe baza cheii private, a membrilor inelului și a problemei. Trasabilitatea se bazează apoi pe ideea că, cu un singur mesaj pentru o cheie privată / inel / emisiune triplă, ar trebui să fie imposibil să se determine care $\sigma_j$ este cea constrânsă fără cheia privată. Totuși, dacă același semnatar semnează două mesaje pentru același apel/emisiune, atunci $\sigma_i$ va fi același pentru cele două mesaje, identificând ambele mesaje provenite de la semnatar $i$. Lucrarea subliniază, totuși, că dacă protocolul ar da semnatarului mână liberă de a alege $\sigma_j$ pentru $j \neq i$, un semnatar ar putea încadra un alt semnatar ca având dublu semnat.
Pentru a depăși acest lucru, lucrarea descrie în schimb o schemă de exprimare a tuturor $\sigma_j$ ca o linie cu o interceptare fixată de algoritm bazat pe un hash al intrărilor și o pantă (determinată de semnatar pe baza $i$, interceptarea și $\sigma_i$).
Lucrarea exprimă $\sigma_j$ valorile ca fiind membru al unui „grup multiplicativ G de ordinul prim q” fără alte informații despre ceea ce au avut în vedere pentru acel grup. Prin urmare, aș dori să aleg $G$ ca curba eliptică Curve25519, care pare să se încadreze în ipotezele autorilor.
Cu toate acestea, acest lucru ridică o provocare cu această schemă de punere $\sigma_j$ valori pe o linie. Hârtia spune:
A stabilit $A_0 = H'(L, m)$ și $A_1 = ({\sigma_i \over A_0})^{1/i}$
Există mai multe interpretări posibile pentru modul de calcul $A_1$ din această. Aparent codomeniul al $H'$ este de asemenea $G$. Interpretând aceasta ca o expresie în $G$ (despre care altcineva a întrebat anterior: Cum se calculează $x^{1/y}$?), totuși, ar însemna rezolvarea problemei logaritmului discret al curbei eliptice. Securitatea întregii scheme din lucrare depinde de faptul că aceasta este imposibil de rezolvat $G$ este ales, deci cred că interpretarea efectuării utilizării operațiunilor de teren probabil nu are sens - și cred că autorii trebuie să fi intenționat ca operația să fie efectuată pe numărul brut care identifică un punct din grup este o optiune.
Prin urmare, întrebarea mea este: deoarece Curve25519 utilizează puncte eliptice comprimate care pot fi identificate printr-un singur întreg $x$, ar fi să se calculeze o implementare sigură și corectă $A_1 = ({\sigma_i \over A_0})^{1/i}$ pe $x$ coordonata punctului?
O problemă pe care o văd cu asta este doar aceea $1/8$ dintre toate valorile sunt puncte de pe curba pentru Curba25519, iar dacă algoritmul de semnare asigură că $\sigma_i$ iese ca pe curba dar nu $\sigma_j$ pentru $i \neq j$, atunci asta ar putea exclude 7/8 din posibilii participanți la ring ca sursă a unei semnături (ceea ce ar fi o scurgere de informații inacceptabilă).
O soluție rezonabilă pentru aceasta ar fi să faceți calculul protocolului de verificare $\sigma_j^{'}$ din $A_0$ și $A_1$, iar apoi incrementați X
coordonați în mod repetat până la un punct de pe curbă ($\sigma_j$) este obținut? Și apoi semnatarul ar putea decrementa $x$ coordonata a $\sigma_i$ în mod repetat pentru a obține cea mai mare $X < \sigma_i$ care nu se află pe curbă, și apoi eșantionează aleatoriu equiprobabil o coordonată x $x \leftarrow [X+1..\sigma_i]$, și folosește-l pentru a calcula $A_1$. În acest fel, un adversar nu ar putea spune dacă un dat $j$ valoarea este $i$, cu exceptia $\sigma_i$ valorile ar fi constrânse pentru a preveni atacul din hârtie. Există probleme evidente cu această implementare pe care le lipsesc?