בתשובה להאייל האלמוני, 19/01/08 11:30
שתי הערות 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 מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות