הרעיון של שימוש בהוכחת אפס ידיעה בקריפטוגרפיה הוא לאלץ הגינות ללא חשיפת פרטיות. הרעיון נובע ממושג שטבע מיכאל רבין, שהמחיש זאת במשל הבא: כיצד יחלקו שני ילדים עוגה בחלוקה הוגנת, אם הם אינם סומכים זה על זה? תשובה: הם יכולים לבצע זאת באמצעות פרוטוקול פשוט ויעיל, הנקרא "Cut and Choose", כדלהלן: מסכמים מראש שילד א' יפרוס את העוגה לשני חלקים שווים וילד ב' יקבל את הזכות לבחור לעצמו את חלקו תחילה. זה עובד, משום שילד א' חייב להיות הוגן בפריסת העוגה, כיוון שההחלטה איזה חלק ייפול בחלקו היא בידי ילד ב'. הוכחה באפס ידיעה מסתמכת על עקרון ההגינות, הנובע מפרוטוקול אינטראקטיבי, שבו הצד המוכיח מוכרח לפעול בהגינות, אם ברצונו לשכנע את הצד המוודא באמיתות הטענה. הפרוטוקול מבטיח, כי אם ההוכחה בוצעה כראוי לפי הוראות הפרוטוקול, המוודא יכול להשתכנע באמיתות הטענה. אם המוכיח אינו פועל בהגינות, הפרוטוקול יסתיים ב"כישלון" במובן זה, שהמוודא יחשוף את הרמאות.
הוכחה באפס ידיעה שימושית במערכת אימות זהויות, שבה צד אחד (הלקוח) מנסה להוכיח את זהותו לצד אחר (השרת), באמצעות הוכחת ידיעת סוד (הסיסמה, במקרה זה). הלקוח מספק לשרת מה שקרוי התחייבות אקראית כלשהי, השרת מציב בפני הלקוח אתגר בהתאם והלקוח משיב לאתגר באופן שמחייב את ידיעת הסיסמה. השרת מסוגל לאמת את ההוכחה מבלי צורך לחשוף את הסיסמה עצמה. גורם זר המצותת לערוץ התקשורת בין השרת ללקוח, לא יוכל ללמוד את הסיסמה מחילופי הדברים ביניהם, כיוון שהסיסמה לא שודרה כלל. דרישת אפס הידיעה הכרחית כאן, שאם לא כן, המאמת או המצותת יוכלו לנצל את הפרוטוקול כדי להשיג מהמוכיח מידע, שלא התכוון לחשוף. עם זאת, תכונת אפס ידיעה לבדה אינה מבטיחה שהפרוטוקול יהיה בטוח מבחינה קריפטוגרפית, אם תהיה דרך קלה לחשוף את סודו של המוכיח גם ללא מידע ממנו. פרוטוקול אפס ידיעה קריפטוגרפי מבוסס על בעיה מתמטית קשה, דוגמת הפירוק לגורמים, באופן שללא מידע מהמוכיח, גילוי סודו יהיה שקול לפתרון הבעיה המתמטית האמורה.
המבנה הבסיסי של פרוטוקול הוכחת אפס ידיעה מורכב משלושה מהלכים:
במהלך הראשון, המוכיח משדר התחייבות אקראית התלויה בסודו.במהלך השני, מחזיר המוודא אתגר אקראי.במהלך השלישי והאחרון, המוכיח משיב על האתגר בהתאם, כאשר תגובת המוכיח אינה חושפת מאומה אודות סודו. המוודא מסוגל לאמת את נכונות הטענה על סמך ההתחייבות שקיבל קודם והמענה לאתגר.
פרוטוקול הוכחת אפס ידיעה קריפטוגרפי.
עדי שמיר (מכון ויצמן) ועמוס פיאט (כיום באוניברסיטת ת"א), הניחו ב-1986 את היסודות למימוש רעיון אפס-ידיעה מבחינה פרקטית בפרוטוקול הנקרא פרוטוקול פיאט-שמיר (Fiat-Shamir) – הפרוטוקול האינטראקטיבי מבוסס אפס-ידיעה הראשון. הפרוטוקול נשען על בעיית שורש ריבועי מודולו שלם פריק; בעיה, השקולה לבעיית פירוק לגורמים. חשוב לציין, שפרוטוקול זה אינו יעיל מעשית, מאחר שבכל סבב מועברת סיבית אתגר אחת בלבד, והוא מוצג כאן להמחשה בלבד. פרוטוקול פייגה-פיאט-שמיר (Feige-Fiat-Shamir) הוא הרחבה של פרוטוקול זה, שפועל על מחרוזת סיביות אתגר בו-זמנית, ועל כן יעיל יותר. כמו כן, קיים פרוטוקול אימות שנור של קלאוס שנור (C.P. Schnorr), המיישם הוכחת אפס ידיעה ומבוסס על בעיית לוגריתם דיסקרטי.
פרוטוקול פיאט-שמיר.
בפרוטוקול משתתפים פגי (המוכיחה) וויקטור (המוודא). פגי בוחרת בסוד שני ראשוניים אקראיים formula_6 ו-formula_7 ומפרסמת את המכפלה שלהם formula_8. המשימה של פגי היא להוכיח לוויקטור ששלם מסוים formula_9 הוא מספר ריבועי מודולו formula_10 מבלי לחשוף בפניו כל מידע שיעזור לו להוכיח לאחרים ש-formula_9 ריבועי מודולו formula_10. יש לזכור שהוצאת שורש ריבועי מודולו שלם פריק formula_10 היא בעיה מתמטית קשה. אך כיוון שפגי יודעת מהם הגורמים הראשוניים של formula_10 והוצאת שורש ריבועי מודולו מספר ראשוני קלה, ביכולתה למצוא בקלות שורש ריבועי מודולרי של כל שלם מודולו formula_10 על ידי משפט השאריות הסיני, נניח שקיים formula_16 המקיים:
ואת זה מעוניינת פגי להוכיח לוויקטור מבלי לחשוף את formula_16 (במקרה זה formula_16 הוא הסיסמה הסודית של פגי). היא מוכיחה זאת באמצעות פרוטוקול המבוצע בכמה סבבים של חילופי מסרים שבסופם ויקטור יקבל או לא יקבל את טענתה. בכל סבב מתבצעים המהלכים הבאים:
פגי וויקטור חוזרים על התהליך המתואר formula_20 פעמים עם formula_20 אתגרים אקראיים שונים כאשר formula_20 גדול מספיק (כגון formula_23). אם תגובתה של פגי בכל הסבבים מניחה את דעתו של ויקטור הוא יכול לקבל את ההוכחה שאכן formula_9 הוא מספר ריבועי (כלומר שיש לו שורש ריבועי) מודולו formula_10 אחרת הוא דוחה אותה כטענה שקרית כי לא סביר שתצליח להוליכו שולל בכל הפעמים. קל להיווכח בשלמות ונאותות הפרוטוקול כנדרש. כי הרי אם formula_9 הוא שורש ריבועי מודולו formula_10 אז formula_28 ששלחה פגי לוויקטור מקיים formula_29 לכן:
לכן ויקטור יכול לקבל את טענתה.
במקרה ההפוך, אם formula_9 אינו ריבועי מודולו formula_10, אזי לא משנה איך היא בחרה את formula_33, רק אחד משני הערכים יהיה נכון. כלומר או formula_33 או formula_35 יהיו מספר ריבועי מודלו formula_10 אבל לא שניהם. כלומר לפגי יש סיכויים של 50% לשקר אם היא לא באמת יודעת מהם הגורמים הראשוניים של formula_10. מכאן נובע שהיא תכשל באתגר בודד של ויקטור במחצית הפעמים במקרה הממוצע. אם האתגרים הם רצף סיביות אקראי הרי שבמחצית מן המקרים בממוצע (כאשר סיבית האתגר היא אפס) היא נדרשת להוכיח ש-formula_33 ריבועי מודולו formula_10 ומחצית מן המקרים היא נדרשת להוכיח ש-formula_35 ריבועי. כך שאם formula_9 אינו ריבועי הסיכויים שפגי תספק מענה נכון בכל formula_20 הסבבים הם formula_43 בסך הכול formula_20 פעמים או בקיצור formula_45. אם היא הצליחה לשלוח 80 תגובות נכונות לאתגרים של ויקטור הרי שהוא יכול בהחלט להיות סמוך ובטוח שאכן formula_9 הוא ריבועי מודולו formula_10 כי ההסתברות שהיא תצליח לרמותו היא formula_48 שהיא סבירות זניחה מאוד.
נותר להבין איך התגובות שקיבל מפגי אינן תורמות מאומה לידיעתו של ויקטור בנוגע לטענתה (כלומר אפס ידיעה). בניסוח אחר השאלה היא האם ויקטור יכול לעשות בהן שימוש כלשהו כדי להוכיח באותה הדרך למישהו אחר נניח ולרי, בסיכויי הצלחה גבוהים יותר מאשר אילו לא קיבל את תגובותיה של פגי, ש-formula_9 הוא מספר ריבועי מודולו formula_10. כמו שיבואר בהמשך ויקטור מסוגל עקרונית לייצר רשימה של ערכים שייראו על פניהם כמו תגובות אותנטיות של פגי ולמרות זאת אין בזה כל ערך בניסיון להוכיח לוולרי את אותה הטענה לכן, התגובות של פגי אינן תורמות מאומה לידיעתו של ויקטור משום שאם כן הרי שהוא היה יכול לבצע חיקוי מושלם שלהן בעצמו ללא עזרתה. ההוכחה התאורטית של אפס הידיעה קשורה לתורת ההסתברות ובעיקרה הטענה היא ששתי ההתפלגויות זהות.
להמחשת הרעיון. לאחר שוויקטור סיים את תהליך ההוכחה עם פגי נותרו בידו formula_20 שלשות ערכים formula_52 כשכל אחד מהם מקיים:
ויקטור יודע שעבור כל שלשה formula_54 רק אחד משני הערכים הוא מספר ריבועי, אם formula_55 הרי ש-formula_56 הוא מספר ריבועי מודולו formula_10 ואם formula_58 הרי ש-formula_59 הוא מספר ריבועי מודולו formula_10 אבל לא שניהם. היות שהתשובה הנכונה תלויה ב-formula_61 הרי שעבור כל שלשה יש לו סיכויים של חמישים אחוז להיכשל. למשל אם formula_62 והוא נדרש להוכיח לוולרי ש-formula_63 ריבועי הוא יכשל כי את המידע הזה לא קיבל מפגי והדרך היחידה שלו להצליח היא לפרק את formula_10 לגורמים.
יתרה מזו, אפילו מבלי ליצור קשר עם פגי ויקטור מסוגל לייצר שלשות ערכים formula_65 שהם בלתי ניתנים להבחנה מערכים תקפים שהיו מתקבלים מפגי אילו יצר איתה קשר. הוא יכול לבצע כדלהלן כאשר הוא בוחר אתגר formula_61 בסבב כלשהו הוא בוחר גם formula_28 אקראי ומציב:
הביטוי המתואר מוכיח מדוע המידע מפגי אינו עוזר לוויקטור כדי להוכיח את הטענה למישהו אחר כי הוא יכול באותה מידה להכין את סט הערכים שייראו תקפים לכל צופה. וזו בדיוק הסיבה מדוע צופה מן הצד לא ישתכנע כיוון שהוא יטען שהערכים מותאמים לטובתו משום שהוא יודע מה הם האתגרים מראש. אלא אם כן יוכיח ויקטור שהוא מסוגל לענות לאתגרים "אקראיים" מבלי לטעות אפילו פעם אחת. מסיבה זו ההוכחה נקראת אינטראקטיבית משום שנכונותה תלויה גם במוודא שמכין מצידו את האתגרים האקראיים (למשל לפי הטלת מטבע) ורק הוא יודע אם האתגרים אכן אקראיים ולא נבחרו בדרך מסוימת כדי לעזור לוויקטור. אילו ויקטור היה יכול לצפות מראש איזה ערכי formula_61 הוא יקבל מולרי אם יש בידו מספיק תגובות של פגי הוא יוכל להתאים את הערכים כך שכל התגובות יראו נכונות לעיני ולרי. היות שערכי formula_61 אינם תלויים בוויקטור אלא בוולרי, התגובות של פגי שבידו מספקות לו מדע חסר ערך.
דוגמה לפרוטוקול פיאט-שמיר.
לצורך הכנה, אליס בוחרת את המודולוס formula_71, שהוא מכפלת הראשוניים formula_72 (קטנים, רק לצורך המחשה כמובן): formula_73, בוחרת סיסמה סודית, נניח: formula_74, ומחשבת את formula_75 המשמש לאימות: formula_76. את formula_77 יחד עם formula_78 היא רושמת אצל צד שלישי נאמן כמפתח ציבורי.
מהלכי הפרוטוקול.
ההוכחה מתקבלת. אילו היה בוב משדר את הסיבית formula_88, אזי המענה במהלך השני היה: formula_89, ואז formula_90, וזהו בדיוק ערכו של formula_91.
הוכחת אפס ידיעה לא אינטראקטיבית.