Είναι ακόμη ασφαλή τα μετακβαντικά πρότυπα κρυπτογραφίας του NIST; Νέα κβαντικά αποτελέσματα και το πρόβλημα Dihedral Coset

Τι αντικαθιστούν τα νέα μετακβαντικά πρότυπα του NIST

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

• το Πρόβλημα Παραγοντοποίησης Ακεραίων (IFP): RSA, που χρησιμοποιείται για κρυπτογράφηση, εγκαθίδρυση κλειδιών και ψηφιακές υπογραφές·
• το Πρόβλημα Διακριτού Λογαρίθμου σε πεπερασμένα σώματα (DLP): Diffie-Hellman (DH) για εγκαθίδρυση κλειδιών και DSA για ψηφιακές υπογραφές· και
• το Πρόβλημα Διακριτού Λογαρίθμου Ελλειπτικών Καμπυλών (ECDLP): elliptic-curve Diffie-Hellman (ECDH) για εγκαθίδρυση κλειδιών, και σχήματα υπογραφής ελλειπτικών καμπυλών όπως ECDSA και EdDSA για ψηφιακές υπογραφές.

Τα RSA, ECDSA, EdDSA και ECDH χρησιμοποιούνται ευρέως για την προστασία της παγκόσμιας ψηφιακής υποδομής, συμπεριλαμβανομένων του Διαδικτύου, των χρηματοπιστωτικών συστημάτων, των κυβερνητικών και στρατιωτικών επικοινωνιών, των ενημερώσεων λογισμικού, των ασφαλών μηνυμάτων και των υπηρεσιών cloud. Αποτελούν επίσης κρίσιμο μέρος της αρχιτεκτονικής ασφάλειας των συστημάτων blockchain και ψηφιακών περιουσιακών στοιχείων. Ειδικότερα, το ECDSA χρησιμοποιείται από το Bitcoin και το Ethereum για την εξουσιοδότηση συναλλαγών, ενώ το EdDSA και συναφή σχήματα υπογραφής ελλειπτικών καμπυλών χρησιμοποιούνται ευρέως σε πολλά άλλα δίκτυα blockchain.

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

Για να προετοιμαστεί για αυτή τη μετάβαση, το U.S. National Institute of Standards and Technology (NIST) ξεκίνησε τη Διαδικασία Τυποποίησης Μετακβαντικής Κρυπτογραφίας το 2016, καλώντας ερευνητές από όλο τον κόσμο να υποβάλουν υποψήφιους αλγορίθμους ικανούς να αντέχουν επιθέσεις τόσο από κλασικούς όσο και από κβαντικούς υπολογιστές. Ύστερα από αρκετούς γύρους διεθνούς κρυπτανάλυσης, αξιολόγησης και δημόσιου διαγωνισμού, το NIST οριστικοποίησε τα πρώτα του μεγάλα πρότυπα μετακβαντικής κρυπτογραφίας το 2024. Τα πρότυπα αυτά προορίζονται να αντικαταστήσουν κλασικούς αλγορίθμους δημόσιου κλειδιού που θα μπορούσαν να γίνουν ευάλωτοι σε επαρκώς ισχυρούς κβαντικούς υπολογιστές, διατηρώντας τις βασικές λειτουργίες της κρυπτογράφησης, της εγκαθίδρυσης κλειδιών και των ψηφιακών υπογραφών σε ένα μελλοντικό περιβάλλον κβαντικών υπολογισμών.

Τα νέα πρότυπα περιλαμβάνουν:

• ML-KEM, που προορίζεται κυρίως να αντικαταστήσει κλασικούς μηχανισμούς εγκαθίδρυσης κλειδιών και κρυπτογράφησης, όπως η μεταφορά κλειδιού RSA και η ανταλλαγή κλειδιών Diffie-Hellman ή elliptic-curve Diffie-Hellman·
• ML-DSA, που προορίζεται να παρέχει μετακβαντική αντικατάσταση για ευρέως χρησιμοποιούμενα συστήματα ψηφιακής υπογραφής, όπως οι υπογραφές RSA και το ECDSA·
• SLH-DSA, ένα πρότυπο ψηφιακής υπογραφής βασισμένο σε hash που παρέχει μια κρυπτογραφικά διαφορετική εναλλακτική στις υπογραφές βασισμένες σε πλέγματα (lattice).

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

Σε αντίθεση με το RSA και την κρυπτογραφία ελλειπτικών καμπυλών, τα ML-KEM και ML-DSA βασίζονται στη φαινομενική δυσκολία μαθηματικών προβλημάτων που αφορούν πλέγματα υψηλών διαστάσεων. Ειδικότερα, η ασφάλειά τους σχετίζεται στενά με δομημένες παραλλαγές του προβλήματος Learning With Errors, ιδίως το Module Learning With Errors (Module-LWE).

Σε σύγκριση με την κρυπτογραφία ελλειπτικών καμπυλών, τα μετακβαντικά σχήματα γενικά απαιτούν πολύ μεγαλύτερα δημόσια κλειδιά και υπογραφές. Περίπου στο επίπεδο ασφάλειας 128-bit (που σημαίνει ότι η καλύτερη γνωστή κλασική επίθεση θα απαιτούσε περίπου 2^128 υπολογιστικές πράξεις), το ECDSA πάνω στην καμπύλη secp256k1 που χρησιμοποιούν το Bitcoin και το Ethereum έχει συμπιεσμένο δημόσιο κλειδί 33 byte και υπογραφή 64 byte. Οι μετακβαντικές υπογραφές είναι πολύ μεγαλύτερες:

Τα ML-KEM, ML-DSA και SLH-DSA υποστηρίζονται ήδη από μεγάλες κρυπτογραφικές και τεχνολογικές πλατφόρμες. Για παράδειγμα, το OpenSSL 3.5 υποστηρίζει και τα τρία πρότυπα του NIST, ενώ η Microsoft έχει ενσωματώσει μετακβαντική κρυπτογραφία στο οικοσύστημα των Windows.

Ένα καλό παράδειγμα υιοθέτησης μετακβαντικής κρυπτογραφίας στο blockchain είναι το NEAR Protocol, το οποίο πρόσθεσε το ML-DSA στο mainnet του στην αναβάθμιση 2.13 τον Ιούλιο του 2026. Το ML-DSA είναι διαθέσιμο ως πρόσθετο μετακβαντικό σχήμα υπογραφής, επιτρέποντας στους λογαριασμούς NEAR να προσθέτουν ή να μεταβαίνουν σε κβαντικά ασφαλή κλειδιά πρόσβασης χωρίς να αλλάζουν την υπάρχουσα ταυτότητα του λογαριασμού τους.

Κβαντική και κλασική ασφάλεια των κλασικών κρυπτοσυστημάτων δημόσιου κλειδιού

Για το RSA, ο αλγόριθμος του Shor μπορεί να υλοποιηθεί χρησιμοποιώντας περίπου 3n λογικά qubit, όπου n είναι το μήκος σε bit του modulus m του RSA. Για παράδειγμα, ένα modulus RSA-2048 m = p*q έχει μήκος 2.048 bit. Η παραγοντοποίησή του, η εξαγωγή των δύο μεγάλων πρώτων p και q από το m, που είναι μέρος του δημόσιου κλειδιού RSA, θα απαιτούσε επομένως περίπου 3n = 3*2048 = 6.144 λογικά qubit.

Τι είναι το ECDLP; Το Πρόβλημα Διακριτού Λογαρίθμου Ελλειπτικών Καμπυλών (ECDLP) είναι το μαθηματικό πρόβλημα που προστατεύει την κρυπτογραφία ελλειπτικών καμπυλών. Δεδομένων δύο σημείων G και P που ανήκουν στην ίδια υποομάδα, ένας επιτιθέμενος πρέπει να βρει έναν αριθμό x, με 0 < x < q, τέτοιο ώστε P = x*G. Ο αριθμός x ονομάζεται διακριτός λογάριθμος του P ως προς το G. Για μια καλά επιλεγμένη ελλειπτική καμπύλη πρώτης τάξης q, οι καλύτερες γνωστές κλασικές επιθέσεις γενικού σκοπού απαιτούν περίπου 2^(n/2) πράξεις, όπου n είναι το μήκος σε bit του q. Για την καμπύλη secp256k1 του Bitcoin, η τάξη της υποομάδας είναι ο 256-bit πρώτος q = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141. Η επίλυση του ECDLP απαιτεί επομένως περίπου 2^(256/2) = 2^128 πράξεις σε κλασικό υπολογιστή, έναν αστρονομικά μεγάλο αριθμό που θεωρείται υπολογιστικά ανέφικτος στην πράξη.

Ο αριθμός των qubit για το σπάσιμο του ECDSA μπορεί να εκτιμηθεί κατά προσέγγιση με τον τύπο 9n + log2(n) + 10 από το άρθρο των Roetteler et al. 2017, όπου n είναι το μήκος της τάξης της κύριας υποομάδας (ο αριθμός των σημείων στην ομάδα στην οποία υπολογίζουμε τον διακριτό λογάριθμο). Αν είχαμε έναν κβαντικό υπολογιστή με περισσότερα από περίπου 9n + log2(n) + 10 = 9*256 + 2*log2(256) + 10 = 2304 + 16 + 10 = 2330 qubit, τότε το ECDLP για μια τέτοια 256-bit καμπύλη θα μπορούσε να λυθεί γρήγορα, σε πολυωνυμικό χρόνο.

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

Αμφιβολίες για τα ML-KEM και ML-DSA: θα μπορούσαν οι κβαντικοί υπολογιστές να λύσουν τα δύσκολα προβλήματα πλεγμάτων ταχύτερα από όσο πιστεύουμε σήμερα;

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

Το πρώτο, "Module Learning With Errors and Structured Extrapolated Dihedral Cosets" των Weiqiang Wen και Jinwei Zheng, μελετά το Module Learning With Errors (MLWE), τη βασική υπόθεση δυσκολίας πίσω τόσο από το ML-KEM όσο και από το ML-DSA. Οι συγγραφείς θεμελιώνουν μια σύνδεση ανάμεσα στο MLWE και σε μια δομημένη εκδοχή του Extrapolated Dihedral Coset Problem (EDCP). Με απλά λόγια, δείχνουν ότι η κατανόηση της κβαντικής δυσκολίας του MLWE μπορεί να μεταφραστεί σε κατανόηση μιας συγκεκριμένης κρυφής δομής που αφορά διεδρικές ομάδες.

Το δεύτερο άρθρο, "A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem" του Daniel R. Simon, πηγαίνει ένα βήμα παραπέρα. Ο Simon παρουσιάζει έναν κβαντικό αλγόριθμο πολυωνυμικού χρόνου για το Dihedral Coset Problem (DCP), ένα πρόβλημα που από καιρό συνδέεται με προβλήματα πλεγμάτων. Σε συνδυασμό με προηγούμενες αναγωγές, το αποτέλεσμά του δίνει κβαντικούς αλγορίθμους πολυωνυμικού χρόνου για ορισμένες εκδοχές του Shortest Vector Problem (SVP) και του Learning With Errors (LWE).

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

Το αποτέλεσμα του Simon δεν σπάει το ML-KEM ή το ML-DSA. Ο αλγόριθμος εφαρμόζεται σε συγκεκριμένα καθεστώτα παραμέτρων και στηρίζεται σε αναγωγές των οποίων οι παράμετροι και οι υποθέσεις έχουν σημασία. Το ίδιο το άρθρο ePrint περιγράφει τους προκύπτοντες αλγορίθμους LWE για συγκεκριμένα καθεστώτα, παρά μια επίθεση στα τυποποιημένα σύνολα παραμέτρων που χρησιμοποιούν τα ML-KEM ή ML-DSA.

Τι σημαίνει αυτό

Η άφιξη των μεγάλης κλίμακας κβαντικών υπολογιστών θα αλλάξει τελικά τους κανόνες της κρυπτογραφίας δημόσιου κλειδιού. Ο αλγόριθμος του Shor δείχνει ότι τα RSA, ECDSA, ECDH και άλλα συστήματα βασισμένα στην παραγοντοποίηση και τους διακριτούς λογαρίθμους μπορούν να σπάσουν αποδοτικά από έναν επαρκώς ισχυρό, ανθεκτικό σε σφάλματα κβαντικό υπολογιστή. Γι’ αυτό η κρυπτογραφική κοινότητα, η βιομηχανία και οι κυβερνήσεις κινούνται προς μετακβαντικά κρυπτογραφικά πρότυπα.

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

Παραπομπές

• FIPS 203, ML-KEM (key establishment / KEM): NIST FIPS 203
• FIPS 204, ML-DSA (digital signatures): NIST FIPS 204
• FIPS 205, SLH-DSA (digital signatures): NIST FIPS 205
• Peter W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring," Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), 1994, pp. 124-134.
• Martin Roetteler, Michael Naehrig, Krysta M. Svore, and Kristin Lauter, "Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms," arxiv.org/pdf/1706.06752.
• Weiqiang Wen and Jinwei Zheng, "Module Learning With Errors and Structured Extrapolated Dihedral Cosets," eprint.iacr.org/2026/155.
• Daniel R. Simon, "A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem," eprint.iacr.org/2026/1591.