Show simple item record

dc.contributor.advisorΚολοκοτρώνης, Νικόλαος
dc.contributor.authorΣμυρλή, Παναγιώτα
dc.date.accessioned2015-05-27T08:20:31Z
dc.date.available2015-05-27T08:20:31Z
dc.date.issued2015-05
dc.identifier.urihttp://amitos.library.uop.gr/xmlui/handle/123456789/2420
dc.descriptionΜ.Δ.Ε. 48el
dc.description.abstractΗ παρούσα διπλωματική εργασία πραγματεύεται την μελέτη κρυπτοσυστημάτων δημοσίου κλειδιού ή ασύμμετρων κρυπτοσυστημάτων (public-key cryptosystems). Τα εν λόγω κρυπτοσυστήματα θεωρούν ότι κάθε χρήστης έχει στην κατοχή του ένα ζεύγος κλειδιών, το ιδιωτικό και το δημόσιο. Το ιδιωτικό κλειδί κρατείται πάντοτε μυστικό, ενώ το δημόσιο διατίθεται ελεύθερα σε όλους τους εν δυνάμει χρήστες ενός ανοικτού και ανασφαλούς δικτύου. Μια από τις βασικές απαιτήσεις ασφαλείας που πρέπει να ικανοποιούν τα εν λόγω κρυπτοσυστήματα, είναι ότι η ανάκτηση του ιδιωτικού κλειδιού από το δημόσιο πρέπει να είναι υπολογιστικά ανέφικτη. Για τον λόγο αυτό, οι κατασκευές των ασύμμετρων κρυπτοσυστημάτων βασίζονται σε δύσκολα μαθηματικά προβλήματα, προερχόμενα, ενδεικτικά, από τον χώρο της θεωρίας αριθμών, της άλγεβρας και της συνδυαστικής, τα οποία ανήκουν στην κλάση υπολογιστικής πολυπλοκότητας NP. Πρόκειται δηλαδή για προβλήματα που δεν επιδέχονται επίλυση σε πολυωνυμικό χρόνο. Χαρακτηριστικά παραδείγματα μεταξύ άλλων, αποτελούν το πρόβλημα της παραγοντοποίησης μεγάλων ακεραίων (integer-factoring) [46], διακριτού λογαρίθμου (discrete logarithm) [46], αποκωδικοποίησης τυχαίων γραμμικών κωδίκων (computational syndrome decoding problem ή CSD) και κρυφής υποομάδας (hidden subgroup problem) [38]. Θα εστιάσουμε την μελέτη μας στο CSD πρόβλημα, λόγω της σημαντικότητάς του στην ασφάλεια ασύμμετρων κρυπταλγορίθμων βασιζόμενων σε κώδικες διόρθωσης σφαλμάτων, όπως τα κρυπτοσυστήματα McEliece και Niederreiter. Αξίζει να αναφέρουμε πως υπάρχουν σοβαρές ενδείξεις ότι παρά την αξιοσημείωτη πρόοδο που έχει καταγραφεί την τελευταία δεκαετία στην περιοχή της κβαντομηχανικής, το πρόβλημα CSD δεν επιδέχεται σημαντικής κβαντικής επιτάχυνσης. Ακολουθεί εκτεταμένη μελέτη αλγορίθμων αποκωδικοποίησης για τυχαίους γραμμικούς κώδικες, εστιάζοντας σε μια ιδιαιτέρως σημαντική κλάση αλγορίθμων, που βασίζονται στην αποκωδικοποίηση συνόλου πληροφορίας (information set decoding), αλλά και κάποιες επιπλέον εναλλακτικές μεθόδους. Παρατίθεται εν συνεχεία, πλήρης ασυμπτωτική ανάλυση μεταξύ των εξεταζόμενων μεθόδων, καθιστώντας δυνατή τη σύγκριση της εκθετικής τους συμπεριφοράς και τέλος καταγράφονται ανοιχτά προβλήματα και μελλοντικές ερευνητικές κατευθύνσεις.el
dc.format.extent166 σελ.el
dc.language.isoelel
dc.publisherΠανεπιστήμιο Πελοποννήσουel
dc.rightsΑναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/gr/*
dc.subjectΚρυπτογραφίαel
dc.subjectΑλγόριθμοιel
dc.subjectΘεωρία σημάτωνel
dc.subjectΘεωρία κωδίκωνel
dc.titleΚρυπτοσυστήματα βασισμένα σε κώδικες: κατασκευές και επιθέσειςel
dc.typeΜεταπτυχιακή διπλωματική εργασίαel
dc.contributor.departmentΤμήμα Πληροφορικής και Τηλεπικοινωνιώνel
dc.contributor.facultyΣχολή Οικονομίας, Διοίκησης και Πληροφορικήςel
dc.contributor.masterΠρόγραμμα Μεταπτυχιακών Σπουδών στην Επιστήμη και Τεχνολογία Υπολογιστώνel
dc.subject.keywordΚρυπτοσυστήματαel
dc.subject.keywordΓραμμικοί Κώδικεςel
dc.subject.keywordΑποκωδικοποίησηel
dc.subject.keywordΑσυμπτωτική ανάλυσηel
dc.description.abstracttranslatedThis thesis offers an insight into public-key cryptosystems. It is assumed that every user of the cryptosystems in question possesses a pair of keys, referred to as the private key and the public key. The private key is always kept secret while the public key is known to every user of an open insecure network. An important security requirement involved in such cryptosystems is that the recovery of the private key from the public key is computationally infeasible. For this reason, the construction of asymmetric cryptosystems is based on difficult mathematical problems, indicatively from areas like number theory, algebra and combinatorics, all of which belong to the complexity class NP. In other words, those mathematical problems cannot be solved within polynomial time. Examples of problems in the above areas are integer-factoring, discrete logarithm, computational syndrome decoding or CSD, and the hidden subgroup problem. Our research will focus on the CSD problem due to its significance in the security of code-based cryptosystems, such as McEliece and Niederreiter. It is worth mentioning that despite considerable improvements which have taken place over the last decade in the field of quantum mechanics, the CSD problem cannot be solved via quantum acceleration techniques. What follows is an extensive research into decoding algorithms of random linear codes, focusing on a particularly important class of algorithms called Information Set Decoding algorithms as well as some additional alternative methods. A holistic asymptotic analysis of the examined methods is performed that allows a detailed comparison of the aforementioned methods with respect to their complexity. A number of open problems and future research directions are also presented.el


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα
Except where otherwise noted, this item's license is described as
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα