Ανάλυση ακολουθιών De Bruijn

Abstract

Αυτή η διατριβή επικεντρώνεται στην ακολουθία De Bruijn, ως ερευνητικό θέμα αυξανόμενου ενδιαφέροντος, το οποίο «αναβιώνει» τα τελευταία χρόνια ακριβώς επειδή τα NLFSR χρησιμοποιούνται μαζικά για τη δημιουργία ισχυρών κρυπτογραφικών αλγορίθμων. Πιο συγκεκριμένα, οι συναρτήσεις Boolean που δημιουργούν ακολουθίες De Bruijn μελετώνται σε αυτή τη διατριβή, όσον αφορά τη διερεύνηση των αντίστοιχων κρυπτογραφικών ιδιοτήτων για συναρτήσεις που δημιουργούν "παρόμοιες" ακολουθίες De Bruijn. Συγκεκριμένα, έχοντας ως αφετηρία κάποια πρόσφατα αποτελέσματα για τον προσδιορισμό ζευγών αλληλουχιών De Bruijn [1]που μοιράζονται τη μεγαλύτερη κοινή ακολουθία, παρουσιάζουμε πρώτα έναν νέο αλγόριθμο προσέγγισης, χρησιμοποιώντας τους (αντίστροφους) πίνακες επιθήματος των ακολουθιών, για να υπολογίσουμε αποτελεσματικά ζεύγη τέτοιων De Bruijn ακολουθιών επεκτείνοντας έτσι περαιτέρω τα πρόσφατα ερευνητικά αποτελέσματα σε αυτόν τον τομέα. Στη συνέχεια, χρησιμοποιώντας κατάλληλα εργαλεία λογισμικού, εξετάσαμε τις ιδιότητες των αντίστοιχων Boolean λειτουργιών τους, όπως αλγεβρικός βαθμός, μη γραμμικότητα και αλγεβρική ανοσία - ενώ μελετάμε επίσης πώς συμπεριφέρεται η γραμμική πολυπλοκότητα για οποιοδήποτε τέτοιο ζεύγος «παρόμοιων» ακολουθιών De Bruijn. Δείχνουμε ότι, αν και στην πλειονότητα των περιπτώσεων αυτές οι ιδιότητες παραμένουν αμετάβλητες, ενδέχεται να έχουμε κάποιες διαφορές που θα μπορούσαν να είναι κρυπτοαναλυτικής αξίας, δημιουργώντας έτσι μια νέα ιδιότητα που πρέπει να ελεγχθεί όταν εξετάζουμε την κατασκευή γεννητριών De Bruijn.