Allekirjoitusmenetelmä

ML-DSA-87 matemaattisesti selitettynä

Miten ML-DSA-87 (FIPS 204) allekirjoittaa McGesund-arvion — Module-LWE:stä rejection samplingin kautta selaimessa tapahtuvaan todennukseen.

Päivitetty: 2026-09-07

1. Mistä tässä on kyse

Kun joku antaa McGesundissa arvion, taustalla tapahtuu enemmän kuin teksti antaa olettaa. Arvio allekirjoitetaan digitaalisesti lähetyshetkellä. Jokainen kävijä voi myöhemmin laskea tämän allekirjoituksen uudelleen omassa selaimessaan — meihin luottamatta ja meiltä kysymättä.

Pro-paketista alkaen se tapahtuu muun muassa ML-DSA-87:llä. Tämä kirjoitus selittää, mitä siinä matemaattisesti tapahtuu.

Tärkeä huomautus aluksi:

ML-DSA ei ole salausmenetelmä. Arvioteksti pysyy julkisesti luettavana — sehän on arvion tarkoitus. ML-DSA ei todista salassapitoa vaan alkuperän ja eheyden.

ML-DSA on kehitetty CRYSTALS-Dilithiumista ja standardoitu nimellä FIPS 204. Luku 87 ilmaisee parametritason. Niitä on kolme:

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

ML-DSA-87 on korkein ja kuuluu NIST-turvallisuusluokkaan 5.

2. Mitä tarkalleen allekirjoitetaan?

Allekirjoitukseen ei mene arvioteksti itse vaan tiivis tietokohde, joka naulaa tekstin yksikäsitteisesti kiinni. McGesundissa se näyttää ytimeltään tältä:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<yritystunnus>",
  "c":   "<arviotunnus>",
  "h":   "<arviotekstin SHA-256>",
  "rh":  "<koko lähetystietueen SHA-256>",
  "rv":  1,
  "qh":  "<QR-Envelopen SHA-256, vain QR-arvioissa>",
  "iat": 1757203200
}

Tämä kohde on viestimme mm. Se sitoo yhteen kuusi väitettä:

  1. Mihin yritykseen arvio kuuluu (f)
  2. Mistä arviosta on kyse (c)
  3. Mikä teksti sen takana oli — tiivistearvona (h)
  4. Mikä tietue kokonaisuudessaan lähetettiin (rh): teksti, sydämet, sijaintitila ja käynnin syytä koskevat tiedot, kanonisesti sarjallistettuina ja tiivistettyinä — skeemaversiossa rv
  5. Mistä QR-koodista arvio on peräisin (qh); ilman QR-koodia kenttä jää pois
  6. Milloin allekirjoitettiin (iat)

Jos joku muuttaa myöhemmin yhden ainoan merkin arviotekstissä, h ei enää täsmää — eikä rh liioin. Se, joka sen sijaan kääntää vain sydämiä, jättää kentän h koskematta mutta rikkoo kentän rh. Jos joku muuttaa jompaakumpaa näistä tiivistearvoista, allekirjoitus ei enää täsmää. Juuri tämä ketju on koko juju.

3. Mitä allekirjoituksen on määrä saada aikaan

Arvion lukevan kävijän on voitava tarkistaa itse kolme asiaa:

  1. Arvio on todella McGesundin antama.
  2. Tekstiä ei ole muutettu lähettämisen jälkeen.
  3. Kukaan ei voi keksiä uutta, kelvolliselta näyttävää arviota.

Sitä varten on avainpari:

  • yksityinen avain — sijaitsee yksinomaan allekirjoituspalvelussa
  • julkinen avain — saa olla kenellä tahansa, ja se osoitetaan Envelopessa olevalla avaintunnuksella (kid)

Allekirjoittaminen tapahtuu yksityisellä avaimella. Todentaminen tapahtuu julkisella — ja nimenomaan lukijan selaimessa, ei meidän palvelimellamme.

4. Miksi ylipäätään post-kvanttimenetelmä?

Monet nykyisin tavanomaiset allekirjoitusmenetelmät perustuvat suurten lukujen tekijöihinjakoon tai diskreetteihin logaritmeihin. Riittävän tehokas kvanttitietokone voisi ratkaista juuri nämä ongelmat tunnetuilla algoritmeilla huomattavasti nopeammin.

Arvion kohdalla se ei ole akateeminen kysymys. Arvion on määrä olla todennettavissa vielä kymmenen vuoden kuluttua. Se, joka allekirjoittaa tänään, allekirjoittaa merkinnän koko elinkaareksi.

Siksi ML-DSA käyttää toisenlaista perustaa:

Hilaongelmat\boxed{\text{Hilaongelmat}}

Tarkemmin: Module-LWE ja Module-SIS.

5. Mikä on hila?

Aluksi vain pisteitä avaruudessa. Otetaan kaksi vektoria:

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

Kaikki kokonaislukukertoimiset yhdistelmät

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

muodostavat hilan. Esimerkiksi:

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
Kaksi vektoria ja kaikki niiden kokonaislukukertoimiset yhdistelmät: hila. Merkitty piste syntyy kahdesta b₁:stä ja yhdestä b₂:sta.

Ratkaisevaa on:

Pienissä ulottuvuuksissa hilaongelmat ovat helppoja. Hyvin korkeissa ulottuvuuksissa tietyistä tehtävistä tulee äärimmäisen vaikeita.

6. Polynomit yksittäisten lukujen sijaan

ML-DSA ei laske kaksiulotteisilla vektoreilla vaan polynomeilla ja polynomivektoreilla.

Polynomi kuten

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

voidaan kirjoittaa kerroinlistana:

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

Laskutoimitukset tehdään renkaassa:

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

Se tarkoittaa kahta asiaa:

  • Zq\mathbb{Z}_q: laskeminen modulo qq
  • xn=−1x^n=-1: lisäsääntö, joka kiinnittää polynomin pituuden

Kaikilla kolmella ML-DSA-tasolla pätee:

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

Polynomilla on siis 256 kerrointa, tarkasteltuna modulo 8 380 417. Tasojen välillä ei muutu nn eikä qq vaan matriisien koko — siitä lisää myöhemmin.

Sivumennen: polynomien kertolasku tässä renkaassa etenee käytännössä NTT:n kautta, joka on nopean Fourier-muunnoksen lukuteoreettinen variantti. ML-DSA ei siis suinkaan tule toimeen ilman FFT-ideoita; ne ovat vain aritmetiikassa eivätkä allekirjoitusperiaatteessa.

7. Keskeinen temppu: Module-LWE

Ydinajatus on Module Learning With Errors:

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

Tässä:

  • A\mathbf{A} — julkinen, näennäisen satunnainen polynomimatriisi
  • s1,s2\mathbf{s}_1,\mathbf{s}_2 — pienet salaiset vektorit
  • t\mathbf{t} — julkinen arvo

Hyökkääjä tuntee arvot A\mathbf{A} ja t\mathbf{t} mutta ei arvoja s1,s2\mathbf{s}_1,\mathbf{s}_2. Yhtälö näyttää hänestä satunnaiselta yhtälöltä, jossa on kohinaa. Pieniä salaisuuksia hänen ei ole määrä pystyä laskemaan siitä tehokkaasti takaisin.

8. Pienenpieni lukuesimerkki

Otamme tarkoituksella naurettavan pienen variantin — tavallisia lukuja polynomien sijaan, ulottuvuus 2 eikä 256, ja

q=17.q=17.

Olkoon

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}.

Silloin:

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}.

Tässä minimuodossa kaikki vaihtoehdot voisi käydä läpi kokeilemalla. ML-DSA-87:ssä A\mathbf{A} on 8×78\times 7-matriisi polynomeja, joilla kullakin on 256 kerrointa — se tarkoittaa yli 14 000 tuntematonta hilarakenteessa.

9. Allekirjoituspalvelun avainpari

Yksityinen avain sisältää muun muassa pienet vektorit s1,s2\mathbf{s}_1,\mathbf{s}_2. ML-DSA-87:ssä niiden kertoimet ovat väliltä

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

siis joukosta {−2,−1,0,1,2}\{-2,-1,0,1,2\}. Tämä pienuus ei ole yksityiskohta vaan ydin: vain siksi, että salaisuudet ovat pieniä, syntyy ylipäätään vaikea hilaongelma.

Julkinen avain on yksinkertaistettuna

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

ρ\rho on siemen, josta A\mathbf{A} voidaan rekonstruoida deterministisesti — matriisia ei siis tarvitse siirtää. t1\mathbf{t}_1 on arvon t\mathbf{t} ylimmät bitit; alimmat d=13d=13 bittiä jäävät pois, mikä pienentää avainta selvästi. Tämä poisjättö on myöhemmin syy niin sanottuihin vihjeisiin.

Näin syntyy haluttu epäsymmetria:

julkinen todennus  ≠  salainen allekirjoitus\boxed{\text{julkinen todennus}\;\neq\;\text{salainen allekirjoitus}}

10. Arviosta tulee luku

Allekirjoituspalvelu tiivistää ensin luvun 2 payload-kohteen:

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

Leluesimerkissämme käytämme keinotekoista minitiivistettä. Todellisessa järjestelmässä μ\mu on 512 bittiä pitkä ja sitoo lisäksi julkisen avaimen mukaan — siten allekirjoitusta ei voi tulkita uudelleen toiselle avaimelle.

11. Commitment

Allekirjoituspalvelu arpoo satunnaisen pienen vektorin y\mathbf{y}. Esimerkissämme:

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

Siitä syntyy välituloksena commitment:

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}.

Tämä ei ole vielä allekirjoitus.

12. Arviosta tulee haaste

Viesti ja commitment tiivistetään yhdessä:

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

ML-DSA-87:ssä cc on polynomi, jossa on täsmälleen τ=60\tau=60 kerrointa joukosta {−1,+1}\{-1,+1\}, ja loput 196 ovat nollia. Tämä rakenne on tarkoituksellinen: se pitää tulon c⋅s1c\cdot\mathbf{s}_1 pienenä.

Leluesimerkissämme asetamme yksinkertaisesti

c=2.c=2.

13. Varsinainen allekirjoitus

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

Meidän arvoillamme:

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. Askel, joka helposti jää huomaamatta: rejection sampling

Tässä on kohta, jossa ML-DSA eroaa naiivista rakenteesta — eikä se ole valinnainen.

z=y+c s1\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1 sisältää salaisuuden s1\mathbf{s}_1. Jos z\mathbf{z} annettaisiin aina yksinkertaisesti ulos, s1\mathbf{s}_1 olisi laskettavissa tilastollisesti riittävän monesta allekirjoituksesta. Arviointiportaalille, joka tekee hyvin paljon allekirjoituksia päivässä, se ei ole teoreettinen riski.

Siksi allekirjoituspalvelu tarkistaa ennen ulosantoa, paljastaako z\mathbf{z} liikaa, ja hylkää allekirjoituksen muussa tapauksessa — silloin aloitetaan alusta uudella satunnaisella y\mathbf{y}:llä. Tätä kutsutaan nimellä Fiat-Shamir with Aborts.

Ehto kuuluu olennaisesti näin:

∥z∥∞<γ1−β.\|\mathbf{z}\|_\infty < \gamma_1-\beta.
commitment w = Ayhaaste c = H(μ, w)vastaus z = y + c · s₁‖z‖∞ < γ₁ − β ?kylläallekirjoitus annetaan ulosei — uusi y
Kolme askelta ja silmukka. Jos z:sta tulee liian suuri, sitä ei paranneta — koko läpimeno hylätään ja aloitetaan alusta tuoreella satunnaisella y:llä. Siksi allekirjoittaminen on tässä silmukkamenetelmä.

ML-DSA-87:llä pätee γ1=219\gamma_1=2^{19} ja β=τ⋅η=60⋅2=120\beta=\tau\cdot\eta=60\cdot2=120. Lisäksi tulee toinen raja alimmille biteille. Käytännössä useat läpimenot ovat normaaleja — allekirjoittaminen on siis silmukkamenetelmä eikä kertaluonteinen askel.

Todennuksen kannalta on tärkeää: juuri tämän rajan selain tarkistaa myöhemmin mukana. Allekirjoitus, jonka kertoimet ovat liian suuria, hylätään, vaikka yhtälö menisi tasan.

15. Miksi selain voi tarkistaa tämän

Lukijan selain tuntee:

  • arvion ja siten viestin mm
  • julkisen avaimen (ρ,t1)(\rho,\mathbf{t}_1)
  • allekirjoituksen (c~,z,h)(\tilde c,\mathbf{z},\mathbf{h})

Arvoa s1\mathbf{s}_1 se ei tunne. Yhteys, joka silti vie sitä eteenpäin:

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.

Ja koska pätee

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

tuntematon As1A\mathbf{s}_1 voidaan korvata julkisella arvolla:

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

Tämä on keskeinen yhtälö — ja se sanoo jotakin tärkeää: selain ei rekonstruoi arvoa AyA\mathbf{y} tarkasti vaan vain pientä termiä c s2c\,\mathbf{s}_2 vaille.

16. Miniesimerkki loppuun asti

Meillä oli:

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}.

Lasketaan tarkistukseksi:

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}.

Alkuperäinen commitment oli

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

Erotus on

(−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.

Siis täsmälleen ennustettu pieni virhetermi. Todentaja ei saa arvoa w\mathbf{w} vaan jotakin, joka on lähellä arvoa w\mathbf{w}.

Juuri siksi ML-DSA ei vertaa arvoja itseään vaan niiden ylimpiä bittejä. Ja juuri siksi allekirjoitus sisältää lisäksi vihjevektorin h\mathbf{h}: se kertoo tiiviisti, missä kohdin pyöristys on pienen virhetermin vuoksi kaatunut rajan yli. ML-DSA-87:ssä sallitaan enintään ω=75\omega=75 tällaista vihjettä. Ne eivät paljasta salaisuutta — ne vain korjaavat pyöristyksen.

Lopuksi selain laskee haasteen uudelleen. Jos se täsmää,

cuusi=c,c_{\text{uusi}}=c,

ja kaikki normit ovat rajojen sisällä, allekirjoitus on kelvollinen.

17. Mitä tapahtuu, jos joku muuttaa arviota?

Oletetaan, että joku, jolla on pääsy tietokantaan — myös joku meiltä — muuttaa arviotekstiä tai yhtä sydämistä. Silloin muuttuu vähintään toinen payloadin kahdesta tiivistearvosta (h tekstin kohdalla, rh minkä tahansa tietueen kentän kohdalla):

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

Siten muuttuu haaste:

c≠c′.c\neq c'.

Olemassa oleva allekirjoitus on kuitenkin luotu vanhalle haasteelle. Selain laskee tarkistukseksi ja toteaa:

cuusi≠callekirjoitus⟹Allekirjoitus virheellinenc_{\text{uusi}}\neq c_{\text{allekirjoitus}} \quad\Longrightarrow\quad \boxed{\text{Allekirjoitus virheellinen}}

Ratkaiseva lause tähän: voimme poistaa arvion, mutta emme voi muuttaa sitä huomaamatta. McGesundissa sama tarkistus ajetaan lisäksi öisin palvelinpuolella koko aineistolle — arvio, joka ei läpäise tätä tarkistusta, ei enää vaikuta yrityksen keskiarvoon.

18. Miksi kukaan ei voi keksiä allekirjoitusta?

Hyökkääjä tuntee arvot A\mathbf{A} ja t\mathbf{t} mutta ei arvoja s1,s2\mathbf{s}_1,\mathbf{s}_2. Rakentaakseen kelvollisen allekirjoituksen hänen pitäisi löytää kolmikko (c~,z,h)(\tilde c,\mathbf{z},\mathbf{h}), joka

  • toteuttaa todennusyhtälön ja
  • pysyy normirajoissa ja
  • vastaa haastetta, joka saadaan täsmälleen näistä arvoista itsestään.

Tämä johtaa ytimeltään vaikeaan hilaongelmaan — konkreettisesti ongelmaan Module-SIS: lyhyiden ratkaisujen löytämiseen homogeeniselle yhtälölle modulo qq. Pienuusehto ei ole tässä koriste vaan varsinainen vaikeusaste. Ilman sitä ratkaisu olisi triviaali.

julkiset tiedot  →  vaikea hilaongelma\boxed{\text{julkiset tiedot}\;\rightarrow\;\text{vaikea hilaongelma}}

19. Miksi ”Module”?

Sana kuvaa rakennetta yksinkertaisten vektorien ja yleisten hilojen välillä. Yksittäisillä luvuilla laskemisen sijaan ML-DSA työskentelee polynomivektoreilla:

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

ja niistä muodostetuilla matriiseilla:

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}.

Etu: saadaan hilan korkea ulottuvuus mutta säilytetään tiivis, tehokkaasti laskettava esitys. Turvallisuutta voidaan hienosäätää matriisin koolla ilman renkaan vaihtamista.

20. Miksi juuri 87?

Kolme tasoa eivät eroa toisistaan renkaan vaan ulottuvuuksien osalta:

ParametriML-DSA-44ML-DSA-65ML-DSA-87
Matriisin koko (k,ℓ)(k,\ell)4×44\times46×56\times58×78\times7
Salaisuusalue η\eta242
Haasteen paino τ\tau394960
Julkinen avain1 312 B1 952 B2 592 B
Allekirjoitus2 420 B3 309 B4 627 B
NIST-luokka235

Huomionarvoista: ML-DSA-87 ei ole yksinkertaisesti ”ML-DSA-65, vain isompana”. Salaisuusalue η\eta palaa arvosta 4 takaisin arvoon 2; turvallisuus tulee tässä suuremmasta matriisista eikä suuremmista kertoimista. Kyseessä on itsenäinen, standardoitu parametrivalinta.

suurempi matemaattinen rakenne→suurempi turvamarginaali\boxed{\text{suurempi matemaattinen rakenne}\rightarrow\text{suurempi turvamarginaali}}

Hinta: 4 627 tavua allekirjoitusta kohti — leimaa kohti, joka tallennetaan ja toimitetaan todennettaessa selaimelle. Siksi McGesundissa on ML-DSA-87:n rinnalla valittavissa myös FALCON, joka tulee toimeen 1 280 tavulla.

21. Fiat-Shamir: miksi se toimii ilman vastapuolta

Vuorovaikutteinen todistus etenisi näin:

  1. Allekirjoituspalvelu lähettää commitmentin.
  2. Todentaja lähettää satunnaisen haasteen.
  3. Allekirjoituspalvelu vastaa.
  4. Todentaja laskee tarkistukseksi.

Arvion kohdalla tätä vuoropuhelua ei ole — lukija saapuu kuukausia myöhemmin. Ratkaisu on Fiat-Shamir-muunnos: haastetta ei arvota, vaan se tiivistetään itse tiedoista:

c=H(julkinen avain,  viesti,  commitment).c=H(\text{julkinen avain},\;\text{viesti},\;\text{commitment}).

Näin vuoropuhelusta tulee asiakirja. Allekirjoituspalvelu ei voi valita haastettaan, sillä sen pitäisi sitä varten hallita tiivistefunktiota.

22. Koko kulku

ALLEKIRJOITUSPALVELU (MCGESUND)KÄVIJÄN SELAINyksityinen avain s₁, s₂payload m = {yritys, arvio, h, rh, iat}tiiviste μsatunnainen vektori ycommitment w = Ayhaaste c = H(μ, w)z = y + c · s₁allekirjoitus (c, z, vihjeet) + kidarvio + allekirjoitus + julk. avainAz − c·t → ylimmät bitit + vihjeethaasteen uudelleenlaskentauudelleen laskettu haaste = toimitettu?kelvollinenvirheellinenhylkää, jos z on liian suuri(rejection sampling)
Arvion koko matka. Katkoviivalla merkitty paluu on rejection sampling — se otetaan niin monta kertaa, kunnes z on riittävän pieni, ettei se paljasta mitään salaisesta avaimesta.

23. Mitä McGesund tekee tällä käytännössä

Kolme tasoa nivoutuu toisiinsa:

Envelope. Jokainen allekirjoitettu arvio kantaa Ed25519-allekirjoitusta. Se on pakollinen variantti — klassinen, hyvin pieni, natiivisti todennettavissa jokaisessa selaimessa.

Post-kvanttileimat. Lisäksi rinnalle voidaan asettaa yksi tai kaksi kvanttiresistenttiä allekirjoitusta. Mitkä, riippuu paketista:

Pakettikäytettävissä olevat allekirjoitustasot
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, molemmat rinnakkain

Rinnakkainen variantti on tarkoituksella redundantti. Jos toinen näistä matemaattisista perheistä — NTRU-hilat FALCONissa, moduulihilat ML-DSA:ssa — osoittautuisi heikommaksi kuin nykyisin oletetaan, toinen kantaa edelleen.

Aikaankkuri. Allekirjoitusavaimen sormenjälki ankkuroidaan OpenTimestampsin kautta Bitcoin-lohkoon. Siten voidaan osoittaa paitsi se, että allekirjoitus on aito, myös se, että se oli olemassa jo tiettynä ajankohtana — ilman että kenenkään täytyisi uskoa meidän aikaleimaamme.

Kaikki tämä todennetaan lukijan selaimessa WASM-moduulin kautta. Me toimitamme tiedot; uudelleenlaskenta tapahtuu kävijän laitteella. Jos poistuisimme huomenna verkosta, kerran ladattu arvio pysyisi todennettavissa.

24. ML-DSA ja FALCON rinnakkain

OminaisuusFALCON (FN-DSA)ML-DSA
Tyyppidigitaalinen allekirjoitusdigitaalinen allekirjoitus
HilaperheNTRUModule-LWE / Module-SIS
RengasZq[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
Ydinmekanismilyhyt vektori Gauss-otannallahaaste-vastaus keskeytyksin
FFT / NTTliukuluku-FFT, turvallisuuskriittinenNTT, vain aritmetiikkaa
Allekirjoituksen koko (korkein taso)1 280 B4 627 B
Toteutusvaativa (liukuluvut)verrattain suoraviivainen
Standardointisuunniteltu standardiksi FIPS 206 (FN-DSA), ei vielä valmisFIPS 204, valmis

Lyhyesti: ML-DSA on helpompi toteuttaa ja todentaa oikein, FALCON tuottaa selvästi tiiviimpiä allekirjoituksia. QR-koodissa ei ole kumpaakaan — siellä on yksin Ed25519-Envelope. Allekirjoituksen koko ratkaisee siksi tallennuksessa ja toimituksessa, robustius toteutuksessa. Siksi tarjoamme molempia.

25. Yksi lause mukaan otettavaksi

ML-DSA muodostaa lyhyesta¨ salaisesta vektorista vastauksen haasteeseen,joka on tiivistetty itse arviosta — ja jonka jokainenjulkisen avaimen haltija voi tarkistaa.\boxed{ \begin{array}{c} \text{ML-DSA muodostaa lyhyestä salaisesta vektorista vastauksen haasteeseen,}\\ \text{joka on tiivistetty itse arviosta — ja jonka jokainen}\\ \text{julkisen avaimen haltija voi tarkistaa.} \end{array}}

Se, jolla on salainen vektori, allekirjoittaa millisekunneissa. Sen, jolla sitä ei ole, olisi ratkaistava hilaongelma yli 14 000 ulottuvuudessa — myös kvanttitietokoneella.

Arvion lukijalle se tarkoittaa yksinkertaisesti: hänen ei tarvitse uskoa meitä. Hän voi laskea itse.