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

תוכן שנמחק תוכן שנוסף
חזרתי-בוט (שיחה | תרומות)
מ שרת ⟸ שרת (מחשבים): תיקון פירושונים (באמצעות WP:JWB)
שורה 24:
בכל סבב של הפרוטוקול המוכיח מגריל [[תמורה (מתמטיקה)|תמורה]] שונה על צבעי הגרף, ומשנה את הצביעה שלו בהתאם. ואז הוא "מכסה" את כל צומתי הגרף ושולח אותו למוודא. המוודא בוחר שני צמתים שמחוברים בקשת ושולח אותם למוכיח, והמוכיח חושף את שני הצמתים הללו (ואותם בלבד). המוודא בודק, שאכן שני הצמתים צבועים בצבע שונה; אם לא – ההוכחה נדחית. על תהליך זה חוזרים כמספר הפעמים הרצוי, עד שהמוודא משתכנע.
 
החלק הקשה בהוכחה הוא שלב ה"כיסוי". המוכיח צריך "להתחייב" מראש על הצביעה של הגרף כולו, ועם זאת, לא לחשוף דבר. קיימות [[סכימת התחייבות|סכימות התחייבות]] שמאפשרות לבצע זאת. הסיבה שפרוטוקול זה הוא בעל תכונת אפס ידיעה, נעוצה בכך שהמידע היחיד אותו מקבל המוודא בכל סבב הוא ששני הצמתים שבחר מהגרף אכן צבועים בצבע שונה, כפי שנדרש מהצביעה. אולם, כיוון שבכל סבב מוגרלת [[פרמוטציה]]תמורה שונה על הצבעים, אין כל תועלת במידע מסבבים קודמים כדי לקבל מושג לגבי צביעת הגרף כולו. להמחשה, אם בסבב הראשון ביקש המוודא את צמתים A,B וראה שהם צבועים בכחול ואדום ובסבב השני ביקש את הצמתים A,C וראה שוב שהם צבועים בכחול ואדום, אין זה אומר ש-B ו-C צבועים בצביעה המקורית באותו הצבע.
 
==עלי באבא והמערה המסתורית==