הוכחה באפס ידיעה (Zero-knowledge proof) היא פרוטוקול אינטראקטיבי שבו צד אחד (המוכיח) משכנע צד שני (המוודא) שטענה מסוימת נכונה,
מבלי לחשוף מידע נוסף על הטענה או על הסוד שמאחוריה. השימוש המעשי הבולט הוא באימות זהויות: ניתן להוכיח ידיעת סיסמה מבלי לתת את הסיסמה.
פרוטוקול אפס ידיעה צריך לקיים שלוש תכונות עיקריות:
- שלמות (Completeness): אם הטענה נכונה והמוכיח והמוודא פועלים כראוי, המוודא יתקבל על דעתו בסבירות גבוהה.
- נאותות (Soundness): אם הטענה שקרית, רמאי לא יצליח לשכנע מוודא הגון, שוב בהסתברות גבוהה.
- אפס ידיעה (Zero knowledge): המוודא לא לומד דבר פרט לכך שהטענה נכונה. ניתן להסביר זאת בכך שמישהו אחר יכול להדמות (לחקות) את ההוכחה בלי לדעת את הסוד.
קיימות שלוש רמות של אפס ידיעה: מושלמת (לא עובר שום מידע), סטטיסטית (הפרשי התפלגות קטנים) וחישובית (צד בעל יכולת חישוב סבירה לא יזהה הבדל).
הרעיון הוצג לראשונה ב-1985 על ידי שפי גולדווסר, סילביו מיקאלי וצ'ארלס ראקוף.
הם הראו שאפשר לבצע הוכחות אינטראקטיביות בלי לחשוף מידע נוסף, והציגו מדדים לכמות המידע שעוברת בפרוטוקול.
דוגמה אינטואיטיבית היא הוכחה שגרף ניתן לצביעה בשלושה צבעים (3-צביע).
המוכיח יודע צביעה סודית של כל הקודקודים. בכל סבב הוא משנה את הצבעים באקראי, "מכסה" את הצביעה ושולח למוודא מידע מוגבל על שני קודקודים בלבד.
המוודא בודק שצמד קודקודים שמחוברים אכן בצבעים שונים. חזרה על התהליך מספר פעמים משכנעת את המוודא, מבלי שהוא ילמד את הצביעה המלאה.
המשל המפורסם מדגים את הרעיון: אדם יודע מילת קסם לפתיחת דלת חשאית במערה.
כדי להוכיח זאת בלי לומר את המילה, הוא נכנס למערה והשומר דורש ממנו לצאת מצד ימין או שמאל אקראי.
אם האדם יודע את המילה, יוכל תמיד לציית. חזרה על הבדיקה מספקת ביטחון שבאמת הוא יודע את המילה.
דוגמאות חופשיות יותר ממחישות כיצד אפשר להוכיח מציאת דמות בהדפסה או חישוב מסוים, מבלי לחשוף את המיקום המדויק או את השיטה.
ברמה הפרקטית משתמשים בהוכחות אלה לאימות זהות ולמניעת חשיפת סיסמאות. המבנה הבסיסי כולל שלושה מהלכים:
1) התחייבות (commitment), המוכיח שולח התחייבות אקראית התלויה בסודו.
2) אתגר (challenge), המוודא בוחר אתגר אקראי ושולח אותו.
3) מענה (response), המוכיח משיב בהתאם, כך שהמוודא יכול לבדוק נכונות בלי ללמוד את הסוד.
חשוב: אפס הידיעה צריכה להשתלב בבעיות מתמטיות קשות (כמו פירוק לגורמים) כדי שהסוד לא יהיה ניתן לחשיפה על ידי חישוב ישיר.
פרוטוקול פיאט-שמיר, שהוצע ב-1986, הוא דוגמה אינטראקטיבית קלאסית המבוססת על קושי מתמטי (שורש ריבועי מודולו מספר פריק).
ברמת הרעיון המוכיח יודע סוד שקושר למפתח ציבורי. בכל סבב הוא שולח התחייבות אקראית, המוודא בוחר אתגר אקראי (סיבית), והמוכיח מחזיר מענה שמאמת את ידיעת הסוד אך לא חושף אותו. חזרה על התהליך פעמים רבות מפחיתה את הסיכוי שהמוכיח מרמה.
אפשר גם לבנות הוכחות לא אינטראקטיביות, שבהן אין צורך בתקשורת חוזרת, אם יש מחרוזת סמך משותפת (CRS) או שימוש בתמצית גיבוב.
הוכחות כאלה שימושיות בחתימות דיגיטליות ובמטבעות פרטיות; למשל zkSNARKs משמשות בפרויקטים כמו Zcash.
=מה זה?
הוכחה באפס ידיעה היא דרך לשכנע מישהו שמשהו נכון מבלי לספר את הסוד.
לדוגמה: להראות שיודעים סיסמה בלי לומר אותה.
=רעיון פשוט עם סיפור המערה
אדם יודע מילת קסם לפתיחת דלת במערה.
השומר מבקש ממנו לצאת מצד ימין או שמאל בטעות.
אם האדם יודע את המילה, תמיד יכול לצאת כפי שהתבקש.
חזרה על הבדיקה מעלה את הביטחון שהוא באמת יודע את המילה.
=דוגמאות קצרות
- בסיפור "איפה אפי?" המוכיח מראה רק שהמצא מצוי בלי לחשוף היכן בדיוק.
- בספירת עלים, המוכיח מראה שהוא יודע את המספר על ידי הדגמה אחרי שהוצאו עלים.
=איך זה קשור למחשבים?
הצורה הזו שימושית באבטחה ובאימות זהות.
אפשר להוכיח שמישהו יודע סיסמה בלי לתת אותה. כך גורם רע בחיבור לא ילמד את הסיסמה.
=לא אינטראקטיבי ויישומים
יש גם גרסאות בלי שיחה בין הצדדים.
טכניקות כאלה משמשות בחתימות דיגיטליות ומטבעות פרטיים כמו Zcash.
תגובות גולשים