Προσεγγιστικοί αλγόριθμοι για δίκαιο καταμερισμό υπολογιστικού φόρτου, με εφαρμογές σε κρυπτοσυστήματα κατωφλίου

Abstract

Σε αυτή την εργασία παρουσιάζουμε ένα FPTAS για την k-εκδοχή του προβλήματος k-WAY NUMBER PARTITIONING RATIO (k-PART) (το οποίο αποτελεί μια παραλλαγή του κλασι- κού στη βιβλιογραφία προβλήματος SUBSET SUM RATIO (SSR)), στο οποίο ζητείται να βρεθεί μια διαμέριση, ενός συνόλου n στοιχείων σε k υποσύνολα, τέτοια ώστε, ο λόγος μεταξύ των αθροισμάτων, του συνόλου με το μεγαλύτερο άθροισμα, προς το σύνολο με το μικρότερο άθροισμα, να είναι ο ελάχιστος δυνατός. Το πρόβλημα αυτό αντιστοιχεί στην ελαχιστοποίηση του λόγου μεγαλύτερου προς μικρότερου αθροίσματος στη γενική οικογένεια προβλημάτων MULTIWAY NUMBER PARTITIONING. Το FPTAS μας για το πρόβλημα k-PART, το οποίο επιτυγ- χάνει χρονική πολυπλοκότητα O(n^{2k}/ε^{k−1}), εμφανίζεται σε εργασία της ομάδας μας που έχει υποβληθεί προς δημοσίευση. Στο δεύτερο μέρος της εργασίας μας, παρουσιάζουμε τις εφαρμογές που έχει το FPTAS του πρώτου μέρους, σε ένα (k, t) Κρυπτοσυστήματα Κατωφλίου, και συγκεκριμένα στο πως μπο- ρεί να χρησιμοποιηθεί για να διαμοιράσει, με προσεγγιστικά βέλτιστο τρόπο, τον υπολο- γιστικό φόρτο αποκρυπτογράφησης n κρυπτοκειμένων (που έχουν κρυπτογραφηθεί με ένα (k, t) Κρυπτοσυστήματα Κατωφλίου), σε k οντότητες. Ορίζουμε τυπικά αυτό το νέο πρόβλημα και αφού παρουσιάσουμε τις βασικές αρχές του και την τρέχουσα επιστημονική γνώση σχετικά με αυτό, σχεδιάζουμε και διερευνούμε 3 σενάρια κρυπτογραφικών εφαρμογών γύρω του. Καταλήγουμε με μια μελέτη της εφικτότητας της γενικευμένης χρήσης του FPTAS για το πρόβλημα αυτό, κάτω από τους περιορισμούς στους χειρισμούς των στιγμιοτύπων εισόδου που απαιτούνται στις αντίστοιχες κρυπτογραφικές εφαρμογές.