جایگشت شبه‌تصادفی

به جای گفتن جایگشت شبه تصادفی بهتر است از عبارت جایگشت‌های شبه تصادفی استفاده کنیم؛ زیرا جایگشت شبه تصادفی به یک عضو از یک خانواده جایگشت‌های شبه تصادفی اطلاق می‌شود و شبه تصادفی بودن آن به تنهایی بی‌معنی است. تعریف جایگشت‌های شبه تصادفی بسیار شبیه به تعریف توابع شبه تصادفی می‌باشد، با این تفاوت که توابع این خانواده، زیر مجموعه‌ای از توابع وارون پذیر اند. توجه کنیم که هر خانواده از جایگشت‌های شبه تصادفی، یک خانواده از توابع شبه تصادفی می‌باشد.

تعریف

فرض کنیم X مجموعه‌ای دلخواه باشد. خانواده همه جایگشتهای روی X را در نظر می‌گیریم. یک زیر مجموعه از این خانواده را شبه تصادفی گوییم هرگاه توابع آن به صورت کارایی محاسبه پذیر باشند و هیچ الگوریتم کارایی (که به همه جایگشتهای روی X دسترسی اراکلی دارد) نتواند با مزیت قابل توجهی، یک تابع ازاین خانواده را، از یک جایگشت تصادفی دلخواه روی X تمایز دهد.

کاربرها

از جایگشت‌های شبه تصادفی در سیستم رمز قالبی استفاده می‌شود؛ به بیان دقیق تر رمزهای قالبی نمونه‌هایی از جایگشت‌های شبه تصادفی اند.

منابع

• کتاب Introduction to modren cryptography/katz and lindell