Псевдовипадкова перестановка (), PRP — це функція, яку неможливо за допомогою розумних зусиль відрізнити від випадкової перестановки (тобто від перестановки обраної випадково й однорідно з сім'ї всіх перестановок на домені функції).
Сім'я випадкових перестановок — це множина псевдовипадкових перестановок, де можна обрати певну перестановку використовуючи ключ.
Ідеалізована абстракція блокового шифру є насправді випадковою перестановкою. Якщо існує алгоритм здатний розрізнити із досягненням значної переваги з меншими зусиллями ніж вказані параметром безпеки блокового шифру (це зазвичай значить, що потрібні зусилля мають бути на рівні повного перебору по простору можливих ключів шифру), тоді шифр вважається зламаним щонайменше в сенсі сертифікації, навіть якщо така вада і не призводить до негайного практичного краху безпеки.
Як приклади безпечних псевдовипадкових перестановок можна навести 3DES, AES.
Математичне визначення Псевдовипадкова перестановка (PRP) визначена на це функція , така що: Існує дієвий детерміністичний алгоритм для обчислення Функція є бієкцією (один до одного) Існує дієвий зворотний алгоритм
Безпечність псевдовипадкової перестановки Для b = 0,1 розглянемо досліди .
Супротивник () виконує запитів і отримує відповідей . По вивчені відповідей ціллю супротивника є вказати з якої саме множини вибрали функцію.
Отже, є захищеною PRP, якщо для будь-якого ефективного супротивника перевага: не значима.
Див. також Блоковий шифр (сім'я псевдовипадкових перестановок, що діють на блоках бітів встановленого розміру) Випадкова перестановка Псевдовипадкова функція
Примітки