פונקציה פסאודו-אקראית

בקריפטוגרפיה, פוּנְקְצִיָּה פסאודו-אַקְרָאִית (באנגלית: Pseudo-random function) בקיצור PRF היא משפחה של פונקציות המדמות אורקל ראנדומלי באופן שלא קיים אלגוריתם יעיל שיכול להבחין עם יתרון משמעותי, בין פונקציה שנבחרה ממשפחה זו לבין אורקל אקראי אמיתי. היא נקראת כך משום שהיא אינה אקראית אמיתית אלא "מעין" אקראית או אקראית מדומה.

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

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

מבוא והגדרה

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

$F:\{0,1\}^{*}\times \{0,1\}^{*}\longrightarrow \{0,1\}^{*}$

נניח שהקלט הראשון נקרא "המפתח" ומסומן באות $k$, באופן כללי אם קובעים את $k$ מתקבלת "פונקציה עם מפתח" שמקבלת קלט באורך כלשהו ומחזירה פלט באורך כלשהו, כל מפתח מגדיר פונקציה אחרת ממשפחה של פונקציות. עבור מפתח קבוע הפונקציה היחידה $F_{k}:\{0,1\}^{*}\rightarrow \{0,1\}^{*}$ המסומנת בקיצור $F_{k}(x)$ מוגדרת רק בהינתן הפרמטר $k$. ללא הגבלת הכלליות, נניח שהפונקציה משמרת אורך כלומר היא חד-חד-ערכית ועל והמפתח, הקלט והפלט הם באורך $n$ סיביות, בניסוח פורמלי $|F_{k}(x)|=|x|=|k|$, אם כי זה לא חובה. וכן חשוב לציין שהפונקציה חייבת להיות "יעילה", כלומר שניתנת לריצה בזמן פולינומי. וכן הפרמטר $k$ נבחר באקראי, מסמנים זאת $k\leftarrow \{0,1\}^{n}$ כאשר $n$ הוא פרמטר ביטחון המייצג את אורך הקלט והפלט והמפתח בסיביות.

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

מנקודת ראות מתמטית, נניח שנתונה קבוצה סופית ${\text{Fnc}}_{n}$ המכילה אוסף של כל הפונקציות הממפות מחרוזות של $n$-סיביות למחרוזות של $n$-סיביות. בחירת פונקציה אחת מהאוסף באופן אקראי מקבילה לדגימה של אלמנט אקראי בהתפלגות אחידה מתוך קבוצה של אלמנטים. אפשר להמחיש זאת בדרך הבאה: נתונות טבלאות חיפוש גדולות שבהן בשורה $x$ בטבלה מאוחסן הערך $f(x)$. עבור כל פונקציה $f$ מתאימה טבלת חיפוש אחת שבה בדיוק $2^{n}$ שורות, אחת עבור כל נקודה בתחום $\{0,1\}^{n}$, כל שורה מכילה מחרוזת באורך $n$ סיביות ובסך הכול גודלה של הטבלה הוא $n\cdot 2^{n}$ סיביות. למעשה אפשר לראות שהפונקציות בקבוצה ${\text{Fnc}}_{n}$ מתאימות אחד-לאחד לטבלאות החיפוש. לכן גודלה של ${\text{Fnc}}_{n}$ הוא בדיוק $2^{n\cdot 2^{n}}$ מחרוזות באורך $n\cdot 2^{n}$. ההתפלגות של הפונקציה $f\in {\text{Fnc}}_{n}$ היא מעל $2^{n\cdot 2^{n}}$ פונקציות ואילו ההתפלגות של $F_{k}$ היא מעל $2^{n}$ פונקציות שונות לכל היותר ולמרות "התנהגות" זו, הן צריכות להראות על פניהן זהות בהתפלגותן עבור כל אלגוריתם הבחנה פולינומי.

לצורך המחשה במקרה ש-$n=2$, ישנן $2^{2}=4$ אפשרויות שונות של קלט: $\{00,01,10,11\}$ ולכן קיימות בדיוק $2^{2\cdot 2^{2}}=256$ אפשרויות למפות 2 סיביות קלט לשתי סיביות פלט, אם בונים טבלה כזו גודלה הכולל יהיה בדיוק $2\cdot 2^{2}\cdot 256=2048$ סיביות. לעומת זאת הפונקציה $F_{k}$ עם מפתח באורך 2 סיביות, היא אחת מתוך ארבע פונקציות אפשריות בלבד, במילים אחרות יש רק ארבע אפשרויות שונות לבחירת מפתח באורך 2 סיביות. אם לא מגבילים את אורך המפתח, אז יש $4!=24$ תמורות אפשריות באורך 2 סיביות או 24 מפתחות שונים.

אורקל אקראי

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

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

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

מבחין

מבחין (Distinguisher) של פונקציה פסאודו-אקראית הוא כלי תאורטי המאפשר להגדיר פסאודו-אקראיות של פונקציה במונחים של ניסוי אינטראקטיבי. אלגוריתם הבחנה D מקבל כקלט את הפונקציה הנדונה ומחליט האם היא אקראית אמיתית או פסאודו-אקראית. היות שלמעשה התחום של משפחת הפונקציות מעריכי (בסדר גודל של $n\cdot 2^{n}$) לא ניתן להגדיר את D כאלגוריתם הבחנה פולינומי, כי אי אפשר לסרוק את כל הערכים האפשריים בזמן פולינומי. ההגדרה המקובלת היא אלגוריתם הסתברותי שיש לו גישה לאורקל אקראי. D רשאי להגיש לאורקל (מספר פולינומי של) שאילתות עבור נקודות שונות $x$ שיבחר והאורקל אמור להחזיר לו את $f(x)$ של הנקודה $x$. בגמר הניסוי אלגוריתם ההבחנה עונה "1" אם הקלט שלו הוא אחת הפונקציות מהמשפחה הפסאודו-אקראית, או "0" אחרת.

הגדרה פורמלית של פונקציה פסאודו-אקראית

תהי $F:\{0,1\}^{*}\times \{0,1\}^{*}\longrightarrow \{0,1\}^{*}$ פונקציה יעילה, הכוללת מפתח ומשמרת אורך. $F$ תקרא פסאודו-אקראית אם עבור כל אלגוריתם הבחנה פולינומי D קיימת פונקציית זניחות ${\text{negl}}$ כך שמתקיים:

$|\Pr[D^{F_{k}(\cdot )}(1^{n})=1]-\Pr[D^{f(\cdot )}(1^{n})=1]|\leq {\text{negl}}(n)$.

כאשר $k\leftarrow \{0,1\}^{n}$ נבחר בהתפלגות אחידה וכן $f$ היא פונקציה שנבחרה אקראית מקבוצת כל הפונקציות האפשריות הממפות מחרוזות של $n$ סיביות ל-$n$ סיביות.

-D יכול להתקשר עם האורקל בחופשיות, לכן הוא יכול לשאול שאלות באופן אדפטיבי ולהתאים את השאילתות על סמך תשובות קודמות. אולם ביכולתו לשאול רק מספר מוגבל של שאלות כי הוא כאמור רץ בזמן פולינומי. וכן חשוב לזכור ש-$k$ אינו ידוע ל-D, כי אין כל היגיון לדרוש ש-$F_{k}$ תהיה פסאודו-אקראית אם $k$ ידוע. כל מה שהמבחין צריך לעשות במקרה כזה הוא להגיש לאורקל שאילתה בנקודה אפס ($x=0$), לקבל את $y$ ולהשוות עם $y'=F_{k}(0)$ וסיכויי ההצלחה שלו במקרה כזה הם כמעט 1 כי הסיכוי ש-$y'=y$ במקרה של פונקציה אקראית אמיתית הוא $2^{-n}$. המשמעות היא שהטענה לפסאודו אקראיות תקפה רק באם $k$ סודי. וכן הטענה שקשה למצוא $x$ כך ש-$F_{k}(x)=0$ נכונה רק אם $k$ לא ידוע למבחין, אחרת אפשר להוכיח שקל למצוא קלט כזה.

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

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

תמורה (פרמוטציה) פסאודו-אקראית

ערך מורחב – תמורה פסאודו-אקראית

באופן שקול, ניתן להגדיר משפחה של תמורות הפסאודו אקראיות בקיצור PRP. במקרה זה קיימות שתי דרישות נוספות:

1. הפונציה $f$ נדרשת להיות $f:\{0,1\}^{n}\to \{0,1\}^{n}$
2. הפונקציה נדרשת להיות פרמוטציה.

בהגדרה זו, הקבוצה $U$ היא קבוצת כלל הפרמוטציות בגודל $n$ (קיימות $n!$ פונקציות כאלו).

בניית פונקציה פסאודו-אקראית עם מחולל פסאודו-אקראי

בשנת 1986 הראו עודד גולדרייך, שפי גולדווסר וסילביו מיקלי כיצד ניתן לבנות פונקציה פסאודו-אקראית $f:n\to k$ אם נתון מחולל פסאודו אקראי $G$ כך שהפלט של המחולל $G$ יהיה באורך כפול מגרעין האקראיות (seed) המוזן למחולל. הרעיון העומד מאחורי הבניה הוא להפעיל את המחולל שוב ושוב - בכל הפעלה כזו יתקבל פלט הארוך פי שניים מהקלט אל המחולל. חוזרים על הפעולה עד אשר מתקבל פלט באורך $k2^{n}$. כעת ניתן לחלק את פלט המחולל ל$2^{n}$ חלקים שווים, כל אחד באורך $k$. פלט הפונקציה הפסאודו-אקראית $f(x)$ הוא החלק שמספרו הסידורי הוא $x$. מכיוון שקיימים לכל היותר $2^{n}$ ערכי $x$ אפשריים, הרי שהפונקציה הפסאודו-אקראית מוגדרת היטב. אם ההפעלה החוזרת של המחולל מבוצעת בצורה יעילה (במבנה של עץ) מתקבל כי בנייה זו אפשרית בזמן פולינומי.

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

שימושים

בניית סכמת הצפנה על ידי פונקציה פסאודו-אקראית

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

על מנת להצפין את ההודעה $m$, מגרילים מספר כלשהו $i$ ושולחים את המידע $ENC_{k}(m)=(i,f_{k}(i)\oplus m)$.

מפתח ההצפנה $k$ קובע את הפונקציה $f_{k}(\cdot )$ הספציפית בה עושים שימוש, מבין כלל הפונקציות במשפחה $F$.

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

בשנת 1985 הציעו מיכאל לובי וצ'ארלס ראקוף שיטה בה ניתן להשתמש בפונקציה פסאודו-אקראית על מנת לבנות צופן בלוקים הבטוח כנגד התקפת גלוי-נבחר (Chosen Plaintext Attack). השיטה מבוססת על מבנה פייסטל תלת-שלבי. באופן מפתיע, מבנה דומה בעל 2 שלבים בלבד אינו מספיק על-מנת ליצור סכמה בטוחה.

ראו גם

• אקראיות
• מחולל מספרים פסאודו-אקראיים
• מחולל מספרים פסאודו-אקראיים קריפטוגרפי