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

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

אורקל אקראי

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

מבחין

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

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

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

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

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