Πριν από τρεις εβδομάδες, πολλοί επιστήμονες του κόσμου της ασφάλειας πανικοβλήθηκαν, όταν Κινέζοι ερευνητές ανακοίνωσαν το σπάσιμο του ευρέως χρησιμοποιούμενου συστήματος κρυπτογράφησης RSA με τη χρήση κβαντικών υπολογιστών.
Οι επιστήμονες και οι κρυπτογράφοι γνωρίζουν εδώ και δύο δεκαετίες ότι μια μέθοδος παραγοντοποίησης γνωστή και σαν αλγόριθμος του Shor καθιστά θεωρητικά δυνατό για έναν κβαντικό υπολογιστή με επαρκείς πόρους να σπάσει την RSA.
Αυτό συμβαίνει επειδή οι μυστικοί πρώτοι αριθμοί που υποστηρίζουν την ασφάλεια ενός κλειδιού RSA είναι εύκολο να υπολογιστούν χρησιμοποιώντας τον αλγόριθμο του Shor. Ο υπολογισμός των πρώτων αριθμών χρησιμοποιώντας κλασικούς υπολογιστές μπορεί να διαρκέσει δισεκατομμύρια χρόνια.
Το μόνο πράγμα που εμποδίζει αυτό το καταστροφικό σενάριο είναι η τεράστια ποσότητα υπολογιστικών πόρων που απαιτούνται για να σπάσει ο αλγόριθμος του Shor τα RSA κλειδιά. Η τρέχουσα εκτίμηση είναι ότι για το σπάσιμο ενός κλειδιού RSA 1.024 bit ή 2.048 bit απαιτεί έναν κβαντικό υπολογιστή με τεράστιους πόρους. Συγκεκριμένα, αυτοί οι πόροι θα πρέπει να είναι περίπου 20 εκατομμύρια qubits που τρέχουν περίπου για οκτώ ώρες. (Ένα qubit είναι μια βασική μονάδα κβαντικού υπολογισμού, ανάλογη με το δυαδικό bit στον κλασικό υπολογισμό. Ενώ όμως ένα κλασικό δυαδικό bit μπορεί να αντιπροσωπεύει μόνο μια ενιαία δυαδική τιμή όπως το 0 ή το 1, ένα qubit αντιπροσωπεύεται από ένα σύνολο πολλαπλών δυνατών τιμών.)
Η εργασία, που δημοσιεύθηκε πριν από τρεις εβδομάδες από μια ομάδα ερευνητών στην Κίνα, ανέφερε ότι βρέθηκε μια μέθοδος παραγοντοποίησης που θα μπορούσε να σπάσει ένα κλειδί RSA 2.048-bit χρησιμοποιώντας ένα κβαντικό σύστημα με μόλις 372 qubits. Το εύρημα, αν αληθεύει, θα σήμαινε ότι το σπάσιμο της κρυπτογράφησης RSA στον κβαντικό υπολογισμό θα μπορούσε να έρθει πολύ πιο σύντομα από ό,τι πιστεύουν οι περισσότεροι.
Στο συνέδριο Enigma 2023 στη Santa Clara της California, την Τρίτη, ο επιστήμονας υπολογιστών και ειδικός σε θέματα ασφάλειας και ιδιωτικότητας Simson Garfinkel διαβεβαίωσε τους ερευνητές ότι το σπάσιμο της RSA ήταν υπερβολικό. Προς το παρόν, ανέφερε, ο κβαντικός υπολογισμός έχει λίγες, έως καθόλου, πρακτικές εφαρμογές.
“Στο άμεσο μέλλον, οι κβαντικοί υπολογιστές θα είναι καλοί για ένα πράγμα, και αυτό θα είναι για την δημοσίευση άρθρων σε έγκριτα περιοδικά”, δήλωσε στο κοινό ο Garfinkel, συν-συγγραφέας με τον Chris Hoofnagle του βιβλίου Law and Policy for the Quantum Age του 2021.
“Το δεύτερο πράγμα στο οποίο είναι αρκετά καλοί, αλλά δεν ξέρουμε για πόσο ακόμη, είναι ότι είναι αρκετά καλοί στο να λαμβάνουν χρηματοδότηση”.
Ακόμη και όταν ο κβαντικός υπολογισμός γίνει αρκετά προηγμένος ώστε να παρέχει χρήσιμες εφαρμογές, η έλλειψη χρήσιμων εφαρμογών στο άμεσο μέλλον μπορεί να επιφέρει έναν “κβαντικό χειμώνα”, παρόμοιο με τους πολλαπλούς χειμώνες που είχαμε στην τεχνητή νοημοσύνη πριν τελικά κάνουμε τα πρώτα βήματα.
Το πρόβλημα με την εργασία που δημοσιεύθηκε νωρίτερα αυτό το μήνα είναι η εξάρτησή της από τον αλγόριθμο του Schnorr (δεν πρέπει να συγχέεται με τον αλγόριθμο του Shor), ο οποίος αναπτύχθηκε το 1994. Ο αλγόριθμος του Schnorr είναι ένας κλασικός υπολογισμός που βασίζεται σε πλέγματα, τα οποία είναι μαθηματικές δομές που έχουν πολλές εφαρμογές στην εποικοδομητική κρυπτογραφία και την κρυπτανάλυση. Οι επιστήμονες που επινόησαν τον αλγόριθμο του Schnorr ανέφεραν ότι θα μπορούσε να ενισχύσει τη χρήση μιας ευρετικής κβαντικής μεθόδου βελτιστοποίησης που ονομάζεται QAOA.
Σε σύντομο χρονικό διάστημα, πάρα πολλοί ερευνητές ανακάλυψαν ελαττώματα στον αλγόριθμο του Schnorr και τον έχουν απομυθοποιήσει. Συγκεκριμένα, δήλωσαν ότι δεν υπάρχουν στοιχεία που να υποστηρίζουν τους ισχυρισμούς ότι ο αλγόριθμος του Schnorr επιτυγχάνει πολυωνυμικό χρόνο, σε αντίθεση με τον εκθετικό χρόνο που επιτυγχάνεται με τους κλασικούς αλγόριθμους.
Η ερευνητική εργασία πριν από τρεις εβδομάδες φάνηκε να χρησιμοποιεί τον αλγόριθμο του Shor στην ονομαστική του αξία. Ακόμη και όταν υποτίθεται ότι έχει βελτιωθεί με την προσθήκη του QAOA -κάτι για το οποίο δεν υπάρχει προς το παρόν- είναι αμφίβολο αν παρέχει κάποια ώθηση στην απόδοση.
“Συνεπώς, αυτό είναι ένα από τα πιο παραπλανητικά κβαντικά υπολογιστικά κείμενα που έχω δει τα τελευταία 25 χρόνια, και έχω δει… πολλά”, ανέφερε ο Scott Aaronson, επιστήμονας υπολογιστών στο Πανεπιστήμιο του Τέξας στο Ώστιν και διευθυντής του Quantum Information Center.
