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

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

הסבר

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

תמורה חד-כיוונית

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

מועמדים לפונקציה חד-כיוונית

קיומן של פונקציות חד-כיווניות מחייב שקיימות בעיות חישוביות אשר שייכות ל-NP ואינן שייכות ל-BPP (מחלקת הבעיות אשר ניתנות לפתרון בזמן ריצה פולינומי עם אלגוריתמים אקראיים), מאחר שלא ידוע האם  (שאלה מעט יותר חלשה, ומפורסמת יותר, היא האם P=NP), לא ניתן להצביע על קיומן של פונקציות כאלה. יתר על כן, ייתכן ש-, ובכל זאת לא יהיו קיימות פונקציות חד כיווניות. (כיוון שנדרש מהן שהיפוכן קשה במקרה הממוצע ולא רק במקרה הקשה). דרך פרקטית להגדיר פונקציה חד-כיוונית היא פונקציה חד-כיוונית חישובית המבוססת על ההשערה שלא קיים אלגוריתם פולינומי המסוגל להפוך אותה ביעילות.
הדוגמה הטובה ביותר היא בעיית פירוק לגורמים ראשוניים של מספר שלם, שהיא מקור טוב לפונקציה חד-כיוונית בהנחה שפירוק לגורמים היא בעיה מעשית קשה. מצד אחד בהינתן שני מספרים שלמים פונקציית הכפל שלהם קלה, מצד שני בהינתן מספר אי-זוגי שהוא כפולה של שני מספרים ראשוניים גדולים, מציאת הגורמים הראשוניים שלו היא בעיה קשה. יש לשים לב שלא תמיד הבעיה קשה, אם  זוגי או שגורמיו קטנים קל להפוך את הפונקציה. הצפנת RSA מבוססת על הנחה זו.
דוגמה אחרת היא בעיית תרמיל הגב שאינה קשורה ישירות לתורת המספרים שידועה כבעיה NP-קשה עליה מבוססת הצפנת תרמיל. נתונה סדרה של  שלמים  לא בהכרח בסדר עולה ונתון שלם  כלשהו, בעיית התרמיל היא למצוא תת-סדרה של  שסכומה הוא . החד כיווניות נובעת מהעובדה שבעוד שבחירת תת-סדרה וחישוב סכומה היא משימה קלה, הרי שבכיוון ההפוך בהינתן ערך כלשהו, מציאת תת-הסדרה שסכומה שווה לערך זה בדיוק, היא משימה קשה. אין זו הוכחה ש- וזה לא מעיד בהכרח שפונקציה חד-כיוונית קיימת, אלא שבעיית התרמיל לא ניתנת לפתרון במקרה הגרוע בזמן פולינומי, בעוד שפונקציה חד-כיוונית נדרשת שתהיה בלתי הפיכה "כמעט תמיד". הטענה שפונקציית תרמיל-הגב האמורה חד-כיוונית מסתמכת רק על כך שלא ידוע על אלגוריתם טוב הפותר את הבעיה בזמן פולינומי ולא על ההנחה שהבעיה הכללית היא NP-קשה.
כיום ידוע שלבעיית התרמיל קשר הדוק לתורת הסריגים. למעשה כל אלגוריתם שפותר את בעיית הווקטור הקצר ביותר יכול לשמש לפתרון בעיית התרמיל. למשל אלגוריתם LLL נחשב לאלגוריתם הטוב ביותר לפתרון בעיות בתורת הסריגים. אלגוריתם זה למעשה היה בסיס להתקפה קריפטוגרפית על כמה מערכות ההצפנה שהתבססו על בעיית התרמיל.

הצפנת מפתח ציבורי

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

העברת סיסמה מוצפנת

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