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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

توجه کنیم که هر خانواده از جایگشت های شبه تصادفی، یک خانواده از توابع شبه تصادفی می باشد.

تعریف[ویرایش]

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

کاربرها[ویرایش]

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

منابع[ویرایش]

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