פונקציה חד-כיוונית
ויקיפדיה האנציקלופדיה encyclopedia
במדעי המחשב ובקריפטוגרפיה, פונקציה חד-כיוונית היא פונקציה שממירה קלט לפלט באופן שקשה מאוד מבחינה חישובית להפוך את הפונקציה, דהיינו לשחזר את הקלט בהינתן הפלט.
בעיות פתוחות במדעי המחשב: האם קיימות פונקציות חד-כיווניות? (בעיות פתוחות נוספות במדעי המחשב) |
ביתר פירוט, בהינתן קלט כלשהו , קל לחשב את הפלט על ידי הפעלת הפונקציה החד-כיוונית בזמן פולינומי, דהיינו במהירות וביעילות אולם הפעולה ההפוכה שהיא בהינתן הפלט חישוב הוא משימה קשה חישובית. בניסוח פורמלי לא קיים אלגוריתם פולינומי הסתברותי המקבל את ומצליח למצוא כלשהו המקיים את אלא בהסתברות זניחה. הקושי החישובי בהיפוך הפונקציה מודד את כוח החישוב הדרוש כדי למצוא זוג של (קלט, פלט) מתאימים, אך אינו אומר דבר על מידע חלקי הזולג מהפונקציה. סיבית שהסיכוי לחשב אותה הוא זניח בהינתן נקראת סיבית קשה.
פונקציה חד-כיוונית היא מאבני הבניין של הקריפטוגרפיה המודרנית ומשמשת כפרימיטיב בפרוטוקולים קריפטוגרפיים רבים. שימוש נפוץ בפונקציה חד-כיוונית הוא כפונקציית גיבוב. אין הוכחה לקיומה של פונקציה חד-כיוונית מבחינה מתמטית - כי להוכחה כזו תהיינה השלכות מרחיקות לכת על תורת הסיבוכיות, אלא רק שקיימות מועמדות מעשיות לפונקציות חד-כיווניות שההשערה היא שקשה מאוד להפוך אותן. על בסיס השערה זו ניתן לבנות מערכת הצפנה שתהיה בטוחה כל עוד ההשערה נותרת בעינה. למעשה אפשר להוכיח שפונקציה חד-כיוונית היא תנאי הכרחי כמעט בכל משימה קריפטוגרפית. בהצפנה סימטרית וא-סימטרית כאחד. למשל צופן בלוקים מבוסס על תמורה פסאודו-אקראית שהיא פרימיטיב קריפטוגרפי המבוסס על ההשערה שפונקציה חד-כיוונית קיימת.
הפונקציות הקיימות כיום בשימוש מעשי נחשבות למועמדות טובות במובן שטרם נמצאה דרך קלה להפוך אותן. למשל AES נחשב לפונקציה חד-כיוונית אם כי לא הוכח תאורטית והוא אחד האלגוריתמים הנפוצים ביותר בהצפנה מודרנית. מהיבט תאורטי ניתן לבנות פונקציה חד-כיוונית מוכחת תחת מודל ביטחון אסימפטוטי או אחר אולם חסרונה הוא שיעילותה נמוכה בהשוואה לפונקציות הקיימות בשימוש מעשי. הבעיה העיקרית בקריפטוגרפיה מודרנית היא לגשר על הפער בין הוכחות תאורטיות לבין יישום מעשי יעיל.