Οι κρυπτογράφοι επινοούν μια προσέγγιση για συνολική αναζήτηση απόρρητο | Περιοδικό Quanta

Όλοι γνωρίζουμε ότι πρέπει να είμαστε προσεκτικοί με τις λεπτομέρειες που μοιραζόμαστε στο διαδίκτυο, αλλά οι πληροφορίες που αναζητούμε μπορεί επίσης να είναι αποκαλυπτικές. Αναζητήστε οδηγίες οδήγησης και η τοποθεσία μας γίνεται πολύ πιο εύκολο να μαντέψει κανείς. Ελέγξτε για έναν κωδικό πρόσβασης σε ένα θησαυροφυλάκιο παραβιασμένων δεδομένων και κινδυνεύουμε να διαρρεύσουμε μόνοι μας.

Αυτές οι καταστάσεις τροφοδοτούν ένα βασικό ερώτημα στην κρυπτογραφία: Πώς μπορείτε να αντλήσετε πληροφορίες από μια δημόσια βάση δεδομένων χωρίς να αποκαλύψετε τίποτα σχετικά με το τι έχετε πρόσβαση; Είναι το ισοδύναμο του να τσεκάρεις ένα βιβλίο από τη βιβλιοθήκη χωρίς ο βιβλιοθηκάριος να ξέρει ποιο.

Η διαμόρφωση μιας στρατηγικής που λύνει αυτό το πρόβλημα - γνωστή ως ανάκτηση ιδιωτικών πληροφοριών - είναι "ένα πολύ χρήσιμο δομικό στοιχείο σε μια σειρά εφαρμογών που διατηρούν το απόρρητο", είπε. Ντέιβιντ Γου, κρυπτογράφος στο Πανεπιστήμιο του Τέξας στο Ώστιν. Από τη δεκαετία του 1990, οι ερευνητές απέρριψαν το ερώτημα, βελτιώνοντας τις στρατηγικές για ιδιωτική πρόσβαση σε βάσεις δεδομένων. Ένας σημαντικός στόχος, ο οποίος εξακολουθεί να είναι αδύνατος με μεγάλες βάσεις δεδομένων, είναι το ισοδύναμο μιας ιδιωτικής αναζήτησης Google, όπου μπορείτε να αναζητήσετε ανώνυμα ένα σωρό δεδομένων χωρίς να κάνετε βαριές υπολογιστικές εργασίες.

Τώρα, τρεις ερευνητές έχουν δημιουργημένο μια από καιρό αναζητούμενη έκδοση της ανάκτησης ιδιωτικών πληροφοριών και την επέκτεινε για να δημιουργήσει μια γενικότερη στρατηγική απορρήτου. Το έργο, το οποίο έλαβε α Βραβείο καλύτερου χαρτιού τον Ιούνιο στο ετήσιο Συμπόσιο Θεωρίας Υπολογιστών, καταρρίπτει ένα σημαντικό θεωρητικό εμπόδιο στο δρόμο για μια πραγματικά ιδιωτική αναζήτηση.

"[Αυτό είναι] κάτι στην κρυπτογραφία που υποθέτω ότι όλοι θέλαμε αλλά δεν πιστεύαμε ότι υπάρχει", είπε Βίνοντ Βαϊκουντανάθαν, κρυπτογράφος στο Ινστιτούτο Τεχνολογίας της Μασαχουσέτης που δεν συμμετείχε στην εργασία. «Είναι ένα αποτέλεσμα ορόσημο».

Το πρόβλημα της πρόσβασης σε ιδιωτικές βάσεις δεδομένων διαμορφώθηκε τη δεκαετία του 1990. Αρχικά, οι ερευνητές υπέθεσαν ότι η μόνη λύση ήταν η σάρωση ολόκληρης της βάσης δεδομένων κατά τη διάρκεια κάθε αναζήτησης, κάτι που θα ήταν σαν να σαρώνετε κάθε ράφι από έναν βιβλιοθηκονόμο πριν επιστρέψετε με το βιβλίο σας. Εξάλλου, εάν η αναζήτηση παραλείπει κάποια ενότητα, ο βιβλιοθηκάριος θα γνωρίζει ότι το βιβλίο σας δεν βρίσκεται σε αυτό το μέρος της βιβλιοθήκης.

Αυτή η προσέγγιση λειτουργεί αρκετά καλά σε μικρότερες κλίμακες, αλλά καθώς η βάση δεδομένων μεγαλώνει, ο χρόνος που απαιτείται για τη σάρωσή της αυξάνεται τουλάχιστον αναλογικά. Καθώς διαβάζετε από μεγαλύτερες βάσεις δεδομένων - και το Διαδίκτυο είναι αρκετά μεγάλο - η διαδικασία γίνεται απαγορευτικά αναποτελεσματική.

Στις αρχές της δεκαετίας του 2000, οι ερευνητές άρχισαν να υποψιάζονται ότι μπορούσαν να αποφύγουν το φράγμα πλήρους σάρωσης «προεπεξεργάζοντας» τη βάση δεδομένων. Χονδρικά, αυτό θα σήμαινε την κωδικοποίηση ολόκληρης της βάσης δεδομένων ως ειδική δομή, έτσι ώστε ο διακομιστής να μπορεί να απαντήσει σε ένα ερώτημα διαβάζοντας μόνο ένα μικρό τμήμα αυτής της δομής. Η αρκετά προσεκτική προεπεξεργασία θα μπορούσε, θεωρητικά, να σημαίνει ότι ένας μεμονωμένος διακομιστής που φιλοξενεί πληροφορίες περνάει από τη διαδικασία μόνο μία φορά, από μόνος του, επιτρέποντας σε όλους τους μελλοντικούς χρήστες να συλλάβουν πληροφορίες ιδιωτικά χωρίς περισσότερη προσπάθεια.

Για Ντάνιελ Γουίτς, κρυπτογράφος στο Πανεπιστήμιο Northeastern και συν-συγγραφέας της νέας εργασίας, αυτό φαινόταν πολύ καλό για να είναι αληθινό. Γύρω στο 2011, άρχισε να προσπαθεί να αποδείξει ότι τέτοιου είδους σχέδιο ήταν αδύνατο. «Ήμουν πεπεισμένος ότι δεν υπήρχε περίπτωση να γίνει αυτό», είπε.

Αλλά το 2017, δύο ομάδες ερευνητών δημοσιεύθηκε αποτελέσματα που του άλλαξε γνώμη. Κατασκεύασαν τα πρώτα προγράμματα που μπορούσαν να κάνουν αυτού του είδους την ανάκτηση ιδιωτικών πληροφοριών, αλλά δεν ήταν σε θέση να δείξουν ότι τα προγράμματα ήταν ασφαλή. (Οι κρυπτογράφοι επιδεικνύουν την ασφάλεια ενός συστήματος δείχνοντας ότι η διακοπή του είναι εξίσου δύσκολη με την επίλυση κάποιου δύσκολου προβλήματος. Οι ερευνητές δεν μπόρεσαν να το συγκρίνουν με ένα κανονικό σκληρό πρόβλημα.)

Έτσι, ακόμη και με την ανανέωση της ελπίδας του, ο Wichs υπέθεσε ότι οποιαδήποτε έκδοση αυτών των προγραμμάτων που ήταν ασφαλής ήταν ακόμη πολύ μακριά. Αντίθετα, αυτός και οι συν-συγγραφείς του — Γουέι-Κάι Λιν, τώρα στο Πανεπιστήμιο της Βιρτζίνια, και Ίθαν Μουκ, επίσης στο Northeastern — εργάστηκαν σε προβλήματα που πίστευαν ότι θα ήταν ευκολότερα, τα οποία αφορούσαν περιπτώσεις όπου πολλοί διακομιστές φιλοξενούν τη βάση δεδομένων.

Στις μεθόδους που μελέτησαν, οι πληροφορίες στη βάση δεδομένων μπορούν να μετατραπούν σε μια μαθηματική έκφραση, την οποία οι διακομιστές μπορούν να αξιολογήσουν για να εξαγάγουν τις πληροφορίες. Οι συγγραφείς σκέφτηκαν ότι μπορεί να είναι δυνατό να γίνει αυτή η διαδικασία αξιολόγησης πιο αποτελεσματική. Έπαιξαν με μια ιδέα του 2011, όταν άλλοι ερευνητές είχαν βρει έναν τρόπο να αξιολογήσουν γρήγορα μια τέτοια έκφραση προεπεξεργάζοντάς την, δημιουργώντας ειδικούς, συμπαγείς πίνακες τιμών που σας επιτρέπουν να παραλείψετε τα κανονικά βήματα αξιολόγησης.

Αυτή η μέθοδος δεν έφερε καμία βελτίωση και η ομάδα κόντεψε να εγκαταλείψει - μέχρι που αναρωτήθηκαν αν αυτό το εργαλείο θα μπορούσε πράγματι να λειτουργήσει στην πολυπόθητη περίπτωση ενός διακομιστή. Διαλέξτε ένα πολυώνυμο αρκετά προσεκτικά, είδαν, και ένας μόνο διακομιστής θα μπορούσε να το προεπεξεργαστεί με βάση το αποτέλεσμα του 2011 — αποδίδοντας το ασφαλές, αποτελεσματικό σύστημα αναζήτησης που ο Wichs είχε σκεφτεί εδώ και χρόνια. Ξαφνικά, είχαν λύσει το πιο δύσκολο πρόβλημα τελικά.

Στην αρχή, οι συγγραφείς δεν το πίστευαν. «Ας καταλάβουμε τι φταίει σε αυτό», θυμήθηκε ο Wichs να σκέφτεται. «Προσπαθούσαμε να καταλάβουμε πού χαλάει».

Αλλά η λύση ίσχυε: Είχαν πραγματικά ανακαλύψει έναν ασφαλή τρόπο προεπεξεργασίας μιας βάσης δεδομένων ενός διακομιστή, ώστε ο καθένας να μπορεί να αντλεί πληροφορίες μυστικά. «Είναι πραγματικά πέρα ​​από όλα όσα περιμέναμε», είπε Γιουβάλ Ισάι, κρυπτογράφος στο Technion στο Ισραήλ που δεν συμμετείχε σε αυτή τη δουλειά. Είναι ένα αποτέλεσμα «δεν ήμασταν αρκετά γενναίοι να το ζητήσουμε», είπε.

Αφού δημιούργησαν το σχέδιο μυστικής αναζήτησης, οι συγγραφείς στράφηκαν στον πραγματικό στόχο μιας ιδιωτικής αναζήτησης στο Διαδίκτυο, ο οποίος είναι πιο περίπλοκος από την άντληση τμημάτων πληροφοριών από μια βάση δεδομένων, είπε ο Wichs. Το σύστημα ιδιωτικής αναζήτησης από μόνο του επιτρέπει μια έκδοση ιδιωτικής αναζήτησης που μοιάζει με το Google, αλλά είναι εξαιρετικά εντατική: Εκτελείτε μόνοι σας τον αλγόριθμο της Google και τραβάτε κρυφά δεδομένα από το Διαδίκτυο όταν είναι απαραίτητο. Ο Wichs είπε ότι μια αληθινή αναζήτηση, όπου στέλνεις ένα αίτημα και κάθεσαι αναπαυτικά ενώ ο διακομιστής συλλέγει τα αποτελέσματα, είναι πραγματικά στόχος για μια ευρύτερη προσέγγιση γνωστή ως ομομορφική κρυπτογράφηση, η οποία συγκαλύπτει τα δεδομένα έτσι ώστε κάποιος άλλος να μπορεί να τα χειριστεί χωρίς να γνωρίζει τίποτα γι 'αυτό. .

Τυπικές ομόμορφες στρατηγικές κρυπτογράφησης θα έπλητταν το ίδιο εμπόδιο με την ανάκτηση ιδιωτικών πληροφοριών, διαπερνώντας όλο το περιεχόμενο του Διαδικτύου για κάθε αναζήτηση. Αλλά χρησιμοποιώντας τη μέθοδο ιδιωτικής αναζήτησης ως σκαλωσιά, οι συγγραφείς κατασκεύασαν ένα νέο σχήμα που εκτελεί υπολογισμούς που μοιάζουν περισσότερο με τα προγράμματα που χρησιμοποιούμε καθημερινά, αντλώντας πληροφορίες κρυφά χωρίς να σαρώνουν ολόκληρο το Διαδίκτυο. Αυτό θα παρείχε ώθηση αποτελεσματικότητας για τις αναζητήσεις στο Διαδίκτυο και για όλα τα προγράμματα που χρειάζονται γρήγορη πρόσβαση σε δεδομένα.

Ενώ η ομομορφική κρυπτογράφηση είναι μια χρήσιμη επέκταση του συστήματος ιδιωτικής αναζήτησης, είπε ο Ishai, βλέπει την ανάκτηση ιδιωτικών πληροφοριών ως το πιο θεμελιώδες πρόβλημα. Η λύση των συγγραφέων είναι το «μαγικό δομικό στοιχείο» και η στρατηγική τους για ομομορφική κρυπτογράφηση είναι μια φυσική συνέχεια.

Προς το παρόν, κανένα από τα δύο σχήματα δεν είναι πρακτικά χρήσιμο: Η προεπεξεργασία αυτή τη στιγμή βοηθά στα άκρα, όταν το μέγεθος της βάσης δεδομένων κινείται προς το άπειρο. Αλλά στην πραγματικότητα η ανάπτυξή του σημαίνει ότι αυτές οι εξοικονομήσεις δεν μπορούν να πραγματοποιηθούν και η διαδικασία θα καταναλώσει πολύ χρόνο και χώρο αποθήκευσης.

Ευτυχώς, είπε ο Vaikuntanathan, οι κρυπτογράφοι έχουν μακρά ιστορία βελτιστοποίησης αποτελεσμάτων που αρχικά ήταν ανέφικτα. Εάν οι μελλοντικές εργασίες μπορούν να εξορθολογίσουν την προσέγγιση, πιστεύει ότι οι ιδιωτικές αναζητήσεις από γιγάντιες βάσεις δεδομένων μπορεί να είναι εφικτές. «Όλοι πιστεύαμε ότι ήμασταν κολλημένοι εκεί», είπε. "Αυτό που δίνει το αποτέλεσμα του Daniel είναι ελπίδα."

Quanta διεξάγει μια σειρά από έρευνες για την καλύτερη εξυπηρέτηση του κοινού μας. Πάρτε το δικό μας έρευνα αναγνωστών επιστήμης υπολογιστών και θα μπείτε για να κερδίσετε δωρεάν Quanta εμπορεύματα.