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

מתוך ויקיפדיה, האנציקלופדיה החופשית
(הופנה מהדף הוכחה באפס ידע)
קפיצה אל: ניווט, חיפוש

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

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

  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 : התחייבות (commitment)
  2. A \larr B : אתגר (challenge)
  3. A \rarr B : מענה (response)

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

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

פרופסור עדי שמיר (מכון ויצמן) ועמוס פיאט (כיום באוניברסיטת ת"א), הניחו ב-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 שחשפה אליס בתגובתה, ניתנים בקלות להדמיה על ידי כל גורם אחר כולל בוב עצמו. רמאי שמנסה להתחזות לאליס (ואליס עצמה) לא יוכלו להעתיק את ההוכחה ולהשתמש בה במועד מאוחר יותר, כיוון שהיא תלויה בערכו של e וזה האחרון תלוי במוודא והוא כאמור ישתכנע רק אם הוא עצמו בחר את e (באקראי).

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

לצורך הכנה אליס בוחרת את המודולוס \ 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) בין המוכיח והמאמת, מספקת ליצירת הוכחת אפס ידיעה חישובית ללא צורך באינטראקציה כלשהי.

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

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