Constructing suitable parameters for pairing-based cryptography

Abstract

Pairings were introduced by André Weil back in 1940 and they were initially viewed as a tool for attacking the elliptic curve discrete logarithm problem. After almost 60 years from their discovery, pairings became one of the major research subjects in cryptography. One of the most important problems in applications that use pairings is the construction of suitable g-dimensional abelian vari- eties defined over a finite field. In order for these abelian varieties to be suitable for implementations, it is required that they have a small embedding degree and a large prime order subgroup. Such abelian varieties are called “pairing-friendly”.This dissertation is dedicated to the problem of constructing pairing-friendly g-dimensional abelian varieties over finite fields. We start with an overview of the theory surrounding pairings and abelian varieties over finite fields. We specialize our study on elliptic curves, which are basically one- dimensional abelian varieties. We describe the pairing-friendly properties and present a survey of the known methods for their construction. In addition we present an analytic study of our methods and results on constructing pairing-friendly elliptic curves and highlight their importance. One of the most important contribution is that in our examples we consider for the first time the recent improvements on reducing the complexity of the discrete logarithm problem in finite field extensions of composite embedding degree. These improvements are obtained by variants of the number field sieve methods and have a major impact on the choice of pairing-friendly curves. As a countermeasure we revise the criteria for selecting elliptic curve parameters for pairing-based applications.Higher-dimensional abelian varieties can be an alternative to elliptic curves and in some cases can be advantageous. Motivated by this we extend our study from elliptic curves to higher-dimensional abelian varieties. We give a short description of the most important methods and results in the literature. We emphasize on our work on absolutely simple and non-absolutely simple, ordinary, pairing-friendly abelian varieties. In both cases our work is specialized on two-dimensional abelian varieties. These are realized as Jacobians of genus 2 hyperelliptic curves and they are likely to offer secure and efficient applications. In addition, we also introduce various examples of non-absolutely simple abelian varieties for dimensions 3 and 4. Throughout the dissertation we provide an extensive analysis of our algorithmic procedures and the examples obtained by our algorithms.Finally we also try to highlight the open problems that exist today in this area, which determine the future of pairing-based cryptography.

Οι ̔ ̔ζευγισμοί ̓ ̓ παρουσιάστηκαν για πρώτη φορά από τον André Weil το 1940 και αρχικά χρησιμοποιήθηκαν ως μηχανισμός επίθεσης στο πρόβλημα διακριτού λογάριθμου σε ελλειπτικές καμπύλες. Περίπου 60 χρόνια μετά την ανακάλυψή τους, οι ζευγισμοί έχουν γίνει ένα από τα σπουδαιότερα αντικείμενα μελέτης στην κρυπτογραφία. ́Ενα από σημαντικότερα προβλήματα σε εφαρμογές που χρησιμοποιούν ζευγισμούς είναι η κατασκευή αβελιανών ποικιλιών (abelian varieties) διάστασης g, πάνω από πεπερασμένα σώματα. Για να είναι αυτές οι αβελιανές ποικιλίες κατάλληλες για εφαρμογές, απαιτείται να έχουν μικρό βαθμό εμφύτευσης (embedding degree) και μια υποομάδα μεγάλης πρώτης τάξης. Τέτοιου είδους αβελιανές ποικιλίες καλούνται ̔ ̔φιλικές για ζευγισμό ̓ ̓ (pairing-friendly).Η συγκεκριμένη διατριβή αφορά στο πρόβλημα κατασκευής αβελιανών ποικιλιών διάστασης g πάνω σε πεπερασμένα σώματα, οι οποίες είναι φιλικές για ζευγισμό. Ξεκινάμε τη μελέτη με μια σύντομη επισκόπηση της θεωρίας ζευγισμών και αβελιανών ποικιλιών υπέρ πεπερασμένων σωμάτων. Ειδικεύουμε τη μελέτη σε ελλειπτικές καμπύλες οι οποίες ουσιαστικά είναι αβελιανές ποικιλίες διάστασης ένα. Περιγράφουμε τις συνθήκες ώστε μια ελλειπτική καμπύλη να είναι κατάλληλη για ζευγισμό και κάνουμε μια επισκόπηση των γνωστών μεθόδων για την κατασκευή τους. Επιπλέον παρουσιάζουμε αναλυτικά τις μεθόδους και τα αποτελέσματά μας υπογραμμίζοντας τη σημασία τους. Μια από τις σημαντικότερες συνεισφορές μας στην κατασκευή κατάλληλων ελλειπτικών καμπυλών είναι οτι στα παραδείγματά μας λαμβάνουμε υπόψιν τα πρόσφατα αποτελέσματα που αφορούν στη μείωση της πολλυπλοκότητας του προβλήματος διακριτού λογάριθμου σε επεκτάσεις σωμάτων σύνθετου βαθμού. Αυτές οι βελτιώσεις προκύπτουν από παραλλαγές της μεθόδου του κόσκινου σώματος αριθμών και έχουν σημαντικές επι- πτώσεις στην επιλογή κατάλληλων ελλειπτικών καμπυλών για κρυπτογραφικά συστήματα ζευγισμών. Ως αντίμετρα, παρουσιάζουμε μια αναθεώρηση των κριτηρίων επιλογής παραμέτρων ελλειπτικών καμπυλών για χρήση σε εφαρμογές ζευγισμών.Οι αβελιανές ποικιλίες μεγαλύτερης διάστασης αποτελούν μια εναλλακτική λύση και σε μερικές περιπτώσεις έχουν σημαντικά πλεονεκτήματα σε σχέση με τις ελλειπτικές καμπύλες. Το γεγονός αυτό αποτελεί το κίνητρό μας για να επεκτείνουμε τη μελέτη σε τέτοιου είδους αβελιανές ποικιλίες. Δίνουμε μια σύντομη περιγραφή των σπουδαιότερων μεθόδων κατασκευής τους καθώς και των πιο σημαντικών αποτελεσμάτων που υπάρχουν στη βιβλιογραφία. Ιδιαίτερη έμφαση δίνεται στη δουλειά μας πάνω σε απολύτως απλές (absolutely simple) και μη-απολύτως απλές (non-absolutely simple) αβελιανές ποικιλίες. Και στις δύο περιπτώσεις η έρευνά μας εξειδικεύεται σε αβελιανές ποικιλίες διάστασης δύο. Τέτοιου είδους αβελιανές ποικιλίες τις βλέπουμε σαν Ιακωβιανές (Jacobians) υπερελλειπτικών καμπυ- λών γένους δύο, οι οποίες δύναται να προσφέρουν ασφαλείς και αποδοτικές εφαρμογές. Παρόλα αυτά, παρουσιάζουμε επίσης και παραδείγματα μη-απολύτως απλών αβελιανών ποικιλιών διαστάσεων 3 και 4. Σε όλη τη διατριβή παρουσιάζουμε αναλυτικές περιγραφές των αλγόριθμων που υλοποιήσαμε, καθώς και των αποτελεσμάτων αυτών.Τέλος, προσπαθούμε να υπογραμμίσουμε τα ανοικτά προβλήματα που υπάρχουν σήμερα στο χώρο αυτό, τα οποία θα καθορίσουν μέλλον της κρυπτογραφίας που βασίζεται σε ζευγισμόυς.