Parašo algoritmas

ML-DSA-87 paaiškintas matematiškai

Kaip ML-DSA-87 (FIPS 204) pasirašo McGesund atsiliepimą — nuo Module-LWE ir atmetimo atrankos iki patikros naršyklėje.

Būklė: 2026-09-07

1. Apie ką čia kalbama

Kai kas nors McGesund sistemoje palieka atsiliepimą, fone įvyksta daugiau, nei leidžia numanyti tekstas. Išsiunčiamas atsiliepimas pasirašomas skaitmeniniu būdu. Šį parašą kiekvienas lankytojas gali vėliau perskaičiuoti savo paties naršyklėje — nepasitikėdamas mumis ir mūsų neklausdamas.

Klientams nuo tarifo Pro tai vyksta, be kita ko, su ML-DSA-87. Šis straipsnis paaiškina, kas tuo metu vyksta matematiškai.

Svarbu iš karto:

ML-DSA nėra šifravimas. Atsiliepimo tekstas lieka viešai skaitomas — juk tokia atsiliepimo prasmė. ML-DSA įrodo ne slaptumą, o kilmę ir vientisumą.

ML-DSA išvystytas iš CRYSTALS-Dilithium ir standartizuotas kaip FIPS 204. Skaičius 87 nurodo parametrų lygį. Jų yra trys:

  • ML-DSA-44
  • ML-DSA-65
  • ML-DSA-87

ML-DSA-87 yra aukščiausias ir priklauso NIST 5 saugumo kategorijai.

2. Kas tiksliai pasirašoma?

Į parašą keliauja ne pats atsiliepimo tekstas, o kompaktiškas duomenų objektas, kuris vienareikšmiškai užfiksuoja tekstą. McGesund sistemoje jis iš esmės atrodo taip:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<įmonės ID>",
  "c":   "<atsiliepimo ID>",
  "h":   "<atsiliepimo teksto SHA-256>",
  "rh":  "<viso pateikimo duomenų rinkinio SHA-256>",
  "rv":  1,
  "qh":  "<QR voko SHA-256, tik QR atsiliepimuose>",
  "iat": 1757203200
}

Šis objektas yra mūsų pranešimas mm. Jis susieja šešis teiginius:

  1. Kuriai įmonei atsiliepimas priklauso (f)
  2. Kuris atsiliepimas turimas omenyje (c)
  3. Koks tekstas už jo stovėjo — kaip maišos reikšmė (h)
  4. Koks duomenų rinkinys iš viso buvo pateiktas (rh): tekstas, širdelės, geo statusas ir aplinkybių duomenys, kanoniškai serializuoti ir sumaišyti — schemos versijoje rv
  5. Iš kurio QR kodo atsiliepimas kilęs (qh); be QR šio lauko nėra
  6. Kada buvo pasirašyta (iat)

Jei kas nors vėliau pakeičia bent vieną atsiliepimo teksto ženklą, h nebetinka — ir rh taip pat ne. Kas vietoj to tik pasuka širdeles, h nepaliečia, bet sulaužo rh. Pakeitus bent vieną iš šių maišos reikšmių, parašas nebetinka. Būtent ši grandinė ir yra esmė.

3. Ką parašas turi užtikrinti

Lankytojas, skaitantis atsiliepimą, turi galėti pats patikrinti tris dalykus:

  1. Atsiliepimą tikrai išdavė McGesund.
  2. Tekstas nuo išsiuntimo nebuvo pakeistas.
  3. Niekas negali išgalvoti naujo, galiojančiai atrodančio atsiliepimo.

Tam naudojama raktų pora:

  • privatusis raktas — laikomas išimtinai parašų tarnyboje
  • viešasis raktas — jį gali turėti bet kas, jis adresuojamas per rakto ID (kid) voke

Pasirašoma privačiuoju raktu. Tikrinama viešuoju — ir būtent skaitytojo naršyklėje, o ne mūsų serveryje.

4. Kam apskritai postkvantinis metodas?

Daugelis šiandien įprastų parašo algoritmų remiasi didelių skaičių skaidymu dauginamaisiais arba diskretiniais logaritmais. Pakankamai galingas kvantinis kompiuteris būtent šiuos uždavinius žinomais algoritmais galėtų išspręsti gerokai greičiau.

Atsiliepimui tai nėra akademinis klausimas. Atsiliepimas turi likti patikrinamas ir po dešimties metų. Kas pasirašo šiandien, pasirašo visam įrašo gyvavimo laikui.

Todėl ML-DSA naudoja kitokį pagrindą:

Gardelių uzˇdaviniai\boxed{\text{Gardelių uždaviniai}}

Tiksliau: Module-LWE ir Module-SIS.

5. Kas yra gardelė?

Iš pradžių tiesiog taškai erdvėje. Imkime du vektorius:

b1=(2,0),b2=(1,2).b_1=(2,0), \qquad b_2=(1,2).

Visos sveikaskaitinės kombinacijos

a b1+b b2,a,b∈Za\,b_1+b\,b_2, \qquad a,b\in\mathbb{Z}

sudaro gardelę. Pavyzdžiui:

2b1+b2=(4,0)+(1,2)=(5,2).2b_1+b_2 = (4,0)+(1,2) = (5,2).
b₁ = (2,0)b₂ = (1,2)(5,2)0
Du vektoriai, visos sveikaskaitinės jų kombinacijos: gardelė. Pažymėtasis taškas gaunamas iš dviejų b₁ ir vieno b₂.

Lemiama:

Mažuose matmenyse gardelių uždaviniai yra lengvi. Labai aukštuose matmenyse tam tikros užduotys tampa ypač sunkios.

6. Daugianariai vietoj pavienių skaičių

ML-DSA skaičiuoja ne su dvimačiais vektoriais, o su daugianariais ir daugianarių vektoriais.

Daugianarį, tokį kaip

a(x)=1+2x+x3a(x)=1+2x+x^3

galima užrašyti koeficientų sąrašu:

a=(1,2,0,1).a=(1,2,0,1).

Skaičiuojama žiede:

Rq=Zq[x]/(xn+1).R_q=\mathbb{Z}_q[x]/(x^n+1).

Tai reiškia du dalykus:

  • Zq\mathbb{Z}_q: skaičiavimas moduliu qq
  • xn=−1x^n=-1: papildoma taisyklė, fiksuojanti daugianario ilgį

Visiems trims ML-DSA lygiams galioja:

n=256,q=8380417.n=256, \qquad q=8380417.

Taigi daugianaris turi 256 koeficientus, nagrinėjamus moduliu 8 380 417. Tarp lygių keičiasi ne nn ar qq, o matricų dydis — apie tai vėliau.

Beje: daugianarių daugyba šiame žiede praktikoje atliekama per NTT — skaičių teorinį greitosios Furjė transformacijos variantą. Taigi ML-DSA anaiptol neapsieina be FFT idėjų; jos tiesiog slypi aritmetikoje, o ne parašo principe.

7. Pagrindinė gudrybė: Module-LWE

Pagrindinė idėja yra Module Learning With Errors:

t=As1+s2(modq).\mathbf{t}=\mathbf{A}\mathbf{s}_1+\mathbf{s}_2 \pmod q.

Čia:

  • A\mathbf{A} — vieša, tariamai atsitiktinė daugianarių matrica
  • s1,s2\mathbf{s}_1,\mathbf{s}_2 — maži slapti vektoriai
  • t\mathbf{t} — vieša reikšmė

Užpuolikas žino A\mathbf{A} ir t\mathbf{t}, bet ne s1,s2\mathbf{s}_1,\mathbf{s}_2. Lygtis jam atrodo kaip atsitiktinė lygtis su triukšmu. Mažų paslapčių iš jos jis neturi sugebėti efektyviai atkurti.

8. Mažytis skaitinis pavyzdys

Sąmoningai imame juokingai mažą variantą — įprastus skaičius vietoj daugianarių, 2 matmenis vietoj 256, ir

q=17.q=17.

Tegul

A=(3572),s1=(1−1),s2=(10).A=\begin{pmatrix}3&5\\7&2\end{pmatrix}, \qquad \mathbf{s}_1=\begin{pmatrix}1\\-1\end{pmatrix}, \qquad \mathbf{s}_2=\begin{pmatrix}1\\0\end{pmatrix}.

Tada:

As1=(3−57−2)=(−25),A\mathbf{s}_1=\begin{pmatrix}3-5\\7-2\end{pmatrix}=\begin{pmatrix}-2\\5\end{pmatrix},
t=As1+s2=(−25)+(10)=(−15)  ≡  (165)(mod17).\mathbf{t}=A\mathbf{s}_1+\mathbf{s}_2=\begin{pmatrix}-2\\5\end{pmatrix}+\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}-1\\5\end{pmatrix} \;\equiv\; \boxed{\begin{pmatrix}16\\5\end{pmatrix}} \pmod{17}.

Tokiame mažame formate būtų galima perrinkti visas galimybes. ML-DSA-87 atveju A\mathbf{A} yra 8×78\times 7 matrica iš daugianarių, kurių kiekvienas turi 256 koeficientus — tai daugiau nei 14 000 nežinomųjų gardelės struktūroje.

9. Parašų tarnybos raktų pora

Privačiajame rakte yra, be kita ko, maži vektoriai s1,s2\mathbf{s}_1,\mathbf{s}_2. ML-DSA-87 atveju jų koeficientai imami iš intervalo

[−η,η]suη=2,[-\eta,\eta] \quad\text{su}\quad \eta=2,

taigi iš aibės {−2,−1,0,1,2}\{-2,-1,0,1,2\}. Šis mažumas nėra smulkmena, o pati esmė: tik dėl to, kad paslaptys yra mažos, apskritai atsiranda sunkus gardelės uždavinys.

Viešasis raktas supaprastintai yra

(ρ,t1).(\rho,\mathbf{t}_1).

ρ\rho yra sėkla, iš kurios A\mathbf{A} galima deterministiškai atkurti — taigi matricos perduoti nereikia. t1\mathbf{t}_1 yra viršutiniai t\mathbf{t} bitai; apatiniai d=13d=13 bitai atmetami, o tai gerokai sumažina raktą. Būtent šis praleidimas vėliau yra vadinamųjų užuominų priežastis.

Taip atsiranda norima asimetrija:

viesˇai tikrinti  ≠  slaptai pasirasˇyti\boxed{\text{viešai tikrinti}\;\neq\;\text{slaptai pasirašyti}}

10. Atsiliepimas virsta skaičiumi

Parašų tarnyba pirmiausia apskaičiuoja 2 skyriaus naudingosios apkrovos objekto maišą:

μ=H(m).\mu=H(m).

Mūsų žaisliniame pavyzdyje imame dirbtinę mažą maišą. Tikroje sistemoje μ\mu yra 512 bitų ilgio ir papildomai susieja viešąjį raktą — dėl to parašo nepavyks pertraktuoti kaip skirto kitam raktui.

11. Įsipareigojimas

Parašų tarnyba ištraukia atsitiktinį mažą vektorių y\mathbf{y}. Mūsų pavyzdyje:

y=(2−1).\mathbf{y}=\begin{pmatrix}2\\-1\end{pmatrix}.

Iš jo gaunama tarpinė reikšmė — įsipareigojimas:

w=Ay=(3⋅2+5⋅(−1)7⋅2+2⋅(−1))=(112).\mathbf{w}=A\mathbf{y} =\begin{pmatrix}3\cdot2+5\cdot(-1)\\7\cdot2+2\cdot(-1)\end{pmatrix} =\begin{pmatrix}1\\12\end{pmatrix}.

Tai dar nėra parašas.

12. Iš atsiliepimo gaunamas iššūkis

Pranešimas ir įsipareigojimas sumaišomi kartu:

c=H(μ,w).c=H(\mu,\mathbf{w}).

ML-DSA-87 atveju cc yra daugianaris su lygiai τ=60\tau=60 koeficientais iš aibės {−1,+1}\{-1,+1\}, o visi likę 196 yra nuliai. Ši struktūra pasirinkta tyčia: ji išlaiko c⋅s1c\cdot\mathbf{s}_1 mažą.

Mūsų žaisliniame pavyzdyje tiesiog imame

c=2.c=2.

13. Pats parašas

z=y+c s1.\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1.

Su mūsų reikšmėmis:

c s1=2(1−1)=(2−2),c\,\mathbf{s}_1=2\begin{pmatrix}1\\-1\end{pmatrix}=\begin{pmatrix}2\\-2\end{pmatrix},
z=(2−1)+(2−2)=(4−3)\mathbf{z}=\begin{pmatrix}2\\-1\end{pmatrix}+\begin{pmatrix}2\\-2\end{pmatrix} =\boxed{\begin{pmatrix}4\\-3\end{pmatrix}}

14. Žingsnis, kurį lengva pražiūrėti: atmetimo atranka

Čia yra vieta, kurioje ML-DSA skiriasi nuo naivios konstrukcijos — ir ji nėra pasirenkama.

z=y+c s1\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1 savyje turi paslaptį s1\mathbf{s}_1. Jei z\mathbf{z} būtų tiesiog visada išduodamas, s1\mathbf{s}_1 iš pakankamai daug parašų būtų galima statistiškai apskaičiuoti. Atsiliepimų portalui su labai daug parašų per dieną tai nėra teorinė rizika.

Todėl parašų tarnyba prieš išdavimą patikrina, ar z\mathbf{z} neatskleidžia per daug, ir priešingu atveju parašą atmeta — tada viskas pradedama iš naujo su nauju atsitiktiniu y\mathbf{y}. Tai vadinama Fiat-Shamir with Aborts.

Sąlyga iš esmės yra tokia:

∥z∥∞<γ1−β.\|\mathbf{z}\|_\infty < \gamma_1-\beta.
Įsipareigojimas w = AyIššūkis c = H(μ, w)Atsakymas z = y + c · s₁‖z‖∞ < γ₁ − β ?taipParašas išduodamasne — naujas y
Trys žingsniai ir ciklas. Jei z išeina per didelis, jis nėra kaip nors taisomas — visas praėjimas atmetamas ir pradedamas iš naujo su šviežiu atsitiktiniu y. Todėl pasirašymas čia yra ciklinis metodas.

ML-DSA-87 atveju galioja γ1=219\gamma_1=2^{19} ir β=τ⋅η=60⋅2=120\beta=\tau\cdot\eta=60\cdot2=120. Prisideda dar antra riba apatiniams bitams. Praktikoje keli praėjimai yra įprasta — taigi pasirašymas yra ciklinis metodas, o ne vienas žingsnis.

Verifikacijai svarbu štai kas: būtent šią ribą naršyklė vėliau taip pat tikrina. Parašas su per dideliais koeficientais atmetamas, net jei lygtis ir tenkinama.

15. Kodėl naršyklė tai gali patikrinti

Skaitytojo naršyklė žino:

  • atsiliepimą, taigi ir mm
  • viešąjį raktą (ρ,t1)(\rho,\mathbf{t}_1)
  • parašą (c~,z,h)(\tilde c,\mathbf{z},\mathbf{h})

Ji nežino s1\mathbf{s}_1. Ryšys, kuris ją vis dėlto veda pirmyn:

z=y+c s1⟹Az=Ay+c As1.\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1 \quad\Longrightarrow\quad A\mathbf{z}=A\mathbf{y}+c\,A\mathbf{s}_1.

Ir kadangi galioja

t=As1+s2\mathbf{t}=A\mathbf{s}_1+\mathbf{s}_2

nežinomą As1A\mathbf{s}_1 galima pakeisti viešąja reikšme:

Az−c t=Ay−c s2.A\mathbf{z}-c\,\mathbf{t}=A\mathbf{y}-c\,\mathbf{s}_2.

Tai pagrindinė lygtis — ir ji sako svarbų dalyką: naršyklė atkuria AyA\mathbf{y} ne tiksliai, o tik iki mažo nario c s2c\,\mathbf{s}_2.

16. Mažas pavyzdys iki galo

Turėjome:

A=(3572),t=(−15),c=2,z=(4−3).A=\begin{pmatrix}3&5\\7&2\end{pmatrix},\quad \mathbf{t}=\begin{pmatrix}-1\\5\end{pmatrix},\quad c=2,\quad \mathbf{z}=\begin{pmatrix}4\\-3\end{pmatrix}.

Perskaičiuokime:

Az=(12−1528−6)=(−322),c t=2(−15)=(−210),A\mathbf{z}=\begin{pmatrix}12-15\\28-6\end{pmatrix}=\begin{pmatrix}-3\\22\end{pmatrix}, \qquad c\,\mathbf{t}=2\begin{pmatrix}-1\\5\end{pmatrix}=\begin{pmatrix}-2\\10\end{pmatrix},
Az−c t=(−112).A\mathbf{z}-c\,\mathbf{t}=\begin{pmatrix}-1\\12\end{pmatrix}.

Pradinis įsipareigojimas buvo

w=(112).\mathbf{w}=\begin{pmatrix}1\\12\end{pmatrix}.

Skirtumas yra

(−112)−(112)=(−20)=−c s2.\begin{pmatrix}-1\\12\end{pmatrix}-\begin{pmatrix}1\\12\end{pmatrix} =\begin{pmatrix}-2\\0\end{pmatrix} =-c\,\mathbf{s}_2.

Taigi būtent numatytas mažas paklaidos narys. Tikrintojas gauna ne w\mathbf{w}, o kai ką, kas yra arti w\mathbf{w}.

Būtent todėl ML-DSA lygina ne pačias reikšmes, o jų viršutinius bitus. Ir būtent todėl parašas papildomai turi užuominų vektorių h\mathbf{h}: jis kompaktiškai praneša, kuriose vietose apvalinimas dėl mažo paklaidos nario persivertė per ribą. ML-DSA-87 atveju leidžiama daugiausia ω=75\omega=75 tokių užuominų. Paslapties jos neatskleidžia — jos tik pataiso apvalinimą.

Pabaigoje naršyklė iš naujo apskaičiuoja iššūkį. Jei jis sutampa,

cnaujas=c,c_{\text{naujas}}=c,

ir visos normos telpa į ribas, parašas galioja.

17. Kas nutinka, kai kas nors pakeičia atsiliepimą?

Tarkime, kažkas, turintis prieigą prie duomenų bazės — taip pat ir kažkas iš mūsų — pakeičia atsiliepimo tekstą arba vieną iš širdelių. Tada pasikeičia bent viena iš dviejų maišos reikšmių naudingojoje apkrovoje (h — dėl teksto, rh — dėl bet kurio duomenų rinkinio lauko):

H(m)≠H(m′).H(m)\neq H(m').

Kartu pasikeičia iššūkis:

c≠c′.c\neq c'.

Tačiau esamas parašas buvo sukurtas senajam iššūkiui. Naršyklė perskaičiuoja ir nustato:

cnaujas≠cparasˇo⟹Parasˇas negaliojac_{\text{naujas}}\neq c_{\text{parašo}} \quad\Longrightarrow\quad \boxed{\text{Parašas negalioja}}

Lemiamas sakinys toks: atsiliepimą galime ištrinti, bet pakeisti jo nepastebimai negalime. McGesund sistemoje ta pati patikra papildomai kas naktį atliekama serveryje visam duomenų kiekiui — atsiliepimas, kuris šios patikros neišlaiko, į įmonės vidurkį nebeįskaitomas.

18. Kodėl niekas negali išgalvoti parašo?

Užpuolikas žino A\mathbf{A} ir t\mathbf{t}, bet ne s1,s2\mathbf{s}_1,\mathbf{s}_2. Kad sukonstruotų galiojantį parašą, jis turėtų rasti trejetą (c~,z,h)(\tilde c,\mathbf{z},\mathbf{h}), kuris

  • tenkina verifikacijos lygtį ir
  • laikosi normų ribų ir
  • atitinka iššūkį, kuris gaunamas iš tų pačių reikšmių.

Iš esmės tai veda prie sunkaus gardelės uždavinio — konkrečiai prie Module-SIS: rasti trumpus homogeninės lygties sprendinius moduliu qq. Mažumo sąlyga čia yra ne priedas, o pats sunkumo šaltinis. Be jos sprendinys būtų trivialus.

viesˇi duomenys  →  sunkus gardele˙s uzˇdavinys\boxed{\text{vieši duomenys}\;\rightarrow\;\text{sunkus gardelės uždavinys}}

19. Kodėl „Module"?

Šis žodis apibūdina struktūrą tarp paprastų vektorių ir bendrųjų gardelių. Užuot skaičiavęs su pavieniais skaičiais, ML-DSA dirba su daugianarių vektoriais:

a=(a1(x),a2(x),…,ak(x)),\mathbf{a}=(a_1(x),a_2(x),\ldots,a_k(x)),

ir su jų matricomis:

A=(a1,1(x)a1,2(x)⋯a2,1(x)a2,2(x)⋯⋮⋮⋱).\mathbf{A}= \begin{pmatrix} a_{1,1}(x)&a_{1,2}(x)&\cdots\\ a_{2,1}(x)&a_{2,2}(x)&\cdots\\ \vdots&\vdots&\ddots \end{pmatrix}.

Privalumas: gaunamas didelis gardelės matmuo, bet išlaikomas kompaktiškas, efektyviai skaičiuojamas pavidalas. Saugumą galima tiksliai derinti keičiant matricos dydį, nekeičiant žiedo.

20. Kodėl būtent 87?

Trys lygiai skiriasi ne žiedu, o matmenimis:

ParametrasML-DSA-44ML-DSA-65ML-DSA-87
Matricos dydis (k,ℓ)(k,\ell)4×44\times46×56\times58×78\times7
Paslapties intervalas η\eta242
Iššūkio svoris τ\tau394960
Viešasis raktas1 312 B1 952 B2 592 B
Parašas2 420 B3 309 B4 627 B
NIST kategorija235

Verta pastebėti: ML-DSA-87 nėra tiesiog „ML-DSA-65, tik didesnis". Paslapties intervalas η\eta nuo 4 vėl grįžta į 2; saugumas čia ateina iš didesnės matricos, o ne iš didesnių koeficientų. Tai savarankiškas, standartizuotas parametrų pasirinkimas.

didesne˙ matematine˙ struktuˉra→didesne˙ saugumo atsarga\boxed{\text{didesnė matematinė struktūra}\rightarrow\text{didesnė saugumo atsarga}}

Kaina: 4 627 baitai vienam parašui — vienam antspaudui, kuris saugomas ir tikrinant pateikiamas naršyklei. Todėl McGesund sistemoje greta ML-DSA-87 galima rinktis ir FALCON, kuriam pakanka 1 280 baitų.

21. Fiat-Shamir: kodėl tai veikia be pašnekovo

Interaktyvus įrodymas vyktų taip:

  1. Parašų tarnyba siunčia įsipareigojimą.
  2. Tikrintojas siunčia atsitiktinį iššūkį.
  3. Parašų tarnyba atsako.
  4. Tikrintojas perskaičiuoja.

Atsiliepimo atveju tokio dialogo nėra — skaitytojas ateina po kelių mėnesių. Sprendimas yra Fiat-Shamir transformacija: iššūkis ne metamas kauliuku, o apskaičiuojamas kaip maiša iš pačių duomenų:

c=H(viesˇasis raktas,  pranesˇimas,  įsipareigojimas).c=H(\text{viešasis raktas},\;\text{pranešimas},\;\text{įsipareigojimas}).

Taip dialogas virsta dokumentu. Parašų tarnyba negali pasirinkti iššūkio, nes tam ji turėtų kontroliuoti maišą.

22. Visa eiga

PARAŠŲ TARNYBA (MCGESUND)LANKYTOJO NARŠYKLĖprivatusis raktas s₁, s₂Naudingoji apkrova m = {įmonė, atsiliepimas, h, rh, iat}Maiša μatsitiktinis vektorius yĮsipareigojimas w = AyIššūkis c = H(μ, w)z = y + c · s₁Parašas (c, z, užuominos) + kidatsiliepimas + parašas + viešasis raktasAz − c·t → viršutiniai bitai + užuominosiššūkį perskaičiuotiperskaičiuotas iššūkis = pateiktasis?galiojanegaliojaatmesti, jei z per didelis(atmetimo atranka)
Visas atsiliepimo kelias. Brūkšninis grįžimas atgal yra atmetimo atranka — jis kartojamas tol, kol z tampa pakankamai mažas, kad nieko neatskleistų apie slaptąjį raktą.

23. Ką konkrečiai su tuo daro McGesund

Susikabina trys lygmenys:

Vokas. Kiekvienas pasirašytas atsiliepimas turi Ed25519 parašą. Tai privaloma dalis — klasikinė, mažytė, natyviai patikrinama kiekvienoje naršyklėje.

Postkvantiniai antspaudai. Papildomai šalia gali būti padėti vienas ar du kvantams atsparūs parašai. Kurie — priklauso nuo tarifo:

Tarifasgalimi parašų lygiai
BasisEd25519, FN-DSA-512
KlassikEd25519, FN-DSA-512, FN-DSA-1024
ProEd25519, FN-DSA-1024, ML-DSA-87
PremiumEd25519, FN-DSA-1024, ML-DSA-87, abu lygiagrečiai

Lygiagretus variantas sąmoningai perteklinis. Jei viena iš dviejų matematinių šeimų — NTRU gardelės FALCON atveju, modulinės gardelės ML-DSA atveju — pasirodytų silpnesnė, nei manoma šiandien, kita laikytų toliau.

Laiko inkaras. Parašo rakto kontrolinis atspaudas per OpenTimestamps įtvirtinamas Bitcoin bloke. Taip galima įrodyti ne tik tai, kad parašas tikras, bet ir tai, kad jis tam tikru momentu jau egzistavo — nereikalaujant iš nieko tikėti mūsų laiko žyma.

Visa tai tikrinama skaitytojo naršyklėje per WASM modulį. Mes pateikiame duomenis; perskaičiuojama lankytojo įrenginyje. Jei rytoj dingtume iš tinklo, kartą atsisiųstas atsiliepimas liktų patikrinamas.

24. ML-DSA ir FALCON greta

SavybėFALCON (FN-DSA)ML-DSA
Tipasskaitmeninis parašasskaitmeninis parašas
Gardelių šeimaNTRUModule-LWE / Module-SIS
ŽiedasZq[x]/(xn+1)\mathbb{Z}_q[x]/(x^n+1), q=12289q=12289Zq[x]/(x256+1)\mathbb{Z}_q[x]/(x^{256}+1), q=8380417q=8380417
Pagrindinis mechanizmastrumpas vektorius per Gauso atrankąiššūkis ir atsakymas su nutraukimais
FFT / NTTslankiojo kablelio FFT, kritinė saugumuiNTT, tik aritmetika
Parašo dydis (aukščiausias lygis)1 280 B4 627 B
Realizacijasudėtinga (slankusis kablelis)palyginti tiesmuka
Standartizavimasnumatytas kaip FIPS 206 (FN-DSA), dar nebaigtasFIPS 204, baigtas

Trumpai tariant: ML-DSA lengviau teisingai realizuoti ir patikrinti, FALCON pateikia gerokai kompaktiškesnius parašus. QR kode nėra nė vieno iš jų — ten yra vien Ed25519 vokas. Todėl parašo dydis svarbus saugant ir pateikiant, o patvarumas — realizuojant. Todėl siūlome abu.

25. Vienas sakinys įsidėmėti

ML-DSA isˇ trumpo slapto vektoriaus sukuria atsakymą į isˇsˇuˉkį,kuris apskaicˇiuotas isˇ paties atsiliepimo maisˇos — patikrinamąkiekvienam, turincˇiam viesˇąjį raktą.\boxed{ \begin{array}{c} \text{ML-DSA iš trumpo slapto vektoriaus sukuria atsakymą į iššūkį,}\\ \text{kuris apskaičiuotas iš paties atsiliepimo maišos — patikrinamą}\\ \text{kiekvienam, turinčiam viešąjį raktą.} \end{array}}

Kas turi slaptąjį vektorių, pasirašo per milisekundes. Kas jo neturi, turėtų išspręsti gardelės uždavinį daugiau nei 14 000 matmenų erdvėje — net ir su kvantiniu kompiuteriu.

Atsiliepimo skaitytojui tai reiškia paprastą dalyką: jam nereikia mumis tikėti. Jis gali perskaičiuoti.