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

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

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

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

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

Математичне визначення ред.

Псевдовипадкова перестановка (PRP) визначена на   це функція  , така що:

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

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

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

 

 

Супротивник (англ. adversary)   виконує   запитів   і отримує   відповідей  . По вивчені відповідей ціллю супротивника є вказати з якої саме множини вибрали функцію.

Отже,   є захищеною PRP, якщо для будь-якого ефективного супротивника   перевага:   не значима.

Див. також ред.

Примітки ред.

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