פונקציה חד-כיוונית

Wikipedia ויקיפדיה העברית - האנציקלופדיה החופשית

Download this dictionary

פונקציה חד כיוונית

הפניה פונקציה חד-כיוונית

להמשך המאמר ראה Wikipedia.org...

פונקציה חד-כיוונית

במדעי המחשב, פונקציה חד-כיוונית היא פונקציה שממירה קלט לפלט, באופן שקשה מאוד, מבחינה חישובית, לשחזר את הקלט מתוך הפלט. כלומר, בהינתן קלט M קל לחשב את הפלט E על ידי הפעלת הפונקציה החד-כיוונית

בזמן פולינומי, דהיינו במהירות וביעילות אולם שחזור קלט בהינתן הפלט היא משימה קשה חישובית. ביתר פירוט, עבור קלט אקראי M, לא קיים אלגוריתם פולינומי הסתברותי המקבל את

ומצליח למצוא X כך ש (f(X)=f(M, אלא בהסתברות זניחה. הקושי החישובי בהיפוך הפונקציה מודד את כח החישוב הדרוש כדי למצוא זוג של (קלט,פלט) המתאימים לפונקציה אך אינו אומר דבר על מידע חלקי הזולג מהפוקנציה. סיבית שהסיכוי לחשב אותה הוא זניח בהינתן

נקראת סיבית קשה.

פונקציות חד-כיווניות הן מאבני הבניין של הקריפטוגרפיה ומשמשות כפרימיטיבים בפרוטוקולים קריפטוגרפיים רבים. שימוש נפוץ בפונקציות חד-כיווניות הוא כפונקציית גיבוב, כלומר כך שהפלט קצר מהקלט.

להמשך המאמר ראה Wikipedia.org...