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

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

הוכחת אפס ידיעה חייבת לקיים את התכונות הבאות:

1. שלמות (Completeness) – פרוטוקול הוכחה אינטראקטיבי ייקרא שלם, אם בהינתן מוכיח ומוודא הגונים (המבצעים את מהלכי הפרוטוקול כראוי), אם הטענה נכונה אזי המוכיח יצליח לשכנע את המוודא בנכונות הטענה בהסתברות גבוהה. במונח "הסתברות גבוהה" מתכוונים כי קיים סיכוי קל לכישלון.
2. נאותות (Soundness) – פרוטוקול הוכחה אינטראקטיבי ייקרא נאות, אם בהינתן טענה שקרית, מוכיח רמאי לא יצליח להונות מוודא הגון בנכונות הטענה. במילים אחרות, נאותות מבטיחה כי הפרוטוקול אכן מספק הוכחת הטענה או ידיעת הסוד וכי מוודא הגון יצליח לחשוף רמאות בהסתברות גבוהה.
3. אפס ידיעה (Zero knowledge) – לפרוטוקול הוכחה אינטראקטיבי תהיה תכונת אפס ידיעה, אם בהינתן טענה נכונה, המוודא לא יוכל ללמוד מאומה אודות הטענה עצמה מעבר לעצם נכונותה. תנאי מהותי בתכונת אפס ידיעה הוא, שבהינתן טענה (ללא גישה לסודו של המוכיח) לא ניתן יהיה להבחין בהבדל כלשהו בינה לבין עותק מזויף. במילים אחרות באפשרותו של מוכיח רמאי "לחקות" הוכחה שניתנה על ידי מוכיח הגון, מזה נובע כי לא ניתן ללמוד מן ההוכחה מידע כלשהו על הטענה. העתקת ההוכחה כשלעצמה אינה מועילה בדבר לרמאי, כיוון שכפי שיובהר בהמשך, ההוכחה תקפה רק עבור המשתתפים בפרוטוקול בזמן אמת, ואין בה כל תועלת לאחר מעשה.

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

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

היסטוריה

רעיון אפס ידיעה נהגה לראשונה ב-1985 על ידי שפי גולדווסר (המכון הטכנולוגי של מסצ'וסטס, מכון ויצמן למדע), סילביו מיקאלי (המכון הטכנולוגי של מסצ'וסטס), וצ'ארלס ראקוף (אוניברסיטת טורונטו). הם תיארו במאמר "The knowledge complexity of interactive proof-systems"^[1] את הרעיון של הוכחת טענה מתמטית באופן אינטראקטיבי (interactive proof-system) ואת הרעיון שניתן לבצע הוכחה כזו ללא חשיפת מידע נוסף (Zero-knowledge proof). הם טבעו את המונח סיבוכיות ידיעה, והציעו מספר מדדים לכמות המידע העובר בהוכחה אינטראקטיבית. הם אף הביאו דוגמה מעשית ראשונה של הוכחת אפס ידיעה: שמספר שלם אינו שארית ריבועית מודולו ${\displaystyle m}$, תוך חשיפת אפס מידע בנוגע למספר עצמו, בהתבסס על העובדה שלא קיים אלגוריתם יעיל לבדיקת שארית ריבועית, אם לא נתונים הגורמים הראשוניים של ${\displaystyle m}$. על תרומתם זו זכו בפרס גדל.

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

דוגמאות

צביעות גרף

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

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

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

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

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

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

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

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

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

איפה אפי?

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

ספירת עלים של עץ

דוגמה נוספת היא היכולת לספור עלים על עץ. נניח שאחת השחקניות, אליס, טוענת שיש לה כוח-על, המאפשר לה למנות את המספר המדויק של עלים על עץ כהרף עין. כדי לשכנע ביכולתה זו, היא מציעה לאדם השני, בוב, לבחור עץ. היא מתבוננת בעץ, ומייד מציינת את מספר העלים שספרה, למשל: 77,777,777. לאחר מכן היא מכסה את עיניה, ומציעה לבוב לקטוף בסתר כמה עלים מן העץ. בוב יכול לקטוף מספר עלים כרצונו, למשל 3 או 10 או אפילו לא לקטוף כלל. לאחר מכן אליס מגלה את עיניה, ומבצעת ספירה חוזרת של העץ. אם בוב קטף 3 עלים, אליס תציין שעכשיו מספר העלים הוא 77,777,774. באופן זה אליס משכנעת את בוב ביכולת-העל שלה, על ידי הוכחה באפס ידיעה.

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

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

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

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

1. ${\displaystyle A\rightarrow B}$ : התחייבות (commitment)
2. ${\displaystyle A\leftarrow B}$ : אתגר (challenge)
3. ${\displaystyle A\rightarrow B}$ : מענה (response)

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

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

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

פרוטוקול פיאט-שמיר

בפרוטוקול משתתפים פגי (המוכיחה) וויקטור (המוודא). פגי בוחרת בסוד שני ראשוניים אקראיים ${\displaystyle p}$ ו-${\displaystyle q}$ ומפרסמת את המכפלה שלהם ${\displaystyle N=pq}$. המשימה של פגי היא להוכיח לוויקטור ששלם מסוים ${\displaystyle y}$ הוא מספר ריבועי מודולו ${\displaystyle N}$ מבלי לחשוף בפניו כל מידע שיעזור לו להוכיח לאחרים ש-${\displaystyle y}$ ריבועי מודולו ${\displaystyle N}$. יש לזכור שהוצאת שורש ריבועי מודולו שלם פריק ${\displaystyle N}$ היא בעיה מתמטית קשה. אך כיוון שפגי יודעת מהם הגורמים הראשוניים של ${\displaystyle N}$ והוצאת שורש ריבועי מודולו מספר ראשוני קלה, ביכולתה למצוא בקלות שורש ריבועי מודולרי של כל שלם מודולו ${\displaystyle N}$ על ידי משפט השאריות הסיני, נניח שקיים ${\displaystyle x}$ המקיים:

${\displaystyle x^{2}\equiv y{\text{ (mod }}N)}$.

ואת זה מעוניינת פגי להוכיח לוויקטור מבלי לחשוף את ${\displaystyle x}$ (במקרה זה ${\displaystyle x}$ הוא הסיסמה הסודית של פגי). היא מוכיחה זאת באמצעות פרוטוקול המבוצע בכמה סבבים של חילופי מסרים שבסופם ויקטור יקבל או לא יקבל את טענתה. בכל סבב מתבצעים המהלכים הבאים:

1. פגי בוחרת שלם אקראי ${\displaystyle r}$ מודולו ${\displaystyle N}$. ומחשבת ושולחת לוויקטור את השלם ${\displaystyle s\equiv r^{2}{\text{ (mod }}N)}$ שנקרא התחייבות. 2. ויקטור בוחר אתגר אקראי שהוא סיבית אחת ${\displaystyle \beta \in \{0,1\}}$ ושולח לפגי את ${\displaystyle \beta }$. 3. פגי מחשבת ושולחת לוויקטור את המענה ${\displaystyle z=x^{\beta }r{\text{ (mod }}N)}$ שפירושו שאם ${\displaystyle \beta =0}$ היא מחזירה לוויקטור רק את ${\displaystyle r}$, אחרת היא מחזירה את ${\displaystyle xr{\text{ (mod }}N)}$, בניסוח אחר: ${\displaystyle z\equiv {\begin{cases}r{\text{ (mod }}N),&{\mbox{if }}\beta =0\\xr{\text{ (mod }}N),&{\mbox{if }}\beta =1\end{cases}}}$. אפשר לראות ש-${\displaystyle x}$ לא נחשף לעיניו של ויקטור כי הוכפל בשלם האקראי ${\displaystyle r}$ מודולו ${\displaystyle N}$ שזהו מעין פנקס חד פעמי. 4. ויקטור בודק שמתקיים ${\displaystyle z^{2}\equiv y^{\beta }s{\text{ (mod }}N)}$ כלומר אם ${\displaystyle \beta =0}$ אז ${\displaystyle z}$ הוא שורש ריבועי של ${\displaystyle s}$, אחרת ${\displaystyle z}$ הוא שורש ריבועי של ${\displaystyle ys}$, בניסוח אחר: ${\displaystyle z^{2}\equiv {\begin{cases}s{\text{ (mod }}N),&{\mbox{if }}\beta =0\\ys{\text{ (mod }}N),&{\mbox{if }}\beta =1\end{cases}}}$. אם תנאי זה מתקיים ויקטור מקבל את טענתה של פגי ביחס לאתגר אחד, אחרת הוא דוחה אותה.

פגי וויקטור חוזרים על התהליך המתואר ${\displaystyle n}$ פעמים עם ${\displaystyle n}$ אתגרים אקראיים שונים כאשר ${\displaystyle n}$ גדול מספיק (כגון ${\displaystyle n=80}$). אם תגובתה של פגי בכל הסבבים מניחה את דעתו של ויקטור הוא יכול לקבל את ההוכחה שאכן ${\displaystyle y}$ הוא מספר ריבועי (כלומר שיש לו שורש ריבועי) מודולו ${\displaystyle N}$ אחרת הוא דוחה אותה כטענה שקרית כי לא סביר שתצליח להוליכו שולל בכל הפעמים. קל להיווכח בשלמות ונאותות הפרוטוקול כנדרש. כי הרי אם ${\displaystyle y}$ הוא שורש ריבועי מודולו ${\displaystyle N}$ אז ${\displaystyle z}$ ששלחה פגי לוויקטור מקיים ${\displaystyle z\equiv x^{\beta }r{\text{ (mod }}N)}$ לכן:

${\displaystyle z^{2}\equiv x^{2\beta }r^{2}\equiv y^{\beta }s{\text{ (mod }}N)}$.

לכן ויקטור יכול לקבל את טענתה.

במקרה ההפוך, אם ${\displaystyle y}$ אינו ריבועי מודולו ${\displaystyle N}$, אזי לא משנה איך היא בחרה את ${\displaystyle s}$, רק אחד משני הערכים יהיה נכון. כלומר או ${\displaystyle s}$ או ${\displaystyle ys}$ יהיו מספר ריבועי מודלו ${\displaystyle N}$ אבל לא שניהם. כלומר לפגי יש סיכויים של 50% לשקר אם היא לא באמת יודעת מהם הגורמים הראשוניים של ${\displaystyle N}$. מכאן נובע שהיא תכשל באתגר בודד של ויקטור במחצית הפעמים במקרה הממוצע. אם האתגרים הם רצף סיביות אקראי הרי שבמחצית מן המקרים בממוצע (כאשר סיבית האתגר היא אפס) היא נדרשת להוכיח ש-${\displaystyle s}$ ריבועי מודולו ${\displaystyle N}$ ומחצית מן המקרים היא נדרשת להוכיח ש-${\displaystyle ys}$ ריבועי. כך שאם ${\displaystyle y}$ אינו ריבועי הסיכויים שפגי תספק מענה נכון בכל ${\displaystyle n}$ הסבבים הם ${\displaystyle \textstyle {\frac {1}{2}}\cdot {\frac {1}{2}}\cdot {\frac {1}{2}}\cdots }$ בסך הכול ${\displaystyle n}$ פעמים או בקיצור ${\displaystyle 2^{-n}}$. אם היא הצליחה לשלוח 80 תגובות נכונות לאתגרים של ויקטור הרי שהוא יכול בהחלט להיות סמוך ובטוח שאכן ${\displaystyle y}$ הוא ריבועי מודולו ${\displaystyle N}$ כי ההסתברות שהיא תצליח לרמותו היא ${\displaystyle 2^{-80}}$ שהיא סבירות זניחה מאוד.

נותר להבין איך התגובות שקיבל מפגי אינן תורמות מאומה לידיעתו של ויקטור בנוגע לטענתה (כלומר אפס ידיעה). בניסוח אחר השאלה היא האם ויקטור יכול לעשות בהן שימוש כלשהו כדי להוכיח באותה הדרך למישהו אחר נניח ולרי, בסיכויי הצלחה גבוהים יותר מאשר אילו לא קיבל את תגובותיה של פגי, ש-${\displaystyle y}$ הוא מספר ריבועי מודולו ${\displaystyle N}$. כמו שיבואר בהמשך ויקטור מסוגל עקרונית לייצר רשימה של ערכים שייראו על פניהם כמו תגובות אותנטיות של פגי ולמרות זאת אין בזה כל ערך בניסיון להוכיח לוולרי את אותה הטענה לכן, התגובות של פגי אינן תורמות מאומה לידיעתו של ויקטור משום שאם כן הרי שהוא היה יכול לבצע חיקוי מושלם שלהן בעצמו ללא עזרתה. ההוכחה התאורטית של אפס הידיעה קשורה לתורת ההסתברות ובעיקרה הטענה היא ששתי ההתפלגויות זהות.

להמחשת הרעיון. לאחר שוויקטור סיים את תהליך ההוכחה עם פגי נותרו בידו ${\displaystyle n}$ שלשות ערכים ${\displaystyle (s_{1},\beta _{1},z_{1}),(s_{2},\beta _{2},z_{2}),...,(s_{n},\beta _{n},z_{n})}$ כשכל אחד מהם מקיים:

${\displaystyle z_{i}^{2}\equiv y^{\beta _{i}}s_{i}{\text{ (mod }}N)}$.

ויקטור יודע שעבור כל שלשה ${\displaystyle i}$ רק אחד משני הערכים הוא מספר ריבועי, אם ${\displaystyle \beta _{i}=0}$ הרי ש-${\displaystyle s_{i}}$ הוא מספר ריבועי מודולו ${\displaystyle N}$ ואם ${\displaystyle \beta _{i}=1}$ הרי ש-${\displaystyle ys_{i}}$ הוא מספר ריבועי מודולו ${\displaystyle N}$ אבל לא שניהם. היות שהתשובה הנכונה תלויה ב-${\displaystyle \beta _{i}}$ הרי שעבור כל שלשה יש לו סיכויים של חמישים אחוז להיכשל. למשל אם ${\displaystyle \beta _{1}=0}$ והוא נדרש להוכיח לוולרי ש-${\displaystyle ys_{1}}$ ריבועי הוא יכשל כי את המידע הזה לא קיבל מפגי והדרך היחידה שלו להצליח היא לפרק את ${\displaystyle N}$ לגורמים.

יתרה מזו, אפילו מבלי ליצור קשר עם פגי ויקטור מסוגל לייצר שלשות ערכים ${\displaystyle (s_{i},\beta _{i},z_{i})}$ שהם בלתי ניתנים להבחנה מערכים תקפים שהיו מתקבלים מפגי אילו יצר איתה קשר. הוא יכול לבצע כדלהלן כאשר הוא בוחר אתגר ${\displaystyle \beta _{i}}$ בסבב כלשהו הוא בוחר גם ${\displaystyle z}$ אקראי ומציב:

${\displaystyle s\equiv z^{2}(y^{\beta })^{-1}{\text{ (mod }}N)}$.

הביטוי המתואר מוכיח מדוע המידע מפגי אינו עוזר לוויקטור כדי להוכיח את הטענה למישהו אחר כי הוא יכול באותה מידה להכין את סט הערכים שייראו תקפים לכל צופה. וזו בדיוק הסיבה מדוע צופה מן הצד לא ישתכנע כיוון שהוא יטען שהערכים מותאמים לטובתו משום שהוא יודע מה הם האתגרים מראש. אלא אם כן יוכיח ויקטור שהוא מסוגל לענות לאתגרים "אקראיים" מבלי לטעות אפילו פעם אחת. מסיבה זו ההוכחה נקראת אינטראקטיבית משום שנכונותה תלויה גם במוודא שמכין מצידו את האתגרים האקראיים (למשל לפי הטלת מטבע) ורק הוא יודע אם האתגרים אכן אקראיים ולא נבחרו בדרך מסוימת כדי לעזור לוויקטור. אילו ויקטור היה יכול לצפות מראש איזה ערכי ${\displaystyle \beta _{i}}$ הוא יקבל מולרי אם יש בידו מספיק תגובות של פגי הוא יוכל להתאים את הערכים כך שכל התגובות יראו נכונות לעיני ולרי. היות שערכי ${\displaystyle \beta _{i}}$ אינם תלויים בוויקטור אלא בוולרי, התגובות של פגי שבידו מספקות לו מדע חסר ערך.

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

לצורך הכנה, אליס בוחרת את המודולוס ${\displaystyle \ n}$, שהוא מכפלת הראשוניים ${\displaystyle \ 173\cdot 227}$ (קטנים, רק לצורך המחשה כמובן): ${\displaystyle \ n=173\cdot 227=39271}$, בוחרת סיסמה סודית, נניח: ${\displaystyle \ x=401}$, ומחשבת את ${\displaystyle \ y}$ המשמש לאימות: ${\displaystyle \ y=401^{2}{\mbox{ mod }}39271=3717}$. את ${\displaystyle \ 3717}$ יחד עם ${\displaystyle \ 39271}$ היא רושמת אצל צד שלישי נאמן כמפתח ציבורי.

מהלכי הפרוטוקול

• אליס בוחרת מספר אקראי, נניח: ${\displaystyle \ r=386}$, ומחשבת את ${\displaystyle s}$:

${\displaystyle \ s=386^{2}{\mbox{ mod }}39271=31183}$

• אליס משדרת לבוב את ההתחייבות: ${\displaystyle 31183}$

• בוב מחזיר לאליס סיבית אתגר אחת, נניח: ${\displaystyle \ \beta =1}$

• אליס מחשבת את ערך ${\displaystyle z}$ בהתאם לסיבית האתגר:

${\displaystyle z=386\cdot 401{\mbox{ mod }}39271=36973}$

ומשדרת לבוב את המענה: ${\displaystyle 36973}$

• כעת נותר לבוב לבדוק את המענה, כיוון ש:

${\displaystyle 36973^{2}\equiv 31183\cdot 3717\,({\mbox{mod }}39271)}$

ההוכחה מתקבלת. אילו היה בוב משדר את הסיבית ${\displaystyle \ \beta =0}$, אזי המענה במהלך השני היה: ${\displaystyle \ z=386}$, ואז ${\displaystyle \ 386^{2}{\mbox{ mod }}39271=31183}$, וזהו בדיוק ערכו של ${\displaystyle \ s}$.

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

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

קישורים חיצוניים

• Handbook of Applied Cryptography
• גדי אלכסנדרוביץ', פרוטוקול פיאט-שמיר, באתר "לא מדויק", 7 באוגוסט 2007
• גדי אלכסנדרוביץ', מוכיחים את הלא נודע, באתר "לא מדויק", 21 ביולי 2007
• גדי אלכסנדרוביץ', על משת”פים ונבוטים בראש, והקשר שלהם להוכחות אפס-ידע, באתר "לא מדויק", 25 ביולי 2007

הערות שוליים

1. The knowledge complexity of interactive proof-systems
2. How to explain zero-knowledge protocols to your children
3. Manuel Blum, Paul Feldman, and Silvio Micali. Non-Interactive Zero-Knowledge and Its Applications. Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC 1988). 103–112. 1988