Secure and efficient searchable encryption
Authors: Μολλά Ειρήνη 
Published: October 2024

Η συνεχόμενη αύξηση της ζήτησης για υπηρεσίες αποθήκευσης των δεδομένων στο υπολογιστικό νέφος (Cloud) θέτει σε κίνδυνο την ιδιωτικότητά τους. Η κρυπτογράφηση αποτελεί την προφανή λύση. Ωστόσο, με την κρυπτογράφηση χάνεται η δυνατότητα της αναζήτησης καθώς ο εξυπηρετητής (Server) δεν μπορεί να επεξεργαστεί τα δεδομένα στην κρυπτογραφημένη τους μορφή. Για να αντιμετωπιστεί αυτό το πρόβλημα, έχουν προταθεί διάφορες κρυπτογραφικές λύσεις, όπως η πλήρης ομομορφηκή κρυπτογράφηση (Fully Homomorphic Encryption, FHE) , η κρυπτογράφηση πολλαπλών μερών (Multi-Party Computation, MPC) , η κρυπτογράφηση διατήρησης ιδιοτήτων (Property Preserving Encryption, PPE) και η συναρτησιακή κρυπτογράφηση (Functional Encryption, FE). Όλες αυτές οι λύσεις είναι είτε μη πρακτικές είτε έχουν ευπάθειες. Μία από τις πιο υποσχόμενες κρυπτογραφικές τεχνικές για την αναζήτηση σε κρυπτογραφημένα δεδομένα είναι η συμμετρική κρυπτογράφηση με δυνατότητα αναζήτησης (Searchable Symmetric Encryption, SSE). Τα μοντέλα SSE προσφέρουν μια καλή ισορροπία μεταξύ ασφάλειας και αποτελεσματικότητας. Η κύρια συνεισφορά της παρούσας διδακτορικής διατριβής επικεντρώνεται σε ερωτήματα εύρους και τομής σε κρυπτογραφημένα δεδομένα χρησιμοποιώντας μοντέλα SSE για βάσεις δεδομένων κλειδιού-τιμής (key-value), θεωρώντας ότι ο εξυπηρετητής είναι ειλικρινής και ταυτόχρονα περίεργος (honest-but-curious). Από το 2000 και την παρουσίαση του SSE από τους Song et al.[1], το μεγαλύτερο μέρος της έρευνας έχει επικεντρωθεί σε μοντέλα που υποστηρίζουν ερωτήματα μίας λέξης-κλειδί (single keyword). Για τα μοντέλα SSE, που υποστηρίζουν ερωτήματα εύρους (range queries), μελετάμε ένα τρόπο αξιοποίησης του ανεστραμμένου ευρετηρίου (inverted index) έτσι ώστε με ένα ερώτημα μίας λέξης-κλειδιού να μπορεί να υπολογιστεί ερώτημα εύρους (range queries). Παρουσιάζουμε μοντέλα SSE που υποστηρίζουν τόσο ερωτήματα μίας λέξης-κλειδί (single keyword) όσο και ερωτήματα εύρους (range queries), βασιζόμενα στο ανεστραμμένο ευρετήριο (inverted index). Το πρώτο μοντέλο ονομάζεται REX, δεν είναι διαδραστικό (single round) και αποκαλύπτει την κρυπτογραφημένη απάντηση (no response-hiding/response revealing). Έχει βέλτιστη πολυπλοκότητα υπολογισμού επικοινωνίας και αναζήτησης, ενώ είναι πολύ πιο ασφαλής από την κρυπτογράφηση που βασίζεται στη διατήρηση ταξινόμησης (Order Preserving Encryption, OPE). Στη συνέχεια, παρουσιάζουμε ένα ακόμη μοντέλο που ονομάζεται oRQSSE, το οποίο προσφέρει ερωτήματα μίας λέξης-κλειδί (single keyword) και ερωτήματα εύρους βασιζόμενο στο ίδιο ανεστραμμένο ευρετήριο (inverted index) με το προηγούμενο μοντέλο, έχοντας όμως μη ανιχνεύσιμες προσβάσεις στη μνήμη (ORAM), ενισχύοντας έτσι την ασφάλεια. Αποδεικνύουμε ότι από το μοντέλο μας δεν διαρρέει το μοτίβο αναζήτησης, (search pattern) το μοτίβο πρόσβασης (access pattern) ή το επικαλυπτόμενο μοτίβο (overlapping pattern) εκτός από το μοτίβο όγκου (volume pattern). Επιπλέον, παρουσιάζουμε ένα μοντέλο SSE που υποστηρίζει ερωτήματα τομής και ονομάζεται ConQSSE. Αποθηκεύουμε τους δημοφιλής συνδυασμούς λέξεων-κλειδιών με συνεχόμενο τρόπο σε ένα ανεστραμμένο ευρετηρίο (inverted index). Αν το ερώτημα τομής αποτελείται από δημοφιλή συνδυασμό λέξεων-κλειδιών τότε η πολυπλοκότητα επικοινωνίας είναι η βέλτιστη, ενώ αν ο συνδυασμός των λέξεων-κλειδιών δεν είναι δημοφιλής τότε απλοποιείται το ερώτημα σε υποερωτήματα συνεχόμενων λέξεων-κλειδιών και οι απαντήσεις αυτών στέλνονται σε άλλο μοντέλο που υποστηρίζει ερωτήματα τομής όπου και υπολογίζεται η τελική απάντηση. Το μοντέλο μας είναι ευέλικτο, επομένως θα μπορούσε να συνδυαστεί εύκολα με άλλα μοντέλα καθώς επίσης θα μπορούσε να εφαρμοστεί και να διαχειρίζεται από έναν αλγόριθμο μη ανιχνεύσιμης μνήμης (ORAM) , ενισχύοντας την ασφάλειά του. Η εφαρμογή του σχήματός μας, λόγω της χρήσης του δημοφιλούς συνδυασμού λέξεων-κλειδιών, μπορεί να εφαρμοστεί από δεδομένα υγειονομικής περίθαλψης έως και δεδομένα εμπιστευτικών εγγράφων σε χρηματοπιστωτικά ιδρύματα.