Το FALCON εξηγημένο μαθηματικά

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

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

Για ένα μέρος αυτών των υπογραφών χρησιμοποιούμε το FALCON — ακριβέστερα τα FN-DSA-512 και FN-DSA-1024. Αυτό το άρθρο εξηγεί τι συμβαίνει μαθηματικά.

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

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

---

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

Δεν υπογράφεται το ελεύθερο κείμενο, αλλά ένα συμπαγές αντικείμενο δεδομένων που καθηλώνει μονοσήμαντα το κείμενο:

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

Αυτό είναι το μήνυμά μας $m$. Δεσμεύει μαζί:

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

Ένας αλλαγμένος χαρακτήρας στο κείμενο της αξιολόγησης σπάει αυτή την αλυσίδα. Αυτός ακριβώς είναι ο σκοπός — και από το rh και μετά το ίδιο ισχύει για μια εκ των υστέρων μετακινημένη καρδιά ή μια αλλαγμένη γεω-κατάσταση.

---

3. Το βασικό πρόβλημα

Ένας αναγνώστης που φτάνει σε ένα προφίλ επιχείρησης έχει δύο ερωτήματα:

1. Προέρχεται πράγματι αυτή η αξιολόγηση από το σύστημα του McGesund;
2. Τροποποιήθηκε εκ των υστέρων;

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

• ένα ιδιωτικό κλειδί — παραμένει στην υπηρεσία υπογραφής
• ένα δημόσιο κλειδί — μπορεί να το έχει ο καθένας

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

---

4. Γιατί FALCON;

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

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

Γι' αυτό το FALCON στηρίζεται στην κρυπτογραφία πλεγμάτων:

Κατασκευάζεται ένα πλέγμα που περιγράφεται μαθηματικά με απλό τρόπο, μέσα στο οποίο μια συγκεκριμένη αναζήτηση είναι εξαιρετικά δύσκολη.

---

5. Τι είναι ένα μαθηματικό πλέγμα;

Δύο διανύσματα:

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

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

Το καθοριστικό είναι:

Το ίδιο το πλέγμα περιγράφεται εύκολα. Η εύρεση ορισμένων ιδιοτήτων μέσα σε αυτό είναι πολύ δύσκολη.

---

6. Το μυστικό είναι τα σύντομα διανύσματα

Το κλασικό δύσκολο ερώτημα είναι:

Αυτό είναι το πρόβλημα του συντομότερου διανύσματος (Shortest Vector Problem). Σε δύο διαστάσεις μπορεί κανείς να το λύσει με εξαντλητική δοκιμή. Το FALCON εργάζεται σε διάσταση 512 ή 1024 — εκεί δεν υπάρχει καμία προοπτική.

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

---

7. Πολυώνυμα αντί για αριθμούς

Το FALCON χρησιμοποιεί ένα πλέγμα NTRU και υπολογίζει με πολυώνυμα. Δηλαδή αντί για μεμονωμένους αριθμούς, με λίστες συντελεστών:

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

Αυτό σημαίνει:

• $\mathbb{Z}_q$: υπολογισμός modulo $q$. Με $q=7$ για παράδειγμα $10\equiv3$, αφού $10-7=3$.
• $x^n=-1$: κρατά τα πολυώνυμα σε σταθερό μήκος.

Το FALCON χρησιμοποιεί συγκεκριμένα:

---

8. Το κεντρικό τέχνασμα

Το ιδιωτικό κλειδί αποτελείται από τέσσερα μικρά πολυώνυμα

με την εξίσωση NTRU

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

Το δημόσιο κλειδί είναι κατ' ουσίαν ένα και μόνο πολυώνυμο:

Από το $h$ προκύπτει το ίδιο πλέγμα, αλλά σε μια δύσχρηστη βάση από μακριά διανύσματα:

Αυτός είναι όλος ο πυρήνας του FALCON. Και οι δύο βάσεις περιγράφουν το ίδιο πλέγμα. Απλώς η μία είναι χρήσιμη για υπολογισμούς και η άλλη όχι.

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

---

9. Η αξιολόγηση γίνεται σημείο

Πριν από την υπογραφή, το αντικείμενο payload περνά από μια συνάρτηση κατακερματισμού. Το FALCON χρησιμοποιεί γι' αυτό το Hash-to-Point: από το μήνυμα δεν προκύπτει αριθμητική τιμή, αλλά απευθείας ένα σημείο στον δακτύλιο.

Επιπλέον η υπηρεσία υπογραφής επιλέγει ένα τυχαίο salt $r$ (320 bit) και το συμπεριλαμβάνει στον κατακερματισμό:

Το salt δεν είναι διακοσμητικό. Χωρίς αυτό η ίδια αξιολόγηση θα έδινε πάντα την ίδια υπογραφή, και από πολλές υπογραφές θα μπορούσε να ανακατασκευαστεί η μυστική βάση. Γι' αυτό ταξιδεύει μαζί μέσα στην υπογραφή.

---

10. Τι είναι μια έγκυρη υπογραφή

Ζητείται ένα ζεύγος

με δύο ιδιότητες:

Η πρώτη συνθήκη από μόνη της ικανοποιείται τετριμμένα — θέτει κανείς $s_2=0$ και $s_1=c$. Η δεύτερη συνθήκη κάνει το πρόβλημα δύσκολο.

---

11. Ένα πλήρως λυμένο μικρο-παράδειγμα

Συρρικνώνουμε τα πάντα σε μέγεθος παιχνιδιού: πολυώνυμα με έναν μόνο συντελεστή, δηλαδή συνηθισμένους αριθμούς, και

Το μυστικό κλειδί. Δύο μικροί αριθμοί:

Το δημόσιο κλειδί. Ισχύει $3^{-1}\equiv65 \pmod{97}$, αφού $3\cdot65=195=2\cdot97+1$. Άρα:

Το πλέγμα. $L=\{(s_1,s_2): s_1+34\,s_2\equiv0 \pmod{97}\}$.

Η δημόσια βάση προκύπτει απευθείας από το $h$:

Και τα δύο ανήκουν στο $L$ — και τα δύο είναι μακριά.

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

αφού $-5+34\cdot3=97\equiv0$ και $-9+34\cdot(-14)=-485=-5\cdot97\equiv0$. Η ορίζουσα είναι

άρα η εξίσωση NTRU επαληθεύεται. Και τα δύο διανύσματα είναι σύντομα.

---

Βήμα 1: Κατακερματισμός της αξιολόγησης

Ας υποθέσουμε ότι το αντικείμενο payload της αξιολόγησης δίνει

Βήμα 2: Μια πρώτη, κακή λύση

ικανοποιεί $71+34\cdot0=71\equiv c$. Το μήκος όμως είναι $71$ — πολύ μεγάλο.

Βήμα 3: Συντόμευση με τη μυστική βάση

Η υπηρεσία υπογραφής εκφράζει το σημείο-στόχο στη σύντομη βάση της:

Αυτό οδηγεί σε $a\approx-10{,}25$ και $b\approx-2{,}20$. Στρογγυλοποιώντας σε $a=-10$, $b=-2$ προκύπτει το σημείο πλέγματος

Έλεγχος: $68+34\cdot(-2)=68-68=0$, άρα πράγματι ανήκει στο $L$. Αφαίρεση:

Μήκος:

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

Βήμα 4: Η ίδια μέθοδος με τη δημόσια βάση

Όποιος γνωρίζει μόνο το $h=34$, έχει τη βάση $\{(97,0),(-34,1)\}$. Ο ίδιος υπολογισμός στρογγυλοποίησης δίνει εκεί το σημείο πλέγματος $(97,0)$ και επομένως

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

Αυτή είναι η καταπακτή του FALCON σε μία γραμμή.

Βήμα 5: Το πρόγραμμα περιήγησης ελέγχει

Το πρόγραμμα περιήγησης λαμβάνει την αξιολόγηση, το salt και το $s_2=2$. Υπολογίζει ξανά τον κατακερματισμό, παίρνει $c=71$, ανακατασκευάζει

και ελέγχει το μήκος:

Βήμα 6: Κάποιος αλλάζει το κείμενο της αξιολόγησης

Αν το κείμενο αλλάξει εκ των υστέρων, αλλάζει ο κατακερματισμός περιεχομένου και μαζί του το σημείο, ας πούμε

Η παλιά υπογραφή παραμένει $(3,2)$, όμως

Μπορούμε να διαγράψουμε μια αξιολόγηση. Δεν μπορούμε όμως να την τροποποιήσουμε χωρίς να γίνει αντιληπτό.

Μια ειλικρινής επισήμανση για το παράδειγμα

Σε δύο διαστάσεις ένας επιτιθέμενος μπορεί να βρει σύντομες λύσεις με απλή δοκιμή — για $c'=40$ π.χ. το $(6,1)$. Το παράδειγμα δεν είναι ασφαλές· δείχνει μόνο τον μηχανισμό. Στο FALCON-1024 το διάνυσμα έχει 2048 συντελεστές, και εκεί η εξαντλητική δοκιμή δεν οδηγεί πουθενά.

---

12. Γιατί δεν γίνεται απλώς στρογγυλοποίηση;

Η μέθοδος του βήματος 3 ονομάζεται στρογγυλοποίηση Babai. Για ένα διδακτικό παράδειγμα αρκεί — για μια πραγματική μέθοδο υπογραφής όχι.

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

Γι' αυτό το FALCON αντλεί τα σύντομα διανύσματα από μια διακριτή κατανομή Gauss πάνω στο πλέγμα:

Τιμές κοντά στο σημείο-στόχο είναι πιθανότερες, αλλά ποια ακριβώς επιλέγεται είναι τυχαίο. Το αποτέλεσμα είναι μια κατανομή που δεν αποκαλύπτει τίποτα για τη βάση που χρησιμοποιήθηκε — μαθηματικά: δεν διακρίνεται από μια κατανομή που εξαρτάται μόνο από το ίδιο το πλέγμα.

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

---

13. Τι μεταδίδεται στην πραγματικότητα

Η υπογραφή αποτελείται από

Μόνο το $s_2$ — όχι το ζεύγος. Το $s_1$ το υπολογίζει ο ελεγκτής μόνος του:

Επειδή οι συντελεστές του $s_2$ είναι μικροί και κατανέμονται γύρω από το μηδέν, συμπιέζονται πολύ αποτελεσματικά. Αυτός είναι ο λόγος για τις εντυπωσιακά συμπαγείς υπογραφές του FALCON:

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

---

14. Γιατί το FALCON ελέγχει γρήγορα

Ο αφελής πολλαπλασιασμός πολυωνύμων κοστίζει

Με τον ταχύ μετασχηματισμό Fourier αυτό μειώνεται περίπου σε

Με $n=1024$ αυτό είναι η διαφορά ανάμεσα σε ένα εκατομμύριο και περίπου δέκα χιλιάδες πράξεις. Γι' αυτό ο έλεγχος στο πρόγραμμα περιήγησης ενός επισκέπτη ολοκληρώνεται σε χιλιοστά του δευτερολέπτου — και γι' αυτό υπάρχει το F στο όνομα:

FAst Fourier Lattice-based COmpact signatures over NTRU.

---

15. Η ροή σε εικόνα

---

16. Γιατί αποτυγχάνει ένας επιτιθέμενος

Γνωρίζει το $h$ και μαζί του ολόκληρο το πλέγμα. Γνωρίζει επίσης το σημείο-στόχο $c$, μόλις η αξιολόγηση δημοσιευθεί. Αυτό που του λείπει είναι η σύντομη βάση.

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

Σε διάσταση 1024 οι καλύτερες γνωστές μέθοδοι — κλασικές όσο και κβαντικές — απέχουν πολύ από αυτό.

---

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

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

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

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

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

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

Για την κατάταξη των ονομάτων: το FALCON τυποποιείται προς το παρόν ως FN-DSA· το σχέδιο προορίζεται ως FIPS 206, δεν έχει όμως ακόμη ολοκληρωθεί. Γι' αυτό τα επίπεδα ονομάζονται στον κώδικα του McGesund FN-DSA-512 και FN-DSA-1024, ακόμη κι αν στην καθομιλουμένη εξακολουθεί να γίνεται λόγος για FALCON.

---

18. Η σημαντικότερη διαίσθηση

Το δημόσιο κλειδί είναι η πλήρης περιγραφή ενός λαβυρίνθου. Καθένας μπορεί να τη δει.

Η υπογραφή είναι η απόδειξη: «Για αυτή ακριβώς την αξιολόγηση βρήκα μια πολύ σύντομη διαδρομή.»

Το ιδιωτικό κλειδί είναι η γνώση των συντομεύσεων.

Ο αναγνώστης δεν χρειάζεται να γνωρίζει τις συντομεύσεις. Απλώς μετρά αν η διαδρομή που του παρουσιάζεται είναι πράγματι σύντομη και ανήκει πράγματι σε αυτή την αξιολόγηση. Και τα δύο μπορεί να τα κάνει χωρίς εμάς.

Όποιος αλλάξει το κείμενο, μετακινεί το σημείο — και η παλιά διαδρομή οδηγεί στο κενό.