Συνδυαστική θεωρία σχεδιασμών, κωδίκων και κρυπτογραφίας
Authors: Σίμος Δημήτριος 
Published: August 2021

Στη διδακτορική αυτή διατριβή, μελετώνται συνδυαστικές κατασκευές διαφόρων κλάσεων σχεδιασμών καθώς και η ανάπτυξη σχετικών αλγόριθμων που βρισκούν εφαρμογή στους κλάδους της Θεωρίας Κωδίκων και της Κρυπτογραφίας. Στο πρώτο μέρος της διατριβής, ``Συνδυαστική Θεωρία Σχεδιασμών'', μελετώνται διάφορα είδη ακολουθιών με σταθερή αυτοσυσχέτιση και συνδυαστικών σχεδιασμών, εισάγονται νέες οικογένειες συνδυαστικών δομών, αποδεικνύονται ορισμένα θεωρήματα σχετικά με τις αναγκαίες και ικανές συνθήκες ύπαρξης και υλοποιείται ένα σχετικό λογισμικό για την εύρεση αυτών. Επιπρόσθετα, αναπτύσσεται μια σειρά συνδυαστικών αλγορίθμων βελτιστοποίησης για την εύρεση νέων ακολουθιών και σχεδιασμών. Ιδιαίτερα, παρουσιάζεται μια νέα μέθοδος υπολογισμού της συνάρτησης αυτοσυσχέτισης για συμβατές ακολουθίες. Αποδεικνύεται μέσω μιας μελέτης της πολυπλοκότητας χείριστης περίπτωσης ότι η νέα μέθοδος είναι αποδοτική για ακολουθίες με μικρό βάρος. Αυτή η μέθοδος επιπλέον επιτρέπει τη μοντελοποίση μιας σειράς συνδυαστικών αλγορίθμων βελτιστοποίησης (mGA, FmGA, OmeGA) για την εύρεση νέων πινάκων στάθμισης, όπου οι ακολουθίες χρησιμοποιούνται ως ενδιάμεσα βήματα για την κατασκευή των σχεδιασμών. Επιπλέον, νέοι μη-ισοδύναμοι πίνακες Hadamard κατασκευάζονται από συμπληρωματικές ακολουθίες, μέσω ενός λογισμικού που υλοποιήθηκε ειδικά για αυτόν τον σκοπό. Επιπρόσθετα, νέες άπειρες οικογένειες ορθογώνιων σχεδιασμών και πίνακων στάθμισης κατασκευάζονται από συμπληρωματικές ακολουθίες, οι οποίες ανανεώνουν το Εγχειρίδιο των Συνδυαστικών Σχεδιασμών (Handbook of Combinatorial Designs) σε πολλές περιπτώσεις. Τέλος, εισάγεται ένα νέο κριτήριο για τριαδικές ακολουθίες με μηδενική μη-περιοδική συνάρτηση αυτοσυσχέτισης, η ζ-αποδοτικότητα, και μελετώνται διάφορες ιδιότητες της, καθώς και οι συνέπειες της στη Θεωρία Σχεδιασμών. Στο δεύτερο μέρος, ``Θεωρία Κωδίκων'', μελετώνται ορισμένες ειδικές οικογένειες κωδικών, όπως είναι για παράδειγμα οι αυτοδϋικοί και πολυκυκλικοί κώδικες, προτείνονται μέθοδοι κατασκευής αυτών από διάφορες κλάσεις σχεδιασμών, και υλοποιούνται γενετικοί αλγόριθμοι για την εύρεση των τιμών των παραμέτρων τους, στην περίπτωση των πολυκυκλικών κωδίκων. Ιδιαίτερα προτείνονται νέες μέθοδοι κατασκευής αυτοδϋικών κωδίκων πάνω από το GF(p) με τη χρήση πινάκων skew-Hadamard, και δίνεται μια πλήρης μελέτη πάνω από μικρά πεπερασμένα σώματα. Επιπλέον, νέοι αυτοδυϊκοί κώδικες με μεγάλο μήκος πάνω από το GF(5) βρίσκονται για πρώτη φορά, ενώ πάνω από το GF(7) παρουσιάζεται ένας νέος [56,28,17] αυτοδϋικός κώδικας, ο οποίος βελτιώνει το κάτω φράγμα στην ελάχιστη απόσταση όλων των αυτοδϋικών κωδίκων με τις ίδιες παραμέτρους. Επιπρόσθετα, μελετάται η συστηματική κατασκευή μέγιστης απόστασης διαχωρίσιμων αυτοδϋικών κωδίκων για μεγάλα πρώτα σώματα που προέρχονται από λύσεις διοφαντικών εξισώσεων. Στο τέλος αυτού του μέρους, μελετώνται δυαδικοί πολυκλικοί κώδικες από στατιστικούς σχεδιασμούς και αποδεικνύεται μια θεμελιώδης σχέση μεταξύ μιας βέλτιστης κλάσης αυτών των σχεδιασμών και των συμπληρωματικά δϋικών δυαδικών πολυκυκλικών κωδίκων. Στο τρίτο και τελευταίο μέρος της διατριβής, ``Κρυπτογραφία'', προτείνονται κρυπτοσυστήματα ιδιωτικού κλειδιού που προέρχονται από κλάσεις ορθογωνίων σχεδιασμών και κρυπτογραφικά σχήματα διαμοιρασμού μυστικού μηνύματος που κατασκευάζονται με τη χρήση σχεδιασμών Hadamard. Ιδιαίτερα, τα νέα συμμετρικά κρυπτογραφήματα δέσμης κατασκευάζονται από πίνακες Hadamard και σχηματισμούς Plotkin. Η μαθηματική δομή των τελευταίων σχεδιασμών επιτρέπει την υλοποίηση κρυπτογραφικών αλγορίθμων κατάλληλων για την κρυπτογράφηση και αποκρυπτογράφηση ενός μηνύματος. Μια εκτεταμένη κρυπτανάλυση αυτών των κρυπτογραφημάτων δείχνει ότι δεν παραβιάζεται η ασφάλεια τους από συγκεκριμένους τύπους κρυπτογραφικών επιθέσεων. Επιπλέον, διμερή κρυπτογραφικά σχήματα διαμοιρασμού μυστικού μηνύματος κατασκευάζονται από σχεδιασμούς Hadamard, που κάτω από ορισμένες προϋποθέσεις παρέχουν πλήρη ασφάλεια.