תאר לעצמך שהיה לך ידע שימושי - אולי מתכון סודי, או המפתח לצופן. האם תוכל להוכיח לחבר שיש לך את הידע הזה, מבלי לחשוף על כך דבר? מדעני מחשב הוכיחו לפני למעלה מ-30 שנה שאפשר, אם תשתמש במה שנקרא הוכחה של אפס ידע.
לדרך פשוטה להבין את הרעיון הזה, נניח שאתה רוצה להראות לחבר שלך שאתה יודע איך לעבור מבוך, מבלי לחשוף פרטים על הדרך. אתה יכול פשוט לחצות את המבוך בתוך מגבלת זמן, בעוד שלחבר שלך נאסר לצפות. (מגבלת הזמן הכרחית כי בהינתן מספיק זמן, כל אחד יכול בסופו של דבר למצוא את דרכו החוצה באמצעות ניסוי וטעייה.) חבר שלך היה יודע שאתה יכול לעשות את זה, אבל הוא לא היה יודע איך.
הוכחות אפס ידע מועילות למקריפטוגרפים, שעובדים עם מידע סודי, אך גם לחוקרים של מורכבות חישובית, העוסקת בסיווג הקושי של בעיות שונות. "הרבה קריפטוגרפיה מודרנית מסתמכת על הנחות מורכבות - על ההנחה שבעיות מסוימות קשות לפתרון, כך שתמיד היו כמה קשרים בין שני העולמות", אמר. קלוד קרפו, מדען מחשבים באוניברסיטת מקגיל. "אבל ההוכחות האלה יצרו עולם שלם של חיבור."
הוכחות אפס ידע שייכות לקטגוריה המכונה הוכחות אינטראקטיביות, כך שכדי ללמוד כיצד הראשונות עובדות, זה עוזר להבין את השניות. ראשון מְתוּאָר במאמר משנת 1985 של מדעני המחשב שאפי גולדווסר, סילביו מיקאלי וצ'רלס רקוף, הוכחות אינטראקטיביות עובדות כמו חקירה: על פני סדרה של הודעות, צד אחד (המוכיח) מנסה לשכנע את השני (המאמת) שהצהרה נתונה נכונה. הוכחה אינטראקטיבית חייבת לעמוד בשני מאפיינים. ראשית, הצהרה אמיתית תמיד תשכנע בסופו של דבר מוודא ישר. שנית, אם ההצהרה הנתונה שקרית, שום מוכיח - אפילו אחד שמתיימר להחזיק בידע מסוים - לא יכול לשכנע את המאמת, אלא בהסתברות קטנה באופן זניח.
הוכחות אינטראקטיביות הן הסתברותיות בטבען. המוכיח יכול לענות בצורה נכונה על שאלה אחת או שתיים פשוט במזל, כך שנדרש מספר מספיק גדול של אתגרים, שאת כולם על המוכיח לעמוד נכון, כדי שהמאמת יהיה בטוח שהמוכיח אכן יודע שהמשפט נכון.
הרעיון הזה של אינטראקציות הגיע כאשר מיקאלי וגולדווסר - אז סטודנטים לתואר שני באוניברסיטת קליפורניה, ברקלי - התלבטו על הלוגיסטיקה של משחק פוקר ברשת. איך כל השחקנים יכולים לוודא שכאשר אחד מהם מקבל קלף מהחפיסה הווירטואלית, התוצאה היא אקראית? הוכחות אינטראקטיביות יכולות להוביל את הדרך. אבל אז, איך שחקנים יכולים לוודא שכל הפרוטוקול - מערכת הכללים המלאה - בוצע כהלכה, מבלי לחשוף את היד של כל שחקן בדרך?
כדי להשיג מטרה זו, מיקלי וגולדווסר הוסיפו תכונה שלישית לשניים הדרושים להוכחה אינטראקטיבית: ההוכחה אינה צריכה לגלות דבר על הידע עצמו, רק את אמיתות האמירה. "יש רעיון של לעבור על פרוטוקול, שבסופו אתה מאמין ש[שחקני הפוקר] לא יודעים שום דבר יותר ממה שהם אמורים לדעת", אמר גולדווסר.
בואו ניקח בחשבון את הדוגמה הקלאסית. אליס רוצה להוכיח לבוב שגרף מסוים G - אוסף ייחודי של קודקודים (נקודות) המחוברים בקצוות (קווים) - יש "מחזור המילטוני". זה אומר שלגרף יש נתיב שמבקר בכל נקודה פעם אחת בדיוק ומסתיים באותה נקודה שממנה התחיל. אליס יכולה לעשות זאת על ידי פשוט להראות לבוב את הנתיב שעושה זאת, אבל כמובן שגם הוא יכיר את הנתיב.
הנה איך אליס יכולה לשכנע את בוב שהיא יודעת שקיים נתיב כזה, מבלי להראות לו אותו. ראשית היא מציירת גרף חדש, H, זה לא נראה G אבל דומה באופן מכריע: יש לו אותו מספר של קודקודים, מחוברים באותם דרכים. (אם G באמת יש מחזור המילטון, משמעות הדמיון הזו H יהיה גם.) לאחר מכן, לאחר כיסוי כל קצה פנימה H עם מסקינטייפ היא נועלת H בקופסה ונותן את הקופסה לבוב. זה מונע ממנו לראות את זה ישירות אבל גם מונע ממנה לשנות את זה. ואז בוב עושה בחירה: או שהוא יכול לבקש מאליס להראות את זה H באמת דומה ל G, או שהוא יכול לבקש ממנה להראות לו את המחזור המילטון H. שתי הבקשות צריכות להיות קלות עבור אליס, בהנחה שכך H באמת דומה מספיק ל Gושהיא באמת מכירה את הדרך.
כמובן, גם אם אליס לא מכירה את המחזור המילטון G, היא יכולה לנסות לרמות את בוב, על ידי ציור גרפים שאינם דומים ל G, או על ידי שליחת גרפים שהיא לא יודעת את הנתיב אליו. אבל אחרי שהם שיחקו סיבובים מרובים, הסיכוי שאליס תרמה את בוב בכל פעם הופך להיות קטן ונעלם. אם היא תעשה הכל נכון, בסופו של דבר בוב ישתכנע שאליס יודעת מחזור המילטון בגרף Gמבלי שבוב ראה את זה מעולם.
לאחר המאמר הראשוני שתיאר לראשונה הוכחות כאלה, גילו מיקלי ושני מתמטיקאים - עודד גולדרייך ואבי וידרסון - תוצאה בלתי צפויה עם השפעות מרחיקות לכת. זה קשור לקטגוריה עיקרית של בעיות בעלות קושי שווה בערך, המכונה NP. בעיות אלו קשות לפתרון, אך קל לאמת את הפתרונות שלהן. שלושת החוקרים מצא כי, אם הצפנה מאובטחת באמת זה אפשרי, אז ניתן להוכיח את הפתרון לכל בעיה ב-NP גם בהוכחת אפס ידע. מחקר זה עזר לחוקרים להעלות על הדעת גרסאות של הוכחות אפס ידע שאפילו לא דורשות הצפנה מאובטחת מלכתחילה; אלו ידועות כהוכחות אינטראקטיביות מרובות מוכיחים.
ובשנת 1988, מיקאלי ואחרים הראה שאם מוכיח ומאמת חולקים מחרוזת קצרה של ביטים אקראיים, אין צורך באינטראקציה. משמעות הדבר הייתה תיאורטית שהוכחות אפס ידע אינן חייבות להיות אינטראקטיביות, מה שרומז שאין צורך בתקשורת מתמדת בין שני צדדים. זה יהפוך אותם להרבה יותר שימושיים לחוקרים, אבל רק לאחר תחילת המאה ה-21 הוכחו הוכחות כאלה.
"בסוף שנות ה-2000, התחלנו לראות את ההתפתחות של טכניקות יעילות לבניית הוכחות אפס ידע", אמר מתיו ד' גרין, קריפטוגרף באוניברסיטת ג'ון הופקינס. "הגענו לנקודה שבה הבנו, 'חכה שנייה, אולי באמת יש דרך להשתמש בזה בפועל'".
כעת מוכיח יכול לשלוח הודעה בודדת למאמת מבלי ששניהם יצטרכו להיות מקוונים, וחוקרים יכולים ליצור הוכחה קצרה מאוד שניתן לאמת במהירות, אפילו עבור בעיות מאוד מסובכות. זה הוביל למספר שימושים מעשיים, כמו היכולת לאמת במהירות את הבלוקצ'יין לאחר עסקת מטבעות קריפטוגרפיים תוך הסתרת פרטי העסקה. ובשנת 2016, קבוצה של פיזיקאים הראה כיצד הוכחות אפס ידע יכולות לעזור לפירוק מנשק גרעיני: מבלי לחשוף סוד כלשהו לגבי תכנון ראש הנפץ הגרעיני שלה, מדינה יכולה כעת להוכיח לפקחי הגרעין אם ראש הנפץ פעיל או לא פעיל.
לאחרונה, התקדמות בתחום המחשוב הקוונטי אילצה את Crépeau לבדוק מחקרים קודמים כדי לוודא שפרוטוקולי אפס ידע עדיין קיימא. ב-2021 הוא עזר להפגין שהוכחות אינטראקטיביות מרובות מוכיחים אמנם שומרות על הסודיות שלהן גם כשמעורבים מחשבים קוונטיים, אבל השגת אותה רמת אבטחה הופכת את הפרוטוקול לאיטי בהרבה. הממצא הוא חדשות טובות, אמר, אך חששות חדשים יתעוררו ככל שהטכנולוגיה תתקדם.
"כל סוג חישוב שאנו עשויים לעשות בעתיד יכלול מחשבים קוונטיים", אמר קרפו. "אז בתור קריפטוגרפים פרנואידים טובים, בכל פעם שאנחנו מעריכים את האבטחה של מערכת, אנחנו רוצים לוודא שהמערכת שלנו בטוחה."
הערת המערכת: שפי גולדווסר קיבלה מימון מקרן סימונס, שגם מממנת זאת פרסום עצמאי בעריכה. להחלטות המימון של קרן סימונס אין השפעה על הסיקור שלנו.
