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

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

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

שתי התכונות הראשונות מאפיינות כל מערכת הוכחה אינטראקטיבית. מערכת המכילה את שני התכונות הללו, נקראת "הוכחת ידע". בעוד שהתכונה השלישית מייחדת מערכת של הוכחה באפס ידע.

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

$A \rarr B$ : הוכחה
$A \larr B$ : אתגר
$A \rarr B$ : מענה

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

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

תוכן עניינים

1 הוכחת אפס ידע בקריפטוגרפיה
2 עלי באבא והמערה המסתורית
3 פרוטוקול הוכחת אפס ידע הראשון
- 3.1 פרוטוקול פיאט-שמיר הבסיסי
4 דוגמה לפרוטוקול פיאט-שמיר הבסיסי
5 הוכחת אפס ידע של בעיית הצביעה של גרפים
6 מקורות

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

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

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

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

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

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

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

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

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

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

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

[עריכה] פרוטוקול הוכחת אפס ידע הראשון

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

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

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

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

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

ההסבר:

A בוחר שלם אקראי חד-פעמי $\ r$ המשמש כהתחייבות (commitment) ושולח ל-B את מסר 1 הנקרא ההוכחה. B בתורו בוחר אתגר אקראי, שהוא סיבית אחת (אפס או אחד) ושולח את מסר 2 ל-A. עם קבלת המסר, A מחשב את $\ y$ ומחזיר את מסר 3 המכונה המענה או התגובה ל-B. אם $\ e = 0$ המענה יהיה $\ y = r$ אם $\ e = 1$ המענה יהיה $\ r \cdot s \mbox{ mod } n$ . המוודא B בודק את המענה עם קבלתו, תחילה כי אינו שווה 0 כדי לשלול מצב ש- $\ 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$ .

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

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

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

מהלכי הפרוטוקול:
A בוחר שלם אקראי (חד פעמי), נניח: $\ r = 386$ ומחשב את ההוכחה $\ x$ :

$\ x = 386^ {2} \mbox{ mod } 39271 = 31183$

A משדר ל-B את ההוכחה: $\ 31183$

B מחזיר ל-A סיבית אתגר אחת, נניח: $\ e = 1$

A מחשב את ערך $\ y$ בהתאם לסיבית האתגר:

$\ y = 386 \cdot 401 \mbox{ mod } 39271 = 36973$

ומשדר ל-B את המענה: $\ 36973$

כעת נותר ל-B לבדוק את המענה, כיוון ש:

$\ 36973^2 \equiv 31183 \cdot 3717 \, (\mbox{mod }39271)$

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

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

[עריכה] הוכחת אפס ידע של בעיית הצביעה של גרפים

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

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

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

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

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

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

נמחיש זאת: אם בסיבוב הראשון ביקש המוודא את צמתים A,B וראה שהם צבועים בכחול ואדום, ובסיבוב השני ביקש את הצמתים A,C וראה שהם שוב צבועים בכחול ואדום, אין זה אומר ש-B ו-C צבועים בצביעה המקורית באותו הצבע.