שיחה:הוכחה באפס ידיעה
שתי הערות על פסקת העלי באבא[עריכת קוד מקור]
ראשית, מה פירוש "ובכן בניסוי בודד, סיכוייו שואפים לחצי"? מה משמעות המילה "שאיפה" אם מתבצע ניסוי בודד בלבד? יש לנסח מחדש.
שנית, עד כמה שאני רואה בערך האנגלי, ועד כמה שאני מבין הוכחות אינטראקטיביות באופן כללי, איש אינו מצפה מהמוכיח להיות הגון. כל הרעיון הוא שגם אם המוכיח הוא רמאי ושקרן, ההסתברות שנאמין לו היא אפסית. לכן המשפט "רק אם המוכיח והמוודא הגונים, הפרוטוקול יצליח" וכל מה שבא לפניו אינו במקום, ואני סבור שלא את המשפט הזה ניסה פרופסור רבין להמחיש בסיפורו. גדי אלכסנדרוביץ' 22:36, 5 בספטמבר 2006 (IDT)
- הביטוי "שואפים לחצי" אינו ביטוי מתמטי. ולכן אני מקבל את הערתך. הכוונה הכללית הייתה שבניסוי בודד יש "סיכוי" של חצי. וזה יתוקן.
- שנית רעיון ההגינות לא יוחס לפרופסור רבין דוקא, זה רעיון כללי שמסביר את הוכחת אפס ידע. מספרות מקצועית שאני ראיתי עלה הביטוי הגון או ישר (Honset) כמה פעמים. לא אתנגד אם תציע ביטוי אחר שמבהיר את הרעיון בצורה טובה. הרעיון של משתתף "הגון" אינו במובן הרגיל, אלא הכוונה היא שרק אם הפרוטוקול מתבצע עם משתתפים שאינם רמאים, המוודא יקבל את הוכחת המוכיח והפרוטוקול יסתיים ב"הצלחה". אם המוודא לא הגון או המוכיח לא הגון הפרוטוקול יסתיים ב"כישלון" מהסיבות המנויות. זה בא לשלול מצב שמוכיח רמאי "יצליח" לשכנע מוודא הגון. וכן להיפך מוודא רמאי לא יכול לעשות שימוש כלשהו בפרוטוקול.
- --Yossiea 18:49, 6 בספטמבר 2006 (IDT)
- אה, אני מבין. אתה מזהה "הצלחה" עם הסיטואציה "המוכיח משכנע את המוודא", ו"כישלון" עם הסיטואציה שבה הוא לא משכנע. זה כמובן ויכוח סמנטי. בעיניי המצב שבו מוכיח שקרן מצליח לעבוד על המוודא הוא כישלון, ואילו מצב שבו מוכיח שקרן נתפס בקלקלתו הוא דווקא הצלחה. גדי אלכסנדרוביץ' 19:23, 6 בספטמבר 2006 (IDT)
- גם זה נכון. אולם הצלחה וכשלון בהקשר שלנו היא במשמעות הצלחת הפרוטוקול או יותר נכון סיום הפרוטוקול בהצלחה כל מקרה שבו הפרוטוקול לא הסתיים בהצלחה, כלומר נכשל, משמעו הצלחה במובן שהרמאי נחשף. אם אתה מבין את כוונתי. או.קיי. מנקודת ראות שלי, כאחד שכבר למד את זה. אני רואה את הדברים כברורים. אולם ייתכן שמנקודת ראות של מישהו שלא למד את הנושא, אולי צריך לחדד אותו כך: "רק אם המוכיח והמוודא הגונים הפרוטוקול יסתיים בהצלחה, אחרת הפרוטוקול יסתיים בכישלון, כלומר הרמאי ייחשף!". אולי כך העניין יובהר טוב יותר. מה דעתך? (בינתיים מחקתי את המשפט הזה).
- --Yossiea 20:53, 6 בספטמבר 2006 (IDT)
- העניין הוא שאני רגיל לחשוב על כל העסק בתור בדיקה האם מילה שייכת לשפה פורמלית כלשהי או לא, בדומה למה שמכונת טיורינג עושה. לכן אני חושב במושגים של "המוודא מקבל" או "המוודא לא מקבל", ולא במובן של "הפרוטוקול מצליח/נכשל". לכן אין פסול במה שכתבת, אבל כדאי להציג אותו בצורה ברורה יותר. גדי אלכסנדרוביץ' 21:01, 6 בספטמבר 2006 (IDT)
- ראיתי שבגרסה הקודמת של הערך הייתה התייחסות לנושא מהביט מתמטי טהור ולאו דוקא מהקשר של קריפטוגרפיה. אני מוכרח לציין שאני התוודעתי לנושא זה מהקשר של קריפטוגרפיה בלבד. כמובן שהתיאוריה של הוכחת אפס-ידע מקיפה יותר. אולם כאשר מדברים על "פרוטוקול" אפס-ידע כמעט תמיד הוא בהקשר קריפטוגרפי. תקן אותי אם אני טועה. בכל אופן אני יתקן את הניסוח מעט.
- --Yossiea 21:39, 6 בספטמבר 2006 (IDT)
- העניין הוא שאני רגיל לחשוב על כל העסק בתור בדיקה האם מילה שייכת לשפה פורמלית כלשהי או לא, בדומה למה שמכונת טיורינג עושה. לכן אני חושב במושגים של "המוודא מקבל" או "המוודא לא מקבל", ולא במובן של "הפרוטוקול מצליח/נכשל". לכן אין פסול במה שכתבת, אבל כדאי להציג אותו בצורה ברורה יותר. גדי אלכסנדרוביץ' 21:01, 6 בספטמבר 2006 (IDT)
תקינות ואיתנות - נאותות?[עריכת קוד מקור]
אני מכיר את Soundness בהקשר הזה בתור "נאותות", ממספר הקשרים שונים. האם במקומות אחרים בארץ זה אחרת? גדי אלכסנדרוביץ' 23:55, 13 בספטמבר 2006 (IDT)
- השתמשתי במילון בבילון ובעוד כמה מילונים מקוונים כדי לבדוק את המילה הזו. המילה "נאותות" לא הופיעה שם אולי "יציבות" או "תקפות" וכו'.
- העתקתי לכאן את תרגום המילה המופיע בבילון:
- Soundness
- (ש"ע) תוקף, תקפות; עומק; חוסן, יציבות; בריאות
- התרגום של מורפיקס:
- Soundness
- חֹסֶן, אֵיתָנוּת, יַצִּיבוּת; בְּרִיאוּת; תַּקִּינוּת; עֹמֶק
- יכול להיות שבהקשר הנדון אולי תרגום סימולטני מטעה, אולי הטיה של תרגום המילה למילה נאותות, אינו מדוייק מבחינה לשונית, אבל מהווה מבחינת הפרשנות שלוה הסבר טוב יותר של המושג. לא יודע. ואין לי עם זה בעיה. אם אתה חושב ככה תשנה.--Yossiea 15:45, 14 בספטמבר 2006 (IDT)
- אני נתקלתי ב"נאותות" הן בקורס בלוגיקה מתמטית והן בקורס בסיבוכיות. גם במאמר באייל הקורא על משפט גדל משתמשים במילה "נאותות".
- אני מאוד לא ממליץ להסתמך על בבילון בתור סמכות. יש לו טעויות גסות לעתים, או סתם פספוסים מביכים (כבר תיקנו את לואיס קארול?). גדי אלכסנדרוביץ' 15:51, 14 בספטמבר 2006 (IDT)
- מאמר מעניין מאוד, ממה שהספקתי לקרוא. לצערי הקישור למאמר המקורי של גדל לא תקין (שבור) על כן לא הצלחתי להשוות עם הנוסח האנגלי. על כל פנים, שם מדברים על מושג של "עקביות" של תורה. האם לדעתך זה מתקשר לרעיון אפס-ידע?. אני מנסה לחדד את הבנתי. כל הרעיון במקרה שלנו לפי מה שהבנתי הוא: היכולת והמסוגלות להוכיח אמיתות טענה בעזרת הפרוטוקול. ובצורה אחרת: קיים אלגוריתם M נניח, שאם קיים מוכיח מתחזה שמסוגל לבצע את הפרוטוקול האמור ולסיימו בהצלחה, אלגוריתם זה מאפשר חילוץ הסוד שבידיו, שלמעשה שקול לסודו של המוכיח האמיתי. במילים אחרות, כל מי שמצליח לבצע את הפרוטוקול באופן תקין מול מוודא כלשהו, יש לו הידע הדרוש כדי לחלץ את הסוד האמור. כאן הייתי אומר שהמילה "איתנות" בהחלט מתאימה, לא?. --Yossiea 18:30, 14 בספטמבר 2006 (IDT)
- באנגלית המושג שבו משתמשים גם בהקשר הזה הוא Soundness. דווקא קל לאתר את הדמיון - בשני המקרים מדובר על מערכת הוכחה - במקרה של גדל מדובר על תחשיב היחסים - והדרישה שלנו מהמערכת היא שאי אפשר יהיה "לרמות" אותנו. כלומר, אי אפשר יהיה להוכיח שמשפט הוא נכון למרות שהוא שגוי. במערכת הוכחה אינטראקטיבית מוותרים קצת ומרשים שהנאותות לא תהיה "מושלמת" אלא הסתברותית, אבל הרעיון הוא אותו רעיון. גם ה"שלמות", שהיא המרכיב השני בדרישות המערכת, היא אותה שלמות מלוגיקה וממשפטי אי השלמות של גדל. גדי אלכסנדרוביץ' 18:45, 14 בספטמבר 2006 (IDT)
- מאמר מעניין מאוד, ממה שהספקתי לקרוא. לצערי הקישור למאמר המקורי של גדל לא תקין (שבור) על כן לא הצלחתי להשוות עם הנוסח האנגלי. על כל פנים, שם מדברים על מושג של "עקביות" של תורה. האם לדעתך זה מתקשר לרעיון אפס-ידע?. אני מנסה לחדד את הבנתי. כל הרעיון במקרה שלנו לפי מה שהבנתי הוא: היכולת והמסוגלות להוכיח אמיתות טענה בעזרת הפרוטוקול. ובצורה אחרת: קיים אלגוריתם M נניח, שאם קיים מוכיח מתחזה שמסוגל לבצע את הפרוטוקול האמור ולסיימו בהצלחה, אלגוריתם זה מאפשר חילוץ הסוד שבידיו, שלמעשה שקול לסודו של המוכיח האמיתי. במילים אחרות, כל מי שמצליח לבצע את הפרוטוקול באופן תקין מול מוודא כלשהו, יש לו הידע הדרוש כדי לחלץ את הסוד האמור. כאן הייתי אומר שהמילה "איתנות" בהחלט מתאימה, לא?. --Yossiea 18:30, 14 בספטמבר 2006 (IDT)
הפתיח לא נהיר[עריכת קוד מקור]
השוו לשפות אחרות. כדאי לרשום באיזה תחום ידע עוסקים (כנראה קריפטוגרפיה) ונראה לי שהמשפט הראשון צריך להיות זה שמופיע שני. הייתי כותב כך :
- הוכחה באפס ידע בקריפטוגרפיה היא מערכת שבה המוכיח מסוגל לשכנע את המאמת בנכונותו של משפט או לשכנעו בידיעת סוד כלשהו, מבלי לחשוף שום מידע אודות המשפט או הסוד עצמו, שאי אפשר היה להשיג באמצעים אחרים, מלבד הוכחת עצם קיומו.
- בדרך זו של הוכחה אינטראקטיבית, המבוססת על אתגר-מענה (Challange-Response), המוכיח והמוודא משתתפים בפרוטוקול, המורכב ממספר "מהלכים" או "חילופי-מסרים". כשבסיומם, המוודא משוכנע בסבירות מכרעת (לא באופן מוחלט), באמיתות טענת המוכיח.
האם יש התנגדות לשינוי בניסוח? שנילי • שיחה 00:25, 14 בספטמבר 2006 (IDT)
- בבקשה. מקסימום ישנו את זה בחזרה אם יראו שזה לא עסק. גדי אלכסנדרוביץ' 08:22, 14 בספטמבר 2006 (IDT)
- האמת, הבלבול נובע מכך, שיש כאלו שמעדיפים, כמו גדי אלכסנדרוביץ' למשל, להתייחס לערך זה מנקודת ראות מתמטית טהורה ולא בהקשר קריפטוגרפי והם צודקים בעיקרון. רק שאני מכיר את הנושא רק בהקשר קריפטוגרפי. וחוץ מזה מבחינה מעשית הוכחת אפס ידע שימושית בקריפטוגרפיה בעיקר. נסיתי להשאיר בנוסח הנוכחי התייחסות להיבט המתמטי, ככל האפשר. מי שמעוניין לשנות את הנוסח מוזמן לנסות. אם זה יהיה טוב, למה לא.
- לא ברור לי למה אתה "מאשים" אותי, בפרט כשאני כלל לא חושב שצריך להתייחס לערך רק מנקודת ראות אחת. לא אני כתבתי את הפתיח, ואתה הוא זה ששינה אותו לצורתו הנוכחית. לדעתי בכלל צריך לכתוב שהוכחה באפס ידע היא מושג במדעי המחשב... שיש לו שימושים בקריפטוגרפיה, ומהווה מקרה מיוחד של מערכת הוכחה אינטראקטיבית. גדי אלכסנדרוביץ' 16:13, 14 בספטמבר 2006 (IDT)
- האמת, הבלבול נובע מכך, שיש כאלו שמעדיפים, כמו גדי אלכסנדרוביץ' למשל, להתייחס לערך זה מנקודת ראות מתמטית טהורה ולא בהקשר קריפטוגרפי והם צודקים בעיקרון. רק שאני מכיר את הנושא רק בהקשר קריפטוגרפי. וחוץ מזה מבחינה מעשית הוכחת אפס ידע שימושית בקריפטוגרפיה בעיקר. נסיתי להשאיר בנוסח הנוכחי התייחסות להיבט המתמטי, ככל האפשר. מי שמעוניין לשנות את הנוסח מוזמן לנסות. אם זה יהיה טוב, למה לא.
- זה בדיוק מה שאני אומר. אני לא "מאשים" אותך אני יודע שלא אתה כתבת את הפתיח, אני "מאשים" את העורך הקודם. אבל משיחות קודמות שלך הבנתי זאת בדיוק כך. אתה סבור שלא נכון להתייחס אל הערך הזה כאל נושא שקשור רק לקריפטוגרפיה, אלא להתייחס אליו כאל תחום במדעי מחשב (או מתמטיקה), עם שימושים מעשיים בקריפטוגרפיה. אני בהחלט מקבל את זה. נסיתי ללא הצלחה יתרה להביא לכך שהפתיח הנוכחי ישקף זאת. אולם טרם הספקתי לעבור על זה שוב. כל המעוניין להשתתף בעריכה, מוזמן לעשות זאת.
- --Yossiea 17:48, 14 בספטמבר 2006 (IDT)
משהו לא ברור[עריכת קוד מקור]
"כדי שפרוטוקול הוכחת אפס ידע יהיה בטוח מבחינה קריפטוגרפית, אין די בתכונות האמורות. הן אינן מספקות בהכרח הוכחה לבטיחות הפרוטוקול. פרוטוקול הוכחת אפס-ידע קריפטוגרפי מתבסס על בעיה מתמטית ידועה, הנחשבת כקשה מאוד לפתרון מבחינה חישובית. ומערב שימוש בסודו של המוכיח שבעזרתו מסוגל להשיב על האתגר."
לא הבנתי למה התכונות האמורות לא מספיקות, ואיך מה שנכתב בהמשך פותר את הבעיה. יש דוגמה להמחשת חוסר הבטיחות? גדי אלכסנדרוביץ' 18:34, 21 בפברואר 2007 (IST)
- כוונת הקטע להדגיש כי ההוכחה שהפרוטוקול הינו "הוכחה באפס ידע" אינה בהכרח הוכחה כי הוא בטוח מבחינה קריפטוגרפית. ביקשת דוגמא, אם למשל הבעיה המתמטית עליה מבוסס הפרוטוקול לא קשה לפתרון, אזי לא משנה אם הפרוטוקול אכן הינו הוכחה באפס ידע כיוון שמשתתף לא הגון יכול לרמות את המשתתפים האחרים על ידי פתרון הבעיה המתמטית האמורה. אפשר להסביר את זה על הדוגמה של פיאט שמיר שכידוע מבוססת על בעיית חישוב שורש ריבועי מודולו שלם פריק שקושיה שקול לבעיית פירוק לגורמים, קרי אם רמאי מסוגל לפרק לגורמים מספרים בהם משתמשים בפרוטוקול, אזי לפרוטוקול אין שום ערך קריפטוגרפי. אולם הפרוטוקול עדיין נחשב כבעל תכונות של הוכחת אפס ידע מעצם ההגדרה ואין בכך סתירה.--יוסי א. 22:13, 21 בפברואר 2007 (IST)
- ערכתי את הפסקה ואני מקווה שהעריכה מקובלת עלייך. גדי אלכסנדרוביץ' 22:25, 21 בפברואר 2007 (IST)
- מקובל מאוד ישר כח. (הוספתי מעט עריכה משלי) --יוסי א. 23:08, 21 בפברואר 2007 (IST)
- ערכתי את הפסקה ואני מקווה שהעריכה מקובלת עלייך. גדי אלכסנדרוביץ' 22:25, 21 בפברואר 2007 (IST)
תבנית עריכה[עריכת קוד מקור]
אין פסקת פתיחה מתומצת ובהירה, לא ברור באיזה תחום משתמשים בהוכחה כזו, ולאיזה צורך. ישר נכנסים לעניינים טכניים ולפירוט דרישות. ניחשתי, על סמך מעט הידע שיש לי, ולאחר קריאה מעטה, שמדובר בעניין של תקשורת בין שרתי מחשב, ורק כשפגשתי בפרק "קריפטוגרפיה" הבנתי שמדובר יותר בעניין מתמטי (למרות שיש לשער שעושים בו שימוש גם במדעי המחשב). בברכה, יוסאריאן • שיחה 22:26, 21 בפברואר 2007 (IST)
- זו דרישה קצת בעייתית, להגיד על ההתחלה לאיזה צורך משתמשים בהוכחה הזו. זה כמו לשאול לאיזה צורך משתמשים בפירוק לגורמים. על כל פנים, ערכתי את הפתיחה ואני מקווה שעכשיו מצבה משופר. גדי אלכסנדרוביץ' 22:34, 21 בפברואר 2007 (IST)
- פשוט ההגדרה נשמעת טכנית - מאפיינים נדרשים, מהלכים, שחקנים(או מוכיח ומשכנע) כולם אגב לא כחולים. במתמטיקה הדברים מוגדרים בדרך כלל ביתר פירוט. כמו כן בדרך כלל מושג מדעי מובא בהקשרו. יוסאריאן • שיחה 23:06, 21 בפברואר 2007 (IST)
- למען האמת, הקישור החשוב ביותר כן כחול - מערכת הוכחה אינטראקטיבית, שמקושר מייד על ההתחלה. מכיוון שהוכחות באפס ידע הן פשוט מקרה פרטי של מערכות הוכחה אינטראקטיביות, זה הלינק החשוב באמת. גדי אלכסנדרוביץ' 23:12, 21 בפברואר 2007 (IST)
- נו, אז מה קורה? אפשר להסיר את תבנית העריכה? אם לא, אפשר ביקורת יותר פרטנית? גדי אלכסנדרוביץ' 15:01, 23 בפברואר 2007 (IST)
- למען האמת, הקישור החשוב ביותר כן כחול - מערכת הוכחה אינטראקטיבית, שמקושר מייד על ההתחלה. מכיוון שהוכחות באפס ידע הן פשוט מקרה פרטי של מערכות הוכחה אינטראקטיביות, זה הלינק החשוב באמת. גדי אלכסנדרוביץ' 23:12, 21 בפברואר 2007 (IST)
- פשוט ההגדרה נשמעת טכנית - מאפיינים נדרשים, מהלכים, שחקנים(או מוכיח ומשכנע) כולם אגב לא כחולים. במתמטיקה הדברים מוגדרים בדרך כלל ביתר פירוט. כמו כן בדרך כלל מושג מדעי מובא בהקשרו. יוסאריאן • שיחה 23:06, 21 בפברואר 2007 (IST)
הסבר לשחזור החלקי[עריכת קוד מקור]
אני חושש שהפסקה, כפי ששונתה, הביעה נקודת מבט צרה מדי. הססמה של המוכיח אינה בהכרח הדבר היחיד שמעניין את המוודא, והוא יכול "להתעלק" על המוכיח כדי לבצע חישובים שאינו מסוגל לבצע בעצמו. למשל, מערכת "נאיבית" שבה ידוע למוכיח פירוק n=pq והוא מוכיח זאת כדי לענות על שאלות של "האם x הוא שארית ריבועית מודולו n?" אינה מערכת אפס ידע, שכן למרות שהפירוק לא נחשף בשום צורה (שאני מכיר), עדיין אפשר לנצל את המוכיח כדי לקבל מידע על מספרים מסויים שאולי המוודא מעוניין לדעת אם הם שאריות ריבועיות או לא. גדי אלכסנדרוביץ' 23:11, 21 בפברואר 2007 (IST)
- לא הבנתי. מדובר כאן על פרוטוקול אימות והסוד היחידי שמעניין אותנו לצורך הענין זה הסיסמה. מה זה משנה אם הפרוטוקול תורם מידע אחר שהוא לא רלוונטי. בהיבט פרקטי, איך להשתמש בתכונת אפס ידע המתוארת כדי לאמת זהות מבלי לחשוף את הסוד אפילו לא בפני המאמת עצמו (בניגוד לשיטת הסיסמה הרגילה) והפסקה מנסה לענות על השאלה האם תכונת אפס הידע עצמה פירושה שהמאמת לא יכול מעצם ההגדרה לנצל את הפרוטוקול כדי לחלץ את הסוד מהמוכיח או שזה לא מספיק להסתמך רק על תכונת אפס ידע המוגדרת בפסקה הקודמת, אלא תכונת אפס ידע באופן מעשי צריכה להיות כזו שהמאמת לא יוכל לחשב את הסוד מהמידע הציבורי לבד וכאן אנחנו מגיעים לבעיות המתמטיות (הבאתי דוגמה קודם למשל שהגורמים הראשוניים יהיו גדולים כדי שלא יהיה קל לפרק לגורמים את המספר) ואז תכונת אפס הידע תהיה מועילה, אחרת אין כל תועלת בפרוטוקול. זה בדיוק סוגיית הבטיחות שדנים בה כמעט בכל נושא קריפטוגרפי. זו הייתה כוונת הפסקה המקורית. --יוסי א. 00:24, 22 בפברואר 2007 (IST)
- שוב, נקודת המבט הזו צרה מדי לדעתי. ברור שהסוד צריך להיות בטוח; הטענה היא שלפעמים גם אם הסוד בטוח עדיף לא להשתמש בפרוטוקול כי הוא חושף מידע שאנחנו לא רוצים להעביר למוודא (אם זה באמת לא היה משנה ש"הפרוטוקול תורם מידע אחר שהוא לא רלוונטי" בכלל לא היה צורך לדבר על הוכחות באפס ידע, אלא רק על "הוכחות של סוד שלא חושפות מה הסוד"). גדי אלכסנדרוביץ' 00:37, 22 בפברואר 2007 (IST)
- או.קיי. אני מתקן את עצמי, זה אכן משנה אם הפרוטוקול מנדב מידע כלשהו אפילו צדדי. אבל עדיין הפסקה מתמקדת אך ורק בנושא אימות שזה אחד הישומים המעשיים של הוכחת אפס ידע ומן הראוי להדגיש שמלבד העובדה שהפרוטוקול חייב שתהיה לו תכונת אפס ידע כדי שלא ינדב מידע כלשהו, עליו להיות "בטוח". אני חושב שהפסקה במתכונתה הנוכחית לא מבטאת זאת היטב. שים לב, המשפט "דרישת אפס הידע של הפרוטוקול היא הכרחית על מנת שיהיה בטוח מבחינה קריפטוגרפית..." אינו מדוייק. הפרוטוקול יהיה בטוח מבחינה קריפטוגרפית אך ורק אם הבעיה המתמטית עליה הוא נשען היא "קשה". תכונת אפס הידע רק מבטיחה כי אף גורם לא יוכל לנצל את הפרוטוקול כדי לחלץ מידע מהמוכיח. צריך להבחין בין שני התכונות הללו. אפשר לתת דוגמא מפרוטוקול הוכחת ידע אחר, למשל אם המוכיח מצפין מידע כלשהו בעזרת סיסמתו (באמצעות אלגוריתם הצפנה ידוע) ואת הצופן הוא משדר למאמת. כאן המוכיח אכן מנדב מידע, א. הצופן עצמו משודר בערוץ הפתוח, ב. על המאמת לדעת את הסיסמה כדי לבדוק את הצופן. למרות שהפרוטוקול המתואר אינו הוכחה באפס ידע, הוא עדיין בטוח מבחינה קריפטוגרפית אם המוכיח השתמש באלגוריתם הצפנה בטוח. --יוסי א. 20:21, 25 בפברואר 2007 (IST)
- מה שניסיתי לומר הוא שאפס הידע הוא תנאי הכרחי, לא מספיק. כלומר, חייבים שהפרוטוקול יהיה אפס ידע, אבל בנוסף לכך צריך גם להסתמך על בעיה קשה. לא הבנתי את הדוגמה שלך של ההצפנה. במקרה הזה, מה המוכיח מנסה בעצם להוכיח? שהוא יודע את הססמא? אבל מדרך ההוכחה עולה שגם המוודא מכיר את הססמא, ולכן אין את הבטיחות הקריפטוגרפית שאליה חותרים בפרוטוקול אפס-ידע - שהמוודא (ולא מישהו שסתם מצותת) לא יוכל "לגנוב" את הסוד של המוכיח. גדי אלכסנדרוביץ' 20:28, 25 בפברואר 2007 (IST)
- אבל ברור לקורא שזהו "תנאי הכרחי" ככלות הכל הערך הלא מדבר בדיוק על זה. זה לא החידוש בפסקה הזו זה כבר נאמר קודם. הדוגמא הושאלה מפרוטוקול אימות Challenge response, פרוטוקול אימות ידוע שבמהותו הרעיון מאוד פשוט, במקום שהמשתמש ישלח את סיסמתו הוא מצפין מידע סרק באמצעותה ורק את הטקסט המוצפן הוא משדר בערוץ הפתוח. הפרוטוקול משיג את מטרתו והוא אימות זהות המשתמש באופן בטוח (כמובן שהמאמת מכיר את המשתמש ואת סיסמתו), על כל פנים מצותת לא יכול לעשות במידע המשודר שימוש כלשהו. וכוונתי הייתה להביא דוגמא לפרוטוקול אימות אינטראקטיבי "בטוח" שאינו מערב תכונת אפס ידע (ראה קרברוס). --יוסי א. 21:14, 25 בפברואר 2007 (IST)
- זה לא נאמר קודם כי רק בפסקה הזו מדברים על שימושים להוכחות אפס ידע בפרוטוקולי אימות... באשר לדוגמה שלך, אתה חייב להגדיר מה זה "פרוטוקול אימות", כי ברור שאנחנו מדברים על שני דברים שונים: אני מדבר על פרוטוקול אימות שלא חושף למוודא את הסוד של המוכיח, ואתה מדבר על אחד שכן עושה את זה. מן הסתם הערך צריך לעסוק רק בפרוטוקולים מן הסוג הראשון. גדי אלכסנדרוביץ' 21:37, 25 בפברואר 2007 (IST)
- אבל ברור לקורא שזהו "תנאי הכרחי" ככלות הכל הערך הלא מדבר בדיוק על זה. זה לא החידוש בפסקה הזו זה כבר נאמר קודם. הדוגמא הושאלה מפרוטוקול אימות Challenge response, פרוטוקול אימות ידוע שבמהותו הרעיון מאוד פשוט, במקום שהמשתמש ישלח את סיסמתו הוא מצפין מידע סרק באמצעותה ורק את הטקסט המוצפן הוא משדר בערוץ הפתוח. הפרוטוקול משיג את מטרתו והוא אימות זהות המשתמש באופן בטוח (כמובן שהמאמת מכיר את המשתמש ואת סיסמתו), על כל פנים מצותת לא יכול לעשות במידע המשודר שימוש כלשהו. וכוונתי הייתה להביא דוגמא לפרוטוקול אימות אינטראקטיבי "בטוח" שאינו מערב תכונת אפס ידע (ראה קרברוס). --יוסי א. 21:14, 25 בפברואר 2007 (IST)
- מה שניסיתי לומר הוא שאפס הידע הוא תנאי הכרחי, לא מספיק. כלומר, חייבים שהפרוטוקול יהיה אפס ידע, אבל בנוסף לכך צריך גם להסתמך על בעיה קשה. לא הבנתי את הדוגמה שלך של ההצפנה. במקרה הזה, מה המוכיח מנסה בעצם להוכיח? שהוא יודע את הססמא? אבל מדרך ההוכחה עולה שגם המוודא מכיר את הססמא, ולכן אין את הבטיחות הקריפטוגרפית שאליה חותרים בפרוטוקול אפס-ידע - שהמוודא (ולא מישהו שסתם מצותת) לא יוכל "לגנוב" את הסוד של המוכיח. גדי אלכסנדרוביץ' 20:28, 25 בפברואר 2007 (IST)
- או.קיי. אני מתקן את עצמי, זה אכן משנה אם הפרוטוקול מנדב מידע כלשהו אפילו צדדי. אבל עדיין הפסקה מתמקדת אך ורק בנושא אימות שזה אחד הישומים המעשיים של הוכחת אפס ידע ומן הראוי להדגיש שמלבד העובדה שהפרוטוקול חייב שתהיה לו תכונת אפס ידע כדי שלא ינדב מידע כלשהו, עליו להיות "בטוח". אני חושב שהפסקה במתכונתה הנוכחית לא מבטאת זאת היטב. שים לב, המשפט "דרישת אפס הידע של הפרוטוקול היא הכרחית על מנת שיהיה בטוח מבחינה קריפטוגרפית..." אינו מדוייק. הפרוטוקול יהיה בטוח מבחינה קריפטוגרפית אך ורק אם הבעיה המתמטית עליה הוא נשען היא "קשה". תכונת אפס הידע רק מבטיחה כי אף גורם לא יוכל לנצל את הפרוטוקול כדי לחלץ מידע מהמוכיח. צריך להבחין בין שני התכונות הללו. אפשר לתת דוגמא מפרוטוקול הוכחת ידע אחר, למשל אם המוכיח מצפין מידע כלשהו בעזרת סיסמתו (באמצעות אלגוריתם הצפנה ידוע) ואת הצופן הוא משדר למאמת. כאן המוכיח אכן מנדב מידע, א. הצופן עצמו משודר בערוץ הפתוח, ב. על המאמת לדעת את הסיסמה כדי לבדוק את הצופן. למרות שהפרוטוקול המתואר אינו הוכחה באפס ידע, הוא עדיין בטוח מבחינה קריפטוגרפית אם המוכיח השתמש באלגוריתם הצפנה בטוח. --יוסי א. 20:21, 25 בפברואר 2007 (IST)
- שוב, נקודת המבט הזו צרה מדי לדעתי. ברור שהסוד צריך להיות בטוח; הטענה היא שלפעמים גם אם הסוד בטוח עדיף לא להשתמש בפרוטוקול כי הוא חושף מידע שאנחנו לא רוצים להעביר למוודא (אם זה באמת לא היה משנה ש"הפרוטוקול תורם מידע אחר שהוא לא רלוונטי" בכלל לא היה צורך לדבר על הוכחות באפס ידע, אלא רק על "הוכחות של סוד שלא חושפות מה הסוד"). גדי אלכסנדרוביץ' 00:37, 22 בפברואר 2007 (IST)
- לא הבנתי. מדובר כאן על פרוטוקול אימות והסוד היחידי שמעניין אותנו לצורך הענין זה הסיסמה. מה זה משנה אם הפרוטוקול תורם מידע אחר שהוא לא רלוונטי. בהיבט פרקטי, איך להשתמש בתכונת אפס ידע המתוארת כדי לאמת זהות מבלי לחשוף את הסוד אפילו לא בפני המאמת עצמו (בניגוד לשיטת הסיסמה הרגילה) והפסקה מנסה לענות על השאלה האם תכונת אפס הידע עצמה פירושה שהמאמת לא יכול מעצם ההגדרה לנצל את הפרוטוקול כדי לחלץ את הסוד מהמוכיח או שזה לא מספיק להסתמך רק על תכונת אפס ידע המוגדרת בפסקה הקודמת, אלא תכונת אפס ידע באופן מעשי צריכה להיות כזו שהמאמת לא יוכל לחשב את הסוד מהמידע הציבורי לבד וכאן אנחנו מגיעים לבעיות המתמטיות (הבאתי דוגמה קודם למשל שהגורמים הראשוניים יהיו גדולים כדי שלא יהיה קל לפרק לגורמים את המספר) ואז תכונת אפס הידע תהיה מועילה, אחרת אין כל תועלת בפרוטוקול. זה בדיוק סוגיית הבטיחות שדנים בה כמעט בכל נושא קריפטוגרפי. זו הייתה כוונת הפסקה המקורית. --יוסי א. 00:24, 22 בפברואר 2007 (IST)
סימולטור[עריכת קוד מקור]
אפשר להזכיר גם את הסימולטור ואיך ולמה זה מראה על אפס ידע. 84.110.199.201 09:55, 23 בינואר 2012 (IST)
צריך לשנות חזרה את שם הערך ל"אפס ידע".[עריכת קוד מקור]
זה השם המקובל, ללא צל של ספק. זה גם התרגום הפשוט של המילה knowledge, ואני לא רואה פה שם בעיה של תרגום שגוי. לא מצאתי תיעוד של דיון כלשהו על שם הערך. --אלעזר - שיחה 16:08, 13 במאי 2016 (IDT)
- לעניות דעתי יש הבדל בין ידע לידיעה, בהקשר של הערך מדובר על ידיעת סוד ספציפי ולא על ידע כללי. בנוסף התרגום הזה נלקח מהרצאה של פרופסור מכאל רבין.--יוסי א. - שיחה 22:38, 14 במאי 2016 (IDT)
מערת עלי באבא - דרוש הסבר טוב יותר[עריכת קוד מקור]
כשניסיתי ״להסביר לילדי״ לפי משל המערה, עלתה השאלה למה לא יכול המוכיח להראות שהוא נכנס בכניסה אחת ויוצא מהשניה? האם זה לא עונה על כל תנאי ה״הוכחה באפס ידיעה״? מדוע המוודא אינו רשאי לראות מאיזו כניסה נכנס? Gil mo - שיחה 18:02, 16 באפריל 2021 (IDT)
האם הדוגמא של צביעות גרף אינה עומדת בתנאים להוכחה באפס ידיעה?[עריכת קוד מקור]
שני דברים לא ברורים: 1. אם למוכיח אין פתרון אבל הוא מרמה, ובכל פעם שהוא מקבל שני קודקודים מהמוודא הוא משקר ומחזיר כתשובה שני צבעים אקראיים, הרי לפי התיאור המוודא יפול בפח. 2. אם לעומת זאת מניחים שהמוכיח חייב לומר אמת (כפי שניתן להבין מסעיף "1. שלמות") הרי שהמוודא יכול לשאול על לגבי כל זוג קודקודים אפשרי ובתהליך של הסקת מסקנות (אם אותו קודקוד מקבל בתשובה צבעים שונים בכל פעם, המוודא מיישב את הסתירה ע"י החלפת הצבע) לשחזר את צביעת הגרף כולו, אמנם לא בהכרח בצבעים אותם בחר המוכיח אבל כן בפרמוטציה כלשהי שלהם. כלומר המוודא ידע בסוף התהליך הרבה על המידע הסודי שנמצא בידי המוכיח, ולא ניתן יהיה לומר שהוא נמצא באפס ידיעה. ―Avnerh11 (שיחה | תרומות | מונה) לא חתם
- אני גם תהיתי בנושא הזה. הרי בסה"כ יש 3 תמורות לצביעה הזו? מצד שני אולי העניין הוא שאין שום מידע מעבר ל"קודקוד א וקודקוד ב הסמוך לו בצבעים שונים", ואת זה אנחנו יודעים מהגדרת הצביעה, אז מה בעצם מוכיחים כאן? «kotz» «שיחה» 10:36, 29 באפריל 2023 (IDT)