הוכחה באפס ידיעה

הוכחת אפס ידיעה חייבת לקיים את התכונות הבאות:

1. שלמות (Completeness); פרוטוקול הוכחה אינטראקטיבי ייקרא שלם, אם בהינתן מוכיח ומוודא הגונים (המבצעים את מהלכי הפרוטוקול כראוי), אם הטענה נכונה אזי המוכיח יצליח לשכנע את המוודא בנכונות הטענה בהסתברות גבוהה. במונח הסתברות גבוהה מתכוונים כי קיים סיכוי קל לכישלון.
2. נאותות (Soundness); פרוטוקול הוכחה אינטראקטיבי ייקרא נאות אם בהינתן טענה שקרית, מוכיח רמאי לא יצליח להונות מוודא הגון בנכונות הטענה. במילים אחרות, נאותות מבטיחה כי הפרוטוקול אכן מספק הוכחת הטענה או ידיעת הסוד וכי מוודא הגון יצליח לחשוף רמאות בהסתברות גבוהה.
3. אפס ידיעה (Zero knowledge); לפרוטוקול הוכחה אינטראקטיבי תהיה תכונת אפס ידיעה אם בהינתן טענה נכונה, המוודא לא יוכל ללמוד מאומה אודות הטענה עצמה מעבר לעובדת עצם קיומה. תנאי מהותי בתכונת אפס ידיעה הוא שבהינתן טענה (ללא גישה לסודו של המוכיח), מוודא רמאי יהיה מסוגל "להעתיק" הוכחה שניתנה על ידי מוכיח הגון, באופן שלא ניתן יהיה להבחין בהבדל כלשהו בינה לבין ההוכחה המקורית. מזה נובע כי לא ניתן ללמוד מן ההוכחה מידע כלשהו על הטענה. העתקת ההוכחה כשלעצמה אינה מועילה דבר לרמאי, כיוון שכפי שיובהר בהמשך, ההוכחה תקפה רק עבור המשתתפים בפרוטוקול בזמן אמת ואין בה כל תועלת לאחר מעשה.

שתי התכונות הראשונות מאפיינות כל מערכת הוכחה אינטראקטיבית. מערכת כזו נקראת הוכחת ידיעה. התכונה השלישית מייחדת מערכת הוכחה באפס ידיעה. היא אינה הוכחה במובן המתמטי של המילה, משום שקיימת סבירות נמוכה במקרה של כשל נאותות, שמוכיח רמאי יהיה מסוגל לשכנע מוודא הגון בנכונות טענה שיקרית. למעשה זוהי הוכחה הסתברותית ולא דטרמיניסטית, אולם ניתן לצמצם את אפשרות השגיאה לכדי הסתברות שולית.