האם תוכלו לשכנע את חבריכם שאתם יודעים סוד כלשהו, מבלי לגלות כלום על הסוד עצמו? "הוכחות באפס ידיעה" מאפשרות לנו לשכנע גורם חיצוני שיש ברשותנו מידע כלשהו, בלי לגלות את המידע עצמו או שום דבר אחר.

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

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

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

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

הוכחות באפס ידיעה הוגדרו ונחקרו לראשונה בסוף שנות ה 80 על ידי המדענית הישראלית שפי גולדווסר, סילביו מיקאלי וצ'רלס רקוף [1], ועל ידי לזלו בבאי ושלמה מורן [2]. כל החמישה זכו בפרס גֶדֶל על ההישג, והשניים הראשונים אף זכו בעקבותו בפרס טיורינג.

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

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

המערה המעגלית של אליס ובוב

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

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

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

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

כיום, מעבר לעניין התיאורטי (הניכר מאוד), להוכחות באפס ידיעה יש השלכות מעשיות רבות:

• במכרזים פומביים מקוונים, למשל, כמה משתתפים מציעים מחיר עבור מוצר כלשהו, וההצעה הגבוהה זוכה. אולם כעת, כל המשתתפים שלא זכו מעוניינים להשתכנע שההצעות שלהם אכן היו נמוכות מההצעה הזוכה (אחרת יש חשד שהמכרז היה "מכור"). מאידך, מארגני המכרז לא מעוניינים לחשוף את גובה ההצעה הזוכה. ניתן, בעזרת הוכחות באפס ידיעה, לשכנע כל אחד מהמשתתפים שההצעה שלו היתה נמוכה מההצעה הזוכה, מבלי לחשוף דבר לגבי ההצעה הזוכה עצמה [5].
• בעת בקשת הלוואה/משכנתא, הגורם המלווה (בנק, למשל) רוצה לבדוק את הסיכון בהלוואה, ועל כן רוצה לדעת מה המצב הפיננסי של מבקש ההלוואה. במקרים מסוימים, מבקש ההלוואה לא רוצה לחשוף את כל פרטיו הפיננסיים. הוכחות באפס ידיעה מאפשרות למבקש להוכיח שיש לו סף מסויים של הכנסות המאפשרות לו לעמוד בהלוואה, מבלי לחשוף דבר מעבר לכך על נכסיו [6].
• מטבעות קריפטוגרפיים מתבססים על רעיון הנקרא בלוקצ'יין, שבו מתועדת ההיסטוריה של כל העברות המטבעות בין "ארנקים" שונים. בחלק מהמטבעות (דווקא לא בביטקוין המפורסם, אבל באחרים), מעוניינים שלא לחשוף את זהות הארנקים שמעורבים בהעברות. ניתן לעשות זאת בעזרת הוכחות באפס ידיעה [7].

מקורות וקריאה נוספת:

[1] Goldwasser, S.; Micali, S.; Rackoff, C. (1989), "The knowledge complexity of interactive proof systems" (PDF), SIAM Journal on Computing, 18 (1): 186–208

[2] Babai, László; Moran, Shlomo (1988), "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class" (PDF), Journal of Computer and System Sciences, 36 (2): 254–276

[3] Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. (1990). How to Explain Zero-Knowledge Protocols to Your Children. 

[4] https://gadial.net/2007/07/21/zero_knowledge_proofs_intro/

[5] Zero Knowledge Proofs Applied to Auctions https://courses.csail.mit.edu/6.857/2019/project/18-doNascimento-Kumari-Ganesan.pdf

[6] Tommy Koens, Coen Ramaekers and Cees van Wijk. (2017) “Efficient Zero-Knowledge Range Proofs in Ethereum”  https://www.ingwb.com/media/2667860/zero-knowledge-range-proofs.pdf

[7] Chirag Bhardwaj (2020) “What is Zero-Knowledge Proof & its Role in the Blockchain World?”

https://appinventiv.com/blog/zero-knowledge-proof-blockchain/

[8] O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM 38(1):691-729, 1991.