שורש, ההוכחה (חלק ב’)

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

הבסיס של הוכחת אפס הידע הוא במספר גדול \( n \) שהוא מכפלה של שני מספרים ראשוניים גדולים. המושג “גדול” אינו מוגדר היטב, ותלוי בכוח החישוב הנוכחי של מחשבים, אבל בימינו פירוש הדבר מספר בן כמה מאות ספרות (400? 600?). הרעיון העקרוני שעומד מאחורי זה הוא שקל לייצג מספרים גדולים ולעבוד איתם (בניסוח נאיבי, צריך רק “400 בייטים” כדי לייצג מספר בן 400 ספרות, והרי בזכרונות המחשב של ימינו זוהי כמות זניחה ביותר. בפועל, צריך הרבה פחות מ-400 בייטים), אבל לא קשה לנסח בעיות שהקושי שלהן תלוי בגודל המספר (ערכו המספרי), ולא בגודל הייצוג שלו (מספר הבייטים שנדרשים לצורך כתיבתו). כדי להבין את ההבדל אעיר שמספר האטומים ביקום מוערך כמספר שאינו גדול מגוגול (\( 10^{100} \), ובמילים אחרות - 1 עם מאה אפסים אחריו) וגוגול הוא יצור פיצי ומסכן לעומת מספר בן 400 ספרות.

הנה המחשה לבעייתיות שבדבר: בדיקת ראשוניות. הדרך שבה יוצרים את \( n \) היא על ידי הגרלה של שני ראשוניים גדולים (אם אנחנו רוצים ש-\( n \) יהיה בגודל 600 ספרות, נגריל ראשוניים בני 300 ספרות) והכפלתם (פעולה שכאמור - קל לבצע גם עבור מספרים גדולים שכאלו, בגלל שגודל הייצוג שלהם סביר). הבעיה היא רק כיצד להגריל שני ראשוניים דווקא, הרי ראשוניים הם לא מספרים נפוצים עד כדי כך.

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

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

אם כן, ייצרנו שני מספרים ראשוניים גדולים \( p,q \) כפלנו אותם וקיבלנו \( n=pq \). כעת זורקים את הראשוניים לכל הרוחות (אם מישהו ידע מה הם, הוא ידע את הפירוק של \( n \) ולכן יוכל להוציא שורש מודולו \( n \) והמערכת חסרת ערך) ומפרסמים את \( n \) לכל דורש. כעת המערכת מסוגלת להתחיל לתפקד.

אני, בתור המוכיח, רוצה להראות למערכת שאני מכיר שורש של מספר כלשהו. אם כן, אני בוחר באקראי מספר מודולו \( n \) שנכנה \( x \) (צריך לוודא גם שהוא זר ל-\( n \) כדי שיהיה איבר בחבורה הכפלית - אבל הסיכוי שניפול על איבר שאינו זר שווה לסיכוי שנצליח לפרק את \( n \) לגורמים “בטעות” - למה?), מעלה אותו בריבוע מודולו \( n \) ומקבל מספר חדש, \( y=x^2(mod n) \). מן הסתם אני צריך לבחור את \( y \) כך שהריבוע שלו יהיה גדול מ-\( n \), אחרת יהיה קל להוציא ל-\( x \) שורש (למה?)

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

ההוכחה הטריוויאלית של “שלח את \( x \), תן למוודא להעלות אותו בריבוע ולוודא שהוא קיבל \( y \)” לא טוב לנו מכיוון שכך \( x \) נחשף לכל מי שרוצה לצותת. ה”תיקון” שיש לבצע להוכחה הנאיבית אינו גדול, במפתיע; מה שנעשה יהיה לכפול את \( x \) במספר אקראי כלשהו, ואז לשלוח את המכפלה. מכיוון שכפלנו את \( x \) במספר אקראי ואנחנו עובדים בחבורה הכפלית מודולו \( n \) (ולכן כל מספר מודולו \( n \) ששייך לחבורה הזו הוא תוצאה אפשרית של המכפלה, תלוי מה המספר האקראי) הרי שאין במכפלה הזו שום מידע על זהותו של \( x \).

אם כן, נסכם: אנו מגרילים \( r \) אקראי מודלו \( n \), ושולחים למוודא את \( xr \). כיצד המוודא יכול לוודא שאנחנו יודעים את שורש \( y \)? אם הוא יעלה את המספר ששלחנו לו בריבוע הוא יקבל את \( (xr)^2=x^2r^2=yr^2 \), ולכן הוא צריך מידע נוסף - מהו \( r^2 \). אם כן, נשלח לו גם את המספר הזה (בלי חשש שאפשר יהיה לגלות ממנו את \( r \), שהרי הוצאת שורש היא קשה), וכעת המוודא אכן יכול לוודא שהכל בסדר: ש-\( y \) כפול המספר השני ששלחנו לו שווה למספר הראשון בריבוע. עשינו זאת מבלי לחשוף שום מידע על \( x \) (שלחנו רק מספרים שנראים אקראיים) ולכן תם ונשלם הפרוטוקול.

האמנם?

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

אנחנו יודעים שהמוודא מצפה לקבל שני מספרים \( a,b \) (בכוונה עברתי לאותיות אחרות) כך שמתקיים \( yb=a^2 \). במילים אחרות, הוא מצפה שיתקיים \( b=\frac{a^2}{y} \). קשה לנו להוציא שורש, אולם לחלק קל, ולכן מה שנעשה יהיה להגריל את \( a \) (שכזכור, אם היינו מוכיחים “הגונים” היה המספר \( xr \), שאינו “סתם” אקראי אלא מהווה פונקציה של \( x \)), להעלות אותו בריבוע, לחלק ב-\( y \) ולחשב ממנו את \( b \) (שכזכור, אם היינו הגונים היה בכלל \( r^2 \)). הצלחנו לענות בכך על כל הדרישות של המוודא, ועם זאת אין לנו שמץ של מושג מה השורש של \( y \). בעיה.

הפתרון הוא הוספת שאלה נוספת למוודא: אם שלחנו לו \( a,b \), הוא יכול לתפוס את הרמאות הזו על ידי דרישת השורש של \( b \). אם היינו הגונים, אז \( b=r^2 \) ולכן כל מה שצריך הוא לשלוח את \( r \); אם רימינו ולא יצרנו את \( b \) על ידי העלאה בריבוע של מספר אקראי אלא על ידי חישוב מהסוג שהוצג לעיל - אז אין סיכוי שנדע את השורש של \( b \) (אם היינו יודעים, היינו יכולים לדעת גם את \( x \) - למה?).

מה הבעיה עכשיו? איבדנו את אפס הידע. מדוע? מכיוון שאם אנחנו הוגנים, ושלחנו למוודא את \( r^2, xr \) ועכשיו הוא דרש מאיתנו גם את \( r \), הרי שהוא מסוגל לחלק את \( xr \) ב-\( r \) ולקבל את \( x \) ישירות - וכך גם כל מי שמצותת לרשת.

הפתרון הוא לבצע פשרה. האבחנה היא שאת \( r^2 \) תמיד אפשר לשלוח, אבל שתי פיסות המידע האחרות, \( r \) ו-\( xr \) לא מתיישבות זו עם זו, ושתיהן גם ממלאות פונקציות שונות: \( xr \) מראה למוודא שאנחנו אכן יודעים את \( x \), ואילו \( r \) מראה למוודא שאנחנו הגונים ובאמת יצרנו את ה-\( b \) באופן אקראי. לכן, מספיק לבחון כל אחת משתי פיסות המידע הללו לסירוגין.

הנה הפרוטוקול השלם והאמיתי: הפרוטוקול שלנו יחולק לסיבובים. בכל סיבוב, המוכיח יגריל \( r \) אקראי וישלח למוודא את \( r^2 \). בשלב הזה המוודא יבצע “הטלת מטבע” ועל פיה יודיע למוכיח אם הוא רוצה לקבל את \( xr \) או את \( r \). אם הוא ביקש את \( xr \), הוא מעלה בריבוע את מה שקיבל, מחלק במספר הראשון שקיבל ובודק אם יצא \( y \). אם הוא ביקש את \( r \), הוא מעלה בריבוע את מה שקיבל ובודק האם זה שווה למספר הראשון שקיבל. אם הבדיקה נכשלה, הוא יודע שהמוכיח שקרן ומעיף אותו. אחרת, ממשיכים לסיבוב הבא.

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

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

נשאר רק מה שהבטחתי קודם - השיפור של פייגה. כאמור, לסוגייה הטכנית אני לא הולך להיכנס אלא רק להפיכה שלו את הפרוטוקול למה שמכונה Proof of Knowledge. כפי שהוא כרגע, הפרוטוקול כן מעביר למוודא מידע כלשהו - הוא אומר לו של-\( y \) יש שורש מודולו \( n \) (דבר שאינו נכון בהכרח לכל המספרים מודולו \( n \)). לכאורה זה לא בעייתי כי ממילא ההנחה המוקדמת של כל הפרוטוקול היא שקיים למספר הזה שורש (אחרת איך אפשר להוכיח שיודעים את השורש שלו?).

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

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