Φανταστείτε ότι είχατε κάποιες χρήσιμες γνώσεις — ίσως μια μυστική συνταγή ή το κλειδί για μια κρυπτογράφηση. Θα μπορούσατε να αποδείξετε σε έναν φίλο ότι είχατε αυτή τη γνώση, χωρίς να αποκαλύψετε τίποτα σχετικά; Οι επιστήμονες υπολογιστών απέδειξαν πριν από περισσότερα από 30 χρόνια ότι θα μπορούσατε, εάν χρησιμοποιούσατε αυτό που ονομάζεται απόδειξη μηδενικής γνώσης.
Για έναν απλό τρόπο κατανόησης αυτής της ιδέας, ας υποθέσουμε ότι θέλετε να δείξετε στον φίλο σας ότι ξέρετε πώς να περνάτε μέσα από έναν λαβύρινθο, χωρίς να αποκαλύπτετε λεπτομέρειες σχετικά με το μονοπάτι. Θα μπορούσατε απλά να διασχίσετε τον λαβύρινθο μέσα σε ένα χρονικό όριο, ενώ ο φίλος σας είχε απαγορευθεί να παρακολουθήσει. (Το χρονικό όριο είναι απαραίτητο γιατί εάν δοθεί αρκετός χρόνος, οποιοσδήποτε μπορεί τελικά να βρει τη διέξοδο μέσω δοκιμής και λάθους.) Ο φίλος σας θα ήξερε ότι μπορείτε να το κάνετε, αλλά δεν θα ήξερε πώς.
Οι αποδείξεις μηδενικής γνώσης βοηθούν τους κρυπτογράφους, που εργάζονται με μυστικές πληροφορίες, αλλά και τους ερευνητές υπολογιστικής πολυπλοκότητας, που ασχολούνται με την ταξινόμηση της δυσκολίας διαφορετικών προβλημάτων. "Πολλή σύγχρονη κρυπτογραφία βασίζεται σε υποθέσεις πολυπλοκότητας - με την υπόθεση ότι ορισμένα προβλήματα είναι δύσκολο να επιλυθούν, επομένως πάντα υπήρχαν κάποιες συνδέσεις μεταξύ των δύο κόσμων", είπε. Claude Crépeau, επιστήμονας υπολογιστών στο Πανεπιστήμιο McGill. «Αλλά [αυτές] οι αποδείξεις έχουν δημιουργήσει έναν ολόκληρο κόσμο σύνδεσης».
Οι αποδείξεις μηδενικής γνώσης ανήκουν σε μια κατηγορία που είναι γνωστή ως διαδραστικές αποδείξεις, επομένως για να μάθετε πώς λειτουργούν οι πρώτες, βοηθάει στην κατανόηση της δεύτερης. Πρώτα περιγράφεται σε μια εργασία του 1985 από τους επιστήμονες υπολογιστών Shafi Goldwasser, Silvio Micali και Charles Rackoff, οι διαδραστικές αποδείξεις λειτουργούν σαν ανάκριση: Σε μια σειρά μηνυμάτων, το ένα μέρος (ο prover) προσπαθεί να πείσει το άλλο (τον επαληθευτή) ότι μια δεδομένη δήλωση είναι αληθινή. Μια διαδραστική απόδειξη πρέπει να ικανοποιεί δύο ιδιότητες. Πρώτον, μια αληθινή δήλωση θα πείσει πάντα τελικά έναν ειλικρινή επαληθευτή. Δεύτερον, εάν η δεδομένη δήλωση είναι ψευδής, κανένας αποδεικτικός - ακόμη και κάποιος που προσποιείται ότι κατέχει ορισμένες γνώσεις - δεν μπορεί να πείσει τον επαληθευτή, παρά μόνο με αμελητέα μικρή πιθανότητα.
Οι διαδραστικές αποδείξεις είναι πιθανολογικής φύσης. Ο επαληθευτής θα μπορούσε να απαντήσει σωστά σε μία ή δύο ερωτήσεις απλά από τύχη, επομένως χρειάζεται ένας αρκετά μεγάλος αριθμός προκλήσεων, τις οποίες ο επαληθευτής πρέπει να τις κάνει σωστά, ώστε ο επαληθευτής να γίνει σίγουρος ότι ο επαληθευτής γνωρίζει πράγματι ότι η δήλωση είναι αληθινή.
Αυτή η ιδέα των αλληλεπιδράσεων προέκυψε όταν ο Micali και ο Goldwasser -τότε μεταπτυχιακοί φοιτητές στο Πανεπιστήμιο της Καλιφόρνια στο Μπέρκλεϋ- μπερδεύτηκαν με τα logistics του παιχνιδιού πόκερ μέσω ενός δικτύου. Πώς μπορούν όλοι οι παίκτες να επαληθεύσουν ότι όταν ένας από αυτούς παίρνει ένα φύλλο από την εικονική τράπουλα, το αποτέλεσμα είναι τυχαίο; Οι διαδραστικές αποδείξεις θα μπορούσαν να οδηγήσουν. Τότε, όμως, πώς μπορούν οι παίκτες να επαληθεύσουν ότι ολόκληρο το πρωτόκολλο - το πλήρες σύνολο κανόνων - τηρήθηκε σωστά, χωρίς να αποκαλυφθεί το χέρι κάθε παίκτη στην πορεία;
Για να επιτύχουν αυτόν τον στόχο, οι Micali και Goldwasser πρόσθεσαν μια τρίτη ιδιότητα στις δύο που απαιτούνται για μια διαδραστική απόδειξη: Η απόδειξη δεν πρέπει να αποκαλύπτει τίποτα για την ίδια τη γνώση, μόνο την αλήθεια της δήλωσης. "Υπάρχει μια ιδέα να περάσει κανείς από ένα πρωτόκολλο, στο τέλος του οποίου πιστεύεις ότι [οι παίκτες πόκερ] δεν ξέρουν τίποτα περισσότερο από αυτό που υποτίθεται ότι γνωρίζουν", είπε ο Goldwasser.
Ας εξετάσουμε το κλασικό παράδειγμα. Η Αλίκη θέλει να αποδείξει στον Μπομπ ότι ένα συγκεκριμένο γράφημα G — μια μοναδική συλλογή κορυφών (κουκκίδων) που συνδέονται με ακμές (γραμμές) — έχει έναν «κύκλο Χαμιλτονίου». Αυτό σημαίνει ότι το γράφημα έχει μια διαδρομή που επισκέπτεται κάθε κουκκίδα ακριβώς μία φορά και τελειώνει στην ίδια κουκκίδα από την οποία ξεκίνησε. Η Αλίκη θα μπορούσε να το κάνει αυτό δείχνοντας απλώς στον Μπομπ το μονοπάτι που το κάνει αυτό, αλλά φυσικά τότε θα ήξερε και εκείνος το μονοπάτι.
Να πώς η Αλίκη μπορεί να πείσει τον Μπομπ ότι ξέρει ότι υπάρχει τέτοιο μονοπάτι, χωρίς να του το δείξει. Πρώτα σχεδιάζει ένα νέο γράφημα, H, αυτό δεν μοιάζει G αλλά είναι παρόμοιο με έναν κρίσιμο τρόπο: Έχει τον ίδιο αριθμό κορυφών, που συνδέονται με τους ίδιους τρόπους. (Αν G έχει πραγματικά έναν Χαμιλτονιανό κύκλο, αυτή η ομοιότητα σημαίνει H θα επίσης.) Στη συνέχεια, αφού καλύψει κάθε άκρη μέσα H με κολλητική ταινία, κλειδώνει H σε ένα κουτί και δίνει το κουτί στον Μπομπ. Αυτό τον εμποδίζει να το δει άμεσα αλλά και την εμποδίζει να το αλλοιώσει. Τότε ο Μπομπ κάνει μια επιλογή: Είτε μπορεί να ζητήσει από την Αλίκη να το δείξει αυτό H είναι πραγματικά παρόμοια με G, ή μπορεί να της ζητήσει να του δείξει τον κύκλο Χαμιλτονιανών H. Και τα δύο αιτήματα θα πρέπει να είναι εύκολα για την Αλίκη, υποθέτοντας ότι H είναι πραγματικά αρκετά παρόμοια με G, και ότι ξέρει πραγματικά το μονοπάτι.
Φυσικά, ακόμα κι αν η Αλίκη δεν γνωρίζει τον κύκλο Χαμιλτονιανών G, μπορεί να προσπαθήσει να ξεγελάσει τον Μπομπ, είτε σχεδιάζοντας γραφήματα που δεν είναι παρόμοια με G, ή υποβάλλοντας γραφήματα δεν γνωρίζει τη διαδρομή. Αλλά αφού έχουν παίξει πολλούς γύρους, η πιθανότητα η Αλίκη να εξαπατά τον Μπομπ κάθε φορά γίνεται εξαιρετικά μικρή. Αν τα κάνει όλα σωστά, τελικά ο Μπομπ θα πειστεί ότι η Αλίκη γνωρίζει έναν κύκλο Χαμιλτονίου σε γράφημα G, χωρίς να το έχει δει ποτέ ο Μπομπ.
Μετά την αρχική εργασία που περιέγραψε για πρώτη φορά τέτοιες αποδείξεις, ο Micali και δύο μαθηματικοί - Oded Goldreich και Avi Wigderson - ανακάλυψαν μια απροσδόκητη συνέπεια με εκτεταμένα αποτελέσματα. Έχει να κάνει με μια μεγάλη κατηγορία προβλημάτων περίπου ίσης δυσκολίας, γνωστή ως NP. Αυτά τα προβλήματα είναι δύσκολο να επιλυθούν, αλλά οι λύσεις τους είναι εύκολο να επαληθευτούν. Οι τρεις ερευνητές ανακάλυψα ότι, εάν η κρυπτογράφηση είναι πραγματικά ασφαλής είναι δυνατόν, τότε η λύση σε κάθε πρόβλημα στο NP μπορεί επίσης να αποδειχθεί με απόδειξη μηδενικής γνώσης. Αυτή η μελέτη βοήθησε τους ερευνητές συλλάβω του παραλλαγές αποδείξεων μηδενικής γνώσης που δεν απαιτούν καν ασφαλή κρυπτογράφηση εξαρχής. Αυτά είναι γνωστά ως διαδραστικές αποδείξεις πολλαπλών αποδείξεων.
Και το 1988, ο Micali και άλλοι έδειξε ότι εάν ένας prover και ένας επαληθευτής μοιράζονται μια σύντομη σειρά από τυχαία bit, δεν απαιτείται αλληλεπίδραση. Αυτό θεωρητικά σήμαινε ότι οι αποδείξεις μηδενικής γνώσης δεν χρειάζεται να είναι διαδραστικές, πράγμα που θα σήμαινε ότι η συνεχής επικοινωνία μεταξύ δύο μερών δεν είναι απαραίτητη. Αυτό θα τα έκανε πολύ πιο χρήσιμα για τους ερευνητές, αλλά μόνο μετά το γύρισμα του 21ου αιώνα τέτοιες αποδείξεις απογειώθηκαν.
«Στα τέλη της δεκαετίας του 2000, αρχίσαμε να βλέπουμε την εξέλιξη αποτελεσματικών τεχνικών για τη δημιουργία αποδείξεων μηδενικής γνώσης», είπε. Matthew D. Green, κρυπτογράφος στο Πανεπιστήμιο John Hopkins. «Φτάσαμε στο σημείο όπου συνειδητοποιήσαμε: «Περιμένετε λίγο, ίσως υπάρχει ένας τρόπος να το χρησιμοποιήσουμε στην πράξη».
Τώρα ένας prover θα μπορούσε να στείλει ένα μόνο μήνυμα σε έναν επαληθευτή χωρίς να χρειάζεται να είναι και οι δύο στο διαδίκτυο και οι ερευνητές θα μπορούσαν να δημιουργήσουν μια πολύ σύντομη απόδειξη που θα μπορούσε να επαληθευτεί γρήγορα, ακόμη και για πολύ περίπλοκα προβλήματα. Αυτό οδήγησε σε πολλές πρακτικές χρήσεις, όπως τη δυνατότητα γρήγορης επαλήθευσης του blockchain μετά από μια συναλλαγή κρυπτονομίσματος, ενώ ταυτόχρονα αποκρύπτονται οι λεπτομέρειες της συναλλαγής. Και το 2016, μια ομάδα φυσικών έδειξε Πώς οι αποδείξεις μηδενικής γνώσης μπορούν να βοηθήσουν στον πυρηνικό αφοπλισμό: Χωρίς να αποκαλύπτει κανένα μυστικό σχετικά με τον σχεδιασμό της πυρηνικής της κεφαλής, μια χώρα θα μπορούσε τώρα να αποδείξει στους πυρηνικούς επιθεωρητές εάν η κεφαλή είναι ενεργή ή ανενεργή.
Πιο πρόσφατα, η πρόοδος στον κβαντικό υπολογισμό ανάγκασε τον Crépeau να κάνει δοκιμασία ακραίων προηγούμενων ερευνών για να βεβαιωθεί ότι τα πρωτόκολλα μηδενικής γνώσης εξακολουθούν να είναι βιώσιμα. Το 2021 βοήθησε αποδεικνύουν ότι οι διαδραστικές αποδείξεις πολλαπλών αποδείξεων διατηρούν τη μυστικότητά τους ακόμη και όταν εμπλέκονται κβαντικοί υπολογιστές, αλλά η επίτευξη του ίδιου επιπέδου ασφάλειας κάνει το πρωτόκολλο πολύ πιο αργό. Το εύρημα ήταν καλά νέα, είπε, αλλά νέες ανησυχίες θα προκύψουν καθώς η τεχνολογία προχωρά.
«Κάθε τύπος υπολογισμού που μπορεί να κάνουμε στο μέλλον θα περιλαμβάνει κβαντικούς υπολογιστές», είπε ο Crépeau. «Ως καλοί παρανοϊκοί κρυπτογράφοι, όποτε αξιολογούμε την ασφάλεια ενός συστήματος, θέλουμε να βεβαιωθούμε ότι το σύστημά μας είναι ασφαλές».
Σημείωση του συντάκτη: Ο Shafi Goldwasser έχει λάβει χρηματοδότηση από το Ίδρυμα Simons, το οποίο χρηματοδοτεί επίσης αυτό δημοσίως ανεξάρτητη δημοσίευση. Οι αποφάσεις χρηματοδότησης του Simons Foundation δεν επηρεάζουν την κάλυψή μας.
