עוד על שימושי הקריפטוגרפיה בחיי היום יום (מציאת אוצרות ומעבר דרך קירות)

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

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

מה עכשיו?

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

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

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

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

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

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

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

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

(מזל טוב לנגה צבי, שזכתה במקום השני בתחרות חצי הגמר של Famelab בטכניון, עם סיפור שיתוף הסוד שהצגתי לעיל!)


נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com