Αποδείξεις Μηδενικής Γνώσης: Ένα Εικονογραφημένο Παράδειγμα. Πρωτόκολλο απόδειξης μηδενικής γνώσης για εμπιστευτικές πληροφορίες

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

Η χρήση αποδείξεων μηδενικής γνώσης για την απόδειξη της ταυτότητας προτάθηκε για πρώτη φορά από τους Uriel Fieg, Amos Fiat και Adi Shamir. Στην περίπτωση αυτή, ο χρήστης αποδεικνύει τη γνώση του ιδιωτικού του κλειδιού, το οποίο στην περίπτωση αυτή λειτουργεί ως μυστικό, χωρίς να το αποκαλύπτει. Με αυτόν τον τρόπο αποδεικνύει την ταυτότητά του.

Η απόδειξη μηδενικής γνώσης έχει τρεις κύριες ιδιότητες:
1. Πληρότητα. Εάν ο επαληθευτής γνωρίζει τη δήλωση, τότε θα είναι σε θέση να πείσει τον επαληθευτή για αυτήν.
2. Ορθότητα. Εάν ο prover δεν γνωρίζει τη δήλωση, τότε μπορεί να εξαπατήσει τον επαληθευτή μόνο με αμελητέα πιθανότητα.
3. Μηδενική γνώση. Ο επαληθευτής, ακόμα κι αν συμπεριφέρεται ανέντιμα, δεν θα μάθει τίποτα άλλο εκτός από το ίδιο το γεγονός ότι η δήλωση είναι γνωστή στον αποδεδειγμένο.

Η απόδειξη έχει τη μορφή ενός διαδραστικού πρωτοκόλλου. Αυτό σημαίνει ότι το Κόμμα Β κάνει μια σειρά από ερωτήσεις στον prover, που αν γνωρίζει το μυστικό, θα απαντήσει σωστά σε όλες τις ερωτήσεις. Εάν το μυστικό είναι άγνωστο στο μέρος Α, αλλά θέλει να πείσει τον εξεταστή για το αντίθετο, έχει κάποια πιθανότητα (ίσως 50%, όπως στα παραδείγματα σε αυτό το θέμα) να απαντήσει σωστά στην ερώτηση. Ωστόσο, μετά από έναν ορισμένο αριθμό ερωτήσεων (10 - 20), ο επαληθευτής είναι πεπεισμένος με αρκετά μεγάλη πιθανότητα ότι ο prover δεν γνωρίζει το μυστικό. Ωστόσο, καμία από τις απαντήσεις δεν δίνει πληροφορίες για το ίδιο το μυστικό.

Σπήλαιο Μηδενικής Γνώσης

Η απόδειξη μηδενικής γνώσης εξηγείται καλά από τους Jean-Jacques Quiskater και Louis Guilloux χρησιμοποιώντας την ιστορία της σπηλιάς του Ali Baba (βλ. εικόνα). Για να περάσετε μέσα από τη σπηλιά, πρέπει να ανοίξετε την πόρτα μεταξύ C και D. Η πόρτα ανοίγει μόνο όταν κάποιος πει τις μαγικές λέξεις. Αφήστε την Peggy να μάθει τις μαγικές λέξεις και θέλετε να το αποδείξετε στον Victor χωρίς να αποκαλύψετε τις ίδιες τις λέξεις.

Δείτε πώς λειτουργεί μια απόδειξη μηδενικής γνώσης σε αυτήν την περίπτωση:
1. Ο Βίκτωρ βρίσκεται στο σημείο Α.
2. Η Πέγκυ περπατά σε όλη τη διαδρομή μέσα από τη σπηλιά μέχρι την πόρτα είτε κατά μήκος του περάσματος Γ είτε του περάσματος Δ. Ο Βίκτορ δεν βλέπει προς ποια κατεύθυνση πήγε η Πέγκυ. Αφού η Πέγκυ εξαφανιστεί στη σπηλιά, ο Βίκτορ μετακινείται στο σημείο Β.
3. Ο Βίκτωρ φωνάζει στην Πέγκυ να βγει από τη σπηλιά είτε από το αριστερό είτε από το δεξί πέρασμα.
4. Η Πέγκυ, χρησιμοποιώντας μαγικές λέξεις για να ξεκλειδώσει την πόρτα αν χρειαστεί, βγαίνει από τη σπηλιά από το πέρασμα από το οποίο ο Βίκτορ της ζήτησε να βγει.
5. Η Peggy και ο Victor επαναλαμβάνουν τα βήματα 1-4 αρκετές φορές.

Στην περίπτωση που η Πέγκυ δεν γνωρίζει το μυστικό, τότε δεν θα μπορέσει να εξαπατήσει τον Βίκτορ εάν τα στάδια απόδειξης (διαπίστευση) επαναληφθούν πολλές φορές στη σειρά. Εφόσον μπορεί να βγει μόνο από το πέρασμα που μπήκε, σε κάθε γύρο του πρωτοκόλλου υπάρχει πιθανότητα 50% να μαντέψει από ποια πλευρά θα της ζητήσει ο Βίκτορ να βγει. Αντίστοιχα, η πιθανότητα της να εξαπατήσει τον Βίκτορ είναι επίσης 50%. Ωστόσο, η πιθανότητα να τον εξαπατήσει σε δύο γύρους είναι ήδη 25%, και σε n γύρους έχει μόνο μία ευκαιρία σε 2^n. Η Victor μπορεί με βεβαιότητα να υποθέσει ότι αν και οι n (n=10-20) γύροι της απόδειξης της Peggy είναι σωστοί, τότε γνωρίζει τις μυστικές λέξεις που ανοίγουν την πόρτα μεταξύ των σημείων C και D.

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

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

Πρωτόκολλο Fiat-Shamir

Ένα από τα πιο γνωστά πρωτόκολλα προσωπικής ταυτοποίησης χρησιμοποιώντας απόδειξη μηδενικής γνώσης είναι το πρωτόκολλο που προτείνεται από τους Amos Fiat και Adi Shamir, η ισχύς του οποίου βασίζεται στη δυσκολία εξαγωγής του modulo της τετραγωνικής ρίζας ενός αρκετά μεγάλου σύνθετου αριθμού n του οποίου η παραγοντοποίηση είναι άγνωστο.

Προηγουμένως, πριν από την ίδια την απόδειξη, το αξιόπιστο κέντρο T επιλέγει και δημοσιεύει μια ενότητα με αρκετά μεγάλο αριθμό n = p*q, η οποία είναι δύσκολο να παραγοντοποιηθεί. Στην περίπτωση αυτή, οι p, q είναι πρώτοι αριθμοί και παραμένουν μυστικοί. Κάθε χρήστης Α επιλέγει ένα μυστικό s από το διάστημα (1, n−1) συμπαραγωγής στο n. Στη συνέχεια υπολογίζεται το δημόσιο κλειδί v = s^2 (mod n).

Το v που προκύπτει καταχωρείται από το κέντρο αξιοπιστίας ως το δημόσιο κλειδί του χρήστη Α και η τιμή s είναι το μυστικό του Α. Είναι η γνώση αυτού του μυστικού s που ο Α πρέπει να αποδείξει στο μέρος Β χωρίς να το αποκαλύψει σε t γύρους. Κάθε διαπίστευση αποτελείται από τα ακόλουθα στάδια:
1. Ο A επιλέγει ένα τυχαίο r από το διάστημα (1, n−1) και στέλνει x = r^2 (mod n) στο μέρος B.
2. Το B επιλέγει τυχαία το bit e (0 ή 1) και το στέλνει στο A.
3. Ο Α υπολογίζει το y = r*s^e (mod n) και το στέλνει πίσω στο B.
4. Η πλευρά Β ελέγχει την ισότητα y^2 ≡ x*v^e (mod n). Εάν είναι αληθές, τότε γίνεται η μετάβαση στον επόμενο γύρο του πρωτοκόλλου, διαφορετικά η απόδειξη δεν γίνεται αποδεκτή.

Η επιλογή του e από το σύνολο σημαίνει ότι εάν το μέρος Α γνωρίζει πραγματικά το μυστικό, τότε θα μπορεί πάντα να απαντήσει σωστά, ανεξάρτητα από το επιλεγμένο e. Ας πούμε ότι ο Α θέλει να εξαπατήσει τον Β, επιλέγει ένα τυχαίο r και στέλνει x = r^2 / v, τότε εάν e = 0, τότε ο A επιστρέφει επιτυχώς B y = r, στην περίπτωση του e = 1, το A δεν θα είναι σε θέση να απαντήσει σωστά, t .To. δεν γνωρίζει s, και η εξαγωγή της τετραγωνικής ρίζας του v modulo n είναι αρκετά δύσκολη.

Η πιθανότητα ότι ο χρήστης Α δεν γνωρίζει το μυστικό s, αλλά πείθει τον επιθεωρητή Β για το αντίθετο, θα εκτιμηθεί από την πιθανότητα ίση με p = =2^(–t), όπου t είναι ο αριθμός των πιστοποιήσεων. Για να επιτευχθεί υψηλή αξιοπιστία, επιλέγεται να είναι αρκετά μεγάλο (t = 20 − 40). Έτσι, ο Β πιστοποιείται ότι γνωρίζει τον Α εάν και μόνο εάν όλοι οι γύροι είναι επιτυχείς.

Για να εκτελεστεί σωστά αυτό το πρωτόκολλο, το Μέρος Α δεν πρέπει ποτέ να επαναχρησιμοποιήσει την τιμή του x. Εάν ο Α είχε κάνει αυτό και ο Β, σε έναν άλλο βρόχο, είχε στείλει στον Α ένα άλλο τυχαίο bit r στο βήμα 2, τότε ο Β θα είχε και τις δύο απαντήσεις του Α και θα μπορούσε να υπολογίσει την τιμή του s και θα γνώριζε το μυστικό κλειδί της Αλίκης.

συμπέρασμα

Για εφαρμογές όπως οι έξυπνες κάρτες, το περιγραφόμενο πρωτόκολλο Fiat-Shamir δεν είναι πολύ κατάλληλο, καθώς οι ανταλλαγές με τον έξω κόσμο χρειάζονται χρόνο και η αποθήκευση δεδομένων για κάθε διαπίστευση μπορεί γρήγορα να εξαντλήσει τις περιορισμένες δυνατότητες της κάρτας. Ως εκ τούτου, οι Gillu και Kiskatr ανέπτυξαν έναν αλγόριθμο αναγνώρισης μηδενικής γνώσης που είναι πιο κατάλληλος για τέτοιες εφαρμογές. Οι ανταλλαγές μεταξύ της Peggy και του Victor, καθώς και οι παράλληλες διαπιστεύσεις σε κάθε ανταλλαγή, διατηρούνται στο απόλυτο ελάχιστο: για κάθε αποδεικτικό υπάρχει μόνο μία ανταλλαγή, στην οποία υπάρχει μόνο μία διαπίστευση. Υπάρχει επίσης ένα σύστημα Schnorr, το οποίο είναι μια εναλλακτική λύση στο σύστημα Gillu-Kiskatra και Fiat-Shamir. Αν σας αρέσει το θέμα, θα γράψω για αυτά στο επόμενο θέμα μου.

Έχουμε ήδη εξετάσει τι είναι ένα πρωτόκολλο απόδειξης 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, ενός κρυπτονομίσματος που χρησιμοποιεί τεχνολογία μηδενικής προστασίας, παλεύουν με αυτό το πρόβλημα εδώ και πολύ καιρό.

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

Ο Άντον ξέρει τις μαγικές λέξεις, ο Μπόρις όχι. Ο Άντον θέλει να αποδείξει στον Μπόρις ότι ξέρει τις μαγικές λέξεις, αλλά με τέτοιο τρόπο που ο Μπόρις εξακολουθεί να παραμένει στο σκοτάδι για αυτές τις λέξεις. Τότε ο Anton μπορεί να χρησιμοποιήσει το ακόλουθο πρωτόκολλο:

1. Ο Μπόρις στέκεται στο σημείο Α.

2. Κατόπιν επιλογής του, ο Anton πλησιάζει την πόρτα είτε από το σημείο C,

ή από το σημείο Δ.

3. Ο Μπόρις μετακινείται στο σημείο Β.

4. Ο Μπόρις διατάζει τον Άντον να εμφανιστεί είτε από το αριστερό πέρασμα προς την πόρτα,

ή μέσω του σωστού.

5. Ο Άντον υπακούει στις εντολές του Μπόρις, αν χρειαστεί χρησιμοποιώντας

μαγικές λέξεις για να περάσεις την πόρτα.

6. Τα βήματα 1-5 επαναλαμβάνονται n φορές, όπου n είναι η παράμετρος πρωτοκόλλου.

Ας υποθέσουμε ότι ο Μπόρις έχει μια βιντεοκάμερα με την οποία καταγράφει όλες τις εξαφανίσεις του Άντον στα βάθη της σπηλιάς και όλες τις επόμενες εμφανίσεις του. Εάν ο Μπόρις εμφανίσει αρχεία όλων των n πειραμάτων που έκανε μαζί με τον Άντον, μπορούν αυτά τα αρχεία να χρησιμεύσουν ως απόδειξη ότι ο Άντον γνωρίζει μαγικές λέξεις για ένα άλλο άτομο (για παράδειγμα, για τον Βλαντιμίρ);

Μετά βίας. Ο Βλαντιμίρ δεν θα μπορέσει ποτέ να βεβαιωθεί ότι ο Άντον δεν ενημέρωσε εκ των προτέρων τον Μπόρις για τις προθέσεις του κάθε φορά, έτσι ώστε ο Μπόρις να τον διατάξει στη συνέχεια να φύγει ακριβώς από την πλευρά της πόρτας από την οποία μπήκε ο Άντον. Ή ότι όλα τα ανεπιτυχή πειράματα κατά τα οποία ο Anton δεν μπόρεσε να εκτελέσει τις εντολές του Boris δεν αποκόπηκαν από την εγγραφή βίντεο.

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

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

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

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

1. Ο Άντον χρησιμοποιεί τις πληροφορίες που έχει και τις παραγόμενες

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

2. Ο Anton χρησιμοποιεί το πρωτόκολλο πρόβλεψης bit για το bit που βρίσκεται στο

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

3. Ο Άντον δείχνει ένα νέο δύσκολο πρόβλημα στον Μπόρις,

4. Ο Μπόρις ζητά από τον Άντον να αποδείξει ότι δύο δύσκολα προβλήματα

(παλιά και νέα) είναι ισόμορφα ή παρέχουν τη λύση που θα έπρεπε να είχε βρει ο Anton στο βήμα 1 και αποδεικνύουν ότι είναι πράγματι μια λύση στο πρόβλημα στο οποίο ο Anton μείωσε το αρχικό πρόβλημα στο ίδιο βήμα.

5. Ο Άντον εκπληρώνει το αίτημα του Μπόρις.

6. Ο Anton και ο Boris επαναλαμβάνουν τα βήματα 1-6 n φορές, όπου το n είναι μια παράμετρος

πρωτόκολλο.

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

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