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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

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

היסטוריה[עריכת קוד מקור | עריכה]

רעיון אפס ידע נהגה לראשונה ב-1985 על ידי שפרירה גולדווסר (המכון הטכנולוגי של מסצ'וסטס, מכון ויצמן למדע), סילביו מיקאלי (המכון הטכנולוגי של מסצ'וסטס), וצ'ארלס ראקוף (אוניברסיטת טורונטו). הם תיארו במאמר "The knowledge complexity of interactive proof-systems"‏[1] את הרעיון של הוכחת טענה מתמטית באופן אינטראקטיבי (interactive proof-system) ואת הרעיון שניתן לבצע הוכחה כזו ללא חשיפת מידע נוסף (Zero-knowledge proof). הם טבעו את המונח סיבוכיות ידע שהוא מדד כמות המידע העובר בהוכחה אינטראקטיבית. הם הביאו אף דוגמה מעשית ראשונה של הוכחת אפס מידע: שמספר שלם אינו שארית ריבועית מודולו m תוך חשיפת אפס מידע בנוגע למספר עצמו, בהתבסס על העובדה שלא קיים אלגוריתם יעיל לבדיקת שארית ריבועית אם לא נתונים הגורמים הראשוניים של m. על תרומתם זו זכו בפרס גדל.

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

דוגמאות[עריכת קוד מקור | עריכה]

צביעות גרף[עריכת קוד מקור | עריכה]

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

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

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

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

עלי באבא והמערה המסתורית[עריכת קוד מקור | עריכה]

ZK cave.jpg

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

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

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

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

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

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

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

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

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

  1. A \rarr B : הוכחה (witness)
  2. A \larr B : אתגר (challenge)
  3. A \rarr B : מענה (response)

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

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

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

פרוטוקול פיאט-שמיר הבסיסי[עריכת קוד מקור | עריכה]

תחילה מכינים שלם \ n שהוא כפולה של שני מספרים ראשוניים גדולים, שווים בגודלם בקירוב. המשתתפת אליס בוחרת לעצמה סוד \ s כלשהו הנמוך מ-\ n. ומחשבת את: \ v = s^{\,2} \mbox{ mod } n, מספר זה יחד עם המודולוס \ n ישמשו להוכחה ויהיו פומביים. כמובן שיש להבטיח שייכותם לאליס בדרך מוסכמת.

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

  1. A \rarr B: \ x = r^ {2} \mbox{ mod } n
  2. A \larr B: \ e \in \{0,1\}
  3. A \rarr B: \ y = rs^ e \mbox{ mod } n

ההסבר: אליס בוחרת שלם אקראי חד-פעמי \ r המשמש כהתחייבות ושולחת לבוב את מסר 1 הנקרא הוכחה. עם קבלת ההוכחה בוב בוחר אתגר אקראי, במקרה זה סיבית אחת (0 או 1) ושולח לאליס את מסר 2. עם קבלת המסר מחשבת אליס את \ y ומחזירה לבוב את מסר 3 הנקרא מענה. אם \ e=0 המענה יהיה \ y=r אם \ e=1 המענה יהיה \ rs\mbox{ mod }n. בוב בודק את המענה עם קבלתו, תחילה כי אינו שווה אפס כדי לשלול מצב ש-\ r=0. לאחר מכן, בודק אם השקילות \ y^2\equiv x \cdot v^e \ (\mbox{mod }n) מתקיימת, אם כן הוא מקבל את ההוכחה אם לא הוא דוחה את ההוכחה. אפשר לראות שמ-\ v = s^2\mbox{ mod }n נובע כי \ y^2=x או \ y^2=x\cdot v\mbox{ mod }n בהתאם לערכו של \ e.

אליס נדרשת בעצם להוכיח כי היא מסוגלת לענות על שתי שאלות, האחת הוכחת ידיעת סודה \ s והשנייה שאלה קלה (למוכיח הגון) כדי למנוע רמאות. במקרה של סיבית אתגר 0 התשובה תהיה \ y=r. אולם במקרה ש-\ e= 1 זו תהיה שאלה קשה אם אליס מתחזה והיא אינה יודעת את \ s. מאידך, מתחזה יכול לנסות לרמות על ידי בחירת: \ x=r^2/v כך שהתשובה עבור סיבית אתגר \ 1 תהיה קלה והיא \ y=r. אולם אז יתקשה לענות במקרה של סיבית אתגר אפס, משום שעליו לחשב את השורש הריבועי של \ x מודולו \ n. מכאן נובע שסיכוייו לרמות בניסוי אחד הם חמישים אחוז. בהגדרה הבסיסית הפרוטוקול אמור להתבצע \ t פעמים (כאשר \ t = 40 לפחות) כדי להגיע למרווח ביטחון רצוי.

הפרוטוקול המתואר מקיים את תכונת אפס ידע הנדרשת כיוון שהמענה \ y=r אינו תלוי בסוד \ s, בעוד שהמענה \ y=r\cdot s\mbox{ mod }n, למרות שלכאורה תלוי ב-\ s, אינו מספק מידע אודותיו בשל האקראיות של \ r. הסוד \ s יכול היה להיות כל ערך אחר במידה שווה. יתרה מזו, הערכים \ x,y שחשפה אליס בתגובתה, ניתנים בקלות להדמיה על ידי כל גורם אחר כולל בוב עצמו. על פניהם, ערכים אלו לא יהיו שונים במאומה מערכי \ x,y האמיתיים שחושבו על ידי אליס בהתבסס על סודה.

דוגמה לפרוטוקול פיאט-שמיר[עריכת קוד מקור | עריכה]

לצורך הכנה אליס בוחרת את המודולוס \ n, שהוא מכפלת הראשוניים \ 173 \cdot 227 (קטנים, רק לצורך המחשה כמובן): \ n = 173 \cdot 227 = 39271 וכן בוחרת סיסמה סודית, נניח: \ s = 401, ומחשבת את \ v המשמש לאימות: \ v = 401^ {2} \mbox{ mod } 39271 = 3717, את \ 3717 יחד עם \ 39271 היא רושמת אצל צד שלישי נאמן כמפתח ציבורי.

מהלכי הפרוטוקול:
אליס בוחר מספר אקראי, נניח: \ r = 386 ומחשבת את ההוכחה \ x:

\ x = 386^ {2} \mbox{ mod } 39271 = 31183
  • אליס משדרת לבוב את ההוכחה: \ 31183
  • בוב מחזיר לאליס סיבית אתגר אחת, נניח: \ e = 1
  • אליס מחשבת את ערך \ y בהתאם לסיבית האתגר:
\ y = 386 \cdot 401 \mbox{ mod } 39271 = 36973

ומשדרת לבוב את המענה: \ 36973

  • כעת נותר לבוב לבדוק את המענה, כיוון ש:
\ 36973^2 \equiv 31183 \cdot 3717 \, (\mbox{mod }39271)

ההוכחה מתקבלת.

אילו היה בוב משדר את הסיבית \ e = 0 אזי המענה במהלך השני היה: \ y = 386, ואז \ 386^2 \mbox{ mod } 39271 = 31183 וזהו בדיוק ערכו של \ x.

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

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]