בתשובה לגדי אלכסנדרוביץ', 18/01/08 23:47
שתי הערות 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 מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות