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

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

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

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

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

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

היסטוריה

רעיון אפס ידיעה נהגה לראשונה ב-1985 על ידי שפי גולדווסר (המכון הטכנולוגי של מסצ'וסטס, מכון ויצמן למדע), סילביו מיקאלי (המכון הטכנולוגי של מסצ'וסטס), וצ'ארלס ראקוף (אוניברסיטת טורונטו). הם תיארו במאמר "The knowledge complexity of interactive proof-systems"^[1] את הרעיון של הוכחת טענה מתמטית באופן אינטראקטיבי (interactive proof-system) ואת הרעיון שניתן לבצע הוכחה כזו ללא חשיפת מידע נוסף (Zero-knowledge proof). הם טבעו את המונח סיבוכיות ידיעה, והציעו מספר מדדים לכמות המידע העובר בהוכחה אינטראקטיבית. הם אף הביאו דוגמה מעשית ראשונה של הוכחת אפס ידיעה: שמספר שלם אינו שארית ריבועית מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} , תוך חשיפת אפס מידע בנוגע למספר עצמו, בהתבסס על העובדה שלא קיים אלגוריתם יעיל לבדיקת שארית ריבועית, אם לא נתונים הגורמים הראשוניים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} . על תרומתם זו זכו בפרס גדל.

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

דוגמאות

צביעות גרף

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

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

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

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

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

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

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

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

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

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

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

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

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

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \rarr B} : התחייבות (commitment)

$A\leftarrow B$ : אתגר (challenge)

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \rarr B} : מענה (response)

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

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

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

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

בפרוטוקול משתתפים פגי (המוכיחה) וויקטור (המוודא). פגי בוחרת בסוד שני ראשוניים אקראיים $p$ ו- $q$ ומפרסמת את המכפלה שלהם $N=pq$ . המשימה של פגי היא להוכיח לוויקטור ששלם מסוים $y$ הוא מספר ריבועי מודולו $N$ מבלי לחשוף בפניו כל מידע שיעזור לו להוכיח לאחרים ש- $y$ ריבועי מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} . יש לזכור שהוצאת שורש ריבועי מודולו שלם פריק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} היא בעיה מתמטית קשה. אך כיוון שפגי יודעת מהם הגורמים הראשוניים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} והוצאת שורש ריבועי מודולו מספר ראשוני קלה, ביכולתה למצוא בקלות שורש ריבועי מודולרי של כל שלם מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} על ידי משפט השאריות הסיני, נניח שקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} המקיים:

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

.

ואת זה מעוניינת פגי להוכיח לוויקטור מבלי לחשוף את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} (במקרה זה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} הוא הסיסמה הסודית של פגי). היא מוכיחה זאת באמצעות פרוטוקול המבוצע בכמה סבבים של חילופי מסרים שבסופם ויקטור יקבל או לא יקבל את טענתה. בכל סבב מתבצעים המהלכים הבאים:

1. פגי בוחרת שלם אקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} . ומחשבת ושולחת לוויקטור את השלם $s\equiv r^{2}{\text{ (mod }}N)$ שנקרא התחייבות. 2. ויקטור בוחר אתגר אקראי שהוא סיבית אחת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta\in\{0,1\}} ושולח לפגי את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} . 3. פגי מחשבת ושולחת לוויקטור את המענה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z=x^{\beta}r\text{ (mod }N)} שפירושו שאם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta=0} היא מחזירה לוויקטור רק את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} , אחרת היא מחזירה את $xr{\text{ (mod }}N)$ , בניסוח אחר: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z \equiv \begin{cases} r\text{ (mod }N), & \mbox{if }\beta=0 \\ xr\text{ (mod }N), & \mbox{if }\beta=1 \end{cases}} . אפשר לראות ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} לא נחשף לעיניו של ויקטור כי הוכפל בשלם האקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} שזהו מעין פנקס חד פעמי. 4. ויקטור בודק שמתקיים $z^{2}\equiv y^{\beta }s{\text{ (mod }}N)$ כלומר אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta=0} אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} הוא שורש ריבועי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} , אחרת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} הוא שורש ריבועי של $ys$ , בניסוח אחר: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z^2 \equiv \begin{cases} s\text{ (mod }N), & \mbox{if }\beta=0 \\ ys\text{ (mod }N), & \mbox{if }\beta=1 \end{cases}} . אם תנאי זה מתקיים ויקטור מקבל את טענתה של פגי ביחס לאתגר אחד, אחרת הוא דוחה אותה.

פגי וויקטור חוזרים על התהליך המתואר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} פעמים עם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} אתגרים אקראיים שונים כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} גדול מספיק (כגון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=80} ). אם תגובתה של פגי בכל הסבבים מניחה את דעתו של ויקטור הוא יכול לקבל את ההוכחה שאכן $y$ הוא מספר ריבועי (כלומר שיש לו שורש ריבועי) מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} אחרת הוא דוחה אותה כטענה שקרית כי לא סביר שתצליח להוליכו שולל בכל הפעמים. קל להיווכח בשלמות ונאותות הפרוטוקול כנדרש. כי הרי אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} הוא שורש ריבועי מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} ששלחה פגי לוויקטור מקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z\equiv x^{\beta}r\text{ (mod }N) } לכן:

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

.

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

במקרה ההפוך, אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} אינו ריבועי מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} , אזי לא משנה איך היא בחרה את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} , רק אחד משני הערכים יהיה נכון. כלומר או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle ys} יהיו מספר ריבועי מודלו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} אבל לא שניהם. כלומר לפגי יש סיכויים של 50% לשקר אם היא לא באמת יודעת מהם הגורמים הראשוניים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} . מכאן נובע שהיא תכשל באתגר בודד של ויקטור במחצית הפעמים במקרה הממוצע. אם האתגרים הם רצף סיביות אקראי הרי שבמחצית מן המקרים בממוצע (כאשר סיבית האתגר היא אפס) היא נדרשת להוכיח ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} ריבועי מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} ומחצית מן המקרים היא נדרשת להוכיח ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle ys} ריבועי. כך שאם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} אינו ריבועי הסיכויים שפגי תספק מענה נכון בכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} הסבבים הם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \frac{1}{2}\cdot \frac{1}{2}\cdot \frac{1}{2}\cdots} בסך הכול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} פעמים או בקיצור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{-n}} . אם היא הצליחה לשלוח 80 תגובות נכונות לאתגרים של ויקטור הרי שהוא יכול בהחלט להיות סמוך ובטוח שאכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} הוא ריבועי מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} כי ההסתברות שהיא תצליח לרמותו היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{-80}} שהיא סבירות זניחה מאוד.

נותר להבין איך התגובות שקיבל מפגי אינן תורמות מאומה לידיעתו של ויקטור בנוגע לטענתה (כלומר אפס ידיעה). בניסוח אחר השאלה היא האם ויקטור יכול לעשות בהן שימוש כלשהו כדי להוכיח באותה הדרך למישהו אחר נניח ולרי, בסיכויי הצלחה גבוהים יותר מאשר אילו לא קיבל את תגובותיה של פגי, ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} הוא מספר ריבועי מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} . כמו שיבואר בהמשך ויקטור מסוגל עקרונית לייצר רשימה של ערכים שייראו על פניהם כמו תגובות אותנטיות של פגי ולמרות זאת אין בזה כל ערך בניסיון להוכיח לוולרי את אותה הטענה לכן, התגובות של פגי אינן תורמות מאומה לידיעתו של ויקטור משום שאם כן הרי שהוא היה יכול לבצע חיקוי מושלם שלהן בעצמו ללא עזרתה. ההוכחה התאורטית של אפס הידיעה קשורה לתורת ההסתברות ובעיקרה הטענה היא ששתי ההתפלגויות זהות.

להמחשת הרעיון. לאחר שוויקטור סיים את תהליך ההוכחה עם פגי נותרו בידו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} שלשות ערכים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (s_1,\beta_1,z_1), (s_2,\beta_2,z_2),..., (s_n,\beta_n,z_n)} כשכל אחד מהם מקיים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_i^2\equiv y^{\beta_i}s_i\text{ (mod }N)} .

ויקטור יודע שעבור כל שלשה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} רק אחד משני הערכים הוא מספר ריבועי, אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta_i=0} הרי ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i} הוא מספר ריבועי מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} ואם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta_i=1} הרי ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle ys_i} הוא מספר ריבועי מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} אבל לא שניהם. היות שהתשובה הנכונה תלויה ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta_i} הרי שעבור כל שלשה יש לו סיכויים של חמישים אחוז להיכשל. למשל אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta_1=0} והוא נדרש להוכיח לוולרי ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle ys_1} ריבועי הוא יכשל כי את המידע הזה לא קיבל מפגי והדרך היחידה שלו להצליח היא לפרק את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} לגורמים.

יתרה מזו, אפילו מבלי ליצור קשר עם פגי ויקטור מסוגל לייצר שלשות ערכים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (s_i,\beta_i,z_i)} שהם בלתי ניתנים להבחנה מערכים תקפים שהיו מתקבלים מפגי אילו יצר איתה קשר. הוא יכול לבצע כדלהלן כאשר הוא בוחר אתגר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta_i} בסבב כלשהו הוא בוחר גם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} אקראי ומציב:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s\equiv z^2(y^{\beta})^{-1}\text{ (mod }N)} .

הביטוי המתואר מוכיח מדוע המידע מפגי אינו עוזר לוויקטור כדי להוכיח את הטענה למישהו אחר כי הוא יכול באותה מידה להכין את סט הערכים שייראו תקפים לכל צופה. וזו בדיוק הסיבה מדוע צופה מן הצד לא ישתכנע כיוון שהוא יטען שהערכים מותאמים לטובתו משום שהוא יודע מה הם האתגרים מראש. אלא אם כן יוכיח ויקטור שהוא מסוגל לענות לאתגרים "אקראיים" מבלי לטעות אפילו פעם אחת. מסיבה זו ההוכחה נקראת אינטראקטיבית משום שנכונותה תלויה גם במוודא שמכין מצידו את האתגרים האקראיים (למשל לפי הטלת מטבע) ורק הוא יודע אם האתגרים אכן אקראיים ולא נבחרו בדרך מסוימת כדי לעזור לוויקטור. אילו ויקטור היה יכול לצפות מראש איזה ערכי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta_i} הוא יקבל מולרי אם יש בידו מספיק תגובות של פגי הוא יוכל להתאים את הערכים כך שכל התגובות יראו נכונות לעיני ולרי. היות שערכי $\beta _{i}$ אינם תלויים בוויקטור אלא בוולרי, התגובות של פגי שבידו מספקות לו מדע חסר ערך.

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

לצורך הכנה, אליס בוחרת את המודולוס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} , שהוא מכפלת הראשוניים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 173 \cdot 227} (קטנים, רק לצורך המחשה כמובן): הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n = 173 \cdot 227 = 39271} , בוחרת סיסמה סודית, נניח: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x = 401} , ומחשבת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y} המשמש לאימות: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ y = 401^ {2} \mbox{ mod } 39271 = 3717} . את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 3717} יחד עם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 39271} היא רושמת אצל צד שלישי נאמן כמפתח ציבורי.

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

אליס בוחרת מספר אקראי, נניח: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r = 386} , ומחשבת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} :

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s = 386^ {2} \mbox{ mod } 39271 = 31183}

אליס משדרת לבוב את ההתחייבות: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 31183}

בוב מחזיר לאליס סיבית אתגר אחת, נניח: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \beta = 1}

אליס מחשבת את ערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} בהתאם לסיבית האתגר:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z = 386 \cdot 401 \mbox{ mod } 39271 = 36973}

ומשדרת לבוב את המענה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 36973}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 36973^2 \equiv 31183 \cdot 3717 \, (\mbox{mod }39271)}

ההוכחה מתקבלת. אילו היה בוב משדר את הסיבית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \beta = 0} , אזי המענה במהלך השני היה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ z = 386} , ואז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 386^2 \mbox{ mod } 39271 = 31183} , וזהו בדיוק ערכו של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} .

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

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

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

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

הערות שוליים

^ The knowledge complexity of interactive proof-systems
^ How to explain zero-knowledge protocols to your children
^ 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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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

[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

[1]

[2]

[3]