הוכחה באפס ידיעה – הבדלי גרסאות

#'''אפס ידיעה''' (Zero knowledge) – לפרוטוקול הוכחה אינטראקטיבי תהיה תכונת '''אפס ידיעה''', אם בהינתן טענה נכונה, המוודא לא יוכל ללמוד מאומה אודות הטענה עצמה מעבר לעובדתלעצם עצם קיומהנכונותה. תנאי מהותי בתכונת אפס ידיעה הוא, שבהינתן טענה (ללא גישה לסודו של המוכיח), מוודא רמאי יהיה מסוגל "להעתיקלחקות" הוכחה שניתנה על ידי מוכיח הגון, באופן שלא ניתן יהיה להבחין בהבדל כלשהו בינה לבין ההוכחה המקורית. מזה נובע כי לא ניתן ללמוד מן ההוכחה מידע כלשהו על הטענה. העתקת ההוכחה כשלעצמה אינה מועילה בדבר לרמאי, כיוון שכפי שיובהר בהמשך, ההוכחה תקפה רק עבור המשתתפים בפרוטוקול בזמן אמת, ואין בה כל תועלת לאחר מעשה.

ישישנן להבחיןשלוש ביןרמות הוכחתשל הוכחות '''אפס ידיעה: '''מושלמת''' לבין, '''הוכחת אפס ידיעהסטטיסטית''' ו-'''חישובית''':. הראשונה משמעה שלא עובר שום מידע למעט ידיעת אמיתות הטענה. השניה משמעה שניתן לייצר בקלות תמלילים מדומים של הפרוטוקול, ב[[מרחק סטטיסטי]] קטן מזה של תמלילים אמיתיים. האחרונה אומרת כי צד-שלישי, המוגבל ליכולת [[חישוב (מדעי המחשב)|חישוב]] [[זמן פולינומי|פולינומית]] בזמן ובמקום, לא יוכל לזהות הבדל כלשהו בין תמליל של פרוטוקול אמיתי לבין עותקתמליל מדומהמזוייף. לכן, מעשית לא ניתן יהיה לחלץ כל מידע, אפילואודות זעוםטענתו של המוכיח. ההגדרה הראשונה היא החזקה ביותר; ההגדרה השניה מעט חלשה יותר, אודותוניתן טענתולהוכיח עליה טענות בקלות רבה יותר; תחת הגדרה זו ניתן להוכיח קיום של המוכיח,בעיות תוךשלמות שימושוקיום בכוחשל חישובפרוטוקולים מוגבלקצרים מאוד. מעשיתההגדרה האחרונה, מסתפקיםהחלשה בהגדרה השנייהביותר, היותרהיא על פי רוב זו הנדרשת לצרכים קלהמעשיים.