Συνήθως, για την απόδειξη της ορθότητας ενός ισχυρισμού, καλούμαστε να παρουσιάσουμε μία διαδικασία η οποία χρησιμοποιεί κάποια αρχικά δεδομένα για να καθορίζει μία σειρά από "λογικά" βήματα , τα οποία μας οδηγούν στο συμπέρασμα ότι ο ισχυρισμός αληθεύει. Διαισθητικά, ένα συμβατικό σύστημα απόδειξης είναι ένα σύστημα σύμφωνα με το οποίο μπορούν να εκφραστούν ευκρινώς κάποιος ισχυρισμός, μία απόδειξη για αυτόν τον ισχυρισμό και ένας αποτελεσματικός τρόπος επιβεβαίωσης της ορθότητάς τους. Αντιθέτως, ένα διαδραστικό σύστημα απόδειξης είναι ένα διαδραστικό πρωτόκολλο στο οποίο δύο πρόσωπα ανταλλάσσουν μηνύματα ώστε το ένα πρόσωπο να αποδείξει έναν ισχυρισμό σε ένα άλλο που ελέγχει την ορθότητα της απόδειξής του. Τα συστήματα αποδείξεων μηδενικής γνώσης είναι διαδραστικά συστήματα αποδείξεων από τα οποία δεν προκύπτει καμία άλλη πληροφορία εκτός της ορθότητας ή μη της πρότασης που εξετάζεται.
Η έννοια της μηδενικής γνώσης παρουσιάσθηκε για πρώτη φορά το 1985 από τους Shafi Goldwasser, Silvio Micali, και Charles Rackoff στην εργασία τους με τίτλο: "The Knowledge Complexity of Interactive Proof-Systems". Στο σύστημα που καθόρισαν, το πρόσωπο που καλείται να αποδείξει ένα θεώρημα είναι μία μηχανή Turing με πολύ μεγάλη υπολογιστική δύναμη, ενώ το πρόσωπο που ελέγχει την απόδειξη είναι μία άλλη μηχανή Turing που λειτουργεί σε πολυωνυμικό χρόνο. Σύμφωνα με τον ορισμό που δίνουν για ένα σύστημα αποδείξεων μηδενικής γνώσης, οτιδήποτε μπορεί να υπολογίσει το πρόσωπο που ελέγχει την απόδειξη κατά τη διάρκεια εκτέλεσης του πρωτοκόλλου, μπορεί να το υπολογίσει και μόνο του, χωρίς να χρειάζεται να πάρει μέρος στο πρωτόκολλο. Αυτό σημαίνει ότι ακόμη και αν ένα άλλο πρόσωπο μπορέσει να υποδυθεί τον "ελεγκτή", δεν θα μπορέσει να τον επηρεάσει ώστε να του αποκαλύψει κάποιο μυστικό.
Τα περισσότερα κρυπτογραφικά πρωτόκολλα εφαρμόζουν μία απόδειξη γνώσης μίας κρυφής πληροφορίας για αυθεντικοποίηση μηνυμάτων, ταυτοποίηση προσώπων κτλ.. Σε πολλά εξ αυτών όμως, κατά την εκτέλεσή τους, αποκαλύπτονται (μερικώς) κάποιες παραπάνω πληροφορίες για την κρυφή πληροφορία, οι οποίες μπορούν να χρησιμοποιηθούν από κάποιο κακόβουλο τρίτο πρόσωπο. Η θεμελίωση όμως της έννοιας της μηδενικής γνώσης έδωσε τη δυνατότητα να αναπτυχθούν συστήματα αποδείξεων και πρωτόκολλα μηδενικής γνώσης που εφαρμόζονται για να δώσουν λύση στα προβλήματα της κρυπτογραφίας.
Στο πρώτο κεφάλαιο παρουσιάζουμε τις βασικές έννοιες της θεωρίας υπολογισμού. Πως ορίζεται ένα πρόβλημα απόφασης και πως αυτό αναπαρίσταται με τη βοήθεια των τυπικών γλωσσών. Περιγράφουμε τη δομή, τη λειτουργεία και τη χρονική πολυπλοκότητα τριών λογικών υπολογιστικών μηχανών Turing (τις ντετερμινιστικές, τις μη-ντετερμινιστικές και τις πιθανοτικές) και πότε αυτές "αναγνωρίζουν" μία γλώσσα. Η αναγνώριση μιας γλώσσας από μία μηχανή θα ισοδυναμεί με την επίλυση του προβλήματος που σχετίζεται με αυτή τη γλώσσα. Η επίλυση ενός υποσυνόλου προβλημάτων από μία υπολογιστική μηχανή ορίζει μία υπολογιστική κλάση στο σύνολο όλων των προβλημάτων. Στο τέλος του κεφαλαίου, ορίζουμε τις κλάσεις που προκύπτουν από τις ντετερμινιστικές και μη-ντετερμινιστικές μηχανές, P και NP αντίστοιχα, και τις κλάσεις RP, co-RP, ZPP και BPP που προκύπτουν από τις πιθανοτικές.
Στη συνέχεια, στο δεύτερο κεφάλαιο, παρουσιάζονται κάποια βασικά κρυπτογραφικά "εργαλεία". Οι one-way συναρτήσεις είναι συναρτήσεις που είναι εύκολα υπολογίσιμες, αλλά οι αντίστροφες εικόνες τους υπολογίζονται δύσκολα. Ιδιαίτερα σημαντικές συναρτήσεις είναι οι συναρτήσεις dexp και pmult. Ο υπολογισμός της αντίστροφης της dexp, dlog, είναι γνωστός ως το πρόβλημα του διακριτού λογαρίθμου, ενώ ο υπολογισμός της αντίστροφης της pmult είναι το πρόβλημα της παραγοντοποίησης ενός αριθμού σε γινόμενο δύο πρώτων αριθμών. Η ασφάλεια πολλών κρυπτοσυστημάτων και κρυπτογραφικών πρωτοκόλλων βασίζεται στις υποθέσεις ότι τα δύο αυτά προβλήματα είναι δύσκολο να επιλυθούν, δηλαδή ότι οι dexp και pmult είναι one-way συναρτήσεις. Οι συναρτήσεις κατακερματισμού είναι συναρτήσεις που συμπιέζουν το μέγεθος ενός μηνύματος και δίνουν ως αποτέλεσμα μία σύνοψη του μηνύματος. Όταν αυτές πληρούν κάποιες προυποθέσεις ασφαλείας, χρησιμοποιούνται για την κρυπτογράφηση και αποκρυπτογράφηση μηνυμάτων, στις ψηφιακές υπογραφές, για αυθεντικοποίηση και άλλους τομείς της κρυπτογραφίας. Δύο τέτοιες συναρτήσεις ειναι η Merkle-Damgård κατασκευή και ο ασφαλής αλγόριθμος κατακερματισμού SHA-1. Στη συνέχεια του κεφαλαίου γίνεται αναφορά σε δύο διαφορετικούς τρόπους κρυπτογράφησης και αποκρυπτογράφησης μηνυμάτων, τα συμμετρικά κρυπτοσυστήματα και τα ασύμμετρα κρυπτοσυστήματα. Στα συμμετρικά, η ασφάλεια της κρυπτογράφησης και αποκρυπτογράφησης βασίζεται σε ένα κρυφό κλειδί που πρέπει να γνωρίζουν μόνο τα δύο πρόσωπα που επιθυμούν να επικοινωνίσουν. Ενώ στα ασύμμετρα, γίνεται χρήση ενός ζεύγους κλειδιών. Ένα δημόσιο για την κρυπτογράφηση και ένα ιδιωτικό για την αποκρυπτογράφηση. Στο τέλος του κεφαλαίου παρουσιάζονται εφαρμογές τους στις ψηφιακές υπογραφές, σε κρυπτογραφικά πρωτόκολλα ανταλλαγής και διανομής κλειδιών και σε μεθόδους αυθεντικοποίησης και σχήματα ταυτοποίησης.
Στο τέταρτο κεφάλαιο γίνεται ο προσδιορισμός των συστημάτων αποδείξεων μηδενικής γνώσης. Η απόδειξη ενός θεωρήματος θα αντιστοιχεί στην ύπαρξη διαδραστικού συστήματος απόδειξης για μιά γλώσσα. Αρχικά, για το προσδιορισμό ενός διαδραστικού συστήματος απόδειξης, καθορίζουμε τον τρόπο λειτουργείας ενός διαδραστικού πρωτοκόλλου. Τα δύο πρόσωπα, μεταξύ των οποίων εξελίσσεται το πρωτόκολλο, είναι δύο διαδραστικές μηχανές Turing, A και B, οι οποίες μπορούν να στέλνουν και να διαβάζουν μηνύματα η μία από την άλλη. Η B πρέπει να λειτουργεί σε πολυωνυμικό χρόνο, ενώ η A χωρίς χρονικούς περιορισμούς. Στη συνέχεια καθορίζουμε τι σημαίνει να υπάρχει ένα διαδραστικό σύστημα απόδειξης για μία γλώσσα. Η ύπαρξή του βέβαια, δε θα αποτελεί απαραίτητη προυπόθεση ώστε να είναι ένα διαδραστικό πρωτόκολλο μηδενικής γνώσης για μία γλώσσα. Ένα διαδραστικό πρωτόκολλο θα είναι μηδενικής γνώσης για μία γλώσσα, όταν μία "ματιά" στα μηνύματα της μηχανής A προς μία άλλη (κακόβουλη) διαδραστική μηχανή B', δεν θα διαφέρει από την "ματιά" στα μηνύματά της προς την μηχανή B. Για να ορίσουμε τι σημαίνει οι δύο "ματιές" να μην διαφέρουν ορίζουμε τις δυσδιάκριτες και τις προσεγγίσιμες οικογένειες τυχαίων μεταβλητών. Όταν ένα διαδραστικό πρωτόκολλο θα είναι και μηδενικής γνώσης και διαδραστικό σύστημα απόδειξης για μία γλώσσα, θα είναι ένα σύστημα απόδειξης για αυτή τη γλώσσα. Στο τέλος του κεφαλαίου παρουσιάζονται δύο συστήματα αποδείξεων μηδενικής γνώσης για τις γλώσσες των τετραγωνικών και μη-τετραγωνικών υπολοίπων.
Στο τελευταίο κεφάλαιο παρουσιάζουμε κάποια κρυπτογραφικά πρωτόκολλα αυθεντικοποίησης των Kurmi και Sodhi που βασίζονται σε συστήματα μηδενικής γνώσης. Αρχικά παρουσιάζονται δύο πρωτόκολλα αυθεντικοποίησης κωδικών πρόσβασης. Στην πρώτη περίπτωση ένας πελάτης αποδεικνύει την ταυτότητά του σε ένα διακομιστή (server), ο οποίος τον αυθεντικοποιεί και αποφασίζει εάν του επιτρέψει ή όχι την πρόσβαση στο σύστημα. Το δεύτερο πρωτόκολλο, είναι παραλλαγή του πρώτου, με τη διαφορά ότι χρησιμοποιείται ένα ασύμμετρο σύστημα κρυπτογράφησης, το οποίο παρέχει επιπλέον ασφάλεια και επιτρέπει και τον πελάτη να αυθεντικοποιήσει τον διακομιστή. Στη συνέχεια, παρουσιάζουμε ένα σχήμα ταυτοποίησης για ένα peer-to-peer σύστημα υπολογιστών, όπου κάθε κόμβος μπορεί να αυθεντικοποιεί την ταυτότητα ενός άλλου κόμβου του συστήματος. Στο τέλος παρουσιάζεται ένα μηδενικής γνώσης πρωτόκολλο ανταλλαγής κλειδιών βασισμένο στο πρωτόκολλο των Diffie-Hellman.
Σε αντίθεση με το πρωτόκολλο των \textlatin{Diffie-Hellman}, σε αυτό το πρωτόκολλο τα δύο πρόσωπα που συμμετέχουν σε αυτό δεν χρειάζεται να ανταλλάξουν κάποια κρυφή πληροφορία για να σχηματίσουν ένα κοινό κρυφό κλειδί.
