בתשובה לדורפל, 15/06/08 4:55
 |
|
 |
||
|
||||
 |
זהו, שניסיתי להמחיש עם הדוגמה שלא מדובר באותה "מידה" של סבירות. הנקודה המהותית היא שאם צריך למצוא "רמז" רק פעם אחת, אז למרות שההשקעה היא מטורללת אפשר להגיע אליה, בעוד שלהגיע לאותה רמת השקעה ב"יום יום" זה לא סביר. הבעיה לא בהכרח ב-BPP אם מתקיים מה שתיארתי. אתה עדיין צריך "רמז" בשביל כל גודל מספר, והחישוב של הרמז הוא עדיין קשה. |
 |
 |
 |
|
|
|
||
|
||||
|
מפתיע אותי וכלל לא ברור לי למה אתה אומר על ההשקעה שאתה בעצמך הגדרת הרגע כמטורללת, בהנחה ששנינו חושבים על אותו סדר גודל, כ"אפשר להגיע אליה". על איזה רמז אתה מדבר? מה הבעיה למצוא את הפירוק של מספר כלשהו בן חמש-מאות ספרות (נגיד בינאריות)? פשוט מכפילים שני ראשוניים ששניהם בני 250 ספרות1, והרי לך מספר פריק בן 500 ספרות ופירוקו. --- 1 בערך. לא נתעכב על זה. |
|
|
|
|
|
|
||
|
||||
|
טוב, בטח התכוונת שקיים אחד ספיציפי כזה, אבל לא ידוע מי הוא. אז: 1. מאוד קשה לי לדמיין את זה (אבל כבר אמרת שגם לדעתך זו דוגמה מאוד מופרכת). 2. אני אניח שאתה מתכוון גם שלכל אורך, המספר הזה הוא שונה. אם אפשר למצוא את המספר הזה בזמן פולינומי, הרי שזו סדרה יוניפורמית (כמו שאמרת בעצמך לאלמוני), והבעיה ממילא ב-BPP. אם אי-אפשר בזמן פולינומי, החל מגודל מסוים, אי-אפשר לפני קץ היקום ובהסתברות ראויה לציון גם אם נשקיע את כל המשאבים שבעולם, אבל עדיין אפשרי לחבר'ה הישרים להשתמש בסכמה במשאבים סבירים (נו, כנראה. לא ידועים לי הקבועים של RSA, ואתה ממילא יכול להעביר את הדיון לכל סכמת הצפנה אחרת ונשאר עם אותו הפרנציפ), ואז מה אכפת לנו שיש גם את ההתקפה הלא-אפשרית הזאת על ההצפנה? אני חוזר על השאלה המקורית שלי - אם גם עם כל המשאבים שאפשר לדמיין אי-אפשר, מה זה משנה לי שיש גם נתיב התקפה שבו מישהו עשוי להיות יותר נכון להשקיע את המשאבים האלו? הם הרי עדיין לא מספיקים. |
|
|
|
|
|
|
||
|
||||
|
הכוונה הייתה שאפשר למצוא את המספר בזמן פולינומי, לא את הפירוק שלו. מאוד אכפת לנו שיש את ההתקפה הלא-אפשרית הזו על ההצפנה כי קיומה *מכריח* אותנו להגדיל את הקבועים שבהם אנחנו משתמשים. אם פתאום ניאלץ, במקום להשתמש ב-RSA של 2048 סיביות, להשתמש בכזה של 32768, זה מעיד על שינוי מהותי שההתקפה הלא-אפשרית גרמה. |
|
|
|
|
|
|
||
|
||||
|
סלח לי, לא הבנתי - להגדיל את הקבועים נאלצים מדי פעם, אבל מה הנקודה? | |
|
|
|
|
|
||
|
||||
|
כי אפשר, אם אתה לא עובד עם מחשב יחיד אלא עם עשרות אלפי מחשבים, ומוכן להשקיע פרק זמן שבדרך כלל היה נחשב בעינייך לא סביר. הרי בימינו *מצליחים* לפרק לגורמים מספרים, זה פשוט קשה. בקשר לפירוק - אה, כן, צודק, דוגמה גרועה. אבל זה הרעיון שחשוב. נסה לשחזר את הדוגמה שלי עם משהו שאי אפשר לייצר בקלות (או לחילופין, עם "צריך פירוק של מספר ספציפי שקל למצוא אותו אבל הפירוק שלו לא ידוע). |
|
|
|
|
|
|
||
|
||||
|
כל העניין בבעיות עם סיבוכיות לא-פולינומית, הוא שאפילו עם מיליארדי מחשבים, אי-אפשר לפתור מופעים גדולים מספיק שלהם. זה שמצליחים לפרק מספרים, אתה בוודאי יודע, זה ממש לא מרשים - אני יכול לפרק חלק בראש; גדולים יותר אפשר עם עשרות אלפי מחשבים; גדולים מספיק, במידה ובעיית הפירוק אכן לא פולינומית, אי-אפשר יהיה גם אם כל אטום בודד ביקום יהיה מעבד מרובה ליבות. אני בוודאי לא צריך להזכיר לך זאת, אבל לא יזיק שיופיע בפרוטוקול - גם עם בעיות ליניאריות, יש מופעים שאי-אפשר לפתור לפני מות היקום עם מיליארדי מחשבים. החלק המעניין, לצרכי קריפטוגרפיה, הוא שהשחקנים הישרים עדיין יכולים לפעול בזמן סביר, בעוד שלתוקף אין שום דרך מלבד זו הדורשת את המשאבים שאין, ולעולם לא יהיו, בנמצא. אני רוצה לחזור על הנקודה שלי, שנדמה לי (סלח לי) שהיא נכונה, פשוטה, ושחמקה ממך באופן מפתיע עד עכשיו (או שאתה מנסה לדבר על משהו אחר, ואני זה שמתבלבל) - יהי סט של בעיות שאפשר לפתור כל אחת מהן בנפרד, או את כולן ביחד. אתה אומר - יש יותר אינטרס לאנשים להשקיע בפתרון הכללי שפותר את כולן ביחד. אני אומר - כל עוד לא זה אפשרי ולא זה אפשרי - בכלל - מידת האינטרס לא משנה. בלתי-אפשרי נשאר בלתי-אפשרי גם אם עובדים בצוות. "נסה לשחזר את הדוגמה שלי עם משהו שאי אפשר לייצר בקלות" - עזור לי בבקשה. |
|
|
|
|
|
|
||
|
||||
|
העניין של "גדולים מספיק אי אפשר גם אם כל אטום ביקום יהיה מעבד מרובה ליבות" נכון, כמובן, גם לדברים עם סיבוכיות פולינומית, כך שאני מציע שתזנח לרגע את גישת ה"אם משהו הוא לא פולינומי, אין שום סיכוי לחשב אותו". הנקודה היא שיש סיכוי, עבור סט של ערכים שהם נמוכים מספיק. אנסה לחדד את הנקודה. אני מבדיל בין שלושה סוגי חישובים - כאלו שהם בלתי פיזיביליים בכלל, ועליהם לא מדברים; כאלו שהם קלים וכל מחשב ביתי עושה בצורה זריזה (לצורך הדיון, אלו הפולינומיים); וכאלו שהם "בינוניים" - במחשב ביתי זה ייקח יותר מדי זמן, אבל אם כל המחשבים בעולם יתאגדו וישתפו פעולה, ויחכו חודש חודשיים, החישוב יסתיים. עכשיו, בוודאי שיש הבדל מהותי בין הסיטואציה שבה בכל פעם שרוצים לפרוץ הודעה צריך לבצע חישוב "בינוני" שכזה, ובין הסיטואציה שבה מספיק שכל העולם יבצע פעם אחת את החישוב ה"בינוני" ואז כל אחד יוכל לפרוץ בקלות הודעות קצרות מספיק. המשמעות של זה פשוטה, והיא זו שניסיתי להסביר בהודעה האחרת שאליה הגבת - אם בעיה כלשהי היא כרגע בטווח ה"בינוני", אז למרות שהאלגוריתם שפותר אותה הוא אקספוננציאלי ואפשר להפוך אותה לבלתי אפשרית על ידי הגדלת פרמטר הבטיחות של ההצפנה, בכל זאת היא תגרום לנו לעשות משהו מעשי מאוד - להגדיל את פרמטר הבטיחות של ההצפנה, אולי בצורה לא טריוויאלית, בטח בקפיצה שלה לא ציפינו. הסיבה שבגללה פרמטר הבטיחות גדל בדרך כלל היא שהפתרון הנאיבי (שגם הוא לא פיזיבילי בהינתן פרמטר גדול מספיק) מתחיל להיות מאיים - ולכן גם אלגוריתמים לא יעילים אחרים מסוגלים להיות מאיימים. |
|
|
|
|
|
|
||
|
||||
|
(אמרתי בעצמי שגם לליניארי זה נכון עבור ערכים מסויימים. הסברתי למה עבור ליניאריים זה לא מעניין, ועבור לא-פולינומיים כן - כי השחקנים הישרים נשארים בזמן סביר.) "הנקודה היא שיש סיכוי, עבור סט של ערכים שהם נמוכים מספיק." - זו לא נקודה מעניינת, כי, לאור הפסקה הקודמת שלי, אין שום סיבה שלא לבחור בהצפנה דווקא את סט הערכים שאינם נמוכים מספיק. (כלומר, יש יתרונות לכך - הצפנה בשניות במקום בשעות - אבל זה לא מחויב המציאות. במידת הצורך, יהיה אפשר לעשות את ההקרבה הזאת, ולהשיג שוב סודיות טובה, במחיר הנוחות של הצפנה כמעט-מיידית.) -- כלומר, הנקודה שלך לאורך הדיון הייתה שיש תרחישים שבהם התקדמות אלגוריתמית דורשת הגדלה של קבוע הבטיחות הנפוץ בהצפנה? מן הסתם אני מסכים. |
|
|
|
|
|
|
||
|
||||
|
בדיוק. אם בגלל איזו תגלית תיאורטית שמעידה על תוצאה ''בלתי אפשרית'' לכאורה גורמת לצורך להצפין בשעות במקום בשניות - כנראה שבכל זאת מדובר במשהו בעל השלכות מעשיות. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |