توابع شبه‌تصادفی
در علم رمزنگاری، یک خانواده از توابع شبه‌تصادفی (به انگلیسی: Pseudorandom function family) که مختصراً با PRF نمایش می‌دهیم، مجموعه‌ای از توابع محاسبه پذیر کارا است، به طوری که هیچ الگوریتم کارایی (که به صورت اراکلی به توابع دسترسی دارد) نتواند با مزیت قابل توجهی، یک تابع ازاین خانواده را، از یک تابع تصادفی دلخواه تمایز دهد.
توابع شبه‌تصادفی نباید با مولدهای شبه‌تصادفی اشتباه گرفته شوند. یک مولد شبه‌تصادفی تابعی است که اگر ورودی آن تصادفی باشد، انتظار داریم خروجی اش تصادفی به نظر برسد؛ اما توابع شبه‌تصادفی خانواده‌ای از توابع است که اگر یک تابع از این خانواده انتخاب کنیم، باید یک تابع تصادفی به نظر برسد؛ یعنی تشخیص اینکه این تابع از همین خانواده انتخاب شده است، برای یک شخص ثالث سخت باشد.
کاربردها
توابع شبه‌تصادفی ابزارهای اساسی در ساختن اولیه‌های (primitive) رمزنگاری هستند.
توابع شبه‌تصادفی ابزاری سودمند برای رسیدن به امنیت متن اصلی انتخابی اند و می‌توان از آنها در احراز هویت و اصالت سنجی پیام استفاده نمود.
توابع شبه‌تصادفی بلوک‌های ساختمانی مهم و مفید در بسیاری از سیستم‌های رمزنگاری می‌باشند. یکی از دلایل مفید بودن توابع شبه‌تصادفی امکان تحلیل زیبا و سرراست سیستم‌هایی است که توابع شبه‌تصادفی در آن استفاده شده است، می‌باشد. برای اثبات امنیت یک سیستم، کافی است نشان دهیم در صورت امن نبودن، توابع شبه‌تصادفی در آن، نمی‌توانند شبه تصادفی باشند و چنین چیزی غیرممکن است.
از توابع شبه‌تصادفی می‌توان در ساختن مولدهای شبه تصادفی استفاده کرد؛ البته عکس این کار نیز امکان‌پذیر است.
یک کاربرد دیگر توابع شبه‌تصادفی، تولید جایگشت‌های شبه تصادفی است، که نمونه بارز آن شبکه فایستل است. ثابت شده است که اگر تعداد دورهای شبکه فایستل بیشتر از ۲ باشد و توابع استفاده شده شبه تصادفی باشند، شبکه فایستل یک جایگشت شبه تصادفی است.
منابع
- کتاب Introduction to modren cryptography/katz and lindell