פונקציה חד-כיוונית היא פעולה שממירה קלט לפלט כך שקל לחשב את הפלט מהקלט אך קשה מאוד להשיג את הקלט מהפלט. "קל" כאן פירושו שניתן לחשב בזמן פולינומי, כלומר בצורה יעילה יחסית במחשב. "קשה" פירושו שאין אלגוריתם פולינומי הסתברותי שמצליח למצוא קלט תואם עם יותר מהסתברות זניחה, כלומר הסתברות מאוד נמוכה.
הקושי בהיפוך יכול להיות רק ביחס ליכולות חישוביות מוגבלות. אפשר תמיד להפוך פונקציה על ידי ניסוי כוחות גסים, אבל זה דורש זמן מעריכי, זמן שגדל בצורה מהירה מאוד עם גודל הקלט. חשוב להבין שיש מקרים שבהם כמה קלטים ממופים לאותו פלט. לכן התוקף צריך למצוא כל קלט שמתאים לפלט, לא דווקא את הקלט המקורי.
תמורה חד-כיוונית היא מקרה שבו הפונקציה שומרת על אורך הקלט והפלט והיא חד-חד-ערכית ועל (כל פלט יש לו מקור יחיד). גם אז, למרות שהפלט מחזיק מידע על הקלט, עדיין קשה למצוא את הקלט.
בפועל מדברים על משפחות של פונקציות התלויות בפרמטר I. יש אלגוריתם שמייצר את I, אלגוריתם שמדגם קלטים, ואלגוריתם שמחשב את הפונקציה. ההגדרה מבחינת קושי משתמשת בניסוי שבו מייצרים I ו-x, מחשבים y, ואז בודקים אם יריב פולינומי יכול למצוא x' עם f_I(x')=y.
פונקציה חד-כיוונית "חלשה" היא כזו שניתן להפוך רק עם הסתברות לא אפסית אך קטנה. אפשר להראות ששימוש נכון בפונקציה חלשה מוביל לבנייה של פונקציה חזקה יותר.
דלת צונחת היא מידע סודי שמקל על ההיפוך. פונקציה כזו קלה לחשב קדימה, וקשה להפוך ללא המידע הזה. דוגמה קלאסית היא העלאה בריבוע מודולו מספר פריק (מספר שמורכב משני ראשוניים). העלאה בריבוע קלה; מציאת שורש ריבועי קשה אם לא יודעים את הגורמים הראשוניים. אם יודעים את הגורמים, אפשר לחשב את ההיפוך בקלות. המושג הוצג לראשונה על ידי דיפי והלמן בשנת 1976.
אין הוכחה מתמטית מוחלטת שקיימות פונקציות כאלה. המועמדות מבוססות על הנחה חישובית שקשורה למחלקות מורכבות (כמו היחס בין NP ל-BPP). דוגמאות פרקטיות: פירוק לגורמים, הכפל של שני מספרים קל, פירוקו קשה. RSA מבוסס על הנחה זו. בעיית התרמיל (knapsack) הוצעה כבסיס אך ניסיונות רבים כשלו; בעיות בסריגים הן כיום תחום מרכזי למועמדים אחרים.
פונקציות חד-כיווניות הן בסיס הקריפטוגרפיה המודרנית. הן משמשות כפונקציות גיבוב, כלים שמייצרים תמצית קבועה מהקלט, ובהצפנה, כולל הצפנת מפתח ציבורי (שמבוססת על דלת צונחת). למשל RSA היא מערכת שמנצלת דלת צונחת המבוססת על פירוק לגורמים. פונקציות גיבוב גם משמשות לאימות סיסמאות: השרת שולח אתגר, הלקוח מחבר את הסיסמה ומחשב גיבוב, והשרת משווה פלטים כדי לאמת את הסיסמה.
פונקציה חד-כיוונית היא פעולה שקלה לעשות קדימה וקשה מאוד לעשות אחורה. פונקציה כאן היא כלל שמקבל משהו ומחזיר משהו אחר. "קל" אומר שמחשב יכול לחשב את זה מהר. "קשה" אומר שרק במקרה נדיר מאוד ניתן למצוא את הקלט מהפלט.
אפשר לנסות למצוא את הקלט על ידי בדיקה של כל האפשרויות. זה נקרא כוח גס. זה מצליח אבל לוקח זמן עצום. לפעמים כמה קלטים נותנים אותו פלט. אז מי מנסה לפרוץ יכול למצוא כל קלט שמתאים.
דלת צונחת היא סוד מיוחד שמאפשר לפתור את הבעיה בקלות. דוגמה: כפל של שני מספרים גדולים קל. פירוק של המספר הזה חזרה לשני המספרים קשה. אם יודעים את שני המספרים המקוריים, זה כמו שיש דלת צונחת. RSA היא שיטה שמשתמשת ברעיון הזה.
הפתרון הזה חשוב להצפנה. למשל לשמור סיסמה בשרת משתמשים בפונקציית גיבוב, גיבוב היא פעולה שמייצרת חתימה קבועה של טקסט. כשיישים רוצים לאמת סיסמה, המחשב משווה את הפלטים. אם הם שווים, הסיסמה נכונה.
תגובות גולשים