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