Μέθοδος υπογραφής

Το ML-DSA-87 εξηγημένο μαθηματικά

Πώς το ML-DSA-87 (FIPS 204) υπογράφει μια αξιολόγηση του McGesund — από το Module-LWE και τη δειγματοληψία απόρριψης έως τον έλεγχο στο πρόγραμμα περιήγησης.

Τελευταία ενημέρωση: 2026-09-07

1. Περί τίνος πρόκειται

Όταν κάποιος υποβάλλει μια αξιολόγηση στο McGesund, στο παρασκήνιο συμβαίνουν περισσότερα από όσα υποδηλώνει το κείμενο. Η αξιολόγηση υπογράφεται ψηφιακά κατά την υποβολή. Αυτή την υπογραφή μπορεί κάθε επισκέπτης να την επαληθεύσει αργότερα στο δικό του πρόγραμμα περιήγησης — χωρίς να μας εμπιστευτεί και χωρίς να μας ρωτήσει.

Για πελάτες από το πακέτο Pro και πάνω αυτό γίνεται μεταξύ άλλων με το ML-DSA-87. Αυτό το άρθρο εξηγεί τι συμβαίνει μαθηματικά.

Μια σημαντική διευκρίνιση εξαρχής:

Το ML-DSA δεν είναι κρυπτογράφηση. Το κείμενο της αξιολόγησης παραμένει δημόσια αναγνώσιμο — αυτό είναι άλλωστε το νόημα μιας αξιολόγησης. Το ML-DSA δεν αποδεικνύει μυστικότητα, αλλά προέλευση και ακεραιότητα.

Το ML-DSA αναπτύχθηκε από το CRYSTALS-Dilithium και έχει τυποποιηθεί ως FIPS 204. Ο αριθμός 87 δηλώνει το επίπεδο παραμέτρων. Υπάρχουν τρία:

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

Το ML-DSA-87 είναι το ανώτατο και ανήκει στην κατηγορία ασφάλειας 5 του NIST.

2. Τι ακριβώς υπογράφεται;

Στην υπογραφή δεν εισέρχεται το ίδιο το κείμενο της αξιολόγησης, αλλά ένα συμπαγές αντικείμενο δεδομένων που καθηλώνει μονοσήμαντα το κείμενο. Στο McGesund έχει στον πυρήνα του την εξής μορφή:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<αναγνωριστικό επιχείρησης>",
  "c":   "<αναγνωριστικό αξιολόγησης>",
  "h":   "<SHA-256 του κειμένου της αξιολόγησης>",
  "rh":  "<SHA-256 ολόκληρης της εγγραφής υποβολής>",
  "rv":  1,
  "qh":  "<SHA-256 του φακέλου QR, μόνο σε αξιολογήσεις μέσω QR>",
  "iat": 1757203200
}

Αυτό το αντικείμενο είναι το μήνυμά μας mm. Δεσμεύει μαζί έξι δηλώσεις:

  1. Σε ποια επιχείρηση ανήκει η αξιολόγηση (f)
  2. Ποια αξιολόγηση εννοείται (c)
  3. Ποιο κείμενο υπήρχε πίσω από αυτήν — ως τιμή κατακερματισμού (h)
  4. Ποια εγγραφή δεδομένων συνολικά υποβλήθηκε (rh): κείμενο, καρδιές, γεω-κατάσταση και στοιχεία αφορμής, κανονικά σειριοποιημένα και κατακερματισμένα — στην έκδοση σχήματος rv
  5. Από ποιον κωδικό QR προέρχεται η αξιολόγηση (qh)· χωρίς QR το πεδίο παραλείπεται
  6. Πότε έγινε η υπογραφή (iat)

Αν κάποιος αλλάξει αργότερα έναν και μόνο χαρακτήρα στο κείμενο της αξιολόγησης, το h δεν ταιριάζει πλέον — και ούτε το rh. Όποιος αντ' αυτού πειράξει μόνο τις καρδιές, αφήνει το h άθικτο αλλά σπάει το rh. Αν κάποιος αλλάξει μία από αυτές τις τιμές κατακερματισμού, η υπογραφή δεν ταιριάζει πλέον. Ακριβώς αυτή η αλυσίδα είναι το ζητούμενο.

3. Τι πρέπει να επιτυγχάνει η υπογραφή

Ένας επισκέπτης που διαβάζει την αξιολόγηση πρέπει να μπορεί να ελέγξει μόνος του τρία πράγματα:

  1. Η αξιολόγηση εκδόθηκε πράγματι από το McGesund.
  2. Το κείμενο δεν τροποποιήθηκε από την υποβολή του και μετά.
  3. Κανείς δεν μπορεί να επινοήσει μια νέα αξιολόγηση που να φαίνεται έγκυρη.

Για αυτό υπάρχει ένα ζεύγος κλειδιών:

  • ένα ιδιωτικό κλειδί — βρίσκεται αποκλειστικά στην υπηρεσία υπογραφής
  • ένα δημόσιο κλειδί — μπορεί να το έχει ο καθένας, προσδιορίζεται μέσω του αναγνωριστικού κλειδιού (kid) στον φάκελο

Η υπογραφή γίνεται με το ιδιωτικό κλειδί. Ο έλεγχος γίνεται με το δημόσιο — και μάλιστα στο πρόγραμμα περιήγησης του αναγνώστη, όχι στον δικό μας διακομιστή.

4. Γιατί εν γένει μια μετακβαντική μέθοδος;

Πολλές σημερινές συνήθεις μέθοδοι υπογραφής στηρίζονται στην παραγοντοποίηση μεγάλων αριθμών ή σε διακριτούς λογαρίθμους. Ένας επαρκώς ισχυρός κβαντικός υπολογιστής θα μπορούσε να λύσει ακριβώς αυτά τα προβλήματα σημαντικά ταχύτερα με γνωστούς αλγορίθμους.

Για μια αξιολόγηση αυτό δεν είναι ακαδημαϊκό ερώτημα. Μια αξιολόγηση πρέπει να είναι επαληθεύσιμη ακόμη και σε δέκα χρόνια. Όποιος υπογράφει σήμερα, υπογράφει για όλη τη διάρκεια ζωής της καταχώρισης.

Γι' αυτό το ML-DSA χρησιμοποιεί άλλη βάση:

Προβληˊματα πλεγμαˊτων\boxed{\text{Προβλήματα πλεγμάτων}}

Ακριβέστερα: Module-LWE και Module-SIS.

5. Τι είναι ένα πλέγμα;

Καταρχάς απλώς σημεία στον χώρο. Ας πάρουμε δύο διανύσματα:

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

Όλοι οι ακέραιοι συνδυασμοί

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

σχηματίζουν το πλέγμα. Για παράδειγμα:

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
Δύο διανύσματα, όλοι οι ακέραιοι συνδυασμοί τους: ένα πλέγμα. Το σημειωμένο σημείο προκύπτει από δύο φορές το b₁ και μία φορά το b₂.

Το καθοριστικό:

Σε μικρές διαστάσεις τα προβλήματα πλεγμάτων είναι εύκολα. Σε πολύ υψηλές διαστάσεις ορισμένα ερωτήματα γίνονται εξαιρετικά δύσκολα.

6. Πολυώνυμα αντί για μεμονωμένους αριθμούς

Το ML-DSA δεν υπολογίζει με διδιάστατα διανύσματα, αλλά με πολυώνυμα και διανύσματα πολυωνύμων.

Ένα πολυώνυμο όπως το

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

γράφεται ως λίστα συντελεστών:

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

Οι υπολογισμοί γίνονται σε έναν δακτύλιο:

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

Αυτό σημαίνει δύο πράγματα:

  • Zq\mathbb{Z}_q: υπολογισμός modulo qq
  • xn=−1x^n=-1: ένας πρόσθετος κανόνας που σταθεροποιεί το μήκος των πολυωνύμων

Για και τα τρία επίπεδα του ML-DSA ισχύει:

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

Ένα πολυώνυμο έχει επομένως 256 συντελεστές, θεωρούμενους modulo 8.380.417. Αυτό που αλλάζει ανάμεσα στα επίπεδα δεν είναι το nn ή το qq, αλλά το μέγεθος των πινάκων — περισσότερα γι' αυτό παρακάτω.

Παρεμπιπτόντως: ο πολλαπλασιασμός πολυωνύμων σε αυτόν τον δακτύλιο υλοποιείται στην πράξη μέσω του NTT, της θεωρητικοαριθμητικής παραλλαγής του ταχέος μετασχηματισμού Fourier. Το ML-DSA επομένως δεν αποφεύγει καθόλου τις ιδέες του FFT· απλώς αυτές βρίσκονται στην αριθμητική και όχι στην αρχή της υπογραφής.

7. Το κεντρικό τέχνασμα: Module-LWE

Η βασική ιδέα είναι το Module Learning With Errors:

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

Όπου:

  • A\mathbf{A} — δημόσιος, φαινομενικά τυχαίος πίνακας από πολυώνυμα
  • s1,s2\mathbf{s}_1,\mathbf{s}_2 — μικρά μυστικά διανύσματα
  • t\mathbf{t} — δημόσια τιμή

Ένας επιτιθέμενος γνωρίζει τα A\mathbf{A} και t\mathbf{t}, όχι όμως τα s1,s2\mathbf{s}_1,\mathbf{s}_2. Η εξίσωση του φαίνεται σαν μια τυχαία εξίσωση με θόρυβο. Τα μικρά μυστικά δεν πρέπει να μπορεί να τα υπολογίσει αντίστροφα με αποδοτικό τρόπο.

8. Ένα ελάχιστο αριθμητικό παράδειγμα

Παίρνουμε σκόπιμα μια γελοία μικρή παραλλαγή — κανονικούς αριθμούς αντί για πολυώνυμα, διάσταση 2 αντί για 256, και

q=17.q=17.

Έστω

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

Τότε:

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

Σε αυτή τη μικρογραφία θα μπορούσε κανείς να δοκιμάσει όλες τις δυνατότητες. Στο ML-DSA-87 ο A\mathbf{A} είναι πίνακας 8×78\times 7 από πολυώνυμα με 256 συντελεστές το καθένα — πρόκειται για πάνω από 14.000 αγνώστους στη δομή του πλέγματος.

9. Το ζεύγος κλειδιών της υπηρεσίας υπογραφής

Το ιδιωτικό κλειδί περιέχει μεταξύ άλλων τα μικρά διανύσματα s1,s2\mathbf{s}_1,\mathbf{s}_2. Στο ML-DSA-87 οι συντελεστές τους προέρχονται από το διάστημα

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

δηλαδή από το {−2,−1,0,1,2}\{-2,-1,0,1,2\}. Αυτή η μικρότητα δεν είναι λεπτομέρεια, αλλά ο πυρήνας: μόνο επειδή τα μυστικά είναι μικρά προκύπτει καν ένα δύσκολο πρόβλημα πλέγματος.

Το δημόσιο κλειδί είναι απλοποιημένα

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

Το ρ\rho είναι ένα seed από το οποίο ο A\mathbf{A} ανακατασκευάζεται ντετερμινιστικά — ο πίνακας επομένως δεν χρειάζεται να μεταδοθεί. Το t1\mathbf{t}_1 είναι τα ανώτερα bit του t\mathbf{t}· τα κατώτερα d=13d=13 bit παραλείπονται, γεγονός που μικραίνει σημαντικά το κλειδί. Αυτή η παράλειψη είναι αργότερα ο λόγος για τις λεγόμενες υποδείξεις.

Έτσι προκύπτει η επιθυμητή ασυμμετρία:

δημοˊσιος εˊλεγχος  ≠  μυστικηˊ υπογραφηˊ\boxed{\text{δημόσιος έλεγχος}\;\neq\;\text{μυστική υπογραφή}}

10. Η αξιολόγηση γίνεται αριθμός

Η υπηρεσία υπογραφής κατακερματίζει πρώτα το αντικείμενο payload της ενότητας 2:

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

Στο παράδειγμα-παιχνίδι μας παίρνουμε έναν τεχνητό μικρο-κατακερματισμό. Στο πραγματικό σύστημα το μ\mu έχει μήκος 512 bit και δεσμεύει επιπλέον και το δημόσιο κλειδί — έτσι μια υπογραφή δεν μπορεί να επαναπροσδιοριστεί ως υπογραφή άλλου κλειδιού.

11. Δέσμευση

Η υπηρεσία υπογραφής επιλέγει ένα τυχαίο μικρό διάνυσμα y\mathbf{y}. Στο παράδειγμά μας:

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

Από αυτό προκύπτει μια ενδιάμεση τιμή, η δέσμευση:

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

Αυτό δεν είναι ακόμη υπογραφή.

12. Από την αξιολόγηση προκύπτει μια πρόκληση

Μήνυμα και δέσμευση κατακερματίζονται μαζί:

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

Στο ML-DSA-87 το cc είναι ένα πολυώνυμο με ακριβώς τ=60\tau=60 συντελεστές από το {−1,+1}\{-1,+1\}, ενώ όλοι οι υπόλοιποι 196 είναι μηδέν. Αυτή η δομή είναι σκόπιμη: κρατά το c⋅s1c\cdot\mathbf{s}_1 μικρό.

Στο παράδειγμα-παιχνίδι μας θέτουμε απλώς

c=2.c=2.

13. Η καθαυτό υπογραφή

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

Με τις τιμές μας:

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. Το βήμα που εύκολα προσπερνά κανείς: η δειγματοληψία απόρριψης

Εδώ βρίσκεται το σημείο στο οποίο το ML-DSA διαφέρει από μια αφελή κατασκευή — και δεν είναι προαιρετικό.

Το z=y+c s1\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1 περιέχει το μυστικό s1\mathbf{s}_1. Αν εξέδιδε κανείς πάντα απλώς το z\mathbf{z}, το s1\mathbf{s}_1 θα μπορούσε να υπολογιστεί στατιστικά από αρκετά πολλές υπογραφές. Σε μια πλατφόρμα αξιολογήσεων με πάρα πολλές υπογραφές την ημέρα αυτός δεν είναι θεωρητικός κίνδυνος.

Γι' αυτό η υπηρεσία υπογραφής ελέγχει πριν από την έκδοση αν το z\mathbf{z} αποκαλύπτει υπερβολικά πολλά, και απορρίπτει διαφορετικά την υπογραφή — τότε ξεκινά από την αρχή με ένα νέο τυχαίο y\mathbf{y}. Αυτό ονομάζεται Fiat-Shamir with Aborts.

Η συνθήκη είναι κατ' ουσίαν:

∥z∥∞<γ1−β.\|\mathbf{z}\|_\infty < \gamma_1-\beta.
Δέσμευση w = AyΠρόκληση c = H(μ, w)Απάντηση z = y + c · s₁‖z‖∞ < γ₁ − β ;ναιΗ υπογραφή εκδίδεταιόχι — νέο y
Τρία βήματα και ένας βρόχος. Αν το z βγει πολύ μεγάλο, δεν διορθώνεται — ολόκληρο το πέρασμα απορρίπτεται και ξεκινά εκ νέου με ένα φρέσκο τυχαίο y. Γι' αυτό η υπογραφή είναι εδώ διαδικασία με βρόχο.

Για το ML-DSA-87 ισχύουν γ1=219\gamma_1=2^{19} και β=τ⋅η=60⋅2=120\beta=\tau\cdot\eta=60\cdot2=120. Προστίθεται ένα δεύτερο όριο στα κατώτερα bit. Στην πράξη είναι φυσιολογικά τα πολλαπλά περάσματα — η υπογραφή είναι επομένως διαδικασία με βρόχο, όχι ένα μεμονωμένο βήμα.

Για την επαλήθευση είναι σημαντικό: ακριβώς αυτό το όριο το ελέγχει αργότερα και το πρόγραμμα περιήγησης. Μια υπογραφή με υπερβολικά μεγάλους συντελεστές απορρίπτεται, ακόμη κι αν η εξίσωση επαληθεύεται.

15. Γιατί το πρόγραμμα περιήγησης μπορεί να το ελέγξει

Το πρόγραμμα περιήγησης του αναγνώστη γνωρίζει:

  • την αξιολόγηση και μαζί της το mm
  • το δημόσιο κλειδί (ρ,t1)(\rho,\mathbf{t}_1)
  • την υπογραφή (c~,z,h)(\tilde c,\mathbf{z},\mathbf{h})

Το s1\mathbf{s}_1 δεν το γνωρίζει. Η σχέση που το βοηθά παρ' όλα αυτά:

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.

Και επειδή ισχύει

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

το άγνωστο As1A\mathbf{s}_1 μπορεί να αντικατασταθεί από τη δημόσια τιμή:

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

Αυτή είναι η κεντρική εξίσωση — και λέει κάτι σημαντικό: το πρόγραμμα περιήγησης ανακατασκευάζει το AyA\mathbf{y} όχι ακριβώς, αλλά μόνο με ακρίβεια μέχρι τον μικρό όρο c s2c\,\mathbf{s}_2.

16. Το μικρο-παράδειγμα ως το τέλος

Είχαμε:

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

Ας υπολογίσουμε:

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

Η αρχική δέσμευση ήταν

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

Η διαφορά είναι

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

Δηλαδή ακριβώς ο μικρός όρος σφάλματος που είχε προβλεφθεί. Ο επαληθευτής δεν λαμβάνει το w\mathbf{w}, αλλά κάτι που βρίσκεται κοντά στο w\mathbf{w}.

Ακριβώς γι' αυτό το ML-DSA δεν συγκρίνει τις ίδιες τις τιμές, αλλά τα ανώτερα bit τους. Και ακριβώς γι' αυτό η υπογραφή περιέχει επιπλέον ένα διάνυσμα υποδείξεων h\mathbf{h}: γνωστοποιεί συμπαγώς σε ποια σημεία η στρογγυλοποίηση ανατράπηκε πάνω από ένα όριο εξαιτίας του μικρού όρου σφάλματος. Στο ML-DSA-87 επιτρέπονται το πολύ ω=75\omega=75 τέτοιες υποδείξεις. Δεν αποκαλύπτουν το μυστικό — απλώς επιδιορθώνουν τη στρογγυλοποίηση.

Στο τέλος το πρόγραμμα περιήγησης υπολογίζει εκ νέου την πρόκληση. Αν συμφωνεί,

cνεˊο=c,c_{\text{νέο}}=c,

και αν όλες οι νόρμες βρίσκονται εντός των ορίων, η υπογραφή είναι έγκυρη.

17. Τι συμβαίνει αν κάποιος αλλάξει την αξιολόγηση;

Ας υποθέσουμε ότι κάποιος με πρόσβαση στη βάση δεδομένων — ακόμη και κάποιος από εμάς — αλλάζει το κείμενο της αξιολόγησης ή μία από τις καρδιές. Τότε αλλάζει τουλάχιστον μία από τις δύο τιμές κατακερματισμού στο payload (h στο κείμενο, rh σε κάθε πεδίο της εγγραφής δεδομένων):

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

Έτσι αλλάζει η πρόκληση:

c≠c′.c\neq c'.

Η υπάρχουσα υπογραφή όμως δημιουργήθηκε για την παλιά πρόκληση. Το πρόγραμμα περιήγησης υπολογίζει και διαπιστώνει:

cνεˊο≠cυπογραφηˊς⟹Άκυρη υπογραφηˊc_{\text{νέο}}\neq c_{\text{υπογραφής}} \quad\Longrightarrow\quad \boxed{\text{Άκυρη υπογραφή}}

Η καθοριστική πρόταση: μπορούμε να διαγράψουμε μια αξιολόγηση, δεν μπορούμε όμως να την αλλάξουμε απαρατήρητα. Στο McGesund ο ίδιος έλεγχος τρέχει επιπλέον κάθε νύχτα στην πλευρά του διακομιστή σε όλο το απόθεμα — μια αξιολόγηση που δεν περνά αυτόν τον έλεγχο δεν συνυπολογίζεται πλέον στον μέσο όρο της επιχείρησης.

18. Γιατί δεν μπορεί κανείς να επινοήσει υπογραφή;

Ένας επιτιθέμενος γνωρίζει τα A\mathbf{A} και t\mathbf{t}, όχι όμως τα s1,s2\mathbf{s}_1,\mathbf{s}_2. Για να κατασκευάσει μια έγκυρη υπογραφή θα έπρεπε να βρει μια τριάδα (c~,z,h)(\tilde c,\mathbf{z},\mathbf{h}) που

  • ικανοποιεί την εξίσωση επαλήθευσης και
  • τηρεί τα όρια των νορμών και
  • ταιριάζει με την πρόκληση που προκύπτει από αυτές ακριβώς τις τιμές.

Αυτό καταλήγει στον πυρήνα του σε ένα δύσκολο πρόβλημα πλέγματος — συγκεκριμένα στο Module-SIS: την εύρεση σύντομων λύσεων μιας ομογενούς εξίσωσης modulo qq. Η συνθήκη μικρότητας δεν είναι εδώ διακοσμητική, αλλά ο ίδιος ο βαθμός δυσκολίας. Χωρίς αυτήν μια λύση θα ήταν τετριμμένη.

δημοˊσια δεδομεˊνα  →  δυˊσκολο προˊβλημα πλεˊγματος\boxed{\text{δημόσια δεδομένα}\;\rightarrow\;\text{δύσκολο πρόβλημα πλέγματος}}

19. Γιατί «Module»;

Η λέξη περιγράφει τη δομή ανάμεσα στα απλά διανύσματα και στα γενικά πλέγματα. Αντί να υπολογίζει με μεμονωμένους αριθμούς, το ML-DSA εργάζεται με διανύσματα πολυωνύμων:

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

και με πίνακες από αυτά:

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

Το πλεονέκτημα: αποκτά κανείς την υψηλή διάσταση ενός πλέγματος, διατηρώντας όμως μια συμπαγή, αποδοτικά υπολογίσιμη αναπαράσταση. Η ασφάλεια ρυθμίζεται με ακρίβεια μέσω του μεγέθους του πίνακα, χωρίς αλλαγή δακτυλίου.

20. Γιατί ακριβώς 87;

Τα τρία επίπεδα δεν διαφέρουν στον δακτύλιο, αλλά στις διαστάσεις:

ΠαράμετροςML-DSA-44ML-DSA-65ML-DSA-87
Μέγεθος πίνακα (k,ℓ)(k,\ell)4×44\times46×56\times58×78\times7
Εύρος μυστικού η\eta242
Βάρος πρόκλησης τ\tau394960
Δημόσιο κλειδί1.312 B1.952 B2.592 B
Υπογραφή2.420 B3.309 B4.627 B
Κατηγορία NIST235

Αξιοσημείωτο: το ML-DSA-87 δεν είναι απλώς «ML-DSA-65, μόνο μεγαλύτερο». Το εύρος του μυστικού η\eta επιστρέφει από το 4 πάλι στο 2· η ασφάλεια προέρχεται εδώ από τον μεγαλύτερο πίνακα, όχι από μεγαλύτερους συντελεστές. Πρόκειται για μια αυτοτελή, τυποποιημένη επιλογή παραμέτρων.

μεγαλυˊτερη μαθηματικηˊ δομηˊ→υψηλοˊτερο περιθωˊριο ασφαˊλειας\boxed{\text{μεγαλύτερη μαθηματική δομή}\rightarrow\text{υψηλότερο περιθώριο ασφάλειας}}

Το τίμημα: 4.627 byte ανά υπογραφή — ανά σφραγίδα που αποθηκεύεται και παραδίδεται στο πρόγραμμα περιήγησης κατά τον έλεγχο. Γι' αυτό στο McGesund προσφέρεται δίπλα στο ML-DSA-87 και το FALCON, που αρκείται σε 1.280 byte.

21. Fiat-Shamir: γιατί λειτουργεί χωρίς συνομιλητή

Μια διαδραστική απόδειξη θα εξελισσόταν ως εξής:

  1. Η υπηρεσία υπογραφής στέλνει μια δέσμευση.
  2. Ο ελεγκτής στέλνει μια τυχαία πρόκληση.
  3. Η υπηρεσία υπογραφής απαντά.
  4. Ο ελεγκτής επαληθεύει.

Σε μια αξιολόγηση δεν υπάρχει αυτός ο διάλογος — ο αναγνώστης έρχεται μήνες αργότερα. Η λύση είναι ο μετασχηματισμός Fiat-Shamir: η πρόκληση δεν επιλέγεται με ζάρια, αλλά προκύπτει από τον κατακερματισμό των ίδιων των δεδομένων:

c=H(δημοˊσιο κλειδιˊ,  μηˊνυμα,  δεˊσμευση).c=H(\text{δημόσιο κλειδί},\;\text{μήνυμα},\;\text{δέσμευση}).

Έτσι ένας διάλογος μετατρέπεται σε έγγραφο. Η υπηρεσία υπογραφής δεν μπορεί να διαλέξει την πρόκληση, γιατί γι' αυτό θα έπρεπε να ελέγχει τον κατακερματισμό.

22. Η συνολική ροή

ΥΠΗΡΕΣΊΑ ΥΠΟΓΡΑΦΉΣ (MCGESUND)ΠΡΌΓΡΑΜΜΑ ΠΕΡΙΉΓΗΣΗΣ ΤΟΥ ΕΠΙΣΚΈΠΤΗιδιωτικό κλειδί s₁, s₂Payload m = {επιχείρηση, αξιολόγηση, h, rh, iat}Κατακερματισμός μτυχαίο διάνυσμα yΔέσμευση w = AyΠρόκληση c = H(μ, w)z = y + c · s₁Υπογραφή (c, z, υποδείξεις) + kidΑξιολόγηση + υπογραφή + δημόσιο κλειδίAz − c·t → ανώτερα bit + υποδείξειςνέος υπολογισμός της πρόκλησηςνέα πρόκληση = η παραδοθείσα;έγκυρηάκυρηαπόρριψη, αν το z είναι πολύ μεγάλο(δειγματοληψία απόρριψης)
Ολόκληρη η διαδρομή μιας αξιολόγησης. Η διακεκομμένη επιστροφή είναι η δειγματοληψία απόρριψης — ακολουθείται τόσες φορές μέχρι το z να είναι αρκετά μικρό ώστε να μην αποκαλύπτει τίποτα για το μυστικό κλειδί.

23. Τι κάνει συγκεκριμένα το McGesund με αυτό

Τρία επίπεδα αλληλοσυμπληρώνονται:

Ο φάκελος. Κάθε υπογεγραμμένη αξιολόγηση φέρει μια υπογραφή Ed25519. Αυτή είναι η υποχρεωτική εκδοχή — κλασική, ελάχιστη σε μέγεθος, ελέγξιμη εγγενώς σε κάθε πρόγραμμα περιήγησης.

Οι μετακβαντικές σφραγίδες. Επιπλέον μπορούν να τοποθετηθούν δίπλα της μία ή δύο κβαντικά ανθεκτικές υπογραφές. Ποιες, εξαρτάται από το πακέτο:

Πακέτοδιαθέσιμα επίπεδα υπογραφής
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, και τα δύο παράλληλα

Η παράλληλη εκδοχή είναι σκόπιμα πλεονάζουσα. Αν μία από τις δύο μαθηματικές οικογένειες — πλέγματα NTRU στο FALCON, πλέγματα Module στο ML-DSA — αποδειχθεί ασθενέστερη από ό,τι υποθέτουμε σήμερα, η άλλη εξακολουθεί να ισχύει.

Το χρονικό αγκύρωμα. Το αποτύπωμα του κλειδιού υπογραφής αγκυρώνεται μέσω OpenTimestamps σε ένα μπλοκ του Bitcoin. Έτσι μπορεί να αποδειχθεί όχι μόνο ότι η υπογραφή είναι γνήσια, αλλά και ότι υπήρχε ήδη σε συγκεκριμένη χρονική στιγμή — χωρίς να χρειάζεται κανείς να πιστέψει τη δική μας χρονοσήμανση.

Όλα αυτά ελέγχονται στο πρόγραμμα περιήγησης του αναγνώστη, μέσω ενός αρθρώματος WASM. Εμείς παρέχουμε τα δεδομένα· ο υπολογισμός γίνεται στη συσκευή του επισκέπτη. Αν αύριο βγαίναμε εκτός δικτύου, μια αξιολόγηση που έχει ήδη ληφθεί θα παρέμενε επαληθεύσιμη.

24. ML-DSA και FALCON δίπλα δίπλα

ΙδιότηταFALCON (FN-DSA)ML-DSA
Τύποςψηφιακή υπογραφήψηφιακή υπογραφή
Οικογένεια πλεγμάτωνNTRUModule-LWE / Module-SIS
ΔακτύλιοςZq[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
Βασικός μηχανισμόςσύντομο διάνυσμα μέσω δειγματοληψίας Gaussπρόκληση-απάντηση με απορρίψεις
FFT / NTTFFT κινητής υποδιαστολής, κρίσιμη για την ασφάλειαNTT, μόνο αριθμητική
Μέγεθος υπογραφής (ανώτατο επίπεδο)1.280 B4.627 B
Υλοποίησηαπαιτητική (κινητή υποδιαστολή)συγκριτικά ευθύγραμμη
Τυποποίησηπροβλέπεται ως FIPS 206 (FN-DSA), δεν έχει ακόμη ολοκληρωθείFIPS 204, ολοκληρωμένη

Με λίγα λόγια: το ML-DSA υλοποιείται και ελέγχεται σωστά ευκολότερα, το FALCON παρέχει σαφώς πιο συμπαγείς υπογραφές. Στον κωδικό QR δεν βρίσκεται καμία από τις δύο — εκεί υπάρχει μόνο ο φάκελος Ed25519. Το μέγεθος της υπογραφής μετρά επομένως στην αποθήκευση και την παράδοση, η ευρωστία στην υλοποίηση. Γι' αυτό προσφέρουμε και τα δύο.

25. Μια πρόταση για να κρατήσετε

Το ML-DSA παραˊγει αποˊ εˊνα συˊντομο μυστικοˊ διαˊνυσμα μια απαˊντηση σεμια προˊκληση που προηˊλθε αποˊ την ιˊδια την αξιολοˊγηση — ελεˊγξιμηαποˊ καθεˊναν με το δημοˊσιο κλειδιˊ.\boxed{ \begin{array}{c} \text{Το ML-DSA παράγει από ένα σύντομο μυστικό διάνυσμα μια απάντηση σε}\\ \text{μια πρόκληση που προήλθε από την ίδια την αξιολόγηση — ελέγξιμη}\\ \text{από καθέναν με το δημόσιο κλειδί.} \end{array}}

Όποιος κατέχει το μυστικό διάνυσμα, υπογράφει σε χιλιοστά του δευτερολέπτου. Όποιος δεν το κατέχει, θα έπρεπε να λύσει ένα πρόβλημα πλέγματος σε πάνω από 14.000 διαστάσεις — ακόμη και με κβαντικό υπολογιστή.

Για τον αναγνώστη μιας αξιολόγησης αυτό σημαίνει απλώς: δεν χρειάζεται να μας πιστέψει. Μπορεί να το επαληθεύσει.