הוכחה באפס ידע
מתוך ויקיפדיה, האנציקלופדיה החופשית
הוכחה באפס ידע, כשמה היא מערכת הוכחה אינטראקטיבית, שבה המוכיח מסוגל לשכנע את המוודא בנכונותו של משפט או לשכנעו בידיעת סוד כלשהו בסבירות מכרעת (לא באופן מוחלט), מבלי לחשוף שום מידע אודות המשפט או הסוד עצמו, שאי אפשר היה להשיג באמצעים אחרים, מלבד הוכחת עצם קיומו. הוכחה באפס ידע היא סוג של הוכחת אתגר-מענה (Challenge-Response), בה המוכיח והמוודא משתתפים בפרוטוקול, המורכב ממספר "מהלכים" או "חילופי-מסרים". כשבסיומם, המוודא משוכנע בסבירות מכרעת באמיתות טענת המוכיח.
הוכחה באפס ידע חייבת להכיל את שלושת המאפיינים הבאים:
- שלמות (Completeness). פרוטוקול הוכחה אינטראקטיבי נקרא "שלם" אם בהינתן מוכיח ומאמת הגונים, הפרוטוקול יסתיים בהצלחה בסבירות מכרעת, בכך שהמאמת מקבל את טענת המוכיח. ההגדרה של סבירות מכרעת היא כי קיים סיכוי אפסי לכישלון מבחינה מעשית.
- נאותות (Soundness). פרוטוקול הוכחה אינטראקטיבי נקרא "נאות" אם בהינתן מוכיח רמאי המנסה להתחזות למוכיח אמיתי, המאמת יצליח לזהות את הרמאות בהסתברות גבוהה מאוד. במילים אחרות נאותות מבטיחה כי הפרוטוקול אכן מספק הוכחת הטענה או ידיעת הסוד וכן מבטיחה כי מוכיח שאינו הגון לא יוכל לשכנע מאמת הגון באמיתות טענה שקרית או בידיעת סוד שאינו ידוע לו.
- אפס ידע (Zero knowledge). לפרוטוקול הוכחה אינטראקטיבי תהיה תכונת "אפס ידע" אך ורק אם הפרוטוקול ניתן להדמיה, במובן זה שלא ניתן יהיה להבחין בין עותק מדומה של מהלכי הפרוטוקול לבין מהלכים אמיתיים שבוצעו עם מוכיח אמיתי. מתכונה זו נובע כי פרוטוקול אפס ידע אינו מספק שום רמז לגבי סודו של המוכיח, מלבד עצם הוכחת קיומו, אפילו אם התבצע מול מאמת זדוני.
שתי התכונות הראשונות מאפיינות כל מערכת הוכחה אינטראקטיבית. מערכת המכילה את שני התכונות הללו, נקראת "הוכחת ידע". בעוד שהתכונה השלישית מייחדת מערכת של הוכחה באפס ידע.
המבנה הבסיסי של הוכחת אפס ידע מורכב משלושה מהלכים:
-
: הוכחה
: אתגר
: מענה
במהלך הראשון משדר המוכיח למוודא הוכחה או התחייבות כלשהי התלויה בסודו. במהלך השני מחזיר המוודא אתגר כלשהו המסתמך על ההתחייבות שניתנה קודם ובמהלך האחרון המוכיח משיב על האתגר בהתאם. כאשר תגובת המוכיח אינה חושפת מאומה אודות סודו. המוודא מסוגל לאמת את נכונות הטענה על סמך ההתחייבות והמענה שקיבל.
הוכחת אפס ידע אינה נחשבת להוכחה מתמטית במובן הרגיל שלה. בשל היותה הסתברותית מטבעה, הצד המוכיח משכנע את הצד המוודא באמיתות הטענה רק בהסתברות גבוהה. תיאורטית קיים מצב, גם אם קלוש ביותר, כי המוכיח ישכנע את המוודא באמיתות טענה שקרית. יש להבחין בין הוכחת אפס ידע מושלמת לבין הוכחת אפס ידע חישובית, האחרונה אומרת כי צד-שלישי המוגבל ליכולת חישוב פולינומאלית בזמן ובמקום, לא יוכל לזהות הבדל כלשהו בין פרוטוקול אמיתי לבין עותק מדומה. במילים אחרות, לא יוכל לחלץ מידע אפילו זעום ביותר אודות סודו של המוכיח, תוך שימוש בכח חישוב מוגבל.
תוכן עניינים |
[עריכה] הוכחת אפס ידע בקריפטוגרפיה
כדי שפרוטוקול הוכחת אפס ידע יהיה בטוח מבחינה קריפטוגרפית, אין די בתכונות האמורות. הן אינן מספקות בהכרח הוכחה לבטיחות הפרוטוקול. פרוטוקול הוכחת אפס-ידע קריפטוגרפי מתבסס על בעיה מתמטית ידועה, הנחשבת כקשה מאוד לפתרון מבחינה חישובית. ומערב שימוש בסודו של המוכיח שבעזרתו מסוגל להשיב על האתגר. במקרה שהמוכיח אינו הגון ואינו יודע את הסוד, לא יוכל להשיב נכונה אלא אם כן יהיה מסוגל לפתור את הבעיה המתמטית האמורה. דוגמה לבעיה כזו היא בעיית פירוק לגורמים.
אפשר ליישם הוכחת אפס ידע לצורך אימות זהויות. מערכת שבה מנסה צד אחד (לקוח) להוכיח את זהותו כלפי צד אחר (השרת) שנקרא כאן המאמת. המוכיח משכנע את המאמת בידיעת סוד הידוע רק לו (הסיסמה) במתן מענה נכון לשאלות או אתגרים שמציב בפניו המאמת (המערבים שימוש במידע ציבורי אודות המוכיח ובפונקציות מוסכמות), אשר נדרשת ידיעת הסיסמה על מנת להשיב עליהן נכונה. כל זאת מבלי לחשוף את הסיסמה עצמה.
[עריכה] עלי באבא והמערה המסתורית
במאמר איך להסביר לילדך את פרוטוקול אפס-ידע, המחישו המתמטיקאים ג'וליו וקוויזקווטר באופן ציורי את הרעיון אפס-ידע, בסיפור עלי-באבא והמערה המסתורית. הרעיון הוא כדלהלן: מערה מסתורית (ראה תרשים) מכילה כניסה אחת המתפצלת לשני מבואות אחד לימין ואחד לשמאל, שבסופם מגיעים למבוי סתום.
אולם ישנה מילת קסם סודית, שאם נאמרת נפתחת דלת סתרים המקשרת בין המעברים, מלת-קסם זו ידועה לראובן ורק הוא מסוגל להיכנס למערה בדרך אחת ולשוב לפתחה בדרך השנייה. כיצד יוכל לשכנע את שמעון שהוא יודע את מילת-הקסם לפתיחת הדלת המסתורית, מבלי שיאלץ לחשוף אותה בפניו?. הנה רעיון. שמעון ימתין בפתח המערה כאשר ראובן נכנס ובוחר בדרך אחת, לאחר מכן יתייצב שמעון בנקודת ההתפצלות ויכריז בקול "ימין" או "שמאל" לפי הטלת מטבע למשל. ובהתאם להכרזתו צריך ראובן לצאת מן המערה. והיה אם ראובן הצליח לצאת בדרך הנכונה משמע כי הוא יודע את הסוד, כי הרי ראובן אינו יודע מראש מה תהיה תוצאת הטלת המטבע או מה תהיה הכרזתו של שמעון.
מה סיכוייו של ראובן לרמות? ובכן בניסוי בודד סיכוייו הם חמישים אחוז. מצד אחד, כיוון ששמעון לא ראה באיזו דרך בחר ראובן להיכנס למערה, ייתכן כי ראובן אינו מכיר כל מילת-קסם, אלא פשוט במקרה נכנס בדיוק בדרך בה התבקש לצאת. מאידך אם שמעון הכריז "ימין" וראובן נכנס בדרך שמאל, ראובן ייכשל.
חשבון פשוט מלמד כי אם חוזרים על הניסוי מספר פעמים, מקטינים את סיכוייו של ראובן לרמות באופן משמעותי. לאחר מספר גדול של ניסויים סיכוייו קטנים כל כך, עד כי ששמעון יכול להיות משוכנע מעל לכל ספק, כי ראובן דובר אמת והוא אכן יודע את מילת הקסם.
המשל האמור אינו מושלם, משום ששמעון יכול היה ללוות את ראובן עד נקודת ההתפצלות כדי לוודא במו עיניו, כי ראובן נכנס בדרך אחת ויוצא בשנייה ובזה תמה ההוכחה. אולם אם לצורך המשל נתעלם מפרט זה, הרי שהמשל מסביר היטב את מושג אפס-ידע. ראובן הוכיח לשמעון ידיעת סוד כלשהו מבלי צורך לחשוף את הסוד עצמו.
יתרה מזו, אילו שמעון היה מסריט את כל המבחנים שעשה עם ראובן. האם יוכל שמעון לשכנע את לוי בעזרת הסרט, באמיתות ההוכחה? או האם יוכל שמעון לעשות שימוש בתהליך ההוכחה הזה, בניסיון להתחזות לראובן בעצמו ולשכנע את לוי כביכול הוא יודע את סודו של ראובן? מסתבר שלא. משום שמתוך התבוננות בסרט בלבד, אין לוי יכול להיות משוכנע מעל לכל ספק כי ראובן ושמעון לא תיאמו ביניהם מראש (כגון, אם החליטו על סדר ההכרזות של שמעון) כדי לרמותו. או שמא שמעון ערך את הסרט והשמיט ממנו את כל המקרים בהם ראובן נכשל.
זוהי תכונה יסודית של פרוטוקול אפס ידע, לא ניתן לעשות שימוש חוזר בהוכחה שניתנה בעבר. מאחר והוכחת אפס-ידע הנה אינטראקטיבית במהותה, תקפות ההוכחה תלויה בשני הצדדים. פרופסור מיכאל רבין העלה לראשונה את הרעיון cut-and-choose הממחיש פרוטוקול אינטראקטיבי. כאשר שני ילדים רוצים לחלוק ביניהם עוגה חלוקה הוגנת, אם הם אינם סומכים זה על זה כלל, כיצד יעשו זאת? מי יפרוס את העוגה? ובכן הם יכולים להחליט על פרוטוקול חלוקה הוגנת כדלהלן. ילד א' יפרוס את העוגה לשני חלקים שווים ואילו ילד ב' ייטול את חלקו תחילה והנותר יהיה לילד א'. באופן זה מובטח כי החלוקה תהיה הוגנת, מאחר ופורס העוגה מתוך אינטרס אישי ברור מחויב לבצע את תפקידו באופן הוגן, אחרת הוא יפסיד. פרוטוקול הוכחת אפס-ידע עושה שימוש ברעיון זה. אם המשתתפים הגונים קרי, פעלו לפי הפרוטוקול, הפרוטוקול יסתיים בהצלחה במובן שהמוודא מקבל את טענת המוכיח. לעומת זאת, אם אחד מהמשתתפים אינו הגון, כלומר המוכיח או המוודא הנו מתחזה או רמאי, הפרוטוקול יסתיים בכישלון במובן זה שהרמאי ייחשף.
[עריכה] פרוטוקול הוכחת אפס ידע הראשון
פרופסור עדי שמיר (מכון ויצמן) ועמוס פיאט, הניחו ב-1986 את היסודות למימוש רעיון אפס-ידע מבחינה פרקטית. בפרוטוקול הנקרא פרוטוקול פיאט-שמיר (Fiat-Shamir), הפרוטוקול האינטראקטיבי מבוסס אפס-ידע הראשון. הפרוטוקול נשען על בעיית שורש-ריבועי מודולו שלם פריק, בעיה השקולה כידוע לבעיית פירוק לגורמים. חשוב לציין כי פרוטוקול זה אינו יעיל מעשית, מאחר ובכל סבב מועברת סיבית אתגר אחת בלבד. פרוטוקול זה מוצג כאן רק לצורך המחשה, ישנם פרוטוקולים יעילים יותר המעבירים יותר מסיבית אתגר אחת בכל סבב. כמו הפרוטוקול המורחב, פייגה-פיאט-שמיר (Feige-Fiat-Shamir) של עדי שמיר, עמוס פיאט ואוריאל פייגה העושה שימוש בהוכחה מרובה ובמחרוזת אתגרים בו-זמנית. או פרוטוקול שנור (Schnorr) המבוסס על בעיית לוגריתם דיסקרטי.
[עריכה] פרוטוקול פיאט-שמיר הבסיסי
תחילה מכינים שלם
שהוא כפולה של שני מספרים ראשוניים גדולים שווים בגודלם בקירוב. המשתתף A בוחר לעצמו סוד
כלשהו הנמוך מ-
. ומחשב את:
, מספר זה יחד עם המודולוס
ישמשו להוכחה ויהיו פומביים. כמובן שיש להפעיל שיטת אימות כלשהי המבטיחה את שייכותם למשתמש A.
מהלכי הפרוטוקול:
: 
: 
: 
ההסבר:
A בוחר שלם אקראי חד-פעמי
המשמש כהתחייבות (commitment) ושולח ל-B את מסר 1 הנקרא ההוכחה. B בתורו בוחר אתגר אקראי, שהוא סיבית אחת (אפס או אחד) ושולח את מסר 2 ל-A. עם קבלת המסר, A מחשב את
ומחזיר את מסר 3 המכונה המענה או התגובה ל-B. אם
המענה יהיה
אם
המענה יהיה
. המוודא B בודק את המענה עם קבלתו, תחילה כי אינו שווה 0 כדי לשלול מצב ש-
. לאחר מכן, בודק אם השוויון
מתקיים, אם כן הוא מקבל את ההוכחה אם לא הוא דוחה את ההוכחה. אפשר לראות שמ-
נובע כי
או
בהתאם לערכו של
.
הסבר: כאן, A נדרש בעצם להוכיח כי הוא מסוגל לענות על שתי שאלות, האחת ידיעת הסוד
והשנייה שאלה קלה (למוכיח הגון) כדי למנוע רמאות. במקרה של סיבית אתגר 0 התשובה תהיה קלה והיא
. אולם במקרה ש-
זו תהיה שאלה קשה עבור מתחזה שאינו יודע את s. מאידך, מתחזה יכול לנסות לרמות על ידי בחירת:
כך שהתשובה עבור סיבית אתגר 1 תהיה קלה והיא
. אולם אז יתקשה לענות במקרה של סיבית אתגר 0, משום שעליו לחשב את השורש הריבועי של
מודולו
. מכאן נובע, כיוון שהמתחזה אינו יודע מראש מה תהיה סיבית האתגר, סיכוייו בניסוי אחד הם
. בהגדרה הבסיסית הפרוטוקול אמור להתבצע
פעמים (
) כדי להגיע למרווח בטחון רצוי.
המענה
אינו תלוי ב-
, בעוד שהמענה
, למרות שתלוי בסוד
, אינו מספק מידע אודותיו בשל האקראיות של
. הסוד
יכול היה להיות כל ערך אחר באותה מידה. יתרה מזו, הערכים
שחשף A בתגובתו, ניתנים בקלות להדמיה על ידי כל גורם אחר כולל המאמת B כאמור לעיל. על פניהם, ערכים אלו לא יהיו שונים במאומה מערכי
האמיתיים שחושבו על ידי A עצמו בהתבסס על סודו.
[עריכה] דוגמה לפרוטוקול פיאט-שמיר הבסיסי
לצורך הכנה A בוחר מודולוס
, שהוא מכפלת הראשוניים
(קטנים, רק לצורך המחשה כמובן):
וכן בוחר סיסמה סודית, נניח:
, ומחשב את
המשמש לאימות:
, את
יחד עם
רושם A אצל צד שלישי נאמן כמפתח ציבורי.
מהלכי הפרוטוקול:
A בוחר שלם אקראי (חד פעמי), נניח:
ומחשב את ההוכחה
:
A משדר ל-B את ההוכחה: 
B מחזיר ל-A סיבית אתגר אחת, נניח: 
A מחשב את ערך
בהתאם לסיבית האתגר:
ומשדר ל-B את המענה: 
כעת נותר ל-B לבדוק את המענה, כיוון ש:
ההוכחה מתקבלת.
אילו היה B משדר את סיבית האתגר
אזי המענה במהלך השני היה:
, ואז
וזהו בדיוק ערכו של
.




