הוכחה באפס ידיעה

היסטוריה

רעיון אפס ידיעה נהגה לראשונה ב-1985 על ידי שפי גולדווסר (המכון הטכנולוגי של מסצ'וסטס, מכון ויצמן למדע), סילביו מיקאלי (המכון הטכנולוגי של מסצ'וסטס), וצ'ארלס ראקוף (אוניברסיטת טורונטו). הם תיארו במאמר "The knowledge complexity of interactive proof-systems" את הרעיון של הוכחת טענה מתמטית באופן אינטראקטיבי (interactive proof-system) ואת הרעיון שניתן לבצע הוכחה כזו ללא חשיפת מידע נוסף (Zero-knowledge proof). הם טבעו את המונח סיבוכיות ידיעה, והציעו מספר מדדים לכמות המידע העובר בהוכחה אינטראקטיבית. הם אף הביאו דוגמה מעשית ראשונה של הוכחת אפס ידיעה: שמספר שלם אינו שארית ריבועית מודולו , תוך חשיפת אפס מידע בנוגע למספר עצמו, בהתבסס על העובדה שלא קיים אלגוריתם יעיל לבדיקת שארית ריבועית, אם לא נתונים הגורמים הראשוניים של . על תרומתם זו זכו בפרס גדל.
עודד גולדרייך (מכון ויצמן), סילביו מיקאלי ואבי ויגדרזון (האוניברסיטה העברית בירושלים) הראו, שבהנחה שקיימת פונקציה חד-כיוונית, ניתן לבסס מערכת הוכחה אינטראקטיבית על בעיה NP-שלמה, כמו בעיית הצביעה בגרפים (ראה להלן). היות שכל בעיה במחלקת הסיבוכיות NP ניתנת לצמצום לבעיה זו, הרי שלכל בעיית NP קיימת הוכחת אפס ידיעה, תחת הנחה זו. באופן כללי, הראו גולדרייך וגולדווסר, שכל דבר שניתן להוכחה באופן אינטראקטיבי, ניתן להוכחה באמצעות הוכחת אפס ידיעה; ולמעשה, כל בעיית NP-שלמה ניתנת לשימוש כבסיס למערכת הוכחה באפס ידיעה, כמו גם בעיות קשות אחרות, כמו בעיית הפירוק לגורמים של מספר שלם.

צביעות גרף

דוגמה אחת היא ההוכחה שגרף כלשהו הוא 3-צביע – כלומר, שניתן באמצעות שלושה צבעים לצבוע את כל קודקודיו בצורה כזו, שבה כל שני קודקודים שמחוברים בקשת יהיו צבועים בצבעים שונים. לדוגמה זו חשיבות, הן בשל האינטואיטיביות היחסית שלה, והן מכיוון שבעיית ה-3-צביעה של גרף היא בעיה NP שלמה, ולכן נובע מכך, שלכל בעיה ששייכת למחלקת הסיבוכיות NP קיימת הוכחה באפס ידיעה.
אופן ההוכחה הוא כדלהלן: בהינתן גרף שהוא 3-צביע, ה"סוד" של המוכיח הוא צביעה אפשרית של הגרף. מציאה של צביעה כזו באופן כללי היא בעיה קשה, ולכן ניתן להניח, שהמוודא אינו יכול לגלות צביעה שכזו בעצמו.
בכל סבב של הפרוטוקול המוכיח מגריל תמורה שונה על צבעי הגרף, ומשנה את הצביעה שלו בהתאם. ואז הוא "מכסה" את כל צומתי הגרף ושולח אותו למוודא. המוודא בוחר שני צמתים שמחוברים בקשת ושולח אותם למוכיח, והמוכיח חושף את שני הצמתים הללו (ואותם בלבד). המוודא בודק, שאכן שני הצמתים צבועים בצבע שונה; אם לא – ההוכחה נדחית. על תהליך זה חוזרים כמספר הפעמים הרצוי, עד שהמוודא משתכנע.
החלק הקשה בהוכחה הוא שלב ה"כיסוי". המוכיח צריך "להתחייב" מראש על הצביעה של הגרף כולו, ועם זאת, לא לחשוף דבר. קיימות סכימות התחייבות שמאפשרות לבצע זאת. הסיבה שפרוטוקול זה הוא בעל תכונת אפס ידיעה, נעוצה בכך שהמידע היחיד אותו מקבל המוודא בכל סבב הוא ששני הצמתים שבחר מהגרף אכן צבועים בצבע שונה, כפי שנדרש מהצביעה. אולם, כיוון שבכל סבב מוגרלת פרמוטציה שונה על הצבעים, אין כל תועלת במידע מסבבים קודמים כדי לקבל מושג לגבי צביעת הגרף כולו. להמחשה, אם בסבב הראשון ביקש המוודא את צמתים A,B וראה שהם צבועים בכחול ואדום ובסבב השני ביקש את הצמתים A,C וראה שוב שהם צבועים בכחול ואדום, אין זה אומר ש-B ו-C צבועים בצביעה המקורית באותו הצבע.

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

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

פרוטוקול הוכחת אפס ידיעה קריפטוגרפי

עדי שמיר (מכון ויצמן) ועמוס פיאט (כיום באוניברסיטת ת"א), הניחו ב-1986 את היסודות למימוש רעיון אפס-ידיעה מבחינה פרקטית בפרוטוקול הנקרא פרוטוקול פיאט-שמיר (Fiat-Shamir) – הפרוטוקול האינטראקטיבי מבוסס אפס-ידיעה הראשון. הפרוטוקול נשען על בעיית שורש ריבועי מודולו שלם פריק; בעיה, השקולה לבעיית פירוק לגורמים. חשוב לציין, שפרוטוקול זה אינו יעיל מעשית, מאחר שבכל סבב מועברת סיבית אתגר אחת בלבד, והוא מוצג כאן להמחשה בלבד. פרוטוקול פייגה-פיאט-שמיר (Feige-Fiat-Shamir) הוא הרחבה של פרוטוקול זה, שפועל על מחרוזת סיביות אתגר בו-זמנית, ועל כן יעיל יותר. כמו כן, קיים פרוטוקול אימות שנור של קלאוס שנור (C.P. Schnorr), המיישם הוכחת אפס ידיעה ומבוסס על בעיית לוגריתם דיסקרטי.

דוגמה לפרוטוקול פיאט-שמיר

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

הוכחת אפס ידיעה לא אינטראקטיבית

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