Ομομορφική κρυπτογραφία με ιδεώδη δικτυώματα

Abstract

Η παρούσα μεταπτυχιακή διατριβή αποτελεί μια μελέτη για την ανάπτυξη της πλήρους ομομορφικής κρυπτογραφίας. Μελετάμε το σχήμα του Gentry το οποίο αποτελεί το πρώτο πλήρες ομομορφικό σχήμα, λύνοντας έτσι ένα ανοιχτό πρόβλημα εδώ και δεκαετίες στον τομέα της Κρυπτογραφίας. Η κατασκευή του Gentry μας επιτρέπει την εκτέλεση αυθαίρετα μεγάλου αριθμού υπολογισμών με κρυπτογραφημένα δεδομένα χωρίς να απαιτείται η αποκρυπτογράφηση τους πρώτα. Η χρήση της πλήρους ομομορφικής κρυπτογράφησης έχει ποικίλες εφαρμογές. Για παράδειγμα, μας επιτρέπει να εκτελέσουμε ερωτήματα σε μια μηχανή αναζήτησης διασφαλίζοντας την ιδιωτικότητα της αναζήτησής μας. Ας υποθέσουμε πως ένας χρήστης επιθυμεί να κάνει μια αναζήτηση σε μια μηχανή αναζήτησης. Για να το πραγματοποιήσει θέτει ένα ερώτημα στην μηχανή σε κρυπτογραφημένη όμως μορφή. Η μηχανή υλοποιεί ένα πλήρες ομομορφικό σχήμα έτσι μπορεί να χειριστεί το κρυπτογραφημένο ερώτημα από τον χρήστη και να του επιστρέψει τα αποτελέσματα σε επίσης κρυπτογραφημένη μορφή. Με αυτό τον σχεδιασμό η μηχανή εκτέλεσε το ερώτημα χωρίς να γνωρίζει ποιό είναι αυτό αφού δεν το αποκρυπτογράφησε πρώτα. Ο χρήστης λαμβάνει το κρυπτογραφημένο αποτελέσματα της αναζήτησης του και στην συνέχεια ο ίδιος το αποκρυπτογραφεί και το διαβάζει. Έτσι εξασφαλίζει την ιδιωτικότητα της αναζήτησής του. Η κατασκευή του Gentry ξεκινά με ένα κάπως ομομορφικό σχήμα (somewhat homomorphic scheme). Στην συνέχεια τροποποιεί κατάλληλα το σχήμα με την τεχνική του squashing ώστε να το εφοδιάσει με μια πολύ χρήσιμη ιδιότητα που καλείται bootstrappability. Τέλος, αποδεικνύει πως κάθε εκκινήσιμο(bootstrappable) σχήμα το οποίο είναι επιπλέον και κάπως ομομορφικό μπορεί να μετατραπεί σε ένα πλήρως ομομορφικό σχήμα με μια αναδρομική διαδικασία αυτό- ενσωμάτωσης. Η ασφάλεια του συστήματος Gentry στηρίζεται σε δύσκολα προβλήματα της θεωρίας δικτυωμάτων και σε μια παραλλαγή του προβλήματος αθροίσματος υποσυνόλων που καλείται sparse subset sum problem.