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

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

«Ήμουν ταραχοποιός», είπε. «Βασικά —όχι εντελώς, αλλά βασικά— με έδιωξαν από το γυμνάσιο».

Καλάι γεννήθηκε και μεγάλωσε στο Τελ Αβίβ του Ισραήλ, σε ακαδημαϊκή οικογένεια. Ο πατέρας της, Yair Tauman, είναι οικονομολόγος και θεωρητικός παιγνίων. Τα μαθήματά της στο γυμνάσιο την βαρέθηκαν – μια έκθεση κατέγραφε περίπου 150 απουσίες από το σχολείο, θυμάται, καθώς προτιμούσε να περνάει τον χρόνο της κάνοντας θαλάσσιο σκι και κοινωνικές συναναστροφές. Αλλά οι αναλυτικές της ικανότητες ήταν πάντα εκεί.

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

Η αδρανής αγάπη της για τα μαθηματικά ξύπνησε τελικά στο κολέγιο, όταν άρχισε να αναγνωρίζει την ομορφιά τους. Τελικά, ανακάλυψε ότι μπορούσε να χρησιμοποιήσει αυτά τα μαθηματικά με υπολογιστές και, συγκεκριμένα, με την ασφάλεια πληροφοριών. Τώρα, η δουλειά της εκτείνεται στους τομείς των μαθηματικών και της επιστήμης των υπολογιστών και οι ιδέες της ήταν θεμελιώδεις για το πώς προστατεύουμε και επαληθεύουμε τους υπολογισμούς στην ψηφιακή εποχή. Τις τελευταίες δύο δεκαετίες, έχει εργαστεί για να διασφαλίσει την ακεραιότητα των smartphone μας, των συνδέσεων cloud, ακόμη και των κρυπτονομισμάτων μας. Τώρα ερευνήτρια στη Microsoft και επίκουρη καθηγήτρια στο Τεχνολογικό Ινστιτούτο της Μασαχουσέτης, κέρδισε πρόσφατα το διάσημο βραβείο ACM in Computing του Association for Computer Machinery για «καινοτομίες στην επαληθεύσιμη ανάθεση υπολογιστών και θεμελιώδεις συνεισφορές στην κρυπτογραφία». Η τελευταία της δουλειά κοιτάζει επίσης στο μέλλον, καθώς εξετάζει πώς οι κβαντικοί υπολογιστές μπορούν να επηρεάσουν το τοπίο ασφαλείας.

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

Πώς έγινες από ταραχοποιός στο γυμνάσιο σε ακαδημαϊκός;

Πάντα ήξερα ότι μου αρέσουν τα μαθηματικά, αλλά τα μαθηματικά στο γυμνάσιο δεν ήταν καθόλου ενδιαφέροντα. Μετά πήγα να σπουδάσω μαθηματικά στο προπτυχιακό, και έμεινα έκπληκτος. Είναι η πρώτη φορά στη ζωή μου που κάθισα και μελετούσα ασταμάτητα, από το πρωί μέχρι το βράδυ. Ήμουν σε ευφορία. Και πρέπει να πω ότι στεναχωρήθηκα λίγο, γιατί σκέφτηκα, «Δεν μπορώ να πιστέψω ότι θα μπορούσα να το είχα απολαύσει όταν ήμουν πολύ νεότερος!»

Τι ήταν αυτό στα μαθηματικά που σας συνεπήρε;

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

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

Σε τι είδους κρυπτογραφικά προβλήματα ασχοληθήκατε;

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

Το λύσαμε αυτό με κάτι που ονομάζαμε ring signatures, οι οποίες εμπνεύστηκαν από μια έννοια στην επιστήμη των υπολογιστών που ονομάζονται αποδείξεις αδιάκριτες μάρτυρες. Ας πούμε ότι υπάρχει μια δήλωση και δύο διαφορετικοί τρόποι για να το αποδείξουμε. Λέμε ότι υπάρχουν δύο «μάρτυρες» ότι η δήλωση είναι σωστή — καθεμία από τις αποδείξεις. Μια απόδειξη που δεν διακρίνεται από τους μάρτυρες είναι η ίδια ανεξάρτητα από το ποια χρησιμοποιείτε: Κρύβει με ποιον μάρτυρα ξεκινήσατε.

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

Θα χρησιμοποιούσε ποτέ ένα ίδρυμα αυτό το σύστημα;

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

Πώς εξελίχθηκε η δουλειά σας στην ανάλυση της ασφάλειας των συσκευών μας;

Στις αρχές της δεκαετίας του 2000 ήμουν στο τέλος του διδακτορικού μου, δουλεύοντας με τον Shafi Goldwasser στο MIT. Ο κόσμος είχε μόλις αρχίσει να μιλά για το cloud computing, το οποίο πλέον χρησιμοποιούμε καθημερινά. Πριν, είχατε μια τεράστια επιφάνεια εργασίας όπου γίνονταν τα πάντα. Με την αύξηση της μεγάλης συλλογής δεδομένων, οι υπολογισμοί έγιναν πιο δαπανηροί και άρχισαν να γίνονται εξ αποστάσεως. Η ιδέα είναι ότι υπάρχει ένα ισχυρό σύννεφο που κάνει υπολογισμούς για εσάς. Αλλά μπορεί να μην εμπιστεύεστε την πλατφόρμα cloud, οπότε πώς ξέρετε ότι κάνουν τον υπολογισμό σωστά; Μερικές φορές μπορεί να υπάρχει ένα κίνητρο για εξαπάτηση επειδή ο υπολογισμός μπορεί να είναι πολύ δαπανηρός. Και στη συνέχεια, σε ορισμένες ρυθμίσεις μπορεί να ανησυχείτε για τυχαίο σφάλμα. Επομένως, θέλετε πραγματικά μια απόδειξη ότι αυτός ο υπολογισμός είναι σωστός.

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

Πώς προέκυψαν αυτές οι αποδείξεις;

Ξεκίνησε το 1985 με τους Shafi Goldwasser, Silvio Micali και Charles Rackoff, οι οποίοι μαζί εισήγαγαν την έννοια των διαδραστικών αποδείξεων. Πριν, όταν οι άνθρωποι σκεφτόντουσαν αποδείξεις, σκέφτηκαν να γράψουν γραμμές δεδομένων και μπορείτε να διαβάσετε και να ελέγξετε αν είναι σωστές ή όχι. Οι Goldwasser, Micali και Rackoff εισήγαγαν έναν εντελώς διαφορετικό τρόπο απόδειξης: χρησιμοποιώντας την αλληλεπίδραση. Υπάρχει ένας prover και υπάρχει ένας επαληθευτής, και ανταλλάσσουν μηνύματα πέρα ​​δώθε. Στη συνέχεια, ο επαληθευτής αποφασίζει εάν είναι πεπεισμένος ή όχι.

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

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

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

Σαν πιστοποιητικό γνησιότητας;

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

Πώς, λοιπόν, καταργείτε την αλληλεπίδραση για τη δημιουργία αυτών των μεταβιβάσιμων πιστοποιητικών;

Με κρυπτογραφία. Επιτρέψτε μου να προσπαθήσω να σας δώσω μια διαίσθηση για το πώς λειτουργεί αυτό. Στις διαδραστικές μας αποδείξεις, ο επαληθευτής συνήθως στέλνει απλώς την τυχαιότητα στον prover — θα μπορούσατε να το σκεφτείτε ως ο επαληθευτής που ελέγχει τυχαία την απόδειξη. Τότε ο Amos Fiat και ο Adi Shamir είχαν μια ιδέα: Γιατί χρειάζεστε αυτόν τον επαληθευτή εάν το μόνο που κάνει είναι να στέλνει τυχαία; Ίσως μπορούμε να αντικαταστήσουμε αυτόν τον επαληθευτή με κάποια λειτουργία, όπως κάτι που ονομάζεται συνάρτηση κατακερματισμού — είναι μια συνάρτηση που φαίνεται τυχαία και είναι ένα πολύ σημαντικό δομικό στοιχείο στην κρυπτογραφία.

Και αποδεικνύεται ότι ναι, μπορούμε. Σήμερα, αυτό γίνεται συνεχώς. Εάν διαθέτετε iPhone ή Android, χρησιμοποιείτε το παράδειγμα Fiat-Shamir όταν το τηλέφωνό σας συνδέεται σε απομακρυσμένους διακομιστές, κάτι που μπορεί να συμβαίνει συχνά κατά τη διάρκεια της ημέρας. Και είναι αυτό το παράδειγμα που χρησιμοποιούμε για να κατασκευάσουμε τις συνοπτικές αποδείξεις που πιστοποιούν ότι οι απομακρυσμένοι υπολογισμοί είναι σωστοί.

Μιλήσατε για μηχανές που πρέπει να είναι «μετακβαντικά ασφαλείς». Τι σημαίνει αυτό?

Οι κβαντικοί υπολογιστές, εάν όντως δημιουργηθούν σε μεγάλη κλίμακα, θα είναι πολύ πιο ισχυροί από τους κλασικούς υπολογιστές. Οι κλασικοί υπολογιστές λειτουργούν σε bit, τα οποία είναι είτε 0 είτε 1. Στους κβαντικούς υπολογιστές, έχετε κβαντικά bit, τα οποία βρίσκονται σε υπέρθεση μεταξύ 0 και 1. Και αυτά τα qubit είναι μπλεγμένα, πράγμα που σημαίνει ότι επηρεάζουν το ένα το άλλο. Αυτό είναι που δίνει πραγματικά τη δύναμή τους στους κβαντικούς υπολογιστές.

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

Το 2018 έγινε μια ρηξικέλευθη αποτέλεσμα από μια φοιτήτρια του Μπέρκλεϊ, την Ουρμίλα Μαχάντεφ. Ήταν η πρώτη που έδειξε μια κλασική, υπολογιστικά ασφαλή απόδειξη για την επαλήθευση των κβαντικών υπολογισμών.

Μπορείτε λοιπόν να χρησιμοποιήσετε έναν κλασικό υπολογιστή για να επαληθεύσετε τους κβαντικούς υπολογισμούς; Αυτό ακούγεται αδύνατο!

Δεν είναι καταπληκτικό; Ήμουν στην επιτροπή προγράμματος όταν η Urmila δημοσίευσε την εργασία της και πέρασα όλη τη νύχτα κοιτάζοντάς την — την ποσότητα καφεΐνης που έπινα! Ήμουν μπερδεμένος. Σε εκείνο το σημείο, ήμουν ένα πλήρες κβαντικό ομοίωμα. Κατάλαβα το κρυπτογραφικό μέρος, αλλά μου πήρε λίγο χρόνο για να καταλάβω πώς αυτό συνδυάστηκε με το κβαντικό μέρος. Και ήταν όμορφο.

Η μετάβαση από την κλασική στην κβαντική υπολογιστική ακούγεται σαν μια απότομη καμπύλη εκμάθησης.

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