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

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

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

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

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

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

${\displaystyle \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 безпечна, якщо випадкову функцію з ${\displaystyle Funs[X,Y]}$ неможливо відрізнити від випадкової функції з ${\displaystyle S_{F}}$. Дамо точніше математичне визначення. Для b = 0,1 розглянемо досліди ${\displaystyle EXP(b)}$.

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

${\displaystyle b=1:Funs[X,Y]\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 F}$ є захищеною PRF, якщо для будь-якого ефективного супротивника ${\displaystyle A}$ перевага: ${\displaystyle Adv_{PRF}[A,F]:={\begin{vmatrix}Pr[EXP(0)=1]-Pr[EXP(1)=1]\end{vmatrix}}}$ не вагома.

Див. також

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

Примітки

1. Oded Goldreich, Shafi Goldwasser, Silvio Micali (1986) "How to Construct Random Functions", , vol.33, no.4, p.792-807. DOI:10.1145/6490.6503; preprint; web page and preprint [ 26 вересня 2007 у Wayback Machine.]