Псевдовипадкова переставка

Псевдовипадкова перестановка (англ. pseudorandom permutation), PRP — це функція, яку неможливо за допомогою розумних зусиль відрізнити від випадкової перестановки (тобто від перестановки обраної випадково й однорідно з сім'ї всіх перестановок на домені функції).

Сім'я випадкових перестановок — це множина псевдовипадкових перестановок, де можна обрати певну перестановку використовуючи ключ.

Ідеалізована абстракція блокового шифру є насправді випадковою перестановкою. Якщо існує алгоритм здатний розрізнити із досягненням значної з меншими зусиллями ніж вказані параметром безпеки блокового шифру (це зазвичай значить, що потрібні зусилля мають бути на рівні повного перебору по простору можливих ключів шифру), тоді шифр вважається зламаним щонайменше в сенсі сертифікації, навіть якщо така вада і не призводить до негайного практичного краху безпеки.

Як приклади безпечних псевдовипадкових перестановок можна навести 3DES, AES.

Математичне визначення

Псевдовипадкова перестановка (PRP) визначена на ${\displaystyle (K,X)}$ це функція ${\displaystyle E:K\times X\to X}$, така що:

1. Існує дієвий детерміністичний алгоритм для обчислення ${\displaystyle E(k,x)}$
2. Функція ${\displaystyle E(k,\cdot )}$ є бієкцією (один до одного)
3. Існує дієвий зворотний алгоритм ${\displaystyle D(k,x)}$

Безпечність псевдовипадкової перестановки

Для b = 0,1 розглянемо досліди ${\displaystyle EXP(b)}$.

${\displaystyle b=0:K\to k,E(k,\cdot )\to f}$

${\displaystyle b=1:Perms[X]\to f}$

Супротивник (англ. adversary) ${\displaystyle A}$ виконує ${\displaystyle q}$ запитів ${\displaystyle x_{1},x_{2},...x_{q}\in X}$ і отримує ${\displaystyle q}$ відповідей ${\displaystyle f(x_{1}),f(x_{2}),...f(x_{q})}$. По вивчені відповідей ціллю супротивника є вказати з якої саме множини вибрали функцію.

Отже, ${\displaystyle E}$ є захищеною PRP, якщо для будь-якого ефективного супротивника ${\displaystyle A}$ перевага: ${\displaystyle Adv_{PRF}[A,E]:={\begin{vmatrix}Pr[EXP(0)=1]-Pr[EXP(1)=1]\end{vmatrix}}}$ не значима.

Див. також

• Блоковий шифр (сім'я псевдовипадкових перестановок, що діють на блоках бітів встановленого розміру)
• Випадкова перестановка
• Псевдовипадкова функція

Примітки

• Mihir Bellare, Phillip Rogaway (20 вересня 2005). Chapter 3: Pseudorandom functions. . Архів оригіналу за 11 жовтня 2007. Процитовано 30 вересня 2007.