בתשובה לגדי אלכסנדרוביץ', 18/01/08 18:46
שתי הערות 468501
נטפקן מתחיל • בתשובה לגדי אלכסנדרוביץ' יום ו', 18/1/2008, 23:00
מגיע לי עונש חמור על אי הדיוק שלי (נשרה לי המילה "שלמה" בנקודה קריטית). אני אנסה לנסח שוב את ניטפוקי:

מאמרך טוען ש: אם P אינו שווה ל-NP, פירוש הדבר הוא שאין סיכוי שאף בעיה שזכתה לתואר "NP-שלמה" ניתנת לפתרון יעיל (ולכן ניתן להסתמך על אי־היכולת לפתור אותה באפליקציות של הצפנה, למשל)

אך לעניות דעתי (הענייה עד מאוד) אין אפליקציות הצפנה המבוססות על בעיות NP-שלמות (למרות שמחפשים).
שתי הערות 468510
גדי אלכסנדרוביץ' • בתשובה לנטפקן מתחיל יום ו', 18/1/2008, 23:47
אכן (עד כמה שידוע לי, כיוון מבטיח אחד הוא הצפנה שמבוססת על ה-Shortest Vector Problem ב-Lattices; זו בעיה NP-קשה לקירוב ברמת דיוק מסויימת, אבל בינתיים לא מכירים הצפנה שפיצוח שלה ידרוש דיוק שכזה אלא פחות מכך).

בכל מקרה, הקיום או אי הקיום כרגע של הצפנות שמבוססות על בעיות כאלו לא משנה את הנקודה העיקרית - שבעיות כאלו יכולות להיות שימושיות, וה"חשש" שיתגלה בהם פגם נמוך יותר, יחסית.
שתי הערות 468543
האייל האלמוני • בתשובה לגדי אלכסנדרוביץ' שבת, 19/1/2008, 11:30
המשפט הנדון לא מבטא את המוטיבציה העיקרית לפתרון בעיית P/NP. לדעתי רוב העוסקים בתחום משערים שהוכחה ש- P שונה מ- NP לא תביא מיידית למציאת פונקציה חד-כיוונית (שהיא אבן הבניין הבסיסית להצפנה). לכן לדעתי היחס בין הצפנה לשאלת P/NP הוא בעיקר בכיוון השלילי: אם P=NP אין אפשרות להצפנה (קלאסית). אולי כדאי בכל זאת לחשוב על שינוי הניסוח במאמר כדי שמי שאין לו רקע בנושא לא יחשוב שפתרון P/NP יניב בהכרח הצפנה (או שזו המוטיבציה בחקר P/NP).

מלבד בעיות Lattice שציינת, היו נסיונות להתבסס על בעיית Subset-Sum (השלמה ב- NP) לצורך הצפנה. למיטב ידיעתי כל השיטות שהוצעו עד עתה התבססו על סוגים ספציפיים של קלטים ונמצאו עבורן שיטות פיצוח.
שתי הערות 468547
גדי אלכסנדרוביץ' • בתשובה להאייל האלמוני שבת, 19/1/2008, 11:47
לא ניסיתי לומר שהמשפט הנדון מבטא את המוטיבציה העיקרית... לדעתי המוטיבציה העיקרית (בהינתן שאכן P שונה מ-NP, כי ההפך הוא סנסציה ומכת מוות לקריפטוגרפיה הא-סימטרית הקיימת) היא תיאורטית, בדומה למוטיבציה להוכיח את משפט פרמה.
שתי הערות 468555
האייל האלמוני • בתשובה לגדי אלכסנדרוביץ' שבת, 19/1/2008, 12:16
מעולה אז כולנו מסכימים. העניין הוא שהנטפקן חשב (ואני מסכים) שממה שכתוב עלולים להשתמע הדברים ה(אולי) לא נכונים האלה.

אגב - לא רק הצפנה אסימטרית אלא כל הצפנה (קלאסית) שמבוססת על קושי חישובי (כלומר הכל חוץ ממפתחות חד פעמיים) נמצאת ב- NP.

ועוד הבהרה לתגובה שלי שמעלייך: המשפט האחרון שלי (על חוסר הצלחה לייצר הצפנה בטוחה) מתייחס ל- Subset-Sum בלבד. יש הרבה הצפנות מבוססות Lattice שנחשבות בטוחות.
שתי הערות 469088
צפנת פענח • בתשובה להאייל האלמוני יום ד', 23/1/2008, 5:36
(1) קימות סכמות הצפנה (סימטריות) המבוססות על הקושי של subset-sum שלא נשברו. ראה למשל:
יחד עם זאת, הסכימה הנ"ל מבוססת על הקושי של הבעיה בטווח של פרמטרים בהם היא אינה ידועה להיות NP-שלמה.

(2) ביסוס קריפטוגרפיה על NP-שלמות היא אחת הבעיות החשובות ביותר בתיאוריה של קריפטוגרפיה.
שתי הערות 469104
האייל האלמוני • בתשובה לצפנת פענח יום ד', 23/1/2008, 11:15
נקודה 2 - בהחלט (השתמע אחרת מתגובתי?). כתבתי שהפרדת P/NP לא תביא מיידית לביסוס קריפטוגרפיה על NP שלמות. ניתן לשער אפילו ששתי הבעיות (הפרדת P/NP וביסוס הצפנה על NPC) הן "בלתי תלויות" במובן מסוים (אבל אי אפשר לדעת).

מלבד זאת, מספר תוצאות שליליות (למשל http://portal.acm.org/citation.cfm?id=1132516.113261...) מצביעות על כך שפונקציה חד כיוונית המבוססת על NP-שלמות צריכה לקיים כמה תנאים מאוד מיוחדים.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות