Η όμορφη ορολογία είναι ένα από τα πλεονεκτήματα της σύγχρονης κρυπτογραφίας. Τα ονόματα των πανκ συγκροτημάτων ή τα παρατσούκλια Tumbl είναι όπως ακούγονται κρυπτογραφικοί όροι όπως "σκληροπυρηνικό κατηγόρημα", "συνάρτηση καταπακτής" ή "αδύνατη διαφορική κρυπτανάλυση"). Μου φαίνεται ότι ένας όρος όπως " μηδενική γνώση".

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

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

Προέλευση μηδενικής γνώσης

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

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

Είναι σημαντικό να σημειωθεί ότι αυτό δεν είναι μόνο ένα θεωρητικό ενδιαφέρον. Υπάρχουν πραγματικές, πρακτικές εφαρμογές στις οποίες αυτά τα πράγματα είναι σημαντικά.

Να ένα: Φανταστείτε ότι ένας πελάτης στον πραγματικό κόσμο θέλει να συνδεθεί σε έναν διακομιστή ιστού χρησιμοποιώντας έναν κωδικό πρόσβασης. Τυπική προσέγγισηστον «πραγματικό κόσμο» το πρόβλημα περιλαμβάνει την αποθήκευση μιας κατακερματισμένης έκδοσης του κωδικού πρόσβασης στον διακομιστή. Η είσοδος σε ένα τέτοιο σύστημα θεωρείται ως ένα είδος «επιβεβαίωσης» ότι ο κατακερματισμός του παρεχόμενου κωδικού πρόσβασης είναι η έξοδος της συνάρτησης κατακερματισμού του τρέχοντος κωδικού πρόσβασης. Και, το πιο σημαντικό, ως "επιβεβαίωση" ότι ο πελάτης γνωρίζει πραγματικά τον κωδικό πρόσβασης.

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

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

Παράδειγμα "Πραγματικού Κόσμου".

Μέχρι στιγμής έχουμε μιλήσει για μάλλον αφηρημένα πράγματα. Πάμε μπροστά και φέρνουμε πραγματικό παράδειγμα(ελαφρώς τρελό) για το πρωτόκολλο μηδενικής γνώσης.

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

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

Φυσικά, πολλοί από εσάς το έχετε ήδη παρατηρήσει. Αυτό που περιέγραψα εδώ είναι μόνο ειδική περίπτωσηδιάσημο θεωρητικό πρόβλημα. Ονομάζεται «πρόβλημα χρωματισμού γραφημάτων τριών χρωμάτων». Μπορεί επίσης να γνωρίζετε ένα πολύ ενδιαφέρον χαρακτηριστικό αυτού του προβλήματος. Για ορισμένα γραφήματα, είναι πολύ δύσκολο να βρεθεί μια λύση ή ακόμα και να προσδιοριστεί ότι υπάρχει μια τέτοια λύση. Το πρόβλημα του χρωματισμού ενός γραφήματος σε τρία χρώματα (και της εύρεσης απάντησης στο ερώτημα αν υπάρχει τέτοια λύση για αυτήν την περίπτωση), όπως είναι γνωστό, ανήκει στην κατηγορία των NP-πλήρης προβλημάτων.

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

Υπάρχει όμως ένα πρόβλημα.

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

ΣΕ πραγματική ζωήΗ κοινή λογική μας λέει ότι η απάντηση σε αυτό το δίλημμα περιλαμβάνει δικηγόρους και λογαριασμούς μεσεγγύησης. Εδώ όμως δεν μιλάμε για πραγματική ζωή, αλλά για κρυπτογραφία. Και, αν έχετε διαβάσει ποτέ τα έργα των κρυπτογράφων, το γνωρίζετε ήδη ο μόνος τρόποςβρείτε μια λύση σε ένα πρόβλημα - βρείτε κάτι εντελώς τρελό τεχνική λύση. Τρελή τεχνική λύση (με καπέλα)

Ας φανταστούμε ότι οι υπάλληλοι της Google συμβουλεύτηκαν τον Silvio Micali από το MIT και αυτός ρώτησε τους συναδέλφους του Oded Goldreich και Avi Wigderson. Μετά από διαβούλευση, ανέπτυξαν ένα πρωτόκολλο που είναι τόσο όμορφο που δεν απαιτεί καν υπολογιστές. Θα χρησιμοποιηθεί μεγάλη αποθήκη με προμήθεια χρωματιστά μολύβια και χαρτί. Θα χρειαστούν περισσότερα ένας μεγάλος αριθμός απόκαπέλα

Ας δούμε πώς λειτουργεί

Αρχικά, θα πάω σε έναν χώρο αποθήκης και θα καλύψω το πάτωμα με χαρτί για να δημιουργήσω έναν χώρο που να αντιπροσωπεύει το κυψελοειδές δίκτυο μου. Μετά θα φύγω από την αποθήκη. Η Google μπορεί τώρα να μπει, να ανακατέψει τη συλλογή των μολυβιών και να επιλέξει οποιαδήποτε τρία χρώματα (όπως κόκκινο/μπλε/μοβ, όπως σε αυτό το παράδειγμα) και το χρώμα που θα αντιπροσωπεύει τη λύση. Σημειώστε ότι το συγκεκριμένο χρώμα που χρησιμοποιείται δεν έχει σημασία.

Πριν φύγετε από την αποθήκη, η Google καλύπτει κάθε κορυφή με ένα καπέλο. Όταν επιστρέψω, αυτό είναι το μόνο που θα δω:

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

Για να με πείσει ότι το πρόβλημα λύθηκε πραγματικά, η Google μου δίνει την ευκαιρία να «ελέγξω» το αποτέλεσμα χρωματισμού του γραφήματος. Έχω το δικαίωμα να επιλέξω, με τυχαία σειρά, ένα πρόσωπο αυτού του γραφήματος (δηλαδή κατά μήκος μιας γραμμής μεταξύ δύο διπλανών καπέλων). Η Google θα αφαιρέσει αυτά τα δύο καπέλα, δείχνοντάς μου ένα μικρό μέρος της λύσης:

Σημειώστε ότι το πείραμά μου έχει δύο πιθανά αποτελέσματα:

Εάν δύο κορυφές που εμφανίζονται έχουν το ίδιο χρώμα (ή καθόλου χρώμα!), τότε ξέρω σίγουρα ότι η Google μου λέει ψέματα. Σε αυτήν την περίπτωση, δεν θα πληρώσω στην Google ούτε ένα σεντ. Εάν οι δύο κορυφές που εμφανίζονται έχουν διαφορετικά χρώματα, τότε η Google δεν με κοροϊδεύει σε αυτήν την περίπτωση.

Ελπίζω η πρώτη δήλωση να είναι προφανής. Το δεύτερο θα απαιτήσει περισσότερα λεπτομερής εξήγηση. Το πρόβλημα είναι ότι ακόμα κι αν το πείραμα ήταν επιτυχές, η Google μπορεί να με εξαπατήσει. Ωστόσο, κοίταξα μόνο κάτω από δύο καπέλα. Εάν υπάρχουν E διακριτές ακμές στο γράφημα, τότε η Google είναι πιθανό να παρέχει μια εσφαλμένη λύση. Για παράδειγμα, μετά από ένα τεστ με κοροϊδεύουν με πιθανότητα (E-1)/E (που για 1000 άκρες θα ήταν 99,9%).

Ευτυχώς, η Google έχει την απάντηση σε αυτήν την ερώτηση. Απλώς θα εκτελέσουμε ξανά το πρωτόκολλο!

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

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

Ένα τέτοιο γεγονός μπορεί να συμβεί - αλλά η πιθανότητα του θα είναι ακόμη μικρότερη. Η πιθανότητα να με κοροϊδέψει η Google δύο φορές στη σειρά είναι (E-1)/E*(E-1)/E (ή περίπου 99,8% πιθανότητα για το παράδειγμά μας 1000 άκρων).

Ευτυχώς, δεν χρειάζεται να σταματήσουμε σε δύο προσπάθειες. Θα προσπαθήσουμε ξανά και ξανά μέχρι να πειστούμε ότι η Google, με μεγάλη πιθανότητα, λέει την αλήθεια.

Σας προτρέπω να μην δέχεστε τον λόγο μου. Δοκιμάστε αυτό το Javascript και δείτε μόνοι σας.

Σημειώστε ότι ποτέ δεν είμαι απολύτως βέβαιος ότι η Google είναι ειλικρινής - υπάρχει πάντα μια μικρή πιθανότητα να με εξαπατήσουν. Όμως, μετά από πολλές επαναλήψεις (Ε^2 στην περίπτωσή μας) θα φτάσω τελικά στο σημείο όπου η Google με κοροϊδεύει με αμελητέα πιθανότητα - αρκετή για να είμαι πρακτικός. Μετά από αυτό, μπορώ εύκολα να δώσω τα χρήματα στην Google.

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

Τι κάνει αυτό το παράδειγμα «μηδενική γνώση»;

Προσπαθώ να σας πείσω ότι αυτό το πρωτόκολλο δεν επιτρέπει τη διαρροή πληροφοριών Λύση Google. Αλλά δεν χρειάζεται να δεχθείτε τα λόγια μου! Ο πρώτος κανόνας των κρυπτογράφων είναι να μην πιστεύουν ποτέ τέτοια πράγματα χωρίς στοιχεία.

Οι Goldwasser, Micali και Rakoff πρότειναν τρία κριτήρια που πρέπει να πληροί κάθε πρωτόκολλο μηδενικής γνώσης. Ανεπίσημα μπορούν να περιγραφούν ως εξής:

Πληρότητα. Εάν η Google μου λέει την αλήθεια, τότε θα πρέπει να έχω ισχυρές αποδείξεις γι' αυτό (αποδείξεις υψηλής πιθανότητας). Αξιοπιστία. Η Google μπορεί να με πείσει μόνο αν λέει την αλήθεια. «Μηδενική αποκάλυψη» (αυτό το κριτήριο λέγεται πραγματικά έτσι). Δεν χρειάζεται να μάθω τίποτα περισσότερο από τη λύση της Google που πήρα.

Έχουμε ήδη συζητήσει τα επιχειρήματα για την πληρότητα. Το πρωτόκολλο θα με πείσει τελικά (με αμελητέα πιθανότητα λάθους) αν το τρέξω αρκετές φορές. Η αξιοπιστία είναι επίσης αρκετά εύκολο να αποδειχθεί. Εάν η Google προσπαθήσει να με εξαπατήσει, θα το εντοπίσω στη συντριπτική πλειονότητα των περιπτώσεων.

Η πιο δύσκολη ιδιότητα παραμένει η «μηδενική γνώση». Για να το καταλάβουμε, ας κάνουμε ένα μάλλον περίεργο πείραμα σκέψης.

Πείραμα σκέψης με μηχανές χρόνου

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

Η ιδέα τους είναι να περάσουν από το εργαστήριο GoogleX και να δανειστούν το πρωτότυπο της χρονομηχανής της Google. Το αρχικό σχέδιο ήταν να γυρίσω μερικά χρόνια πίσω και να χρησιμοποιήσω το επιπλέον ώρα εργασίαςνα βρει νέες λύσεις στο πρόβλημα. Δυστυχώς, όπως και με πολλά άλλα πρωτότυπα της Google, η μηχανή του χρόνου είχε αρκετούς περιορισμούς. Το πιο σημαντικό, μπορεί να ταξιδέψει πίσω στο χρόνο μόνο τεσσεράμισι λεπτά.

Έτσι, δεν χρειάζεται να χρησιμοποιήσετε μια χρονομηχανή για να αυξήσετε τον χρόνο που απαιτείται για την ολοκλήρωση μιας εργασίας. Ωστόσο, αποδεικνύεται ότι αυτή η πολύ περιορισμένη τεχνολογία μπορεί να χρησιμοποιηθεί για να με εξαπατήσει.

Πραγματικά δεν ξέρω τι συμβαίνει εδώ. Αλλά φαίνεται ότι θα ήταν χρήσιμο.

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

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

Ουσιαστικά, η χρονομηχανή επιτρέπει στην Google να "διορθώνει" οποιαδήποτε αποτυχημένη σύνδεση χωρίς να υποψιάζομαι τίποτα. Δεδομένου ότι τα κακά αποτελέσματα θα συμβούν μόνο το 1/3 του χρόνου, ο αναμενόμενος χρόνος εκτέλεσης του πρωτοκόλλου (από την άποψη της Google) είναι οριακά μόνο μεγαλύτερος από ό,τι αν το πρωτόκολλο εκτελούνταν δίκαια. Από την άποψή μου δεν ξέρω καν ότι συμβαίνει αυτό το ταξίδι στο χρόνο.

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

Και τι προκύπτει από αυτό;

Αυτό που μόλις δείξαμε είναι ένα θεωρητικό παράδειγμα. Σε έναν κόσμο όπου ο χρόνος προχωρά μόνο μπροστά και κανείς δεν μπορεί να με κοροϊδέψει με μια χρονομηχανή, το πρωτόκολλο του καπέλου λειτουργεί σωστά. Μετά από E^2 γύρους εκτέλεσης, θα πρέπει να είμαι σίγουρος (όχι εντελώς, αλλά με αμελητέα πιθανότητα εξαπάτησης) ότι το γράφημα είναι σωστά χρωματισμένο και η Google έχει παράσχει τις σωστές πληροφορίες.

Εάν ο χρόνος μπορεί να χειραγωγηθεί (ιδίως, εάν η Google μπορεί να "ανασύρει τον χρόνο"), τότε μπορεί να παραποιήσει το πρωτόκολλο, ακόμα κι αν δεν έχει καθόλου πληροφορίες σχετικά με το πώς πρέπει να χρωματιστεί το γράφημα.

Από την άποψή μου, ποια είναι η διαφορά μεταξύ αυτών των δύο πρωτοκόλλων; Έχουν την ίδια στατιστική κατανομή και μεταδίδουν το ίδιο ποσό ΧΡΗΣΙΜΕΣ ΠΛΗΡΟΦΟΡΙΕΣ.

Είτε το πιστεύετε είτε όχι, αυτό αποδεικνύει κάτι πολύ σημαντικό.

Συγκεκριμένα, υποτίθεται ότι εγώ (ο Επαληθευτής) έχω κάποιο είδος στρατηγικής που θα μου επιτρέψει να «εξάγω» χρήσιμες πληροφορίες σχετικά με τον τρόπο με τον οποίο η Google κάνει το χρωματισμό εάν εκτελείται το ειλικρινές πρωτόκολλο. Τότε η στρατηγική μου θα πρέπει να λειτουργεί εξίσου καλά αν με ξεγελούν με τη μηχανή του χρόνου. Οι εκτελέσεις πρωτοκόλλου είναι, από την άποψή μου, στατιστικά πανομοιότυπες. Φυσικά δεν μπορώ να δείξω τη διαφορά.

Έτσι, ο όγκος των πληροφοριών που θα λάβω στο «πραγματικό πείραμα» και στο «πείραμα της μηχανής του χρόνου» είναι εντελώς πανομοιότυπος. Ο όγκος των πληροφοριών που βάζει η Google στο πείραμα της χρονομηχανής είναι ακριβώς μηδενικός. Επομένως, ακόμη και στον πραγματικό κόσμο, δεν θα υπάρχει διαρροή πληροφοριών. Το μόνο που μένει είναι να δείξουμε ότι οι επιστήμονες υπολογιστών έχουν μια χρονομηχανή (σσσς, είναι μυστικό).

Πώς να απαλλαγείτε από τα καπέλα και τις μηχανές του χρόνου

Φυσικά, δεν θα θέλαμε πραγματικά να εκτελέσουμε το πρωτόκολλο χρησιμοποιώντας καπέλα. Και ακόμη και η Google (πιθανότατα) δεν έχει μηχανή πραγματικού χρόνου.

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

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

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

Έτσι καταφέραμε να απαλλαγούμε από τα καπέλα. Πώς όμως αποδεικνύουμε ότι αυτό το πρωτόκολλο είναι μηδενικής γνώσης;

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

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

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

Ακόμη και χωρίς να ληφθούν υπόψη οι εικονικές μηχανές, οποιοδήποτε πρόγραμμα υπολογιστή μπορεί να "επαναδιπλωθεί" σε μια προηγούμενη κατάσταση απλά ξεκινώντας το πρόγραμμα από την αρχή και στέλνοντας τα ίδια δεδομένα ως είσοδο. Με την προϋπόθεση ότι οι είσοδοι (συμπεριλαμβανομένης της εισαγωγής τυχαίων αριθμών) είναι σταθερές, το πρόγραμμα θα ακολουθεί πάντα την ίδια διαδρομή εκτέλεσης. Μπορούμε λοιπόν να γυρίσουμε το πρόγραμμα προς τα πίσω, ξεκινώντας το από την αρχή και «διχαλώνοντας» την εκτέλεσή του όταν το πρόγραμμα φτάσει σε ένα συγκεκριμένο επιθυμητό σημείο.

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

Τι προκύπτει από όλα αυτά;

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

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

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

Στοιχεία για όλα τα NP!

Για όσους έφτασαν μέχρι εδώ, έχω σημαντικά νέα. Το έργο του χρωματισμού ενός κυψελοειδούς δικτύου σε τρία χρώματα είναι ενδιαφέρον από μόνο του, αλλά δεν είναι μόνο αυτό. Στ 'αλήθεια ενδιαφέρον πράγμασχετικά με το πρόβλημα χρωματισμού τριών χρωμάτων είναι ότι ανήκει στην κατηγορία των NP-complete. Αυτό σημαίνει ότι οποιοδήποτε άλλο πρόβλημα ανήκει στην κλάση NP μπορεί να μειωθεί σε αυτό.

Με απλά λόγια, οι Goldrich, Micali και Widgerson απέδειξαν ότι υπάρχουν "αποδοτικά" ZK για μια ευρεία κατηγορία χρήσιμων προβλημάτων. Πολλά από αυτά είναι πολύ πιο ενδιαφέροντα από το πρόβλημα της εκχώρησης συχνοτήτων σε ένα κυψελοειδές δίκτυο.

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

Αντί για αποτελέσματα

Φυσικά, θα ήταν απίστευτα ανόητο να αρχίσετε αμέσως να χρησιμοποιείτε αυτό το πρωτόκολλο στην πράξη. Το υπολογιστικό του κόστος θα περιλαμβάνει το συνολικό μέγεθος της αρχικής δήλωσης και αποδεικτικών στοιχείων, συν το κόστος μετάφρασης του προβλήματος σε γράφημα και άλλες εκτελέσεις E^2 του πρωτοκόλλου που είναι απαραίτητες για την επαλήθευση της ορθότητας της λύσης. Θεωρητικά αυτό είναι "αποδοτικό", αλλά δεδομένου ότι το συνολικό κόστος της απόδειξης θα είναι ένα πολυώνυμο του μήκους της εισόδου, δεν είναι εφαρμόσιμο στην πράξη.

Έτσι, μέχρι στιγμής έχουμε αποδείξει μόνο ότι τέτοιες αποδείξεις είναι δυνατές. Μένει να βρεθούν αποδεικτικά στοιχεία που να είναι αρκετά πρακτικά για πραγματική χρήση.

Σημειώσεις

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

**Αυτό το παράδειγμα βασίζεται σε αρχική λύση Goldwasser, Micali και Rakoff και ένα σεμινάριο με χρήση καπέλων που αναπτύχθηκε από τον Silvio Micali.

****** Ένα απλό παράδειγμα δέσμευσης μπορεί να κατασκευαστεί χρησιμοποιώντας ένα παράδειγμα συνάρτησης κατακερματισμού. Για να δημιουργήσουμε μια δέσμευση για την τιμή "x", απλώς δημιουργούμε κάποια (αρκετά μεγάλη) συμβολοσειρά τυχαίων αριθμών, την οποία ονομάζουμε "salt" και η δέσμευση εξόδου είναι C = hash(salt || x). Για να ανοίξετε μια δέσμευση, απλά ανοίγετε "x" και "salt". Οποιοσδήποτε μπορεί να επαληθεύσει ότι η αρχική δέσμευση είναι έγκυρη, υπολογίζοντας ξανά τον κατακερματισμό. Αυτό ασφαλής μέθοδοςκάτω από κάποιες μετρίως ισχυρές υποθέσεις για την ίδια τη συνάρτηση.

Ένα από τα καλύτερα πράγματα για τη σύγχρονη κρυπτογραφία είναι η υπέροχη ορολογία της. Μπορείτε να δημιουργήσετε όσες μπάντες πανκ θέλετε με ονόματα όπως Hardcore Predicate, Trapdoor Function ή Impossible Differential Cryptanalysis. Ωστόσο, υπάρχει ένας όρος που ξεπερνά όλους τους άλλους. Αυτή είναι η απόδειξη μηδενικής γνώσης - "μηδενική απόδειξη γνώσης".

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

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

Ιστορία μηδενικής γνώσης

Η έννοια της «μηδενικής γνώσης» προτάθηκε για πρώτη φορά τη δεκαετία του 1980 από τους ερευνητές του MIT Shafi Goldwasser, Silvio Micali και Charles Rackoff. Μελέτησαν προβλήματα που σχετίζονται με συστήματα διαδραστικής απόδειξης - θεωρητικά συστήματα στα οποία ένα μέρος (ο "Προβεβαίωσης") ανταλλάσσει μηνύματα με ένα δεύτερο μέρος (τον "Επαληθευτή") προσπαθώντας να το πείσει για την αλήθεια κάποιας μαθηματικής δήλωσης.*

Πριν από την Goldwasser και τους συναδέλφους της, η εργασία σε αυτόν τον τομέα επικεντρώθηκε κυρίως στην ορθότητα του συστήματος απόδειξης. Με άλλα λόγια, οι επιστήμονες εξέτασαν καταστάσεις στις οποίες ένας κακός Prover προσπάθησε να «εξαπατήσει» τον Επαληθευτή ώστε να πιστέψει μια ψευδή δήλωση. Οι Goldwasser, Micali και Rekoff ανέτρεψαν το πρόβλημα. Αντί να ανησυχούν μόνο για τον Prover, αποφάσισαν να σκεφτούν τι θα συμβεί αν δεν εμπιστεύεσαι Στον επιθεωρητή.

Το συγκεκριμένο πρόβλημα που έθεταν ήταν διαρροή πληροφοριών. Οι επιστήμονες αναρωτήθηκαν πόσες πρόσθετες πληροφορίες μαθαίνει ο Επαληθευτής κατά τη διάρκεια μιας απόδειξης πέρα ​​από το γεγονός ότι η δήλωση είναι αληθινή.

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

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

Αυτό που πρότειναν οι Goldwasser, Micali και Rekoff ανανέωσαν την ελπίδα για την εφαρμογή αποδείξεων μηδενικής γνώσης που αποδεδειγμένα δεν λένε καμία πληροφορίαεκτός από ένα bit που σημαίνει «αυτή η δήλωση είναι αλήθεια».

Παράδειγμα "Πραγματικού Κόσμου".

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

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

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

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

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

Αυτό όμως οδηγεί σε πρόβλημα.

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

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

Τρελή τεχνική λύση (με καπέλα!)

Σημειώστε ότι δεν θα είμαι ποτέ απολύτως σίγουρος ότι η Google είναι ειλικρινής - θα υπάρχει πάντα τουλάχιστον μια μικρή πιθανότητα η Google να με εξαπατά. Ωστόσο, μετά από μεγάλο αριθμό επαναλήψεων (δηλαδή μι^2 ) η αυτοπεποίθησή μου θα αυξηθεί σε σημείο που η πιθανότητα να εξαπατηθεί η Google είναι αμελητέα - αρκετά μικρή, ώστε σε όλους πρακτικά προβλήματα θα μπορούσε να παραμεληθεί. Με αυτόν τον τρόπο μπορώ να δώσω με ασφάλεια τα χρήματά μου στην Google.

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

Τι κάνει αυτή τη «μηδενική γνώση»;

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

Οι Goldwasser, Micali και Rekoff πρότειναν τρεις ιδιότητες που πρέπει να ικανοποιεί οποιοδήποτε πρωτόκολλο μηδενικής γνώσης. Ανεπίσημα μπορούν να εκφραστούν ως εξής:

1. πληρότητα (πληρότητα). Αν η Google λέει την αλήθεια, θα μπορέσει τελικά να με πείσει (από τουλάχιστον, με μεγάλη πιθανότητα).
2. ορθότητα (ορθότητα). Η Google μπορεί να με πείσει για τη σωστή απόφαση μόνοσε αυτή την περίπτωση, Ανστην πραγματικότητα λέει την αλήθεια.
3. Μηδενική γνώση (μηδέν— γνώση) . Δεν ακούω τίποτα περισσότερο για την απόφαση της Google.

Έχουμε ήδη συζητήσει το επιχείρημα της πληρότητας. Το πρωτόκολλο είναι τέτοιο που μετά από αρκετές επαναλήψεις η Google θα με πείσει τελικά (με αμελητέα πιθανότητα λάθους). Η επίδειξη της ορθότητας αυτού του πρωτοκόλλου είναι επίσης αρκετά εύκολη. Αν η Google προσπαθήσει ποτέ να με εξαπατήσει, είναι σχεδόν βέβαιο ότι θα ανακαλύψω την προδοσία.

Είναι η τρίτη ιδιότητα που είναι προβληματική εδώ, αλλά για να το καταλάβουμε αυτό πρέπει να κάνουμε ένα πολύ περίεργο πείραμα σκέψης.

Πείραμα σκέψης (με μηχανές χρόνου)

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

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

Έτσι, η επιλογή χρήσης μιας χρονομηχανής για την απόκτηση πρόσθετου χρόνου εργασίας εξαλείφεται. Ωστόσο, αποδεικνύεται ότι ακόμη και αυτή η πολύ περιορισμένη τεχνολογία μπορεί ακόμα να χρησιμοποιηθεί για να με ξεγελάσει.

Δεν έχω ιδέα τι συμβαίνει εδώ, αλλά σκέφτηκα ότι η εικόνα ταιριάζει.

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

Ωστόσο, αναπόφευκτα αργά ή γρήγορα θα σηκώσω ένα ζευγάρι καπέλα, θα ανακαλύψω δύο κορυφές έναςχρώματα και πιάστε την Google να εξαπατά. Και εδώ είναι που μπαίνει η μηχανή του χρόνου. Όταν η Google βρίσκεται σε αυτήν την περίεργη κατάσταση, απλώς την εξαλείφει. Με άλλα λόγια, ένας ειδικός "Googler" γυρίζει τον διακόπτη εναλλαγής, "επανατυλίγει" τον χρόνο κατά περίπου τέσσερα λεπτά και η ομάδα της Google επαναχρωματίζει πλήρως το γράφημα με μια νέα τυχαία λύση. Μετά από αυτό ξεκινούν ξανά το χρόνο, επιτρέποντάς μου να προσπαθήσω ξανά.

Ουσιαστικά, η μηχανή του χρόνου επιτρέπει στην Google να «αναρρώσει» από ό,τι άσχημο συμβαίνει κατά την εκτέλεση του ψεύτικο πρωτοκόλλου της, κάτι που μου κάνει τα πάντα να φαίνονται φυσιολογικά. Δεδομένου ότι μια επιτυχημένη προσπάθεια αμφισβήτησης του πρωτοκόλλου συμβαίνει μόνο στο 1/3 περίπου των φορών, ο αναμενόμενος χρόνος εκτέλεσης του πρωτοκόλλου (από την άποψη της Google) είναι μόνο μέτρια μεγαλύτερος από τον χρόνο εκτέλεσης του δίκαιου πρωτοκόλλου. Όσο για μένα, ούτε καν υποψιάζομαι ότι γίνονται ταξίδια στο χρόνο.

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

Προς τι όλα αυτά;

Αυτό που μόλις εξετάσαμε είναι ένα παράδειγμα προσομοιώσεις. Σημειώστε ότι σε έναν κόσμο όπου ο χρόνος προχωρά μόνο μπροστά και κανείς δεν μπορεί να με κοροϊδέψει με μια χρονομηχανή, το πρωτόκολλο με τα καπέλα σωστός, δηλαδή μετά μι^2 γύρους, πρέπει να είμαι πεπεισμένος (πέρα από μια αμελητέα πιθανότητα) ότι το γράφημα μπορεί στην πραγματικότητα να χρωματιστεί και ότι η Google έχει μια έγκυρη λύση.

Μόλις δείξαμε ότι αν ο χρόνος δεν κυλήσει απλώς προς τα εμπρός - πιο συγκεκριμένα, εάν η Google μπορεί να "ανασύρει" την ιδέα μου για τον χρόνο - τότε η Google μπορεί να παραποιήσει την πραγματική εκτέλεση του πρωτοκόλλου ακόμη και χωρίς πληροφορίες για τον πραγματικό χρωματισμόμιγραφική παράσταση.

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

Είτε το πιστεύετε είτε όχι, αυτό αποδεικνύει κάτι πολύ σημαντικό.

Ας πούμε ότι εγώ (ο Επαληθευτής) έχω κάποια στρατηγική που «εξάγει» χρήσιμες πληροφορίες σχετικά με τον χρωματισμό της Google αφού παρατηρήσω την εκτέλεση ενός ειλικρινούς πρωτοκόλλου. Τότε η στρατηγική μου θα πρέπει να λειτουργεί εξίσου καλά σε περιπτώσεις που με εξαπατά η μηχανή του χρόνου. Από την άποψή μου, οι εκτελέσεις πρωτοκόλλου είναι στατιστικά πανομοιότυπες - φυσικά δεν μπορώ να διακρίνω τη διαφορά.

Έτσι, εάν ο όγκος των πληροφοριών που μπορώ να εξαγάγω στο "πραγματικό πείραμα" και στο "πείραμα της μηχανής του χρόνου" είναι πανομοιότυπος, αλλά ο όγκος των πληροφοριών που παρέχει η Google στο "πείραμα της μηχανής του χρόνου" είναι ακριβώς μηδενικός, αυτό υποδηλώνει ότι ακόμη και στο στον πραγματικό κόσμο, το πρωτόκολλο δεν πρέπει να παράγει χρήσιμες πληροφορίες. Το μόνο που μένει είναι να δείξουμε ότι οι επιστήμονες υπολογιστών έχουν μηχανές χρόνου. Ναι, τα έχουμε! (Αυτό είναι ένα καλά φυλαγμένο μυστικό.)

Απαλλαγείτε από τα καπέλα (και τις μηχανές του χρόνου)

Φυσικά, στην πραγματικότητα δεν θέλουμε να κάνουμε το πρωτόκολλο καπέλου και ακόμη και η Google δεν έχει μηχανή πραγματικού χρόνου (πιθανώς).

Για να τα συνδέσουμε όλα μαζί, πρέπει πρώτα να μεταφέρουμε το πρωτόκολλό μας στον ψηφιακό κόσμο. Αυτό απαιτεί να κατασκευάσουμε το ψηφιακό ισοδύναμο ενός "καπέλου" - κάτι που τόσο κρύβει το ψηφιακό νόημα και ωστόσο "δεσμεύει" τον δημιουργό σε αυτό ("υποχρεώνει") ώστε να μην μπορεί να αλλάξει γνώμη εκ των υστέρων.

Ευτυχώς, έχουμε το τέλειο εργαλείο για αυτό, που ονομάζεται Digital Commitment Scheme. Ένα σχέδιο δεσμεύσεων επιτρέπει σε ένα μέρος να «δεσμευτεί» σε ένα συγκεκριμένο μήνυμα κρατώντας το σε έναν «μυστικό φάκελο» και στη συνέχεια να «ανοίξει» τον φάκελο δεσμεύσεων για να αποκαλύψει τι υπάρχει μέσα. Οι δεσμεύσεις μπορούν να δημιουργηθούν από μια ποικιλία συστατικών, συμπεριλαμβανομένων (ισχυρών) κρυπτογραφικών συναρτήσεων κατακερματισμού.***

Με ένα σχέδιο δεσμεύσεων, έχουμε όλα όσα χρειαζόμαστε για να εκτελέσουμε ηλεκτρονικά ένα πρωτόκολλο μηδενικής γνώσης. Ο prover κωδικοποιεί πρώτα τα χρώματα των κορυφών ως ένα σύνολο ψηφιακών μηνυμάτων (για παράδειγμα, χρησιμοποιώντας τους αριθμούς 0, 1, 2) και στη συνέχεια δημιουργεί ψηφιακές υποχρεώσεις για καθένα από αυτά. Αυτές οι υποχρεώσεις προωθούνται στον Αναθεωρητή. Όταν ο Επαληθευτής αμφισβητεί μια απόφαση για ένα άκρο, ο Prover απλώς δημοσιεύει τις τιμές για τις δεσμεύσεις που αντιστοιχούν στις δύο κορυφές.

Άρα καταργήσαμε τα καπέλα, αλλά πώς μπορούμε να αποδείξουμε ότι πρόκειται για πρωτόκολλο μηδενικής γνώσης;

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

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

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

Ένα παράδειγμα επανατύλιξης στιγμιότυπων εικονικών μηχανών. Το αρχικό VM αναπαράγεται προς τα εμπρός, επανέρχεται στο αρχικό στιγμιότυπο και, στη συνέχεια, εκτελείται ένας άλλος κλάδος.

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

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

Εντάξει, τι σημαίνουν όλα αυτά;

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

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

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

Στοιχεία για όλα τα NP!

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

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

Αυτό το αποτέλεσμα, με μια πτώση - χάρη στους Goldreich, Micali και Widjerson - αποδεικνύει ότι υπάρχουν «αποτελεσματικές» αποδείξεις μηδενικής γνώσης για μια ευρεία κατηγορία χρήσιμων δηλώσεων, πολλές από τις οποίες πολύ περισσότεροενδιαφέρουσα από την εκχώρηση συχνοτήτων δίκτυα κινητής τηλεφωνίας. Απλώς βρίσκετε τη δήλωση (στην κλάση NP) που θέλετε να αποδείξετε, όπως το παραπάνω παράδειγμα συνάρτησης κατακερματισμού, και στη συνέχεια τη μετατρέπετε σε μια παρουσία του προβλήματος των 3 χρωμάτων. Μετά από αυτό, απλά εκτελείτε την ψηφιακή έκδοση του πρωτοκόλλου με καπέλα.

Ας το συνοψίσουμε

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

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

Σε άλλες αναρτήσεις θα μιλήσω για μερικά από αυτά - δηλαδή αποτελεσματικόςαποδείξεις διαφόρων χρήσιμων δηλώσεων. Θα δώσω μερικά παραδείγματα (από πραγματικές εφαρμογές), όπου χρησιμοποιήθηκαν τέτοιες τεχνικές. Επίσης, κατόπιν αιτήματος ενός από τους αναγνώστες, θα σας πω γιατί δεν μου αρέσει τόσο πολύ το πρωτόκολλο SRP (Secure Remote Password).

Σημειώσεις

* Επίσημα, ο στόχος μιας διαδραστικής απόδειξης είναι να πείσει τον Επαληθευτή ότι μια συγκεκριμένη συμβολοσειρά ανήκει σε κάποια γλώσσα. Συνήθως, το Prover είναι πολύ (απεριόριστα) ισχυρό και ο Verifier είναι περιορισμένος σε υπολογιστικούς πόρους.

** Αυτό το παράδειγμα βασίζεται στην αρχική λύση των Goldwasser, Micali και Rekoff και το παράδειγμα εκμάθησης με καπέλα βασίζεται στην εξήγηση που έδωσε ο Silvio Micali. Είμαι υπεύθυνος μόνο για λάθη, εάν υπάρχουν.

*** Ένα απλό παράδειγμα δέσμευσης μπορεί να κατασκευαστεί χρησιμοποιώντας μια συνάρτηση κατακερματισμού. Για να δημιουργήσετε μια δέσμευση για την τιμή "x", απλώς δημιουργήστε μια (αρκετά μεγάλη) σειρά τυχαίων αριθμών, την οποία θα ονομάσουμε "salt" και εκτυπώστε τη δέσμευση ντο = Χασίσι(άλας || Χ) . Για να δημοσιοποιήσετε μια δέσμευση, απλώς εμφανίζετε ένα "x" και ένα αλάτι. Οποιοσδήποτε μπορεί να επαληθεύσει ότι η αρχική δέσμευση είναι έγκυρη, υπολογίζοντας εκ νέου τον κατακερματισμό. Είναι ασφαλές εφόσον πληρούνται ορισμένες (μετρίως αυστηρές) απαιτήσεις για την ίδια τη λειτουργία.

Μάθιου Γκριν

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

Πρωτόκολλο απόδειξης Zero-Knowledge: Πώς λειτουργεί;

Ως υπενθύμιση, λοιπόν, η μηδενική απόδειξη συμφωνίας σάς επιτρέπει να αποδείξετε ότι είστε ο κάτοχος ορισμένων πληροφοριών χωρίς να αποκαλύψετε το περιεχόμενό τους. Για την υλοποίηση αυτής της έννοιας, θα χρειαστεί να εισαγάγουμε 3 αλγόριθμους ταυτόχρονα, τους οποίους θα υποδηλώσουμε ως GK, P και V. Ας εξετάσουμε τον σκοπό τους:

• Το GK είναι μια γεννήτρια κλειδιών που δέχεται είσοδο α και το πρόγραμμα C, δημιουργώντας δύο κλειδιά: ένα κλειδί επαλήθευσης για το proofer PK και ένα κλειδί επαλήθευσης για την επαλήθευση VK. Αυτά τα κλειδιά είναι δημόσια σε όλα τα μέρη που εμπλέκονται στην απόδειξη.
• Το P είναι ένας χρήστης που χρειάζεται να χρησιμοποιήσει 3 τύπους δεδομένων εισόδου για απόδειξη: 1) κλειδί επαλήθευσης PK. 2) τυχαία είσοδο X, η οποία θα είναι δημόσια διαθέσιμη στα μέρη. 3) μια δήλωση που πρέπει να αποδειχθεί χωρίς να αποκαλυφθεί το νόημά της - W. Ο ίδιος ο αλγόριθμος P δημιουργεί μια απόδειξη απόδειξης, η οποία θα ικανοποιεί τις ακόλουθες προϋποθέσεις: Απόδειξη = P (PK; X; W).
• Το V είναι ένας αλγόριθμος επαληθευτή που επιστρέφει μια μεταβλητή Boolean. Μπορεί να αναπαρασταθεί σε δύο τιμές: TRUE (true) ή FALS (false). Έτσι, ο επαληθευτής λαμβάνει τα ακόλουθα δεδομένα εισόδου V(VK; X; Proof), βάσει των οποίων καθορίζει αν είναι αληθές ή ψευδές.

Έτσι λειτουργεί ένα πρωτόκολλο απόδειξης μηδενικής γνώσης. Το μόνο πράγμα για το οποίο θα ήθελα να μιλήσω ξεχωριστά είναι το νόημα α, που αναφέρεται στην παράγραφο περί ΓΚ. Γεγονός είναι ότι αυτή η παράμετροςπεριπλέκει σημαντικά τη χρήση του Zk-SNARK σε πραγματικές εφαρμογές, επειδή όποιος το κατέχει μπορεί να δημιουργήσει μια ψευδή απόδειξη, στην οποία το σύστημα θα επιστρέψει True. Οι προγραμματιστές του ZCash, ενός κρυπτονομίσματος που χρησιμοποιεί τεχνολογία μηδενικής προστασίας, παλεύουν με αυτό το πρόβλημα εδώ και πολύ καιρό.

Ας υποθέσουμε ότι η Αλίκη γνωρίζει την απόδειξη ενός συγκεκριμένου θεωρήματος και θέλει να πείσει τον Μπομπ ότι το θεώρημα είναι αληθινό. Φυσικά, η Alice μπορεί απλά να δώσει την απόδειξη στον Bob για επαλήθευση. Αλλά τότε ο Μπομπ θα μπορέσει στη συνέχεια να αποδείξει αυτό το θεώρημα σε τρίτους ο ίδιος, χωρίς τη βοήθεια της Αλίκης. Μπορεί η Αλίκη να πείσει τον Μπομπ χωρίς να λάβει πληροφορίες που θα τον βοηθούσαν να ανακατασκευάσει την απόδειξη του θεωρήματος; Αυτές οι δύο φαινομενικά αμοιβαία αποκλειόμενες απαιτήσεις ικανοποιούνται από πρωτόκολλα απόδειξης μηδενικής γνώσης. Η τελευταία ιδέα εισήχθη από τους Goldwasser, Micali και Rakoff το 1985.

Εξετάζεται το ακόλουθο μοντέλο πρωτοκόλλου. Η Αλίκη και ο Μπομπ έχουν στη διάθεσή τους πιθανολογικές μηχανές Turing, αντίστοιχα. Οι υπολογιστικοί πόροι που μπορεί να χρησιμοποιήσει η Alice είναι απεριόριστοι, ενώ η μηχανή V εκτελείται σε πολυωνυμικό χρόνο. Τα μηχανήματα έχουν κοινή τροφοδοσία επικοινωνίας για την ανταλλαγή μηνυμάτων. Μετά την εγγραφή ενός μηνύματος στην κασέτα επικοινωνίας, το μηχάνημα εισέρχεται σε κατάσταση αναμονής και εξέρχεται από αυτήν μόλις εγγραφεί ένα μήνυμα απάντησης στην κασέτα. Τα μηχανήματα έχουν επίσης μια κοινή ταινία εισόδου στην οποία αναγράφεται η λέξη εισόδου x. Η δήλωση που αποδεικνύει η Αλίκη είναι όπου υπάρχει κάποια σταθερή (γνωστή τόσο στην Αλίκη όσο και στον Μπομπ) γλώσσα. Για να αποφευχθεί η επιπολαιότητα, η γλώσσα πρέπει να είναι σκληρή (για παράδειγμα, NP-complete), διαφορετικά ο Bob μπορεί να το επαληθεύσει ανεξάρτητα Ουσιαστικά, το πρωτόκολλο απόδειξης είναι ότι ο Bob, χρησιμοποιώντας την τυχαιότητα, επιλέγει μερικές ερωτήσεις, τις θέτει στην Alice και ελέγχει την ορθότητα. των απαντήσεων. Το πρωτόκολλο τελειώνει όταν το μηχάνημα V σταματά, και βγάζει 1 εάν η απόδειξη γίνει αποδεκτή και 0 διαφορετικά.

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

Ορισμός 4. Μια διαδραστική απόδειξη για μια γλώσσα είναι ένα ζεύγος διαδραστικών μηχανών Turing έτσι ώστε να πληρούνται οι ακόλουθες δύο προϋποθέσεις.

1. (Πληρότητα). Για όλα

2. (Ορθότητα). Για κάθε μηχανή Turing για οποιοδήποτε πολυώνυμο και για όλα αρκετά μεγάλου μήκους

Πληρότητα σημαίνει ότι εάν η λέξη εισαγωγής ανήκει στη γλώσσα και τόσο η Alice όσο και ο Bob ακολουθούν το πρωτόκολλο, τότε η απόδειξη θα γίνεται πάντα αποδεκτή. Η απαίτηση της ορθότητας προστατεύει τον Μπομπ από την ανέντιμη Αλίκη, η οποία προσπαθεί να τον εξαπατήσει «αποδεικνύοντας» μια ψευδή δήλωση. Σε αυτήν την περίπτωση, η Alice μπορεί να παρεκκλίνει με οποιονδήποτε τρόπο από τις ενέργειες που προβλέπονται από το πρωτόκολλο, δηλαδή να χρησιμοποιήσει οποιοδήποτε άλλο μηχάνημα αντί για μηχανή Turing. Απαιτείται σε κάθε περίπτωση η πιθανότητα εξαπάτησης να είναι αμελητέα.

Ορισμός 5. Ένα διαδραστικό πρωτόκολλο απόδειξης για μια γλώσσα ονομάζεται απόδειξη απολύτως μηδενικής γνώσης εάν, εκτός από τις συνθήκες 1 και 2, ικανοποιείται και η ακόλουθη συνθήκη.

3. (Μηδενική Ιδιότητα Γνώσης). Για κάθε πολυωνυμική πιθανολογική μηχανή Turing V, υπάρχει μια πιθανολογική μηχανή Turing που λειτουργεί σε πολυωνυμικό χρόνο κατά μέσο όρο, και τέτοια ώστε για όλα τα

Η μηχανή ονομάζεται μηχανή προσομοίωσης για Θεωρείται ότι η μαθηματική προσδοκία του χρόνου λειτουργίας της περιορίζεται από ένα πολυώνυμο στο μήκος x. Αυτό σημαίνει ότι, κατ 'αρχήν, ανάλογα με τις τιμές που λαμβάνουν οι τυχαίες μεταβλητές που χρησιμοποιούνται στην εργασία του, μπορεί να λειτουργήσει για αρκετά μεγάλο χρονικό διάστημα. Όμως η πιθανότητα ο χρόνος λειτουργίας του να υπερβεί ένα ορισμένο πολυωνυμικό όριο είναι μικρή. Για κάθε μηχανή V, κατασκευάζεται η δική της μηχανή μοντελοποίησης. το τελευταίο μπορεί να χρησιμοποιήσει το V ως υπορουτίνα. Through υποδηλώνει μια τυχαία μεταβλητή - τη λέξη εξόδου της μηχανής όταν λαμβάνει τη λέξη x στην είσοδο.

Η ιδιότητα μηδενικής γνώσης προστατεύει την Αλίκη από έναν ανέντιμο Μπομπ ο οποίος, αποκλίνοντας αυθαίρετα από τις ενέργειες που ορίζει το πρωτόκολλο (χρησιμοποιώντας V αντί για V), προσπαθεί να αποσπάσει από την εκτέλεσή του Επιπλέον πληροφορίες. Η συνθήκη 3 σημαίνει ότι ο Bob μπορεί να λάβει μόνο τέτοιες πληροφορίες που θα μπορούσε να υπολογίσει ανεξάρτητα εκτελώντας το πρωτόκολλο) σε πολυωνυμικό χρόνο.

Ας πάρουμε ένα παράδειγμα ενός πρωτοκόλλου απόδειξης απολύτως μηδενικής γνώσης για μια γλώσσα από το έργο των Goldreich, Micali και Wigderson. Η λέξη εισόδου είναι ένα ζεύγος γραφημάτων και Εδώ είναι ένα σύνολο κορυφών που μπορούν να ταυτιστούν με το σύνολο των φυσικών αριθμών ενός συνόλου ακμών, έτσι ώστε οι γραφικές παραστάσεις να ονομάζονται ισόμορφες εάν υπάρχει μια μετάθεση στο σύνολο έτσι ώστε εάν και μόνο εάν (που συμβολίζεται με το Πρόβλημα αναγνώρισης ισομορφισμού γραφήματος είναι πολύ γνωστό μαθηματικό πρόβλημα, για το οποίο στις αυτή τη στιγμήδεν είναι γνωστοί πολυωνυμικοί αλγόριθμοι. Από την άλλη πλευρά, είναι άγνωστο εάν αυτό το πρόβλημα είναι NP-πλήρες, αν και υπάρχουν καλοί λόγοι να υποθέσουμε ότι δεν είναι.

Πρωτόκολλο IG

Αφήστε τον ισομορφισμό μεταξύ Τα ακόλουθα τέσσερα βήματα να εκτελεστούν σε βρόχο μία φορά, κάθε φορά με ανεξάρτητες τυχαίες μεταβλητές.

1. Το P επιλέγει μια τυχαία μετάθεση στο σύνολο, υπολογίζει και στέλνει αυτό το γράφημα

2. Το V επιλέγει ένα τυχαίο bit και το στέλνει

3. Εάν στη συνέχεια στέλνει V μετάθεση, διαφορετικά - μετάθεση o

4. Εάν η μετάθεση που προκύπτει από το V δεν είναι ισομορφισμός μεταξύ, τότε το V σταματά και απορρίπτει την απόδειξη. Διαφορετικά, η εκτέλεση του πρωτοκόλλου συνεχίζεται.

Εάν οι έλεγχοι στο βήμα 4 έδωσαν θετικό αποτέλεσμασε όλους τους κύκλους, τότε ο V δέχεται την απόδειξη.

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

Θεώρημα 2 (). Το πρωτόκολλο IG είναι μια απολύτως απόδειξη μηδενικής γνώσης για τη γλώσσα GRAPH ISOMORPHISM.

Η πληρότητα του πρωτοκόλλου IG είναι προφανής.

Για να αποδειχθεί η ορθότητα, αρκεί να σημειωθεί ότι το bit a, το οποίο επιλέγει το V στο βήμα 2, δείχνει για ποιο από τα γραφήματα - ή είναι απαραίτητο να αποδειχθεί ισομορφισμός με το γράφημα, τότε μπορεί να είναι ισομορφικό το καλύτερο σενάριο, ένας από αυτούς. Επομένως, ο έλεγχος του βήματος 4 θα δώσει θετικό αποτέλεσμα με πιθανότητα 1/2 σε έναν κύκλο και με πιθανότητα σε όλους τους κύκλους.

Η απόδειξη της ιδιότητας μηδενικής γνώσης είναι πολύ πιο δύσκολη. Επομένως, αναπαράγουμε μόνο την κύρια ιδέα. Πρώτα απ 'όλα, σημειώνουμε ότι το κύριο καθήκον του μηχανήματος V είναι να αποκτήσει το μέγιστο πιθανές πληροφορίεςσχετικά με τον ισομορφισμό μεταξύ Είναι φυσικό να υποθέσουμε ότι, σε αντίθεση με το V, θα παράγει ως λέξη εξόδου όχι ένα bit, αλλά όλες τις πληροφορίες που λαμβάνονται ως αποτέλεσμα της εκτέλεσης του πρωτοκόλλου, συμπεριλαμβανομένων των περιεχομένων της τυχαίας ταινίας, των γραφημάτων και των μεταθέσεων που λαμβάνονται σε βήματα 1 και 3, αντίστοιχα πρωτόκολλο IG. Η μηχανή μοντελοποίησης πρέπει να μπορεί να κατασκευάσει τις ίδιες τυχαίες συμβολοσειρές, γραφήματα και μεταθέσεις, χωρίς να γνωρίζει τον ισομορφισμό, επομένως, προσπαθεί να μαντέψει το bit a που θα είναι το αίτημα της μηχανής V στο βήμα 2. Για να το κάνετε αυτό, επιλέξτε ένα. τυχαίο bit, μια τυχαία μετάθεση, και υπολογίζει Στη συνέχεια θυμάται την κατάσταση της μηχανής V (συμπεριλαμβανομένων των περιεχομένων μιας τυχαίας ταινίας) και την καλεί ως υπορουτίνα, τροφοδοτώντας την ένα γράφημα ως είσοδο ένα. Αν τότε η προσομοίωση σε αυτόν τον κύκλο ολοκληρωθεί με επιτυχία γιατί μπορεί να δείξει τον απαιτούμενο ισομορφισμό. Εάν και μετά επαναφέρει την προηγουμένως αποθηκευμένη κατάσταση του μηχανήματος V και προσπαθεί ξανά.

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

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

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

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

Ας υποθέσουμε, για παράδειγμα, ότι η Alice είναι μια έξυπνη τραπεζική κάρτα στην οποία εφαρμόζεται ένας αλγόριθμος και ο Bob είναι ένας τραπεζικός υπολογιστής που εκτελεί το πρόγραμμα Πριν ξεκινήσει οποιαδήποτε τραπεζική συναλλαγή, η τράπεζα πρέπει να επαληθεύσει τη γνησιότητα της κάρτας και να αναγνωρίσει τον ιδιοκτήτη της. Με άλλα λόγια, σε κρυπτογραφική γλώσσα, η κάρτα πρέπει να περάσει έλεγχο ταυτότητας. Κατ' αρχήν, το παραπάνω πρωτόκολλο IG μπορεί να χρησιμοποιηθεί για το σκοπό αυτό. Σε αυτήν την περίπτωση, ένα ζεύγος γραφημάτων που σχετίζονται με την Alice αποθηκεύεται στη μνήμη του τραπεζικού υπολογιστή και το ίδιο ζεύγος γραφημάτων και ισομορφισμού αποθηκεύονται στην έξυπνη κάρτα. ίσως, Bob) και επομένως χρησιμοποιώντας το πρωτόκολλο IG η κάρτα αποδεικνύει την αυθεντικότητά της. Επιπλέον, η ιδιότητα της πληρότητας σημαίνει ότι η κάρτα σίγουρα θα αποδείξει τη γνησιότητά της. Η ιδιότητα ορθότητας προστατεύει τα συμφέροντα της τράπεζας από έναν εισβολέα ο οποίος, χωρίς να είναι πελάτης της τράπεζας, προσπαθεί να ελέγξει την ταυτότητα χρησιμοποιώντας μια ψεύτικη κάρτα. Η ιδιότητα zero-knowledge προστατεύει τον πελάτη από έναν εισβολέα ο οποίος, έχοντας κρυφακούσει μία ή περισσότερες εκτελέσεις του πρωτοκόλλου ελέγχου ταυτότητας της κάρτας, προσπαθεί να ελέγξει την ταυτότητα ως Alice. Φυσικά, σε αυτή την περίπτωση δεν έχει νόημα να αποδείξουμε ότι ένα ζεύγος γραφημάτων ανήκει στη γλώσσα GRAP ISOMORPHISM, αφού προφανώς επιλέγεται από αυτή τη γλώσσα. Αντίθετα, η Αλίκη αποδεικνύει ότι γνωρίζει τον ισομορφισμό Οι διαδραστικές αποδείξεις αυτού του τύπου ονομάζονται αποδείξεις γνώσης.

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

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

Τα κβαντικά ανθεκτικά συστήματα/πρωτόκολλα θεωρούνται εκείνα τα συστήματα/πρωτόκολλα που δεν μπορούν να παραβιαστούν με χρήση υπολογιστικής ισχύος κβαντικός υπολογιστής. Ο όρος κβαντική σταθερότητα εισάγεται στη μετα-κβαντική κρυπτογραφία.

Περιεχόμενα

Δήλωση του προβλήματος ασφάλειας πληροφοριών

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

ZKBoo

Το ZKBoo βασίζεται στο πρωτόκολλο Confidential Computing (MPC). Η ιδέα του ZKBoo είναι να αντικαταστήσει το MPC με μια (2,3)-αποσύνθεση της αλυσίδας.

Η απόδειξη κατασκευάζεται σύμφωνα με το ακόλουθο σχήμα:

1) Το P υπολογίζει τη f χρησιμοποιώντας την αποσύνθεση και συλλαμβάνει 3 καταστάσεις.

2) Το P στέλνει τις υποχρεώσεις και τα αποτελέσματα κάθε κατάστασης μετά τη χρήση του ευρετικού FS.

3) Η απάντηση έρχεται ποιες 2 από τις 3 καταστάσεις ανοίγουν για κάθε N εκτόξευση.

4) Το V ελέγχει τα δεδομένα εξόδου για την πληρότητα της ανάκτησης. ελέγχει ότι καθεμία από τις 2 ανοιχτές καταστάσεις έχει υπολογιστεί σωστά και υπολογίζει εάν η κλήση έχει υπολογιστεί σωστά.

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

ZKB++

ZKB++ είναι τροποποιημένη έκδοση ZKBoo.

1) Αποσύνθεση: στην Προβολή1 και στην Προβολή2, το P πρέπει να περιλαμβάνει το k(i) αφού το x(i) μπορεί να υπολογιστεί ντετερμινιστικά με το V.

2) Χωρίς να περιλαμβάνονται δεδομένα εισόδου: τα μερίδια εισόδου που δημιουργούνται ψευδοτυχαία χρησιμοποιώντας k(i) δεν χρειάζεται να συμπεριληφθούν στην αναπαράσταση όταν e = 1. Τα δεδομένα πρέπει να αποστέλλονται μόνο εάν e = 2 ή e = 3, αφού για τρίτη κατάσταση, Τα δεδομένα εισόδου δεν μπορούν να ληφθούν από το αρχικό, καθώς δημιουργούνται ψευδοτυχαία χρησιμοποιώντας k(i).

3) Χωρίς υποχρεώσεις αποστολής.

4) Καμία πρόσθετη τυχαία σειρά για υποχρεώσεις.

5) Χωρίς να λαμβάνεται υπόψη το αποτέλεσμα: το αποτέλεσμα μπορεί να υπολογιστεί από τα υπόλοιπα στοιχεία.

6) Χωρίς να συμπεριλαμβάνεται η αναπαράσταση κατάστασης: Το V μπορεί να υπολογίσει εκ νέου την κατάσταση λαμβάνοντας υπόψη μόνο τα τυχαία k(e) και k(e+1).

Το πλήρες κύκλωμα ZKB++ φαίνεται στο Σχήμα 1.

Οι βελτιώσεις που έγιναν για τη βελτιστοποίηση του ZKBoo μειώνουν το μέγεθος των δοκιμών κατά 2 για το ZKB++.