From pre-quantum to post-quantum : a comprehensive analysis of key encapsulation mechanisms

Abstract

Η ραγδαία πρόοδος των κβαντικών υπολογιστικών απειλεί τη μακροχρόνια ασφάλεια της συμβατικής κρυπτογραφίας και πιο συγκεκριμένα αλγόριθμους όπως ο RSA και αλγόριθμους ελλειπτικών καμπύλων (EC). Οι αλγόριθμοι αυτοί αποτελούν σήμερα τη βάση της ασφαλής επικοινωνίας στο παγκόσμιο διαδίκτυο. Η εξέλιξη αυτή καθιστά επιτακτική τη μετάβαση σε μετακβαντικούς αλγορίθμους, ικανούς να παραμένουν ασφαλείς ακόμη και απέναντι σε κβαντικούς υπολογιστές. Στο πλαίσιο αυτό, η παρούσα διατριβή μελετά τους Μηχανισμούς Ενθυλάκωσης Κλειδιών (Key Encapsulation Mechanisms - KEMs) ως την κεντρική αρχιτεκτονική ανταλλαγής κλειδιών μεταξύ δύο πλευρών στην κλασική και μετα-κβαντική εποχή. Αρχικά, παρουσιάζονται τυπικοί ορισμοί για τα KEMs και αναλύονται οι αντίστοιχες έννοιες ασφάλειας όπως και τα μοντέλα επιθέσεων. Στη συνέχεια εξετάζεται ο ρόλος των αλγόριθμων παραγωγής κλειδιών (Key Derivation Functions) οι οποίοι μετατρέπουν ένα κοινό μυστικό ενός KEM σε τελικά κλειδιά πρωτοκόλλου με κατάλληλο μήκος και ομοιομορφία. Ακολουθεί η μελέτη κλασικών KEMs, όπως ο RSA-KEM, FFDH-KEM και ECDH-KEM, οι οποίοι βασίζονται στα γνωστά μαθηματικά προβλήματα παραγοντοποίησης, διακριτού λογαρίθμου και διακριτού λογαρίθμου σε ελλειπτικές καμπύλες αντίστοιχα, αναδεικνύοντας τόσο τα πλεονεκτήματα όσο και τους περιορισμούς τους υπό την απειλή κβαντικών υπολογιστών. Το κύριο μέρος της διατριβής επικεντρώνεται σε μετα-κβαντικά KEMs που συμμετείχαν ή επιλέχθηκαν στη διαδικασία τυποποίησης του NIST, και συγκεκριμένα στους ML-KEM (πρώην CRYSTALS-Kyber), HQC-KEM και Classic McEliece KEM. Για κάθε σχήμα παρουσιάζονται τα μαθηματικά θεμέλια, οι διαδικασίες παραγωγής κλειδιών, ενθυλάκωσης και αποενθυλάκωσης, καθώς και οι εγγυήσεις ασφάλειας που επιτυγχάνονται μέσω των συγκεκριμένων πρωτοκόλλων. Τέλος, πραγματοποιείται συγκριτική αξιολόγηση των υπό εξέταση KEMs ως προς το μέγεθος δημοσίων κλειδιών, το μέγεθος των κρυπτογραφημένων μηνυμάτων, τους χρόνους για κάθε εσωτερική διαδικασία του αλγορίθμου, καθώς και την καταλληλότητά τους για πραγματικές εφαρμογές (υβριδική δημόσια κρυπτογραφία, πρωτόκολλα ασφαλούς επικοινωνίας τύπου TLS κ.α) ή συμβατικούς υπολογιστές.