על משת”פים ונבוטים בראש, והקשר שלהם להוכחות אפס-ידע

בפוסט הקודם הצגתי הוכחות אפס-ידע תוך נסיון להתחמק מהפרטים הטכניים. הפעם ובפעם הבאה אנסה להציג גם את הפרטים הללו, תוך סיכון ממשי לאבד את שני הקוראים שעדיין מצליחים לעקוב. ארצה לעשות שני דברים: להסביר באופן כללי מה הרעיון שמאחורי ההגדרה הפורמלית של הוכחה באפס-ידע, וכיצד “עובדת” מערכת ההוכחה שהצגתי בפעם הקודמת ועוסקת בהוצאת שורש ריבועי בחבורה כפלית מודולו n.

אז ראשית, כיצד ניתן להראות באופן פורמלי שמערכת הוכחה היא אפס-ידע? כיצד ניתן לפרמל את המושג של “המוודא לא מגלה שום דבר חדש תוך כדי ההוכחה, פרט לדבר שמנסים להוכיח”? התשובה היא שהוכחה נחשבת הוכחת אפס-ידע אם אפשר “לזייף” אותה בצורה שתצליח לשטות במי שצופה בה מן הצד.

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

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

מתי אפשר לתפוס את בארנבוים בשקר? אם הוא מתחיל לחזור על עצמו. נניח שכעבור שנה אנו רואים עוד ראיון עם בארנבוים (לא היה ולא נברא, אבל נניח), ובו עושים לו את אותו ה”מבחן”, ושואלים אותו בדיוק על אותן יצירות - אז כבר נרגיש שמשהו מסריח פה. הדבר דומה לפרשיית “מלחמות היהודים” ומשה קצב, ששייכת לימים שבהם טרם נקשר שמו של קצב לפרשיות “בוגרות” יותר - בראיון חגיגי לרגל ראש השנה (או משהו בסגנון) נשאל קצב מה הספר שמונח כעת לצד מיטתו, וענה “מלחמות היהודים”, כיאה לנשיא משכיל ומחובר לשורשיו. כעבור מספר שנים, בראיון דומה, הוא נשאל את אותה השאלה, וענה את אותה התשובה… כמובן שלא הוגן ללעוג לנשיא שעיסוקיו הרבים מונעים ממנו להתקדם בספר שהוא ממילא עב כרס, ולכן הדוגמה הזו היא בגדר אסוציאציה אישית שלי בלבד.

אם כן, הוכחה היא הוכחת אפס-ידע אם אפשר “לזייף” אותה מבלי שהיא תיפול בצורה דומה לזו שלעיל. חשוב להבהיר שב”זיוף” איני מתכוון דווקא ל”אפשר להוכיח שמשהו שגוי הוא נכון” - כי שוב, ההוכחה מיועדת לשכנע רק את המוודא, ולא אף מתבונן מהצד - אלא גם למצב שבו המוכיח אולי מנסה להוכיח משהו נכון, אבל פשוט אין לו את הידע הנוסף או כוח החישוב הנוסף שיש למוכיח בדרך כלל. למשל: בהינתן גרף עם 3-צביעה, מנסים לזייף פרוטוקול הוכחה בצורה כזו שיראה למתבונן מהצד שהמוכיח אכן מוכיח בצורה משכנעת למוודא שהוא מכיר את 3 הצביעה הזו, למרות שבפועל המוכיח לא יודע כלום.

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

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

המגבלה העיקרית שמושתת על הסימולטור היא הדרישה שמבחינה חישובית הוא לא יהיה חזק יותר מהמוודא - כלומר, אין לו את הידע הנוסף של המוכיח, וגם אין לו זמן “לאתחל” (נבוט בראש, החרמת סרט הצילום, וכו’) את השאלה של המוודא שוב ושוב עד שתגיע שאלה מוצלחת.

חשוב לציין שוב - מושג הסימולטור הוא מושג קשה ומורכב יחסית, ולא הצגתי אותו כאן בצורה מדוייקת כלל. המטרה שלי היא בעיקר לתת “תחושה” של המושג (וככל הנראה, זוהי בעיקר תחושתי הסובייקטיבית), ולכן יש לנהוג במשנה זהירות.

בואו נעבור להדגמה של סימולטורים לשני הפרוטוקולים שכבר ראינו: זה של איפה אפי, וזה של ה-3-צביעה.

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

גם הסימולטור לבעית ה-3-צביעה אינו מסובך במיוחד. גם כאן הסימולטור ישתמש במוודא משת”ף. הוא יבקש מהמוודא לבחור צמתים באקראי מהגרף כפי שעושה כל מוודא אחר, אבל לאחר שהמוודא יבחר, הסימולטור יעצור לרגע את ההקלטה, ירים את הכיסוי של הצמתים, יחשוף שמתחתיו אין לצמתים צבע בכלל, יצבע את שניהם בצבעים שונים באופן אקראי, יחזיר את הכיסוי ויתחיל מחדש את ההקלטה (יסיר את הכיסוי ויחשוף “למרבה הפלא” שני צמתים הצבועים בצבעים שונים). המוודא המשת”ף יראה את כל הפרוצדורה הזו לנגד עיניו ולא יצייץ. התוצאה? קלטת וידאו שנראית כמו פרוטוקול אמיתי, תודות ליכולות העריכה של הסימולטור.

כל זה נשמע קצת מגוחך. קלטות וידאו, נבוט בראש, מוודא משת”ף - מה לאלו ולמתמטיקה? האמת היא שההבדל קטן ממה שניתן לחשוב. סימולטור מנוסח בפורמליזם מתמטי מדוייק של מכונות חישוב, אולם הפעולות שהוא נוקט בהן דומות מאוד לאלו שתיארתי לעיל: הוא מייצר “תעתיק” של הפרוטוקול שהוא פשוט טקסט ארוך שמתאר את ההודעות שנשלחו מהמוודא למוכיח ולהפך - זו קלטת הוידאו, והוא מסוגל לערוך אותו כרצונו, העיקר שהתוצאה תהיה משביעת רצון מבחינת המתבונן מן הצד. הנבוט בראש גם הוא ניתן לפורמליזם: הסימולטור מפעיל את מכונת החישוב של המוודא, ואם היא לא נתנה לו את התוצאה שהוא התעניין בה, הוא מאתחל אותה ומפעיל אותה מחדש. גם המוודא המשת”ף הוא בסך הכל דרך ציורית לתיאור העובדה שבפרוטוקול שהסימולטור מייצר הוא רשאי לכתוב מה שבא לו בתור דברי המוודא - כל עוד זה ייראה אמין - ולכן אפשר לחשוב שיש מוודא “עושה דברו” שמשתתף ביצירת התעתיק.

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