הוכחה באפס ידיעה
הוכחת אפס ידיעה בקריפטוגרפיה > פרוטוקול הוכחת אפס ידיעה קריפטוגרפי > פרוטוקול פיאט-שמיר

בפרוטוקול משתתפים פגי (המוכיחה) וויקטור (המוודא). פגי בוחרת בסוד שני ראשוניים אקראיים  p ו- q ומפרסמת את המכפלה שלהם  N=pq. המשימה של פגי היא להוכיח לוויקטור ששלם מסוים  y הוא מספר ריבועי מודולו  N מבלי לחשוף בפניו כל מידע שיעזור לו להוכיח לאחרים ש- y ריבועי מודולו  N. יש לזכור שהוצאת שורש ריבועי מודולו שלם פריק  N היא בעיה מתמטית קשה. אך כיוון שפגי יודעת מהם הגורמים הראשוניים של  N והוצאת שורש ריבועי מודולו מספר ראשוני קלה, ביכולתה למצוא בקלות שורש ריבועי מודולרי של כל שלם מודולו  N על ידי משפט השאריות הסיני, נניח שקיים  x המקיים:
ואת זה מעוניינת פגי להוכיח לוויקטור מבלי לחשוף את  x (במקרה זה  x הוא הסיסמה הסודית של פגי). היא מוכיחה זאת באמצעות פרוטוקול המבוצע בכמה סבבים של חילופי מסרים שבסופם ויקטור יקבל או לא יקבל את טענתה. בכל סבב מתבצעים המהלכים הבאים:
פגי וויקטור חוזרים על התהליך המתואר  n פעמים עם  n אתגרים אקראיים שונים כאשר  n גדול מספיק (כגון  n=80). אם תגובתה של פגי בכל הסבבים מניחה את דעתו של ויקטור הוא יכול לקבל את ההוכחה שאכן  y הוא מספר ריבועי (כלומר שיש לו שורש ריבועי) מודולו  N אחרת הוא דוחה אותה כטענה שקרית כי לא סביר שתצליח להוליכו שולל בכל הפעמים. קל להיווכח בשלמות ונאותות הפרוטוקול כנדרש. כי הרי אם  y הוא שורש ריבועי מודולו  N אז  z ששלחה פגי לוויקטור מקיים  z\equiv x^{\beta }r{\text{ (mod }}N) לכן:
לכן ויקטור יכול לקבל את טענתה.
במקרה ההפוך, אם  y אינו ריבועי מודולו  N, אזי לא משנה איך היא בחרה את  s, רק אחד משני הערכים יהיה נכון. כלומר או  s או  ys יהיו מספר ריבועי מודלו  N אבל לא שניהם. כלומר לפגי יש סיכויים של 50% לשקר אם היא לא באמת יודעת מהם הגורמים הראשוניים של  N. מכאן נובע שהיא תכשל באתגר בודד של ויקטור במחצית הפעמים במקרה הממוצע. אם האתגרים הם רצף סיביות אקראי הרי שבמחצית מן המקרים בממוצע (כאשר סיבית האתגר היא אפס) היא נדרשת להוכיח ש- s ריבועי מודולו  N ומחצית מן המקרים היא נדרשת להוכיח ש- ys ריבועי. כך שאם  y אינו ריבועי הסיכויים שפגי תספק מענה נכון בכל  n הסבבים הם  \textstyle {\frac {1}{2}}\cdot {\frac {1}{2}}\cdot {\frac {1}{2}}\cdots  בסך הכול  n פעמים או בקיצור  2^{-n}. אם היא הצליחה לשלוח 80 תגובות נכונות לאתגרים של ויקטור הרי שהוא יכול בהחלט להיות סמוך ובטוח שאכן  y הוא ריבועי מודולו  N כי ההסתברות שהיא תצליח לרמותו היא  2^{-80} שהיא סבירות זניחה מאוד.
נותר להבין איך התגובות שקיבל מפגי אינן תורמות מאומה לידיעתו של ויקטור בנוגע לטענתה (כלומר אפס ידיעה). בניסוח אחר השאלה היא האם ויקטור יכול לעשות בהן שימוש כלשהו כדי להוכיח באותה הדרך למישהו אחר נניח ולרי, בסיכויי הצלחה גבוהים יותר מאשר אילו לא קיבל את תגובותיה של פגי, ש- y הוא מספר ריבועי מודולו  N. כמו שיבואר בהמשך ויקטור מסוגל עקרונית לייצר רשימה של ערכים שייראו על פניהם כמו תגובות אותנטיות של פגי ולמרות זאת אין בזה כל ערך בניסיון להוכיח לוולרי את אותה הטענה לכן, התגובות של פגי אינן תורמות מאומה לידיעתו של ויקטור משום שאם כן הרי שהוא היה יכול לבצע חיקוי מושלם שלהן בעצמו ללא עזרתה. ההוכחה התאורטית של אפס הידיעה קשורה לתורת ההסתברות ובעיקרה הטענה היא ששתי ההתפלגויות זהות.
להמחשת הרעיון. לאחר שוויקטור סיים את תהליך ההוכחה עם פגי נותרו בידו  n שלשות ערכים  (s_{1},\beta _{1},z_{1}),(s_{2},\beta _{2},z_{2}),...,(s_{n},\beta _{n},z_{n}) כשכל אחד מהם מקיים:
ויקטור יודע שעבור כל שלשה  i רק אחד משני הערכים הוא מספר ריבועי, אם  \beta _{i}=0 הרי ש- s_{i} הוא מספר ריבועי מודולו  N ואם  \beta _{i}=1 הרי ש- ys_{i} הוא מספר ריבועי מודולו  N אבל לא שניהם. היות שהתשובה הנכונה תלויה ב- \beta _{i} הרי שעבור כל שלשה יש לו סיכויים של חמישים אחוז להיכשל. למשל אם  \beta _{1}=0 והוא נדרש להוכיח לוולרי ש- ys_{1} ריבועי הוא יכשל כי את המידע הזה לא קיבל מפגי והדרך היחידה שלו להצליח היא לפרק את  N לגורמים.
יתרה מזו, אפילו מבלי ליצור קשר עם פגי ויקטור מסוגל לייצר שלשות ערכים  (s_{i},\beta _{i},z_{i}) שהם בלתי ניתנים להבחנה מערכים תקפים שהיו מתקבלים מפגי אילו יצר איתה קשר. הוא יכול לבצע כדלהלן כאשר הוא בוחר אתגר  \beta _{i} בסבב כלשהו הוא בוחר גם  z אקראי ומציב:
הביטוי המתואר מוכיח מדוע המידע מפגי אינו עוזר לוויקטור כדי להוכיח את הטענה למישהו אחר כי הוא יכול באותה מידה להכין את סט הערכים שייראו תקפים לכל צופה. וזו בדיוק הסיבה מדוע צופה מן הצד לא ישתכנע כיוון שהוא יטען שהערכים מותאמים לטובתו משום שהוא יודע מה הם האתגרים מראש. אלא אם כן יוכיח ויקטור שהוא מסוגל לענות לאתגרים "אקראיים" מבלי לטעות אפילו פעם אחת. מסיבה זו ההוכחה נקראת אינטראקטיבית משום שנכונותה תלויה גם במוודא שמכין מצידו את האתגרים האקראיים (למשל לפי הטלת מטבע) ורק הוא יודע אם האתגרים אכן אקראיים ולא נבחרו בדרך מסוימת כדי לעזור לוויקטור. אילו ויקטור היה יכול לצפות מראש איזה ערכי  \beta _{i} הוא יקבל מולרי אם יש בידו מספיק תגובות של פגי הוא יוכל להתאים את הערכים כך שכל התגובות יראו נכונות לעיני ולרי. היות שערכי  \beta _{i} אינם תלויים בוויקטור אלא בוולרי, התגובות של פגי שבידו מספקות לו מדע חסר ערך.