הוכחה באפס ידיעה – הבדלי גרסאות

במקרה ההפוך, אם <math>y</math> אינו ריבועי מודולו <math>N</math>, אזי לא משנה איך היא בחרה את <math>s</math>, רק אחד משני הערכים יהיה נכון. כלומר או <math>s</math> או <math>ys</math> יהיו מספר ריבועי מודלו <math>N</math> אבל לא שניהם. כלומר לפגי יש סיכויים של 50% לשקר אם היא לא באמת יודעת מהם הגורמים הראשוניים של <math>N</math>. מכאן נובע שהיא תכשל באתגר בודד של ויקטור במחצית הפעמים במקרה הממוצע, כיוון שאם האתגרים הם רצף סיביות אקראיות הרי שבמחצית מן המקרים בממוצע (כאשר סיבית האתגר היא אפס) היא נדרשת להוכיח ש-<math>s</math> ריבועי מודולו <math>N</math> ומחצית מן המקרים היא נדרשת להוכיח ש-<math>ys</math> ריבועי. כך שאם <math>y</math> אינו ריבועי הסיכויים שפגי תספק מענה נכון בכל <math>n</math> הסבבים הם <math>2^{-n}</math>. אם היא הצליחה לשלוח 80 תגובות נכונות לאתגרים של ויקטור הרי שהוא יכול בהחלט להיות סמוך ובטוח שאכן <math>y</math> הוא ריבועי מודולו <math>N</math> כי ההסתברות שהיא תצליח לרמותו היא <math>2^{-80}</math> שהיא סבירות זניחה מאוד במונחים של ימינו.

 

 

:<math>z_i^2\equiv y^{\beta_i}s_i\text{ (mod }N)</math>.

ויקטור יודע שעבור כל שלשה <math>i</math> רק אחד משני הערכים הוא מספר ריבועי, אם <math>\beta_i=0</math> הרי ש-<math>s_i</math> הוא מספר ריבועי מודולו <math>N</math> ואם <math>\beta_i=1</math> הרי ש-<math>ys_i</math> הוא מספר ריבועי מודולו <math>N</math> אבל לא שניהם. היות שהתשובה הנכונה תלויה ב-<math>\beta_i</math> הרי שעבור כל שלשה יש לו סיכויים של חמישים אחוז להיכשל במענה האם <math>s_i</math> הוא מספר ריבועי. ערכי <math>\beta</math> אינם תלויים בויקטור אלא במוודא, במקרה זה ולרי. לכן הערכים שבידו מספקים לו מדע חסר ערך.

יתרה מזו, אפילו מבלי ליצור קשר עם פגי ויקטור מסוגל לייצר שלשות ערכים <math>(s_i,\beta_i,z_i)</math> שהם בלתי ניתנים להבחנה מערכים תקפים שהיו מתקבלים מפגי אילו יצר איתה קשר. הוא יכול לבצע כדלהלן כאשר הוא בוחר אתגר <math>\beta_i</math> בסבב כלשהו הוא בוחר גם <math>z</math> אקראי ומציב:

:<math>s\equiv z^2(y^{\beta})^{-1}\text{ (mod }N)</math>.