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

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

Εξετάζεται το ακόλουθο μοντέλο πρωτοκόλλου. Η Alice και ο Bob έχουν στη διάθεσή τους πιθανοτικές μηχανές 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 θα είναι λίγο α. Αν τότε το μόντελινγκ σε αυτόν τον κύκλοολοκληρώθηκε με επιτυχία γιατί μπορεί να επιδείξει τον απαιτούμενο ισομορφισμό. Εάν και μετά επαναφέρει την προηγουμένως αποθηκευμένη κατάσταση του μηχανήματος V και προσπαθεί ξανά.

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

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

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

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

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

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

Ας δοθεί ένα διαδραστικό σύστημα απόδειξης (P,V,S).
Στον ορισμό ενός διαδραστικού συστήματος απόδειξης, δεν είχε προηγουμένως θεωρηθεί ότι ο V θα μπορούσε να είναι αντίπαλος (μόνο η πιθανότητα ύπαρξης ενός ανέντιμου συμμετέχοντος P υποτέθηκε, αλλά ο V μπορεί να αποδειχθεί ότι είναι ένας αντίπαλος που θέλει να το μάθει). μερικές νέες πληροφορίες από τον Π. ΧΡΗΣΙΜΕΣ ΠΛΗΡΟΦΟΡΙΕΣσχετικά με τη δήλωση του Σ. Σε αυτή την περίπτωση, ο Π μπορεί να μην θέλει να συμβεί αυτό ως αποτέλεσμα της εργασίας
Πρωτόκολλο διαδραστικού συστήματος αποδεικτικών στοιχείων. Έτσι
28 Zapechnikov S. V. Κρυπτογραφικά πρωτόκολλα και οι προκάτοχοί τους
Έτσι φτάνουμε στην ιδέα ενός πρωτοκόλλου απόδειξης μηδενικής γνώσης. Η γνώση μηδενικής γνώσης υποδηλώνει ότι, ως αποτέλεσμα του πρωτοκόλλου του διαδραστικού συστήματος απόδειξης, ο V δεν θα αυξήσει τις γνώσεις του σχετικά με την πρόταση S, ή, με άλλα λόγια, δεν θα είναι σε θέση να εξάγει οποιαδήποτε πληροφορία σχετικά με το γιατί το S είναι αληθές.
Όπως και πριν, το πρωτόκολλο διατυπώνει προκαταρκτικά μια συγκεκριμένη δήλωση S, για παράδειγμα, ότι κάποιο αντικείμενο w έχει την ιδιότητα L: we L. Κατά τη διάρκεια του πρωτοκόλλου, τα P και V ανταλλάσσουν μηνύματα. Κάθε ένα από αυτά μπορεί να δημιουργήσει τυχαίους αριθμούςκαι χρησιμοποιήστε τα στους υπολογισμούς σας. Στο τέλος του πρωτοκόλλου, ο V πρέπει να πάρει την τελική του απόφαση για το αν το S είναι αληθές ή ψευδές.
Ο στόχος του P είναι πάντα να πείσει τον V ότι το S είναι αληθινό, ανεξάρτητα από το αν είναι στην πραγματικότητα αληθινό ή όχι, δηλαδή, ο P μπορεί να είναι ενεργός αντίπαλος και η δουλειά του V είναι να δοκιμάσει τα επιχειρήματα του Συμμετέχοντος V είναι να κρίνει αν ο S είναι αληθινό ή ψευδές. Όπως και πριν, το V έχει πολυωνυμικά περιορισμένες υπολογιστικές δυνατότητες, δηλαδή, ο χρόνος λειτουργίας του περιορίζεται από κάποιο πολυώνυμο σε
μήκος της δήλωσης που πρέπει να αποδειχθεί: Ας εξετάσουμε τώρα παραδείγματα πρωτοκόλλων απόδειξης με μηδενικές γνώσεις.
1. «Το πρόβλημα με τη σπηλιά του Αλί Μπαμπά». Υπάρχει μια σπηλιά, η κάτοψη της οποίας φαίνεται στο Σχ. 1.2. Η σπηλιά έχει μια πόρτα με ένα μυστικό μεταξύ των σημείων Γ και Δ. Όποιος ξέρει μαγικές λέξεις, μπορεί να ανοίξει αυτή την πόρτα και να πάει από το C στο D ή το αντίστροφο. Για όλους τους άλλους, και τα δύο περάσματα των σπηλαίων οδηγούν σε αδιέξοδο.
Αφήστε τον R να μάθει το μυστικό της σπηλιάς. Θέλει να αποδείξει στον V τις γνώσεις του για αυτό το μυστικό χωρίς να αποκαλύψει τις μαγικές λέξεις. Ακολουθεί το πρωτόκολλο επικοινωνίας τους:
Το V βρίσκεται στο σημείο Α.
Το P μπαίνει στη σπηλιά και φτάνει είτε στο σημείο C είτε στο σημείο D\
Αφού ο P εξαφανιστεί στη σπηλιά, ο V φθάνει στο σημείο Β, χωρίς να γνωρίζει ποιος δρόμος πήγε ο P.
Ο V καλεί τον R και του ζητά να βγει είτε από τον αριστερό είτε από τον δεξιό διάδρομο της σπηλιάς σύμφωνα με τις επιθυμίες του V.
Ο R το κάνει αυτό, ανοίγοντας την πόρτα αν χρειαστεί, αν, φυσικά, ξέρει τις μαγικές λέξεις.
P και V επαναλάβετε τα βήματα (1) - (5) n φορές.

Μετά από n γύρους του πρωτοκόλλου, η πιθανότητα θα μειωθεί στο 1/2".
2. Απόδειξη ισομορφισμού γραφήματος. Ο P θέλει να αποδείξει τον V ισομορφισμό των γραφημάτων Go και Gb Έστω G, = (p(G0):G0 = G, όπου φ είναι ο μετασχηματισμός ισομορφισμού· m είναι η πληθώρα του συνόλου N των κορυφών των γραφημάτων. Ο Πίνακας 1.4 δείχνει το πρωτόκολλο για την απόδειξη αυτής της δήλωσης.
Ας εξηγήσουμε τη δομή αυτού του πρωτοκόλλου. Στο βήμα (1), ο συμμετέχων P δημιουργεί ένα τυχαίο γράφημα H, ισόμορφο του G\. Στο βήμα (2), ο συμμετέχων V, επιλέγοντας ένα τυχαίο bit a = (0D), ζητά να αποδείξει ότι
Н ~G0 ή ότι Н « Gj. Στο βήμα (3), ο συμμετέχων P στέλνει στον συμμετέχοντα V τον μετασχηματισμό \|/, τον οποίο κατασκευάζει με τέτοιο τρόπο ώστε για a = 1, ως αποτέλεσμα της εφαρμογής αυτού του μετασχηματισμού στο γράφημα Gu, το γράφημα F1 = TtG, = H προκύπτει και για a = 0, ως αποτέλεσμα της εφαρμογής αυτού του μετασχηματισμού στο γράφημα Ga, λαμβάνουμε το γράφημα F0 =.
Zo Zapechnikov S.V. Κρυπτογραφικά πρωτόκολλα και η εφαρμογή τους
= 7i((p(G0))~7iG] = #, Στο βήμα (4), ο συμμετέχων V, εκτελώντας έναν έλεγχο ισότητας γραφήματος, καθορίζει έτσι εάν η συνθήκη ικανοποιείται
Ν = Φα. Τα βήματα (1) - (4) επαναλαμβάνονται t φορές. Εάν σε όλους τους γύρους m αυτού του πρωτοκόλλου το αποτέλεσμα της δοκιμής είναι θετικό, το V αποδέχεται την απόδειξη.
Πίνακας 1.4. Πρωτόκολλο για την απόδειξη ισομορφισμού γραφημάτων P V 1% - τυχαία μετάθεση κορυφών, υπολογίζει H = nGl 2 f n, εάν (a -1),
V = 1 / h 1 l o f αν (a = 0) -> m επί 4 Υπολογίζει το γράφημα \j/Ga και συγκρίνει: H =\jfGa 5 Δέχεται την απόδειξη εάν και μόνο εάν για Vm
Αυτό το πρωτόκολλο είναι πραγματικά ένα πρωτόκολλο μηδενικής γνώσης, αφού στην περίπτωση του ισομορφικού G0 ~ Gx, ο συμμετέχων V δεν λαμβάνει καμία πληροφορία εκτός από ισομορφισμούς των γραφημάτων G0 και G\ με κάποιες τυχαίες αναρίθμησή τους, τις οποίες θα μπορούσε να λάβει και ανεξάρτητα , επιλέγοντας ένα τυχαίο bit a και επαναριθμώντας τυχαία το γράφημα Ga.
3. Απόδειξη γνώσης του διακριτού λογάριθμου x του αριθμού X. Πριν από την έναρξη του πρωτοκόλλου, καθορίζονται ανοιχτές ποσότητες: p,
q- πρώτοι αριθμοί, έτσι ώστε q\(p -1), στοιχείο g e Z*, αριθμός X. Do-]. Βασικά κρυπτογραφικά πρωτόκολλα 31
το άτομο που καλεί το P γνωρίζει τη μυστική τιμή x\xΠίνακας 1.5. Πρωτόκολλο για την απόδειξη γνώσης του διακριτού λογάριθμου P V I r&RZ
M = g (mod p) 2 A. Απόδειξη γνώσης της αναπαράστασης του αριθμού y στη βάση (απόδειξη μηδενικής γνώσης γνώσης της παράστασης y). Πριν ξεκινήσει το πρωτόκολλο, καθορίζονται ανοιχτές ποσότητες που είναι γνωστές σε όλους τους συμμετέχοντες: πρώτοι αριθμοί p, q, στοιχεία y, gvg2,..., gk Є Gq. Ο prover P γνωρίζει τις μυστικές ποσότητες ara 2,...,ake ZQ: y =
= 8і" " 8г1""> γνώσεις για τις οποίες πρέπει να αποδείξει στον V χωρίς να αποκαλύψει αυτές οι ίδιες οι ποσότητες. Το πρωτόκολλο παρουσιάζεται στον πίνακα. 1.6.
Πίνακας 1.6. Πρωτόκολλο απόδειξης γνώσης αντιπροσώπευσης
αριθμοί στη βάση P V 1 rl.r2,...,rk. ЄІ( Zq, 2 5. Απόδειξη γνώσης της αναπαράστασης ενός συνόλου αριθμών στις αντίστοιχες βάσεις (απόδειξη μηδενικής γνώσης γνώσης ισότητας αναπαράστασης όλων των y(j) στις αντίστοιχες βάσεις). Πριν ξεκινήσει το πρωτόκολλο, ορίζονται ανοιχτές ποσότητες, γνωστές
W I >\
γνωστό σε όλους τους συμμετέχοντες: πρώτοι αριθμοί p, q, στοιχεία y, 82^є για κάποιους (/). Ο prover P γνωρίζει τις μυστικές τιμές 0C[,a2,...,a,. є Zq, έτσι ώστε για V/ у^ =
= (ι^) " 1 > γνώση για την οποία πρέπει να αποδείξει V,
χωρίς να αποκαλύπτουν οι ίδιοι αυτές τις αξίες. Στον πίνακα Το 1.7 δείχνει ένα πρωτόκολλο που λύνει αυτό το πρόβλημα.
Πίνακας 1.7. Πρωτόκολλο για την απόδειξη γνώσης ενός συνόλου αριθμών
στις αντίστοιχες βάσεις P V 1 rvr21...lrkeR για U/ 2 (AiP«iT-(lt-
6. Απόδειξη γνώσης πολλαπλασιαστικής σχέσης μεταξύ δεσμευμένων αξιών. Στοιχείο Χ = gx μιας κυκλικής υποομάδας απλή παραγγελία, στο οποίο το πρόβλημα διακριτού λογαρίθμου θεωρείται υπολογιστικά σύνθετο, ονομάζεται κατατεθείσα τιμή (δεσμευμένη τιμή), που αντιπροσωπεύει τη μυστική τιμή x. Αφήνω
Το d είναι ένα άγνωστο στοιχείο έτσι ώστε h = gd. Πριν ξεκινήσει το πρωτόκολλο, καθορίζονται ανοιχτές ποσότητες: πρώτοι αριθμοί p, q, στοιχεία A, B, C Є Gq. Ο prover του P γνωρίζει μυστικές ποσότητες
a, a, b, b, c, c, έτσι ώστε c = ab, A = gah"\ B = gbhb, C = gche. Πρέπει να αποδείξει τη γνώση τους V, χωρίς να αποκαλύψει οι ίδιοι τις τιμές. Στον Πίνακα 1.8 , με - έχει τηρηθεί πρωτόκολλο τέτοιων αποδεικτικών στοιχείων.
Πίνακας 1.8. Πρωτόκολλο για την απόδειξη γνώσης της πολλαπλασιαστικής σχέσης κατατεθειμένων ποσοτήτων P V 1 М=і">/Ї, j Mt = gx-h*\ ¦ M2= Bx ¦ h"1 2 =CK-M2
αποκάλυψη της γνώσης
Πίνακας 1.9. Δομή πρωτοκόλλων απόδειξης με μηδέν P S: x є L - η δήλωση που αποδεικνύεται, h - dp, δημόσιες παράμετροι και ποσότητες, s - μυστικά δεδομένα του prover σχετικά με το γιατί το S είναι αληθές, r - τυχαίος αριθμός V 1 rp - τυχαίος, 2 rv - τυχαίος αριθμός,
c = LM Ας γενικεύσουμε τα παραδείγματα που εξετάστηκαν και ας διατυπώσουμε έναν αριθμό ορισμών. ΣΕ γενική εικόναΤο πρωτόκολλο διαδραστικής απόδειξης με γνώση μηδενικής γνώσης (Πίνακας 1.9) αποτελείται από τέσσερα βήματα:
Τέλος τραπεζιού. 1.9 P S: xe L είναι η δήλωση που αποδεικνύεται, h είναι άλλες δημοσίως διαθέσιμες παράμετροι και ποσότητες, s είναι τα μυστικά δεδομένα του prover σχετικά με το γιατί το S είναι αληθές, r είναι ένας τυχαίος αριθμός V 3 R = f3(C,x) 4
ο prover μεταφέρει στον επαληθευτή τα λεγόμενα στοιχεία (μάρτυρας -W) - το αποτέλεσμα του υπολογισμού μιας μονόδρομης συνάρτησης της μυστικής τιμής, τη γνώση της οποίας αποδεικνύει.
ο κριτής του στέλνει ένα τυχαίο αίτημα.
ο prover απαντά σε αυτό το ερώτημα και η απάντηση εξαρτάται τόσο από το τυχαίο ερώτημα όσο και από τη μυστική τιμή, αλλά είναι υπολογιστικά αδύνατο να ληφθεί αυτή η μυστική τιμή από αυτόν.
Λαμβάνοντας την απάντηση, ο V ελέγχει τη συνοχή του με τα «αποδεικτικά στοιχεία» που μεταδίδονται στο πρώτο βήμα.
Ας εξετάσουμε τις βασικές αρχές της κατασκευής αποδείξεων με μηδενική αποκάλυψη γνώσης: τι συνεπάγεται η ιδιότητα της γνώσης μηδενικής γνώσης.
Στη θεωρία απόδειξης μηδενικής γνώσης, η γνώση P και V αντιμετωπίζονται ως «μαύρα κουτιά» (Εικ. 1.3).
Έστω \tr ), \)Py ) το σύνολο όλων των μηνυμάτων που μεταδίδονται από το P στο V (αντίστοιχα από το V στο P), καθένα από τα οποία είναι μια τυχαία μεταβλητή, και έτσι (x,h,rv,(mp ),( mv)) = = προβολή, ϐϵ)