Constructing suitable parameters for pairing-based cryptography

Abstract

Οι ``ζευγισμοί'' παρουσιάστηκαν για πρώτη φορά από τον André Weil το 1940 και αρχικά χρησιμοποιήθηκαν ως μηχανισμός επίθεσης στο πρόβλημα διακριτού λογάριθμου σε ελλειπτικές καμπύλες. Περίπου 60 χρόνια μετά την ανακάλυψή τους, οι ζευγισμοί έχουν γίνει ένα από τα σπουδαιότερα αντικείμενα μελέτης στην κρυπτογραφία. ́Ενα από σημαντικότερα προβλήματα σε εφαρμογές που χρησιμοποιούν ζευγισμούς είναι η κατασκευή αβελιανών ποικιλιών (abelian varieties) διάστασης g, πάνω από πεπερασμένα σώματα. Για να είναι αυτές οι αβελιανές ποικιλίες κατάλληλες για εφαρμογές, απαιτείται να έχουν μικρό βαθμό εμφύτευσης (embedding degree) και μια υποομάδα μεγάλης πρώτης τάξης. Τέτοιου είδους αβελιανές ποικιλίες καλούνται ``φιλικές για ζευγισμό'' (pairing-friendly).

Η συγκεκριμένη διατριβή αφορά στο πρόβλημα κατασκευής αβελιανών ποικιλιών διάστασης g πάνω σε πεπερασμένα σώματα, οι οποίες είναι φιλικές για ζευγισμό. Ξεκινάμε τη μελέτη με μια σύντομη επισκόπηση της θεωρίας ζευγισμών και αβελιανών ποικιλιών υπέρ πεπερασμένων σωμάτων. Ειδικεύουμε τη μελέτη σε ελλειπτικές καμπύλες οι οποίες ουσιαστικά είναι αβελιανές ποικιλίες διάστασης ένα. Περιγράφουμε τις συνθήκες ώστε μια ελλειπτική καμπύλη να είναι κατάλληλη για ζευγισμό και κάνουμε μια επισκόπηση των γνωστών μεθόδων για την κατασκευή τους. Επιπλέον παρουσιάζουμε αναλυτικά τις μεθόδους και τα αποτελέσματά μας υπογραμμίζοντας τη σημασία τους. Μια από τις σημαντικότερες συνεισφορές μας στην κατασκευή κατάλληλων ελλειπτικών καμπυλών είναι οτι στα παραδείγματά μας λαμβάνουμε υπόψιν τα πρόσφατα αποτελέσματα που αφορούν στη μείωση της πολλυπλοκότητας του προβλήματος διακριτού λογάριθμου σε επεκτάσεις σωμάτων σύνθετου βαθμού. Αυτές οι βελτιώσεις προκύπτουν από παραλλαγές της μεθόδου του κόσκινου σώματος αριθμών και έχουν σημαντικές επιπτώσεις στην επιλογή κατάλληλων ελλειπτικών καμπυλών για κρυπτογραφικά συστήματα ζευγισμών. Ως αντίμετρα, παρουσιάζουμε μια αναθεώρηση των κριτηρίων επιλογής παραμέτρων ελλειπτικών καμπυλών για χρήση σε εφαρμογές ζευγισμών.

Οι αβελιανές ποικιλίες μεγαλύτερης διάστασης αποτελούν μια εναλλακτική λύση και σε μερικές περιπτώσεις έχουν σημαντικά πλεονεκτήματα σε σχέση με τις ελλειπτικές καμπύλες. Το γεγονός αυτό αποτελεί το κίνητρό μας για να επεκτείνουμε τη μελέτη σε τέτοιου είδους αβελιανές ποικιλίες. Δίνουμε μια σύντομη περιγραφή των σπουδαιότερων μεθόδων κατασκευής τους καθώς και των πιο σημαντικών αποτελεσμάτων που υπάρχουν στη βιβλιογραφία. Ιδιαίτερη έμφαση δίνεται στη δουλειά μας πάνω σε απολύτως απλές (absolutely simple) και μη-απολύτως απλές (non-absolutely simple) αβελιανές ποικιλίες. Και στις δύο περιπτώσεις η έρευνά μας εξειδικεύεται σε αβελιανές ποικιλίες διάστασης δύο. Τέτοιου είδους αβελιανές ποικιλίες τις βλέπουμε σαν Ιακωβιανές (Jacobians) υπερελλειπτικών καμπυλών γένους δύο, οι οποίες δύναται να προσφέρουν ασφαλείς και αποδοτικές εφαρμογές. Παρόλα αυτά, παρουσιάζουμε επίσης και παραδείγματα μη-απολύτως απλών αβελιανών ποικιλιών διαστάσεων 3 και 4. Σε όλη τη διατριβή παρουσιάζουμε αναλυτικές περιγραφές των αλγόριθμων που υλοποιήσαμε, καθώς και των αποτελεσμάτων αυτών.

Τέλος, προσπαθούμε να υπογραμμίσουμε τα ανοικτά προβλήματα που υπάρχουν σήμερα στο χώρο αυτό, τα οποία θα καθορίσουν μέλλον της κρυπτογραφίας που βασίζεται σε ζευγισμόυς.