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

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

לפונקציה פסידו-אקראית חשיבות רבה בקריפטוגרפיה והיא מאבני הבניין של ההצפנה מודרנית, באמצעותה ניתן לבנות פרימיטיבים קריפטוגרפיים וסכמות הצפנה בטוחות. מהיבט תאורטי, הוכח שאפשר לבנות פונקציה פסידו-אקראית באמצעות מחולל פסידו אקראי קריפטוגרפי,^[1] אולם הפרימיטיבים הקריפטוגרפיים הקיימים בשימוש מעשי כיום אינם מוכחים אלא מאמינים שהם מועמדים טובים לפונקציה פסידו-אקראית. לדוגמה צופן סימטרי כמו 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. במקרה זה קיימות שתי דרישות נוספות:

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

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

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

בשנת 1986 הראו עודד גולדרייך, שפי גולדווסר וסילביו מיקלי^[2] כיצד ניתן לבנות פונקציה פסידו-אקראית $f:n\to k$ אם נתון מחולל פסידו אקראי $G$ כך שהפלט של המחולל $G$ יהיה באורך כפול מגרעין האקראיות (seed) המוזן למחולל.^[1] הרעיון העומד מאחורי הבניה הוא להפעיל את המחולל שוב ושוב - בכל הפעלה כזו יתקבל פלט הארוך פי שניים מהקלט אל המחולל. חוזרים על הפעולה עד אשר מתקבל פלט באורך $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 הציעו מיכאל לובי וצ'ארלס ראקוף שיטה^[3] בה ניתן להשתמש בפונקציה פסידו-אקראית על מנת לבנות צופן בלוקים הבטוח כנגד התקפת גלוי-נבחר (Chosen Plaintext Attack). השיטה מבוססת על מבנה פייסטל תלת-שלבי. באופן מפתיע, מבנה דומה בעל 2 שלבים בלבד אינו מספיק על-מנת ליצור סכמה בטוחה.

ראו גם

הערות שוליים

^ ^1.0 ^1.1 עודד גולדרייך, שפי גולדווסר וסילביו מיקאלי, How to construct pseudorandom functions
^ Goldreich, Oded; Goldwasser, Shafi; Micali, Silvio (October 1986). "How to Construct Random Functions" (PDF). Journal of the ACM. 33 (4,): 792–807. doi:10.1145/6490.6503. web page and preprint
^ Michael Luby, Charles Rackoff. "How to construct pseudo-random permutations from pseudo-random functions", 1985. [1] [2]

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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

[GGM-1] 1.0 ^1.1 עודד גולדרייך, שפי גולדווסר וסילביו מיקאלי, How to construct pseudorandom functions

[2] Goldreich, Oded; Goldwasser, Shafi; Micali, Silvio (October 1986). "How to Construct Random Functions" (PDF). Journal of the ACM. 33 (4,): 792–807. doi:10.1145/6490.6503. web page and preprint

[3] Michael Luby, Charles Rackoff. "How to construct pseudo-random permutations from pseudo-random functions", 1985. [1] [2]

[1]

[2]

[3]