Псевдовипадкова функція

Сімейство псевдовипадкових функцій (Шаблон:Lang-en, PRF) — це множина ефективно-обчислювальних функцій, що імітують Шаблон:Нп наступним чином: не існує дієвого алгоритму, що може розрізнити (з вагомою Шаблон:Нп) між функцією випадково обраною з PRF сімейства і випадковим оракулом (результати якого фіксуються повністю навмання). Псевдовипадкові функції життєво важливі засоби при будові криптографічних примітивів, особливо безпечних схем шифрування.

Не плутаймо псевдовипадкові функції з псевдовипадковими генераторами (Шаблон:Lang-en). PRG гарантують, що один вихід виявиться випадковим, якщо на вході було випадкове значення. З іншого боку, PRF гарантує, що всі виходи здаватимуться випадковими, незалежно від того як обирали відповідні вхідні дані, доти доки функція була випадково витягнута з сімейства PRF.

Псевдовипадкову функцію можна побудувати з псевдовипадкового генератора. Розрізняють PRF зі змінною довжиною вхідних даних (Шаблон:Lang-en) і PRF зі сталою довжиною (Шаблон:Lang-en).

Математичне підґрунтя

Файл:PRF global set n key set.png

Нехай $F:K\times X\to Y$ буде PRF.

$\{\begin{array}{c}Funs[X,Y]:\mathrm{\forall }F:X\to Y\\ S_F=\{F(k,\cdot ),k\in K\}\subseteq Funs[X,Y]\end{array}$

Інтуїтивно PRF безпечна, якщо випадкову функцію з $Funs[X,Y]$ неможливо відрізнити від випадкової функції з $S_F$. Дамо точніше математичне визначення. Для b = 0,1 розглянемо досліди $EXP(b)$.

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

$b=1:Funs[X,Y]\to f$

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

Отже, $F$ є захищеною PRF, якщо для будь-якого ефективного супротивника $A$ перевага: $Ad{v}_{PRF}[A,F]:=\left|\begin{array}{c}Pr[EXP(0)=1]-Pr[EXP(1)=1]\end{array}\right|$ не вагома.

Див. також

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