כל פונקציה ניתנת להפיכה, בהינתן מספיק זמן. למעשה אפשר להפוך את הפונקציה פשוט על ידי ניסוי כל האפשרויות או מחצית מהאפשרויות במקרה הממוצע, להתקפה כזו קוראים כוח גס. אולם סיבוכיות אלגוריתם כזה היא מעריכית. עובדה זו למעשה מוכיחה כי פונקציה חד-כיוונית נקראת כך רק ביחס לעוצמת המחשוב הדרושה כדי להפוך אותה.
תמורה חד-כיוונית.
לעיתים יש צורך בפונקציה חד-כיוונית עם תכונה מבנית נוספת. אם הפונקציה משמרת אורך כלומר formula_26 עבור כל formula_1 והפונקציה היא חד-חד-ערכית ועל היא נקראת פרמוטציה (תמורה). בניסוח פורמלי:
תהי פונקציה חד-כיוונית formula_28 משמרת אורך, ונניח ש-formula_29 מגבילה את התחום של formula_11 כך ש-formula_15 מזה נובע formula_32. היא תקרא פרמוטציה חד-כיוונית אם עבור כל formula_14 הפונקציה formula_29 היא חד-חד-ערכית ועל.
בניגוד לפונקציה חד-כיוונית בפרמוטציה חד-כיוונית עבור כל formula_2 קיים רק מקור formula_1 יחיד לכן formula_5. המשמעות היא ש-formula_2 למעשה מכיל מידע לגבי formula_1 ולמרות זאת עדיין קשה למצוא אותו.
משפחה של פונקציות חד-כיווניות.
ההגדרה של פונקציה או תמורה חד-כיוונית לא מטיבה לתאר את הפונקציות או התמורות החד-כיווניות המועמדות בפועל, כי היא מדברת על פונקציה יחידה מעל מקור ותמונה אין סופיים. הגדרה יותר קולעת היא שקיים אלגוריתם המפיק פרמטר formula_40 כלשהו המגדיר פונקציה/תמורה כלשהי formula_41 מעל מקור כלשהו formula_42, כך שהיא תהיה חד-כיוונית כמעט לגמרי למעט הסתברות זניחה מעל formula_40. מפני שכל ערך של formula_40 מגדיר פונקציה אחרת אפשר להתייחס אליה כאל "משפחה" של פונקציות/תמורות חד-כיווניות. ההגדרה כעת בניסוח פורמלי היא, השלישייה formula_45 המייצגת אלגוריתם פולינומי הסתברותי, נקראת משפחה של פונקציות אם:
באופן דומה כדי לקבל הגדרה של משפחה של תמורות, ההבדלים הם שבתמורות formula_59 והפונקציה formula_41 היא חד-חד-ערכית ועל. היתר זהה. כעת הניסוי formula_61 משתנה בהתאם:
פונקציה חד-כיוונית במובן החלש.
ניתן להגדיר פונקציה חד-כיוונית במובן חלש, שהא פונקציה הניתנת לחישוב בזמן פולינומי, והעונה לתנאי הבא:
ניתן להראות שקיומה של פונקציה חד-כיוונית במובן החלש מעיד על קיומה של פונקציה חד-כיוונית במובן החזק, כלומר, בעזרת פונקציה formula_11 חד-כיוונית במובן חלש, ניתן לבנות פונקציה formula_76 חד-כיוונית במובן החזק.
פונקציה חד-כיוונית עם דלת צונחת.
פונקציה חד-כיוונית עם דלת צונחת (באנגלית: trapdoor one-way function), היא פונקציה חד-כיוונית שקל לחשבה בכיוון אחד אך קשה לחשבה בכיוון ההפוך אלא אם כן קיים מידע נוסף הנקרא "דלת צונחת" שמאפשר לחשב את הפונקציה ההופכית בקלות. בניסוח פורמלי, הפונקציה formula_9 קלה לחשוב בעוד שהפונקציה formula_78 קשה מאוד לביצוע ללא הרמז הנוסף. המידע הנוסף נקרא בהקשר זה מפתח פענוח.
דוגמה קלאסית לפונקציה עם דלת צונחת היא מציאת שורש ריבועי מודולו מספר פריק שהוא כפולה של שני ראשוניים גדולים. העלאה בריבוע של מספר גדול היא פעולה קלה במחשב, בעוד שהפעולה ההפוכה קשה, לא קיים אלגוריתם יעיל לחישוב שורש ריבועי מודולו מספר פריק. לעומת זאת קיימים אלגוריתמים לחישוב שורש ריבועי מודולו מספר ראשוני. אם ידועים הגורמים הראשוניים של המודולוס אפשר לחשב תחילה את השורשים הריבועים של המספר מודולו כל אחד מהגורמים ואז לחלץ מזה ארבעה פתרונות אפשריים מודולו המספר הפריק. במקרה זה, ידיעת הגורמים הראשוניים של המודולוס מאפשרת לבצע את הפעולה ההפוכה, קרי הוצאת שורש בקלות. לכן הגורמים הראשוניים של המודולוס נחשבים מהיבט זה דלת צונחת. רק מי שיודע מה הם הגורמים הראשוניים יכול לפתור את הבעיה בקלות.
המונח דלת צונחת הוטבע לראשונה על ידי ויטפילד דיפי ומרטין הלמן במאמרם משנת 1976 "כיוונים חדשים בהצפנה". מאז הוצעו מועמדים רבים לפונקציה חד-כיוונית עם דלת צונחת. קיים מגוון בעיות מתמטיות קשות לא בהכרח מתורת המספרים שאפשר לבסס עליהן פונקציה חד-כיוונית. לדוגמה בעיית מציאת הווקטור הקצר ביותר בתורת הסריגים. אולם המכשול העיקרי הוא שכאשר מוסיפים דלת צונחת, הבעיה הופכת בעצם למקרה פרטי של הבעיה הכללית ואין הוכחה שהיא נותרת קשה לפתרון כמו הבעיה הכללית ולא הוחדרו חולשות כלשהן מבלי משים. מקרה אחד מעניין הוא הצפנת תרמיל. לאחר מחקר של שנים הסתבר שכל הניסיונות לייצר פונקציה חד-כיוונית עם דלת צונחת המבוססת על בעיית התרמיל, כשלו. למרות חשיבותה הרבה בקריפטוגרפיה קשה מאוד למצוא פונקציה חד-כיוונית עם דלת צונחת שהיא גם יעילה וגם בטוחה.
קיימות כמה משפחות של מועמדים לפונקציות חד-כיווניות עם דלת צונחת שההשערה לגביהן שהן בטוחות:
מועמדים לפונקציה חד-כיוונית.
קיומן של פונקציות חד-כיווניות מחייב שקיימות בעיות חישוביות אשר שייכות ל-NP ואינן שייכות ל-BPP (מחלקת הבעיות אשר ניתנות לפתרון בזמן ריצה פולינומי עם אלגוריתמים אקראיים), מאחר שלא ידוע האם formula_79 (שאלה חזקה יותר, ומפורסמת יותר, היא האם P=NP), לא ניתן להצביע על קיומן של פונקציות כאלה. יתר על כן, ייתכן ש-formula_80, ובכל זאת לא יהיו קיימות פונקציות חד כיווניות. (כיוון שנדרש מהן שהיפוכן קשה במקרה הממוצע ולא רק במקרה הקשה). דרך פרקטית להגדיר פונקציה חד-כיוונית היא פונקציה חד-כיוונית חישובית המבוססת על ההשערה שלא קיים אלגוריתם פולינומי המסוגל להפוך אותה ביעילות.
הדוגמה הטובה ביותר היא בעיית פירוק לגורמים ראשוניים של מספר שלם, שהיא מקור טוב לפונקציה חד-כיוונית בהנחה שפירוק לגורמים היא בעיה מעשית קשה. מצד אחד בהינתן שני מספרים שלמים פונקציית הכפל שלהם קלה, מצד שני בהינתן מספר אי-זוגי שהוא כפולה של שני מספרים ראשוניים גדולים, מציאת הגורמים הראשוניים שלו היא בעיה קשה. יש לשים לב שלא תמיד הבעיה קשה, אם formula_14 זוגי או שגורמיו קטנים קל להפוך את הפונקציה. הצפנת RSA מבוססת על הנחה זו.
דוגמה אחרת היא בעיית תרמיל הגב שאינה קשורה ישירות לתורת המספרים שידועה כבעיה NP-קשה עליה מבוססת הצפנת תרמיל. נתונה סדרה של formula_14 שלמים formula_83 לא בהכרח בסדר עולה ונתון שלם formula_84 כלשהו, בעיית התרמיל היא למצוא תת-סדרה של formula_85 שסכומה הוא formula_84. החד כיווניות נובעת מהעובדה שבעוד שבחירת תת-סדרה וחישוב סכומה היא משימה קלה, הרי שבכיוון ההפוך בהינתן ערך כלשהו, מציאת תת-הסדרה שסכומה שווה לערך זה בדיוק, היא משימה קשה. אין זו הוכחה ש-formula_87 וזה לא מעיד בהכרח שפונקציה חד-כיוונית קיימת, אלא שבעיית התרמיל לא ניתנת לפתרון במקרה הגרוע בזמן פולינומי, בעוד שפונקציה חד-כיוונית נדרשת שתהיה בלתי הפיכה "כמעט תמיד". הטענה שפונקציית תרמיל-הגב האמורה חד-כיוונית מסתמכת רק על כך שלא ידוע על אלגוריתם טוב הפותר את הבעיה בזמן פולינומי ולא על ההנחה שהבעיה הכללית היא NP-קשה.
כיום ידוע שלבעיית התרמיל קשר הדוק לתורת הסריגים. למעשה כל אלגוריתם שפותר את בעיית הווקטור הקצר ביותר יכול לשמש לפתרון בעיית התרמיל. למשל אלגוריתם LLL נחשב לאלגוריתם הטוב ביותר לפתרון בעיות בתורת הסריגים. אלגוריתם זה למעשה היה בסיס להתקפה קריפטוגרפית על כמה מערכות ההצפנה שהתבססו על בעיית התרמיל.
שימושים.
הצפנת מפתח ציבורי.
הצפנה בשיטת מפתח ציבורי שמכונה גם הצפנה א-סימטרית, היא בעצם פונקציה חד-כיוונית עם דלת צונחת. לפונקציות אלה התכונה שישנו מידע אשר ידוע רק לנמען המורשה של ההודעה (המפתח הפרטי) שבעזרתו קל לחשב את הפונקציה ההופכית, כלומר לבצע את פענוח ההודעה המוצפנת. מי שאין בידו המידע הזה ומנסה לפענח את ההודעה המוצפנת, עומדת לפניו משימה חישובית קשה מאוד. אלגוריתם RSA הנזכר לעיל עושה שימוש בפונקציה מסוג זה.
העברת סיסמה מוצפנת.
מקובל להשתמש בפונקציית גיבוב חד-כיוונית כדי להעביר סיסמה למחשב המאמת (השרת). דוגמה: השרת המאמת שולח משפט למחשב ברשת, זה האחרון לוקח את המשפט, מוסיף אליו את הסיסמה לאימות ומעביר אותם לפונקציית גיבוב חד-כיוונית. את הפלט (המהווה הסיסמה המוצפנת) הוא שולח לשרת. השרת מבצע את אותה הפעולה בדיוק. אם שני הפלטים זהים - יאשר השרת כי הסיסמה נכונה.
משפט אוריסון
בטופולוגיה, מרחבים מטריים עומדים בראש הפירמידה של המרחבים הטופולוגיים, כמעט בכל היבט של התאוריה. משפט אוריסון (על שם פאבל סמואילוביץ' אוריסון), הידוע גם כמשפט המטריזביליזציה, אומר שמרחבים טופולוגיים המקיימים שתי תכונות חזקות במיוחד, הם בעצם מרחבים מטריים:
באופן כללי יותר, המשפט (עם אותה הוכחה) מראה שכל מרחב רגולרי המקיים את אקסיומת המנייה השנייה הוא מרחב סמי-מטרי.
מעבר לזה, המשפט מראה שמרחבי T3 (ובפרט, מרחבי האוסדורף קומפקטיים) בעלי בסיס בן מנייה הם תת-מרחבים של מרחב הסדרות formula_1, ובכך הוא מבסס את המרכזיות של המרחב האחרון בטופולוגיה ובאנליזה פונקציונלית.
הוכחה.
בניית השיכון.
המרחב שלנו מקיים את תכונת המנייה השנייה, ולכן יש לטופולוגיה שלו בסיס בן מנייה. כל נקודה formula_3 במרחב X שייכת לאיבר של הבסיס, formula_4. בנוסף לזה, בגלל הרגולריות, קיים איבר בסיס formula_5 כך ש formula_6. לפי הלמה של אוריסון (למרחבים נורמליים), קיימת פונקציית אוריסון formula_7 כך ש formula_8 ו formula_9. את הפונקציות formula_10 אפשר לסדר, ולסמן formula_11, לשם הפשטות.
כעת נגדיר formula_12
באמצעות הנוסחה formula_13. פונקציה זו היא ההומאומורפיזם המבוקש.
בדיקות לגבי G.
נותר להוכיח ש:
1) הפונקציה G מוגדרת היטב שכן לכל x,
ולכן formula_15. מכאן ש G מוגדרת היטב.