בתשובה לנטפקן מתחיל, 18/01/08 17:50
 |
|
 |
||
|
||||
 |
מן הסתם RSA, דיפי-הלמן ודומיו מבוססים על בעיות שהן ב-NP (לא NP-שלמות) כך שקיימות אפליקציות כאלו. בוודאי שכך ש-P אינו שווה ל-NP לא אומר ששיטות שמבוססות על בעיה NP-קשה הופכות לבלתי ניתנות לפיצוח; זה רק מגביר את הקושי שאנחנו מייחסים להן. (אפשר לנטפק עוד יותר אם רוצים ולומר ש-NP הוא רק בעיות הכרעה ומה הקשר בינו לבין חישובי הפונקציות של RSA ודיפי הלמן ושות') |
 |
 |
 |
|
|
|
||
|
||||
|
מגיע לי עונש חמור על אי הדיוק שלי (נשרה לי המילה "שלמה" בנקודה קריטית). אני אנסה לנסח שוב את ניטפוקי: מאמרך טוען ש: אם P אינו שווה ל-NP, פירוש הדבר הוא שאין סיכוי שאף בעיה שזכתה לתואר "NP-שלמה" ניתנת לפתרון יעיל (ולכן ניתן להסתמך על אי־היכולת לפתור אותה באפליקציות של הצפנה, למשל) אך לעניות דעתי (הענייה עד מאוד) אין אפליקציות הצפנה המבוססות על בעיות NP-שלמות (למרות שמחפשים). |
|
|
|
|
|
|
||
|
||||
|
אכן (עד כמה שידוע לי, כיוון מבטיח אחד הוא הצפנה שמבוססת על ה-Shortest Vector Problem ב-Lattices; זו בעיה NP-קשה לקירוב ברמת דיוק מסויימת, אבל בינתיים לא מכירים הצפנה שפיצוח שלה ידרוש דיוק שכזה אלא פחות מכך). בכל מקרה, הקיום או אי הקיום כרגע של הצפנות שמבוססות על בעיות כאלו לא משנה את הנקודה העיקרית - שבעיות כאלו יכולות להיות שימושיות, וה"חשש" שיתגלה בהם פגם נמוך יותר, יחסית. |
|
|
|
|
|
|
||
|
||||
|
המשפט הנדון לא מבטא את המוטיבציה העיקרית לפתרון בעיית P/NP. לדעתי רוב העוסקים בתחום משערים שהוכחה ש- P שונה מ- NP לא תביא מיידית למציאת פונקציה חד-כיוונית (שהיא אבן הבניין הבסיסית להצפנה). לכן לדעתי היחס בין הצפנה לשאלת P/NP הוא בעיקר בכיוון השלילי: אם P=NP אין אפשרות להצפנה (קלאסית). אולי כדאי בכל זאת לחשוב על שינוי הניסוח במאמר כדי שמי שאין לו רקע בנושא לא יחשוב שפתרון P/NP יניב בהכרח הצפנה (או שזו המוטיבציה בחקר P/NP). מלבד בעיות Lattice שציינת, היו נסיונות להתבסס על בעיית Subset-Sum (השלמה ב- NP) לצורך הצפנה. למיטב ידיעתי כל השיטות שהוצעו עד עתה התבססו על סוגים ספציפיים של קלטים ונמצאו עבורן שיטות פיצוח. |
|
|
|
|
|
|
||
|
||||
|
לא ניסיתי לומר שהמשפט הנדון מבטא את המוטיבציה העיקרית... לדעתי המוטיבציה העיקרית (בהינתן שאכן P שונה מ-NP, כי ההפך הוא סנסציה ומכת מוות לקריפטוגרפיה הא-סימטרית הקיימת) היא תיאורטית, בדומה למוטיבציה להוכיח את משפט פרמה. | |
|
|
|
|
|
||
|
||||
|
מעולה אז כולנו מסכימים. העניין הוא שהנטפקן חשב (ואני מסכים) שממה שכתוב עלולים להשתמע הדברים ה(אולי) לא נכונים האלה. אגב - לא רק הצפנה אסימטרית אלא כל הצפנה (קלאסית) שמבוססת על קושי חישובי (כלומר הכל חוץ ממפתחות חד פעמיים) נמצאת ב- NP. ועוד הבהרה לתגובה שלי שמעלייך: המשפט האחרון שלי (על חוסר הצלחה לייצר הצפנה בטוחה) מתייחס ל- Subset-Sum בלבד. יש הרבה הצפנות מבוססות Lattice שנחשבות בטוחות. |
|
|
|
|
|
|
||
|
||||
|
(1) קימות סכמות הצפנה (סימטריות) המבוססות על הקושי של subset-sum שלא נשברו. ראה למשל: יחד עם זאת, הסכימה הנ"ל מבוססת על הקושי של הבעיה בטווח של פרמטרים בהם היא אינה ידועה להיות NP-שלמה. (2) ביסוס קריפטוגרפיה על NP-שלמות היא אחת הבעיות החשובות ביותר בתיאוריה של קריפטוגרפיה. |
|
|
|
|
|
|
||
|
||||
|
נקודה 2 - בהחלט (השתמע אחרת מתגובתי?). כתבתי שהפרדת P/NP לא תביא מיידית לביסוס קריפטוגרפיה על NP שלמות. ניתן לשער אפילו ששתי הבעיות (הפרדת P/NP וביסוס הצפנה על NPC) הן "בלתי תלויות" במובן מסוים (אבל אי אפשר לדעת). מלבד זאת, מספר תוצאות שליליות (למשל http://portal.acm.org/citation.cfm?id=1132516.113261...) מצביעות על כך שפונקציה חד כיוונית המבוססת על NP-שלמות צריכה לקיים כמה תנאים מאוד מיוחדים. |
|
|
|
|
|
|
||
|
||||
|
האם קיים פתרון בסיבוכיות ידועה עבור אחת (ומכאן כל) הבעיות הNP-שלמות ? | |
|
|
|
|
|
||
|
||||
|
בוודאי; למשל, עבור SAT (שהשאלה בה היא "האם פסוק לוגי בתחשיב הפסוקים הוא ספיק?") פתרון פשוט הוא "בדוק את כל ההשמות בזו אחר זו; אם אחת סיפקה את הפסוק, ענה "כן", אחרת ענה "לא"". הבעיה בפתרון הזה היא שמספר ההשמות הוא אקספוננציאלי באורך הפסוק - כלומר, הסיבוכיות של הפתרון גבוהה מדי מכדי שהוא ייחשב מעשי. |
|
|
|
|
|
|
||
|
||||
|
אבל המשמעות של זה היא שכל בעיה שניתן לוודא את הפתרון שלה באופן פולינומי, ניתן לפתור באופן אקספוננציאלי. זה יכול להיות מאוד שימושי עבור בעיות שזמן הפתרון הרגיל שלהן גדל מהר יותר מאקספוננט. |
|
|
|
|
|
|
||
|
||||
|
אתה בהחלט צודק - זו אכן המשמעות של כך. אני לא מכיר בעיות שזמן הפתרון הרגיל שלהן גדל מהר יותר מאקספוננט ועם זאת פתרון שלהן ניתן לבדיקה פולינומית. מכיוון ש"בצע רדוקציה ל-SAT ובדוק את כל ההצבות) הוא פתרון נאיבי למדי (במובן זה שאין בו שום דבר מחוכם מעבר לקופסה השחורה של הרדוקציה), קח בחשבון ש"הפתרון הרגיל" מוגדר בהתאם. |
|
|
|
|
|
|
||
|
||||
|
אפשר גם לומר שכיוון שלפי ההגדרה לכל בעיה ב- NP יש הוכחה באורך פולינומי שאפשר לבדוק בזמן פולינומי, אפשר פשוט לבדוק את כל המחרוזות באורך המתאים ולראות אם הן מהוות הוכחה וזה ייתן פתרון בזמן אקספוננציאלי (כשהמעריך הוא פולינום באורך הקלט). לא ידוע (וכנראה שלא נכון) שכל בעיה ב- NP ניתנת לפתרון בזמן אקספוננציאלי עם מעריך ליניארי באורך הקלט. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |