בקריפטוגרפיה, תְּמוּרָה פְּסֵאוֹדוֹ-אקראית (Pseudorandom Permutation) בקיצור PRP היא פונקציה שלא ניתן להבחין בינה לבין תמורה אקראית שנבחרה בהתפלגות אחידה מתוך משפחת כל התמורות בעלות תחום דומה^[1]. במילים אחרות PRP היא משפחה של תמורות המדמות אורקל אקראי באופן שלא קיים אלגוריתם יעיל שיכול להבחין עם יתרון משמעותי לפי הפלט, בין תמורה שנבחרה ממשפחה זו לבין תמורה אקראית. ההבדל היחיד בין תמורה פסאודו-אקראית לפונקציה פסאודו-אקראית הוא שבתמורה תמיד קיימת פונקציה הופכית.

אובייקט תאורטי דומה נקרא תמורה בלתי צפויה (unpredictable permutation) בקיצור UP. על בסיס פונקציה בלתי צפויה, תמורה בלתי צפויה היא תמורה שלא קיים אלגוריתם אקראי יעיל שיכול לחזות את ערכיה בדיוק גבוה באופן משמעותי מניחוש אקראי^[2].

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

תהי ${\displaystyle P:\{0,1\}^{*}\times \{0,1\}^{*}\longrightarrow \{0,1\}^{*}}$ פונקציה יעילה, משמרת-אורך, עם מפתח. אפשר להתייחס אל ${\displaystyle P}$ כאל משפחה של תמורות, למשל הפונקציה ${\displaystyle P_{k}(\cdot )}$ היא תמורה אחת מתוך המשפחה, כך שעבור כל ${\displaystyle k}$ שנבחר באקראי ${\displaystyle P_{k}}$ היא תמורה עם מפתח של הקלט. כיוון שאורך הפלט זהה לאורך הקלט, מזה נובע שהיא חד-חד-ערכית ועל. היא נקראת יעילה אם קיים אלגוריתם יעיל שיכול להריץ את ${\displaystyle P_{k}(x)}$ בזמן פולינומי בהינתן ${\displaystyle x}$ ו-${\displaystyle k}$ וכן קיים אלגוריתם יעיל שיכול לחשב את התמורה ההופכית ${\displaystyle P_{k}^{-1}(y)}$ בהינתן ${\displaystyle y}$ ו-${\displaystyle k}$. ההנחה המשתמעת מכאן שאורכי הקלט, הפלט והמפתח זהים אינה בהכרח מדויקת תמיד. למעשה הפלט חייב להיות כאורך הקלט אחרת היא לא תקרא תמורה, אולם המפתח יכול להיות באורך שונה. נהוג לכנות את אורך הקלט והפלט "בלוק" שאורכו הוא ${\displaystyle n}$ סיביות. וכן ${\displaystyle n}$ נקרא פרמטר ביטחון.

בדומה לפונקציה פסאודו-אקראית, כדי שהתמורה ${\displaystyle P_{k}}$ תקרא פסאודו-אקראית היא צריכה להיות בלתי ניתנת להבחנה מתמורה אקראית באורך זהה. למעשה ההבדל בין פונקציה פסאודו-אקראית לבין תמורה פסאודו-אקראית אינו גדול כי תמורה ופונקציה באורך זהה ניראות גם ככה דומות ולא ניתן לזהות הבדל ביניהן אלא אם כן מוצאים שני ערכים ${\displaystyle x}$ ו-${\displaystyle x'}$ כך שמתקיים ${\displaystyle f(x)=f(x')}$ שאז אנחנו יודעים שהיא אינה תמורה. אולם ההסתברות שימצאו שני ערכים כאלה בזמן פולינומי כאשר ${\displaystyle n}$ גדול, זניחה.

למעשה הטענה הבאה נכונה: אם ${\displaystyle P}$ היא פרמוטציה פסאודו-אקראית אז היא גם פונקציה פסאודו-אקראית. אך מפני שבכל תמורה ${\displaystyle P_{k}}$ מחייבת שתהיה גם פונקציה הופכית ${\displaystyle P_{k}^{-1}}$, עובדה זו יוצרת בעיה שלא קיימת בפונקציה פסאודו-אקראית, כי כעת צריך לוודא שהתמורה תהיה בטוחה גם אם למבחין גישה לאורקל הפונקציה ההופכית. מעצם ההגדרה של פונקציה פסאודו-אקראית לא בהכרח קיימת פונקציה הופכית. אם התמורה ${\displaystyle P}$ היא בעלת תכונה כזו היא תקרא תמורה פסאודו-אקראית חזקה. בניסוח פורמלי:

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

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

תמורה בלתי צפויה היא הגדרה קצת יותר חלשה מתמורה פסאודו-אקראית. היריב במקרה של תמורה בלתי צפויה הוא אלגוריתם הסתברותי שמקבל גישה לאורקל לשני הכיוונים, התמורה ${\displaystyle P_{k}}$ והתמורה ההופכית ${\displaystyle P_{k}^{-1}}$. היריב מקבל אתגר ${\displaystyle k}$ והוא מתבקש לנחש מה יהיה פלט הפונקציה ${\displaystyle P_{k}}$. הוא רשאי לבצע סדרה של שאילתות לאורקל למעט שאילתה בנוגע ל-${\displaystyle k}$.

אלגוריתם אקראי פולינומי ייקרא תמורה בלתי צפויה אם עבור כל מבחין הסתברותי פולינומי ${\displaystyle A}$ שלא רשאי להגיש לאורקל שאילתה בנוגע לתחזית עצמה (התמורה), קיימת פונקציית זניחות כך שמתקיים:

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

לדוגמה, רשת פייסטל היא מבנה קריפטוגרפי פופולרי, שמקבל פונקציה חד-כיוונית לא הפיכה וממנה מייצר תמורה הפיכה עם מפתח. רשת פייסטל היא מבנה איטרטיבי הפועל כדלהלן. הקלט באורך ${\displaystyle 2n}$ סיביות מחולק לשני חצאים ${\displaystyle R}$ ו-${\displaystyle L}$ (חצי ימני וחצי שמאלי בהתאמה) כל אחד באורך ${\displaystyle n}$ סיביות, בהינתן פונקציה פסאודו-אקראית ${\displaystyle f}$ שמקבלת את ${\displaystyle k}$ וקלט באורך ${\displaystyle n}$ ומחזירה פלט פסאודו-אקראי באורך ${\displaystyle n}$ מבנה פייסטל מתבצע כך:

ברור שבמהלך הראשון המבנה המתואר אינו פסאודו-אקראי אפילו ש-${\displaystyle f}$ פסאודו-אקראית כי החצי השמאלי הוא למעשה חצי הקלט הימני ללא שינוי. וכן במהלך השני אפשר להראות שהפלט אינו פסאודו-אקראי כי קיים אלגוריתם פולינומי שיכול להבחין בינו לבין פלט אקראי. יש לזכור שבכל מהלך צריך מפתח שונה ובלתי תלוי במפתחות הקודמים. למרבה ההפתעה רשת פייסטל בשלושה מהלכים עם שלושה מפתחות שונים, נחשבת לפסאודו-אקראית אך לא פסאודו-אקראית חזקה. לעומת זאת הוכח שרשת פייסטל בארבעה מהלכים עם ארבעה מפתחות שונים נחשבת לתמורה פסאודו-אקראית חזקה, בהנחה שהפונקציה הפנימית נחשבת פסאודו-אקראית^[3].

צריך לזכור שצופן בלוקים כשלעצמו אינו בטוח לשימוש לבד, אלא הוא רק "אבן בניין" שאיתה ניתן לבנות מערכת הצפנה בטוחה. לצורך המחשה, אם משתמשים בצופן בלוקים ישירות במערכת הצפנה, למשל המצפין שולח את ${\displaystyle c=P_{k}(m)}$ למקבל, כאשר ${\displaystyle P_{k}}$ הוא צופן בלוקים שמקבל את המפתח ${\displaystyle k}$ איתו הוא מצפין את ${\displaystyle m}$ ומחזיר את ${\displaystyle c}$ (למשל AES). אפשר להוכיח שמערכת כזו לא תהיה עמידה נגד התקפת מוצפן-נבחר, מפני שהצפנה כזו היא דטרמיניסטית באופייה ולכן המתקיף יכול להבחין בקלות אם הוצפנו בלוקים זהים עם אותו מפתח. הבחנה זו חשובה ולא תמיד מושם עליה דגש כראוי. אחת הדרכים להתמודד עם חיסרון זה היא להשתמש בצופן הבלוקים במסגרת מצב הפעלה בטוח. קיימים מצבי הפעלה שונים של צופן בלוקים הכוללים בין היתר הצפנה מאומתת, כשכל אחד מהם מספק ביטחון בדרך שונה ובעל מאפיינים שונים בהתאם לסביבה, מידת האיום ואילוצי יעילות. במערכות הצפנה מודרניות נהוג לשלב אקראיות כדי לעמוד במודלים של ביטחון מחמירים יותר.

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