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

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

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

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

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

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

הגדרה

תהי $f:\{0,1{\}}^{*}⟶\{0,1{\}}^{*}$ פונקציה המקבלת קלט באורך כלשהו מבצעת חישוב מסוים ומחזירה פלט באורך כלשהו (המיוצג על ידי הכוכבית). נניח שנתון אלגוריתם ${𝒜}$ ושלם כלשהו $n$ המשמש כפרמטר ביטחון. הניסוי הבא המסומן על ידי ${\text{Invert}}_{{𝒜},f}(n)$ מתואר כך:

1. בוחרים את הקלט $x⟵\{0,1{\}}^n$ ומחשבים את $y=f(x)$.
2. האלגוריתם ${𝒜}$ מקבל כקלט את $n$ ואת $y$ ומפיק את $x^{\prime }$.
3. תוצאת הניסוי תהיה '1' (המייצג הצלחה) אם $f(x^{\prime })=y$ אחרת התוצאה היא '0'.

יש לשים לב שהניסוי $\text{Invert}$ לא חייב למצוא את $x$ אלא כל ערך שיקיים את התנאי המבוקש. הדרישה שהאלגוריתם ${𝒜}$ יקבל גם את $n$ אינה הכרחית אולם הרעיון הוא לאפשר לאלגוריתם לרוץ בזמן פולינומי ביחס לפרמטר הביטחון ללא תלות ב-$y$. לסיכום הפונקציה תקרא חד-כיוונית אם מתקיימים התנאים הבאים:

1. $f$ ניתנת לחישוב בזמן פולינומי.
2. לכל מכונה היסתברותית פולינומית ${𝒜}$ ופונקציה $\text{negl}(n)$ הנקראת פונקציית זניחות, עבור קלטים באורך $n$ כלומר $x\in \{0,1{\}}^n$, מתקיים $\mathrm{Pr}[{\text{Invert}}_{{𝒜},f}(n)=1]\le \text{negl}(n)$ או בצורה כללית יותר:

:$\underset{x\leftarrow \{0,1{\}}^n}{\mathrm{Pr}}[{𝒜}(f(x))\in f^{-1}(f(x))]\le \text{negl}(n)$

הסבר

התנאי הראשון קובע שהפונקציה קלה לחישוב. כלומר בעלת סיבוכיות פולינומית. התנאי השני מהוה את עיקר ההגדרה, הוא קובע שלכל יריב בעל עוצמת חישוב פולינומית לכל היותר, סיכויו זניח להצליח "להפוך" את הפונקציה. אם ליריב ידוע $f(x)$ הסיכוי שיימצא את $y$ כך ש-$y=f(x)$ זניח. יש לשים לב כי ייתכן שישנם קלטים נוספים הממופים על ידי $f$ לאותו ערך. לכן היריב נדרש למצוא אחד מהם $y\in f^{-1}(f(x))$ ולאו דווקא את הערך המקורי $x$.

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

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

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

לעיתים יש צורך בפונקציה חד-כיוונית עם תכונה מבנית נוספת. אם הפונקציה משמרת אורך כלומר $|f(x)|=|x|$ עבור כל $x$ והפונקציה היא חד-חד-ערכית ועל היא נקראת פרמוטציה (תמורה). בניסוח פורמלי:

תהי פונקציה חד-כיוונית $f:\{0,1{\}}^{*}⟶\{0,1{\}}^{*}$ משמרת אורך, ונניח ש-$f_n$ מגבילה את התחום של $f$ כך ש-$x\in \{0,1{\}}^n$ מזה נובע $f_n(x)=f(x)$. היא תקרא פרמוטציה חד-כיוונית אם עבור כל $n$ הפונקציה $f_n$ היא חד-חד-ערכית ועל.

בניגוד לפונקציה חד-כיוונית בפרמוטציה חד-כיוונית עבור כל $y$ קיים רק מקור $x$ יחיד לכן $x=f^{-1}(y)$. המשמעות היא ש-$y$ למעשה מכיל מידע לגבי $x$ ולמרות זאת עדיין קשה למצוא אותו.

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

ההגדרה של פונקציה או תמורה חד-כיוונית לא מטיבה לתאר את הפונקציות או התמורות החד-כיווניות המועמדות בפועל, כי היא מדברת על פונקציה יחידה מעל מקור ותמונה אין סופיים. הגדרה יותר קולעת היא שקיים אלגוריתם המפיק פרמטר $I$ כלשהו המגדיר פונקציה/תמורה כלשהי $f_I$ מעל מקור כלשהו ${{𝒟}}_I$, כך שהיא תהיה חד-כיוונית כעמט לגמרי למעט היסתברות זניחה מעל $I$. בגלל שכל ערך של $I$ מגדיר פונקציה אחרת אפשר להתייחס אליה כאל "משפחה" של פונקציות/תמורות חד-כיווניות. ההגדרה כעת בניסוח פורמלי היא, השלישייה $\mathrm{\Pi }=(\text{Gen},\text{Samp},f)$ המייצגת אלגוריתם פולינומי היסתברותי, נקראת משפחה של פונקציות אם:

1. אלגוריתם ההכנה Gen מפיק פרמטר $I$ כך שמתקיים $|I|\ge n$ שמגדיר את המקור ${{𝒟}}_I$ ותמונה ${{ℛ}}_I$ של הפונקציה $f_I$ המוגדרת להלן.
2. אלגוריתם הדגימה Samp פולט בהינתן $I$ אלמנט מתוך ${{𝒟}}_I$ בהיתפלגות אחידה למעט היסתברות זניחה ביחס ל-$|I|$
3. אלגוריתם ההערכה $f$, בהינתן $I$ ו-$x\in {{𝒟}}_I$ פולט את האלמנט $y\in {{ℛ}}_I$. מציינים זאת על ידי $y=f_I(x)$.

באופן דומה כדי לקבל הגדרה של משפחה של תמורות, ההבדלים הם שבתמורות ${𝒟}={ℛ}$ והפונקציה $f_I$ היא חד-חד-ערכית ועל. היתר זהה. כעת הניסוי ${\text{Invert}}_{{𝒜},\mathrm{\Pi }}(n)$ משתנה בהתאם:

1. תחילה מריצים את Gen כדי להפיק את $I$ ואז את הפונקציה $\text{Samp}(I)$ כדי לקבל את $x\in {{𝒟}}_I$ ואז מחשבים את $y=f_I(x)$.
2. האלגוריתם ${𝒜}$ מקבל את $I$ ואת $y$ ומפיק את $x^{\prime }$.
3. תוצאת הניסוי היא '1' אם $f_I(x^{\prime })=y$.

פונקציה חד-כיוונית במובן החלש

ניתן להגדיר פונקציה חד-כיוונית במובן חלש, שהא פונקציה הניתנת לחישוב בזמן פולינומי, והעונה לתנאי הבא:

• לכל מכונת-טיורינג מטילת מטבעות $A$ ולכל קבוע $c$, עבור קלטים ארוכים מספיק $x\in \{0,1{\}}^n$, מתקיים, $\mathrm{Pr}[A(f(x))=f^{-1}(f(x))]<1-\frac{1}{n^c}$.

ניתן להראות שקיומה של פונקציה חד-כיוונית במובן החלש מעיד על קיומה של פונקציה חד-כיוונית במובן החזק, כלומר, בעזרת פונקציה $f$ חד-כיוונית במובן חלש, ניתן לבנות פונקציה $F$ חד-כיוונית במובן החזק^{[דרוש מקור]}.

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

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

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

דוגמה אחרת היא בעיית תרמיל הגב שאינה קשורה ישירות לתורת המספרים שידועה כבעיה NP-קשה עליה מבוססת הצפנת תרמיל. נתונה סדרה של $n$ שלמים $A=(a_1,a_2,...,a_n)$ לא בהכרח בסדר עולה ונתון שלם $s$ כלשהו, בעיית התרמיל היא למצוא תת-סדרה של $A$ שסכומה הוא $s$. החד כיווניות נובעת מהעובדה שבעוד שבחירת תת-סדרה וחישוב סכומה היא משימה קלה, הרי שבכיוון ההפוך בהינתן ערך כלשהו, מציאת תת-הסדרה שסכומה שווה לערך זה בדיוק, היא משימה קשה. יש לציין שאין זו הוכחה ש-$P\ne NP$ וזה לא מעיד בהכרח שפונקציה חד-כיוונית קיימת, אלא שבעיית התרמיל לא ניתנת לפתרון בקרה הגרוע בזמן פולינומי, בעוד שפונקציה חד-כיוונית נדרשת שתהיה בלתי הפיכה "כמעט תמיד". הטענה שפונקציית תרמיל-הגב האמורה חד-כיוונית מסתמכת רק על כך שלא ידוע על אלגוריתם טוב הפותר את הבעיה בזמן פולינומי ולא על ההנחה שהבעיה הכללית היא NP-קשה.

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

שימושים

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

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

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

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

ראו גם

• סיבית קשה של פונקציה חד-כיוונית
• פונקציית גיבוב קריפטוגרפית
• קריפטוגרפיה
• הנדסה לאחור

לקריאה נוספת

• Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. פרקים מהספר באתר המחבר
• Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography.