Η κατασκευή ενός ολοκληρωμένου κβαντικού υπολογιστή αποτελεί μια πρόκληση για τη σύγχρονη επιστήμη. Ο κβαντικός υπολογιστής μας δίνει την ελπίδα πως κάποια στιγμή στο κοντινό μέλλον, θα είμαστε σε θέση να λύνουμε προβλήματα ταχύτερα και πιο αποδοτικά από ότι κάνει ένας κλασσικός υπολογιστής σήμερα. Για παράδειγμα, ο κβαντικός αλγόριθμος παραγοντοποίησης του Shor [3] πετυχαίνει εκθετική επιτάχυνση έναντι του κλασσικού, κάτι που σημαίνει πως η χρήση του πρωτόκολλου κρυπτογράφησης RSA δεν θα είναι όσο ασφαλής είναι σήμερα. Αυτό θα έχει ως αποτέλεσμα μεγάλες αλλαγές στις επικοινωνίες και στις συναλλαγές στο προσεχές μέλλον. Στην παρούσα διπλωματική εργασία θα περιγράψουμε τις αρχές που πρέπει να πληρεί ένα κβαντικό σύστημα για να θεωρηθεί κβαντικός υπολογιστής, πώς υλοποιούμε ένα qubit που είναι η μονάδα πληροφορίας του και τέλος θα μιλήσουμε για το πώς κωδικοποιούμε την κβαντική πληροφορία ώστε να είμαστε σε θέση να τη διορθώσουμε. Αρχίζουμε με τη διατύπωση των αρχών της κβαντικής μηχανικής , όπως προκύπτουν από την πειραματική διαδικασία. Συνεχίζουμε με την υπεραγωγιμότητα, το φαινόμενο που μας επιτρέπει να χειριζόμαστε μακροσκοπικά της κβαντικές ιδιότητες της ύλης, όπως και κάποια ακόμα φαινόμενα, όπως αυτό του Meissner, που μας δίνουν τη δυνατότητα να δημιουργήσουμε το κυκλώμα που υλοποιεί το qubit. Τέλος, περιγράφουμε θεωρητικά ένα καθολικό σύνολο από κβαντικές πύλες και τα κυκλώματα διόρθωσης λαθών κβαντικού κώδικα.
Η κατασκευή ενός ολοκληρωμένου κβαντικού υπολογιστή αποτελεί μια πρόκληση για τη σύγχρονη επιστήμη. Ο κβαντικός υπολογιστής μας δίνει την ελπίδα πως κάποια στιγμή στο κοντινό μέλλον, θα είμαστε σε θέση να λύνουμε προβλήματα ταχύτερα και πιο αποδοτικά από ότι κάνει ένας κλασσικός υπολογιστής σήμερα. Για παράδειγμα, ο κβαντικός αλγόριθμος παραγοντοποίησης του Shor [3] πετυχαίνει εκθετική επιτάχυνση έναντι του κλασσικού, κάτι που σημαίνει πως η χρήση του πρωτόκολλου κρυπτογράφησης RSA δεν θα είναι όσο ασφαλής είναι σήμερα. Αυτό θα έχει ως αποτέλεσμα μεγάλες αλλαγές στις επικοινωνίες και στις συναλλαγές στο προσεχές μέλλον. Στην παρούσα διπλωματική εργασία θα περιγράψουμε τις αρχές που πρέπει να πληρεί ένα κβαντικό σύστημα για να θεωρηθεί κβαντικός υπολογιστής, πώς υλοποιούμε ένα qubit που είναι η μονάδα πληροφορίας του και τέλος θα μιλήσουμε για το πώς κωδικοποιούμε την κβαντική πληροφορία ώστε να είμαστε σε θέση να τη διορθώσουμε. Αρχίζουμε με τη διατύπωση των αρχών της κβαντικής μηχανικής , όπως προκύπτουν από την πειραματική διαδικασία. Συνεχίζουμε με την υπεραγωγιμότητα, το φαινόμενο που μας επιτρέπει να χειριζόμαστε μακροσκοπικά της κβαντικές ιδιότητες της ύλης, όπως και κάποια ακόμα φαινόμενα, όπως αυτό του Meissner, που μας δίνουν τη δυνατότητα να δημιουργήσουμε το κυκλώμα που υλοποιεί το qubit. Τέλος, περιγράφουμε θεωρητικά ένα καθολικό σύνολο από κβαντικές πύλες και τα κυκλώματα διόρθωσης λαθών κβαντικού κώδικα.
Γίνεται όλο και πιο φανερό ότι η περίοδος που διανύουμε αποτελεί μια περίοδο άνθησης των κβαντικών υπολογιστών. Οι κβαντικοί υπολογιστές είναι πλέον ελεύθερα διαθέσιμοι για την εκτέλεση κβαντικών αλγορίθμων που έχουν υλοποιηθεί σε Python με τη χρήση των βιβλιοθηκών ανοιχτού κώδικα Qiskit που έχει αναπτύξει η ΙΒΜ. Η εκπαιδευτική μας πρόταση αποτελείται από: α)Σημειωματάριο Jupyter το οποίο οι εκπαιδευόμενοι έρχονται άμεσα σε επαφή με τις αρχές των κβαντικών υπολογιστών μέσω παραδειγμάτων κα κβαντικών αλγορίθμων με τη χρήση της γλώσσας κβαντικού προγραμματισμού Qiskit της IBM, β)διάλεξη-παρουσίαση και συζήτηση του προαναφερθέντος σημειωματάριου με παράλληλη εργαστηριακή άσκηση των εκπαιδευομένων και γ) ασκήσεις με προτεινόμενες λύσεις. Θα γίνει εισαγωγή στο κβαντικό μπιτ (qubit), στις κβαντικές πύλες, στα κβαντικά κυκλώματα και θα παρουσιαστεί ως παράδειγμα υπεροχής των κβαντικών υπολογιστών, ο αλγόριθμος υπέρπυκνης κωδικοποίησης.
Η μελέτη των κρυπτογραφικών αλγόριθμων δημοσίου κλειδιού οι οποίοι θα είναι ασφαλείς και μετά την έλευση των κβαντικών υπολογιστών, αποτελεί σημαντικό ερευνητικό πεδίο, καθώς οι σημερινοί αλγόριθμοι δημοσίου κλειδιού θα είναι επισφαλείς στο νέο τεχνολογικό περιβάλλον. Αλγόριθμοι οι οποίοι θα είναι ασφαλείς ακόμα και μετά την έλευση κβαντικών υπολογιστών ανήκουν στο χώρο της λεγόμενης μετα-κβαντικής κρυπτογραφίας, ωστόσο προκύπτουν συχνά θέματα στην υλοποίησή τους ή/και στην απόδοσή τους. \nΣτόχος της παρούσας διατριβής, είναι να μελετήσει, τα κρυπτογραφικά σχήματα ψηφιακών υπογραφών, στην μετα-κβαντική κρυπτογραφία. Ιδιαίτερη έμφαση θα δοθεί σε σχήματα που βασίζονται σε κρυπτογραφικές συναρτήσεις κατακερματισμού, όπως τα σχήματα ψηφιακών υπογραφών μιας χρήσης των Lamport, Merkle, W-OTS+, Merkle Trees και XMSS. Τα σχήματα αυτά θα αναλυθούν ως προς τον τρόπο λειτουργίας τους, τα χαρακτηριστικά ασφαλείας τους και θα αξιολογηθούν ως προς την απόδοσή τους σε σημερινά συμβατικά υπολογιστικά συστήματα. Για την αξιολόγηση και συγκριτική αποτίμηση της απόδοσής τους, χρησιμοποιούμε τη προγραμματιστική βιβλιοθήκη Bouncy Castle για την υλοποίηση ορισμένων σεναρίων δοκιμών, για τη σύγκριση ενός συμβατικού αλγορίθμου (RSA ψηφιακής υπογραφής), για διάφορες παραμέτρους, και ενός γνωστού αλγορίθμου μετα-κβαντικής κρυπτογραφίας για ψηφιακή υπογραφή (XMSS). \nΑπό τα αποτελέσματα των σεναρίων που πραγματοποιήθηκαν, συμπεραίνουμε ότι όσο μεγαλύτερη είναι η επεξεργαστική ισχύς του υπολογιστή, τόσο μικρότερος είναι ο χρόνος εκτέλεσης των αλγόριθμων που δοκιμάσαμε (όπως εξάλλου αναμενόταν). Ο αλγόριθμος RSA είναι ταχύτερος από τον αλγόριθμο XMSS. Το μέγεθος της υπογραφής, επηρεάζεται στον αλγόριθμο RSA, μόνο από το μήκος των κλειδιών, ενώ στον αλγόριθμο XMSS, επηρεάζεται από το αριθμό εξυπηρέτησης υπογραφών στο σχήμα (μεγαλύτερο ύψος) και την συνάρτηση κατακερματισμού που χρησιμοποιεί ο αλγόριθμος. Συμπερασματικά, οι αλγόριθμοι μετα-κβαντικής κρυπτογραφίας ψηφιακών υπογραφών παραμένουν σαφώς πιο αργοί, ωστόσο προκύπτει ότι είναι ρεαλιστικά υλοποιήσιμοι.
Στις επικοινωνίες ανάμεσα σε ανοιχτά συστήματα υπάρχουν τέσσερις κύριες κατηγορίες απειλών: Μη εξουσιοδοτημένη απόκτηση της πληροφορίας, Μη εξουσιοδοτημένη τροποποίηση της πληροφορίας, Πλαστοπροσωπία χρήστη, Αποκήρυξη της επικοινωνίας. Ο βασικός μηχανισμός για την παροχή ασφάλειας με τα χαρακτηριστικά που περιγράφηκαν πιο πάνω είναι η κρυπτογραφία. Οι συμμετρικοί αλγόριθμοι κρυπτογραφίας είναι πολύ ασφαλείς, γρήγοροι και έχουν διαδεδομένη χρήση. Ωστόσο, υπάρχουν διάφορες ελλείψεις που σχετίζονται με σχήματα συμμετρικού κλειδιού, όπως το πρόβλημα της διανομής κλειδιού, το μεγάλο πλήθος των κλειδιών που απαιτούνται και επίσης δεν παρέχουν καμία προστασία ενάντια σε επιθέσεις της επικοινωνίας. Τα παραπάνω προβλήματα λύνονται με τη χρήση ασύμμετρων αλγορίθμων ή αλλιώς δημοσίου κλειδιού σε καλά σχεδιασμένα πρωτόκολλα ασφάλειας και ανταλλαγής κλειδιού. Υπάρχουν τρεις κυρίαρχες οικογένειες αλγορίθμων δημοσίου κλειδιού οι οποίες έχουν πρακτικό αντίκρισμα. Μπορούν να ταξινομηθούν με βάση το υπολογιστικό πρόβλημα που τις χαρακτηρίζουν: Συστήματα παραγοντοποίησης ακεραίου, Συστήματα διακριτού λογαρίθμου, Συστήματα ελλειπτικών καμπυλών. Κάθε μία από αυτές τις τρεις οικογένειες μπορούν να παρέχουν τους βασικούς μηχανισμούς δημοσίου κλειδιού, όπως της εγκαθίδρυσης κλειδιού, της μη αποποίησης μέσω ψηφιακών υπογραφών και της κρυπτογράφησης δεδομένων. Ο RSA ανήκει στη κατηγορία των κρυπτογραφικών συστημάτων παραγοντοποίησης ακεραίου και είναι κατάλληλος για κρυπτογράφηση/αποκρυπτογράφηση δεδομένων, για την δημιουργία ψηφιακών υπογραφών και την επαλήθευσή τους καθώς και για την ασφαλή μεταφορά κλειδιών. Ο αλγόριθμος Diffie-Hellman Key Exchange (DHKE) ανήκει στη κατηγορία των κρυπτογραφικών συστημάτων διακριτού λογαρίθμου και αποτελεί μία εντυπωσιακή εφαρμογή του προβλήματος του διακριτού λογαρίθμου. Η θεμελιώδης αυτή τεχνική συμφωνίας κλειδιού υλοποιείται σε πολλά ανοιχτά και εμπορικά κρυπτογραφικά πρωτόκολλα όπως, στο SSH (Secure Shell) και στο IPsec (Internet Protocol Security). Στη τρίτη κατηγορία ανήκει το Elliptic Curve Diffie-Hellman ECDH το οποίο βρίσκεται σε πλήρη αναλογία με τον παραδοσιακό DHKE που αναφέραμε προηγουμένως, μόνο που εδώ πραγματοποιείται ανταλλαγή κλειδιού χρησιμοποιώντας ελλειπτικές καμπύλες. Κάποια από τα πιο γνωστά πρωτόκολλα ασφάλειας πρωτοκόλλων που χρησιμοποιούνται σήμερα κατά κόρον και χρησιμοποιούν ανταλλαγή και εγκαθίδρυση κλειδιού είναι το IPSec σε συνδυασμό με το IKE και το SSL. Ο βασικός στόχος οποιουδήποτε πρωτοκόλλου εγκαθίδρυσης επικυρωμένου κλειδιού είναι να διανέμει δεδομένα κλειδιού με ασφαλή τρόπο χρησιμοποιώντας πρωτόκολλα με έμμεση πιστοποίηση κλειδιού, με ρητή επιβεβαίωση κλειδιού κ.α. Στα πλαίσια της διατριβής αυτής και με σκοπό τη πρακτική μελέτη κάποιων από των πιο διαδεδομένων πρωτοκόλλων κρυπτογράφησης που παρουσιάστηκε και αναλύθηκε στα προηγούμενα κεφάλαια, αναπτύχθηκε μια εφαρμογή σε Java SE. Χρησιμοποιήθηκαν κυρίως το πλαίσιο ανάπτυξης Java Cryptography Architecture (JCA), το περιβάλλον ανάπτυξης λογισμικού netbeans, καθώς και κρυπτογραφικές βιβλιοθήκες JCE provider, και τη συλλογή Bouncy Castle.
Στην παρούσα διατριβή μελετήθηκε η δυνατότητα υλοποίησης συστημάτων κβαντικού υπολογισμού που βασίζονται σε εναλλακτικούς τύπους απεικόνισης κβαντικής πληροφορίας. Μελετήθηκαν δύο κύριες τεχνικές. Η πρώτη βασίστηκε σε αρχιτεκτονική πλέγματος άμεσης γειτνίασης, στην οποία προτάθηκε μηχανισμός εκτέλεσης κβαντικού υπολογισμού με τη χρήση ενός μόνο παλμού σε κάθε υπολογιστικό βήμα. Η εναλλακτική απεικόνιση βασίστηκε στη διαδικασία της τηλεμεταφοράς για την επίτευξη της επιθυμητής διάταξης των κβαντικών μπιτ. Το γεγονός ότι μόνο ένας παλμός εφαρμόζεται σε κάθε βήμα, μπορεί να μειώσει το λάθος που οφείλεται σε αλληλεπιδράσεις κβαντικών μπιτ λόγω διάχυσης του σήματος. Συνεπώς, αν μία υλοποίηση υποστηρίζει αποτελεσματικές πράξεις κβαντικής τηλεμεταφοράς, η μεθοδολογία μπορεί να οδηγήσει σε αρκετά σημαντική μείωση του συνολικού θορύβου. Στη δεύτερη τεχνική, χρησιμοποιήθηκαν τα ανώτερα ενεργειακά επίπεδα ενός κβαντικού μπιτ τύπου τρανσμόν (transmon) για την αποθήκευση κβαντικής πληροφορίας. Μέσω θεωρητικής απόδειξης και πειραμάτων που εκτελέστηκαν στους κβαντικούς επεξεργαστές της IBM Quantum Platform αποδείχθηκε ότι μπορεί να επιτευχθεί διεμπλοκή σε λογικό επίπεδο χρησιμοποιώντας τους βαθμούς ελευθερίας ενός μόνο συστήματος. Αυτό μπορεί να έχει ως αποτέλεσμα τη μείωση των αναγκαίων παλμών σύζευξης, που είναι η κύρια πηγή θορύβου στους σύγχρονους κβαντικούς επεξεργαστές.
Η εκπόνηση της παρούσας διατριβής αφορά το πεδίο της Βελτιστοποίησης Αλγορίθμων και πιο συγκεκριμένα με το πεδίο της συνδυαστικής βελτιστοποίησης. Στην ουσία πραγματεύεται τη διερεύνηση μεθευρετικών μεθόδων που βασίζονται σε συμβατικές ή μη συμβατικές, εμπνευσμένες από τον κβαντικό υπολογισμό τεχνικές με σκοπό την εφαρμογή τους σε αλγόριθμους βελτιστοποίησης για την επίλυση προβλημάτων από τον πραγματικό κόσμο. Πιο συγκεκριμένα, παρουσιάζουμε την κβαντικά εμπνευσμένη μεθευρετική μέθοδο qGVNS (quantum General Variable Neighborhood Search), την οποία χρησιμοποιούμε για να επιλύσουμε το πρόβλημα του πλανόδιου πωλητή (Travelling Salesman Problem, TSP εν συντομία) όπως επίσης και το πρόβλημα του πλανόδιου πωλητή με χρονικά παράθυρα (Travelling Salesman Problem with Time Windows, TSPTW εν συντομία). Ο τελικός σκοπός είναι η επίλυση ρεαλιστικών προβλημάτων από τον πραγματικό κόσμο που έχουν μοντελοποιηθεί σαν προβλήματα βελτιστοποίησης (TSP ή TSPTW) χρησιμοποι-ώντας τις μη συμβατικές μεθευρετικές μεθόδους που αναπτύξαμε. Το πρόβλημα του πλανόδιου πωλητή χρησιμοποιείται ως σημείο αναφοράς σε πολλές μεθόδους βελτιστοποίησης και έχει πλήθος εφαρμογών σε πολλές και διαφορετικές περιοχές, όπως στην τεχνητή νοημοσύνη, την βιοπληροφορικη, την βέλτιστη αναζήτηση διαδρομών και αλλού. Σε αυτή τη διατριβή διερευνούμε ιδιαίτερα την εκδοχή του TSP προβλήματος, που αποτελείται από κάποιους επιπρόσθετους περιορισμούς, όπως τα χρονικά παράθυρα (time windows). Η εκδοχή αυτή είναι γνωστή ως TSPTW (Travelling Salesman Problem with Time Windows). Με βάση το πρόβλημα του πλανόδιου πωλητή (TSP) αλλά και το πρόβλημα του πλανόδιου πωλητή με χρονικά παράθυρα (TSPTW) επιλύσαμε το πρόβλημα περισυλλογής απορριμάτων από τον πραγματικό κόσμο, σε δύο διαφορετικές εκδοχές του. Το απλό πρόβλημα της περισυλλογής των απορριμάτων όπως και το πρόβλημα περισυλλογής των απορριμάτων με χρονικά παράθυρα. Συνεχίζοντας, πραγματοποιήσαμε αναλυτική και διεξοδική συγκριτική μελέτη απόδοσης ανά-μεσα στην νέα κβαντικά εμπνευσμένη μέθοδο που προτείναμε και σε άλλες συμβατικές μεθόδους. Η παρούσα διατριβή ολοκληρώνεται με την παρουσίαση μερικών βασικών σημείων και βιβλιογραφίας σχετική με την κβαντική βελτιστοποίηση και την κβαντική ανόπτηση (quantum annealing).
Η μελέτη κρυπτογραφικών αλγορίθμων δημοσίου κλειδιού, οι οποίοι θα είναι ανθεκτικοί και μετά την έλευση των κβαντικών υπολογιστών, αποτελούν ένα πολύ σημαντικό ερευνητικό πεδίο, καθώς οι σημερινοί κλασικοί αλγόριθμοι δημοσίου κλειδιού (RSA, ελλειπτικών καμπυλών κ.α.) δεν θα παρέχουν πλέον καμία ασφάλεια στο νέο αυτό τεχνολογικό περιβάλλον. Ήδη γνωρίζουμε διάφορους κρυπτογραφικούς αλγορίθμους οι οποίοι είναι, ή φέρονται να είναι, ασφαλείς ακόμα και με την υπόθεση ότι διαθέτουμε κβαντικούς υπολογιστές (ήτοι πρόκειται για αλγόριθμους μετακβαντικής κρυπτογραφίας). Ωστόσο πολλά θέματα ως προς τη δυνατότητα υλοποίησής τους παραμένουν ανοιχτά. \nΣτην παρούσα εργασία μελετάται η μετακβαντική κρυπτογραφία και τα συναφή μαθηματικά προβλήματα πάνω στα οποία δομούνται οι μετακβαντικοί αλγόριθμοι, με έμφαση στα προβλήματα που άπτονται της θεωρίας κωδίκων, παρουσιάζοντας και υλοποιώντας το κρυπτοσύστημα McEliece – ένα κλασικό κρυπτογραφικό σύστημα που αποτελεί ήδη έναν από τους υποψήφιους κρυπταλγορίθμους στη διαδικασία προτυποποίησης που έχει εκκινήσει ο οργανισμός NIST. Απώτερος στόχος είναι η συγκριτική αποτίμηση της απόδοσης του McEliece σε εφαρμογές πραγματικού χρόνου, σε σχέση με σημερινούς συμβατικούς κρυπταλγορίθμους. Αρχικά πραγματοποιείται μία βιβλιογραφική επισκόπηση σε θεωρητικά ζητήματα της κλασσικής και μετακβαντικής κρυπτογραφίας αλλά και σε θέματα της θεωρίας της πληροφορίας με έμφαση στον κβαντικό υπολογιστή. Στη συνέχεια παρουσιάζονται τα χαρακτηριστικά του κρυπτοσυστήματος McEliece. Αναπτύσσεται μια υλοποίηση κρυπτοσυστήματος δημόσιου κλειδιού RSA, που αποτελεί και έναν κλασσικό αλγόριθμο, καθώς επίσης και μία αντίστοιχη υλοποίηση κρυπτοσυστήματος δημοσίου κλειδιού με τον αλγόριθμο McEliece: και οι δύο υλοποιήσεις αφορούν μία τυπική εφαρμογή συνομιλίας (chat). Ακολούθως, γίνεται συγκριτική αποτίμηση των δύο υλοποιήσεων. Η μελέτη καταδεικνύει ότι πράγματι ο αλγόριθμος McEliece, ως αλγόριθμος μετακβαντικής κρυπτογραφίας, είναι σημαντικά πιο αργός, αναδεικνύοντας την ανάγκη εύρεσης μεθόδων βελτίωσης της απόδοσης των αλγορίθμων αυτής της κατηγορίας.