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

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

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

Псевдовипадкову функцію можна побудувати з псевдовипадкового генератора. Розрізняють PRF зі змінною довжиною входових даних (англ. variable-input-length, VIL PRF) і PRF зі сталою довжиною (англ. fixed-input-length, FIL PRF).

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

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

$\left\{ \begin{matrix} Funs[X,Y]: \forall F:X \to Y \\ S_F = \left\{ F(k, \cdot), k \in K \right\} \subseteq Funs[X,Y] \end{matrix} \right.$

Інтуїтивно 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$

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

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

Див. також

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