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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Примітки

• Mihir Bellare, Phillip Rogaway (2005-09-20). «Chapter 3: Pseudorandom functions». Introduction to Modern Cryptography. Процитовано 2007-09-30.