Η παρούσα διπλωματική εργασία έχει ως σκοπό την ανάπτυξη εφαρμογής σε iPhone για την προσομοίωση κβαντικών υπολογισμών. Για την υλοποίηση του γραφικού περιβάλλοντος της εφαρμογής αντί για τη native γλώσσα προγραμματισμού για iphone (objective c), καθώς και τα επίσημα εργαλεία της apple επιλέχθηκε η πλατφόρμα phonegap. Αρχικά μελετήθηκαν: πρώτον, οι βασικές έννοιες που διέπουν τους κβαντικούς υπολογιστές και δεύτερον, η χρήση και οι δυνατότητες των διάφορων προγραμματιστικών γλωσσών και εργαλείων. Στη συνέχεια δημιουργήθηκε η γραφική διεπαφή της εφαρμογής με το χρήστη και εν τέλει αναπτύχθηκε η βιβλιοθήκη η οποία εκτελεί τους κβαντικούς υπολογισμούς.
Η παρούσα διπλωματική εργασία έχει ως σκοπό την ανάπτυξη εφαρμογής σε iPhone για την προσομοίωση κβαντικών υπολογισμών. Για την υλοποίηση του γραφικού περιβάλλοντος της εφαρμογής αντί για τη native γλώσσα προγραμματισμού για iphone (objective c), καθώς και τα επίσημα εργαλεία της apple επιλέχθηκε η πλατφόρμα phonegap. Αρχικά μελετήθηκαν: πρώτον, οι βασικές έννοιες που διέπουν τους κβαντικούς υπολογιστές και δεύτερον, η χρήση και οι δυνατότητες των διάφορων προγραμματιστικών γλωσσών και εργαλείων. Στη συνέχεια δημιουργήθηκε η γραφική διεπαφή της εφαρμογής με το χρήστη και εν τέλει αναπτύχθηκε η βιβλιοθήκη η οποία εκτελεί τους κβαντικούς υπολογισμούς.
Η παρούσα διπλωματική εργασία αφορά την ανάπτυξη βιβλιοθήκης συναρτήσεων για κβαντικό υπολογισμό και τη δημιουργία γραφικού περιβάλλοντος το οποίο χρησιμοποιεί τη συγκεκριμένη βιβλιοθήκη. Αρχικά μελετήθηκαν: πρώτον, οι βασικές έννοιες που διέπουν τους κβαντικούς υπολογιστές και δεύτερον, η χρήση και οι δυνατότητες της γλώσσας python. Εν συνέχεια, ύστερα από εμβάθυνση στα ανωτέρω πεδία πραγματοποιήθηκε η συγγραφή της κβαντικής βιβλιοθήκης καθώς και η δημιουργία του γραφικού περιβάλλοντος που χρησιμοποιεί τη κβαντική αυτή βιβλιοθήκη. Επίσης δημιουργήθηκε και μία γραφική διεπαφή για την παρουσίαση των γραφικών παραστάσεων που παρουσιάζουν τα αποτελέσματα του κβαντικού υπολογισμού. Η ανάπτυξη του προγράμματος πραγματοποιήθηκε σε γλώσσα Python.
Γίνεται όλο και πιο φανερό ότι η περίοδος που διανύουμε αποτελεί μια περίοδο άνθησης των κβαντικών υπολογιστών. Οι κβαντικοί υπολογιστές είναι πλέον ελεύθερα διαθέσιμοι για την εκτέλεση κβαντικών αλγορίθμων που έχουν υλοποιηθεί σε Python με τη χρήση των βιβλιοθηκών ανοιχτού κώδικα Qiskit που έχει αναπτύξει η ΙΒΜ. Η εκπαιδευτική μας πρόταση αποτελείται από: α)Σημειωματάριο Jupyter το οποίο οι εκπαιδευόμενοι έρχονται άμεσα σε επαφή με τις αρχές των κβαντικών υπολογιστών μέσω παραδειγμάτων κα κβαντικών αλγορίθμων με τη χρήση της γλώσσας κβαντικού προγραμματισμού Qiskit της IBM, β)διάλεξη-παρουσίαση και συζήτηση του προαναφερθέντος σημειωματάριου με παράλληλη εργαστηριακή άσκηση των εκπαιδευομένων και γ) ασκήσεις με προτεινόμενες λύσεις. Θα γίνει εισαγωγή στο κβαντικό μπιτ (qubit), στις κβαντικές πύλες, στα κβαντικά κυκλώματα και θα παρουσιαστεί ως παράδειγμα υπεροχής των κβαντικών υπολογιστών, ο αλγόριθμος υπέρπυκνης κωδικοποίησης.
Στις επικοινωνίες ανάμεσα σε ανοιχτά συστήματα υπάρχουν τέσσερις κύριες κατηγορίες απειλών: Μη εξουσιοδοτημένη απόκτηση της πληροφορίας, Μη εξουσιοδοτημένη τροποποίηση της πληροφορίας, Πλαστοπροσωπία χρήστη, Αποκήρυξη της επικοινωνίας. Ο βασικός μηχανισμός για την παροχή ασφάλειας με τα χαρακτηριστικά που περιγράφηκαν πιο πάνω είναι η κρυπτογραφία. Οι συμμετρικοί αλγόριθμοι κρυπτογραφίας είναι πολύ ασφαλείς, γρήγοροι και έχουν διαδεδομένη χρήση. Ωστόσο, υπάρχουν διάφορες ελλείψεις που σχετίζονται με σχήματα συμμετρικού κλειδιού, όπως το πρόβλημα της διανομής κλειδιού, το μεγάλο πλήθος των κλειδιών που απαιτούνται και επίσης δεν παρέχουν καμία προστασία ενάντια σε επιθέσεις της επικοινωνίας. Τα παραπάνω προβλήματα λύνονται με τη χρήση ασύμμετρων αλγορίθμων ή αλλιώς δημοσίου κλειδιού σε καλά σχεδιασμένα πρωτόκολλα ασφάλειας και ανταλλαγής κλειδιού. Υπάρχουν τρεις κυρίαρχες οικογένειες αλγορίθμων δημοσίου κλειδιού οι οποίες έχουν πρακτικό αντίκρισμα. Μπορούν να ταξινομηθούν με βάση το υπολογιστικό πρόβλημα που τις χαρακτηρίζουν: Συστήματα παραγοντοποίησης ακεραίου, Συστήματα διακριτού λογαρίθμου, Συστήματα ελλειπτικών καμπυλών. Κάθε μία από αυτές τις τρεις οικογένειες μπορούν να παρέχουν τους βασικούς μηχανισμούς δημοσίου κλειδιού, όπως της εγκαθίδρυσης κλειδιού, της μη αποποίησης μέσω ψηφιακών υπογραφών και της κρυπτογράφησης δεδομένων. Ο 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.
Η εργασία αυτή έχει θέμα την κβαντική κρυπτογραφία. Η προσέγγιση του θέματος έγινε αρχικά μέσω την κβαντομηχανικής και στη συνέχεια μέσω της ιστορίας της κρυπτογραφίας για να καταλήξουμε στα επιτεύγματα της εποχής μας, τους κβαντικούς υπολογιστές. Η εργασία είναι χωρισμένη σε 3 ενότητες, την «εισαγωγή στην κβαντομηχανική», την «κβαντική κρυπτογραφία» και τους «κβαντικούς υπολογιστές». Στην πρώτη ενότητα γίνεται αρχικά αναφορά σε βασικές έννοιες της κβαντομηχανικής. Στη συνέχεια γίνεται ο χωρισμός της περιόδου σε προκβαντική και σε κβαντική. Ακολουθούν αναφορές σε σημαντικούς φυσικούς που έπαιξαν σημαντικό ρόλο στην ανάπτυξη και την θεμελίωση της κβαντομηχανικής. Μετά υπάρχουν θεματικές ενότητες με βασικές θεωρίες της κβαντομηχανικής όπως η ακτινοβολία μέλανος σώματος, το φωτοηλεκτρικό φαινόμενο, το φαινόμενο Compton και ο κυματοσωματιδιακός δυϊσμός. Στις θεματικές αυτές ενότητες γίνεται αναφορά προσπάθειες κλασσικής και κβαντικής ερμηνείας, σε βασικές αρχές και ιδιαίτερα χαρακτηριστικά, σε ιστορικές αναδρομές, σε παραδείγματα και σε πειράματα. Η δεύτερη ενότητα ξεκινά με τον διαχωρισμό της κρυπτογραφίας σε 3 περιόδους, με αναφορά στα σημαντικότερα γεγονότα κάθε περιόδου. Μετά ακολουθεί μια μικρή λίστα με εξήγηση των βασικών όρων της εργασίας. Το μεγαλύτερο μέρος της ενότητας αφορά την ιστορία της εξέλιξης της επιστήμης της κρυπτογραφίας , από τον Β΄ Παγκόσμιο Πόλεμο μέχρι τις μέρες μας. Χαρακτηριστικό είναι το παράδειγμα επικοινωνίας της Αλίκης και του Μπομπ, με υποκλοπέα την Εύα. Στην πορεία δίνονται πληροφορίες για τις κβαντικές πύλες και τα qubits. Ακολουθεί ο Αλγόριθμος του Shor με το κβαντικό και το κλασικό κομμάτι καθώς και τα προβλήματα του. Τέλος γίνεται μια προσπάθεια να κατανοήσουμε αν η κβαντική κρυπτογραφία είναι ή όχι μια ασφαλής μέθοδος επικοινωνίας. Η τρίτη ενότητα επεξεργάζεται τους κβαντικούς υπολογιστές. Ξεκινώντας από την υλοποίηση τους, και αφού γίνει αναφορά στα πλεονεκτήματα και στις εφαρμογές τους, στα προβλήματα που παρουσιάστηκαν κατά την υλοποίηση καθώς και στην κβαντική διόρθωση των σφαλμάτων, καταλήγουμε στις τεχνολογίες κατασκευής των κβαντικών υπολογιστών καθώς και στις προοπτικές και το μέλλον τους. Η πρώτη πώληση κβαντικού υπολογιστή έχει ήδη πραγματοποιηθεί!
H διπλωματική εργασία αποτελεί μια βιβλιογραφική ανασκόπηση της θεωρίας και των εφαρμογών στην περιοχή της Κρυπτογραφίας Πλεγμάτων (Lattice Cryptography). Ένας μακροπρόθεσμος στόχος στην Κρυπτογραφία Δημοσίου Κλειδιού, για τη μετάβαση από τις υφιστάμενες και δοκιμασμένες μεθόδους σε προτάσεις για τις μελλοντικές γενιές επεξεργαστών (quantum-safe cryptography), είναι η αντικατάσταση των πρωταρχικών δομικών κρυπτογραφικών στοιχείων (cryptographic primitives). Προϋπόθεση για την επίτευξη αυτού του στόχου είναι η εύρεση εναλλακτικών οι οποίες στηρίζονται σε μαθηματικό υπόβαθρο (provable security) και επιπλέον ικανοποιούν τις τεχνικές απαιτήσεις για πρακτική ασφάλεια (security levels) και αποδοτική υλοποίηση (efficiency properties). H Κρυπτογραφία Πλεγμάτων έχει αναδειχθεί τις τελευταίες δεκαετίες σε μια ερευνητική περιοχή που συγκεντρώνει μεγάλο ενδιαφέρον τόσο για τον πλούτο των θεωρητικών κατασκευών όσο και για τις πιο πρόσφατες επιτυχίες στις προτάσεις υλοποίησης αποδοτικών αλγορίθμων. Στο Κεφάλαιο 1 δίνεται η μαθηματική περιγραφή και οι βασικοί αλγόριθμοι για τα υπολογιστικά προβλήματα πλεγμάτων που αξιοποιούνται στην κρυπτογραφία. Στο Κεφάλαιο 2 παρουσιάζονται οι τεχνικές κατασκευής πρωταρχικών κρυπτογραφικών στοιχείων οι οποίες βασίζονται στα προβλήματα Learning With Errors (LWE) και Short Integer Solution (SIS) με αναγωγή σε προβλήματα πλεγμάτων. Καταγράφονται, επίσης, τα κλασικά συστήματα κρυπτογράφησης και ψηφιακών υπογραφών τα οποία έχουν μελετηθεί στον ακαδημαϊκό χώρο. Στο Κεφάλαιο 3 γίνεται αναφορά στις πρόσφατες προσπάθειες προτυποποίησης και σε ορισμένα σύγχρονα κρυπτογραφικά σχήματα που έχουν υλοποιηθεί. Το μεγάλο εύρος στο ακαδημαϊκό πεδίο της έρευνας καθιστά δύσκολη την εξαντλητική συγκριτική ανάλυση και πολλές πρακτικές λεπτομέρειες δεν έχουν διευκρινιστεί ακόμα. H βιομηχανία τελικά θα υιοθετήσει μόνο τις ολοκληρωμένες κρυπτογραφικές προτάσεις που έχουν διερευνηθεί και προτυποποιηθεί από την ερευνητική κοινότητα. Η συστηματική θεμελίωση και αξιολόγηση των υποσχόμενων νέων τεχνικών κρυπτογράφησης πρέπει να προηγηθεί της έρευνας και κατασκευής νέων επεξεργαστών, οι οποίοι θα επιβάλλουν ριζική αναθεώρηση της δημόσιας Κρυπτογραφίας. Στο άμεσο μέλλον αναμένεται να συγκεντρωθούν και να παρουσιαστούν σαφέστερα οι επικρατέστερες εναλλακτικές προκειμένου να καθοριστούν συγκεκριμένες κατευθύνσεις εξειδίκευσης της έρευνας · είναι βέβαιο ότι οι κατασκευές της σύγχρονης Κρυπτογραφίας Πλεγμάτων θα έχουν θέση ανάμεσα σε αυτές.
Η σημερινή εποχή χαρακτηρίζεται από την ολοένα αυξανόμενη ενσωμάτωση των ηλεκτρονικών υπολογιστών και των ενσωματωμένων συστημάτων σε όλες τις πτυχές της καθημερινής μας ζωής. Τα ολοκληρωμένα κυκλώματα συνεχώς σμικρύνονται, γίνονται ταχύτερα, απαιτούν όλο και μικρότερα ποσά ενέργειας με τη βοήθεια νέων υλικών και αρχιτεκτονικών. Αυτό έχει ως αποτέλεσμα οι ηλεκτρονικές συσκευές να βρίσκουν όλο και περισσότερες εφαρμογές σε όλους τους τομείς της ζωής μας και με τον καιρό να μετατρέπονται σε ένα αόρατο και απαραίτητο στρώμα διεπαφής μας με το περιβάλλον. Το αντικείμενο με το οποίο ασχολείται μέχρι στιγμής η παρούσα διατριβή είναι η ελαχιστοποίηση λογικών εκφράσεων ’’αποκλειστικού ή” (XOR) για τυχαία λογική συνάρτηση, και πιο συγκεκριμένα με τη μείωση των όρων από τους οποίους αυτή αποτελείται καθώς και με την απεικόνιση τέτοιων εκφράσεων σε αρχιτεκτονικές νέων τεχνολογιών όπως οι κβαντικοί υπολογιστές. Ένα ολοκληρωμένο κύκλωμα αποτελεί την πρακτική υλοποίηση μιας τέτοιας λογικής έκφρασης. Κατά συνέπεια, γίνεται προσπάθεια για την βελτιστοποίηση λογικών κυκλωμάτων. Η πιο γνωστή τέτοια κατηγορία εκφράσεων είναι οι λεγάμενες εκφράσεις ESOP (Exclusive or Sum Of Products), όπου μια λογική συνάρτηση εκφράζεται ως άθροισμα XOR από λογικά γινόμενα. Μια άλλη πιο γενική κατηγορία είναι οι ESCT (Exclusive or Sum of Complex Terms) εκφράσεις, οι οποίες μπορούν να θεωρηθούν ως επέκταση των ESOP, αφού πλέον οι όροι ονομάζονται σύνθετοι (complex terms) και δεν περιλαμβάνουν μόνο τη λογική πράξη ΚΑΙ ανάμεσα στις μεταβλητές, αλλά εν γένει οποιαδήποτε λογική πράξη (συνάρτηση δύο εισόδων μιας εξόδου). Η σημασία των παραπάνω εκφράσεων τονίζεται και από το γεγονός ότι μπορούν, με τετριμμένο τρόπο, να απεικονισθούν σε αντιστρέψιμες αρχιτεκτονικές. Ένα αντιστρέψιμο λογικό κύκλωμα έχει μικρότερες απώλειες ενέργειας σε σχέση με ένα τυπικό λογικό κύκλωμα και για το λόγο αυτό η σύνθεση αντιστρέψιμων κυκλωμάτων θεωρείται το μέλλον στη λογική σχεδίαση. Ένα ακόμα σημαντικό τους πλεονέκτημα είναι ότι μπορούν να χρησιμοποιηθούν και για τη σύνθεση κβαντικών κυκλωμάτων. Η ελαχιστοποίηση αυτών των εκφράσεων καθώς και οι κβαντικές επεκτάσεις τους είναι το κύριο αντικείμενο έρευνας με το οποίο ασχολείται αυτή η εργασία. Η εργασία αυτή ασχολείται καταρχήν, με το θεωρητικό υπόβαθρο της ελαχιστοποίησης τέτοιων εκφράσεων. Αποδεικνύονται θεωρήματα τα οποία υποδεικνύουν μια μεθοδολογία για την εύρεση ελάχιστης ESCT έκφρασης για οποιαδήποτε πλήρως ορισμένη λογική συνάρτηση μοναδικής εξόδου, αλλά με περιορισμό ως προς τον αριθμό των όρων σε μια ελάχιστη έκφρασή της ή με περιορισμό ως προς τον αριθμό των μεταβλητών εισόδου της. Γίνεται, επιπλέον, μελέτη πώς τα παραπάνω συμπεράσματα μπορούν να χρησιμοποιηθούν για ευριστική ελαχιστοποίηση συναρτήσεων που δεν εμπίπτουν στους παραπάνω περιορισμούς. Στη συνέχεια τα παραπάνω πορίσματα επεκτείνονται, ευριστικά, για ατελώς ορισμένες λογικές συναρτήσεις πολλών εξόδων. Η παραπάνω θεωρητική μελέτη του προβλήματος ελαχιστοποίησης εκφράσεων ’’αποκλειστικού ή”, χρησιμοποιείται για την υλοποίηση συμβατικών και κβαντικών αλγορίθμων οι οποίοι, όπως φαίνεται και από τα πειραματικά αποτελέσματα, δίνουν καλύτερα αποτελέσματα από τους αντίστοιχους της διεθνούς βιβλιογραφίας. Πιο συγκεκριμένα, οι κβαντικοί αλγόριθμοι που μπορούν να χρησιμοποιηθούν για την ακριβή ελαχιστοποίηση εκφράσεων ’’αποκλειστικού ή” και καταδεικνύουν τη σαφή υπεροχή των κβαντικών υπολογιστών έναντι των κλασικών τους αναλόγων. Τέλος, πραγματοποιείται εφαρμογή των παραπάνω αποτελεσμάτων στο πεδίο της κρυπτογράφησης και των ασφαλών υπολογισμών. Πιο συγκεκριμένα, γίνεται χρήση των αλγορίθμων ελαχιστοποίησης εκφράσεων ESCT για την επίτευξη έως και 39% λιγότερου κόστους επικοινωνίας σε σχέση με τις υπόλοιπες αντίστοιχες προσπάθειες της βιβλιογραφίας. Κατά τη διάρκεια της εκπόνησης της συγκεκριμένης διατριβής έχουν προκύψει οι δημοσιεύσεις που παρουσιάζονται στον κατάλογο δημοσιεύσεων που ακολoυθεί.