Сімейство псевдовипадкових функцій (, PRF) — це множина ефективно-обчислювальних функцій, що імітують наступним чином: не існує дієвого алгоритму, що може розрізнити (з вагомою ) між функцією випадково обраною з PRF сімейства і випадковим оракулом (результати якого фіксуються повністю навмання). Псевдовипадкові функції життєво важливі засоби при будові криптографічних примітивів, особливо безпечних схем шифрування.
Не плутаймо псевдовипадкові функції з псевдовипадковими генераторами (). PRG гарантують, що один вихід виявиться випадковим, якщо на вході було випадкове значення. З іншого боку, PRF гарантує, що всі виходи здаватимуться випадковими, незалежно від того як обирали відповідні вхідні дані, доти доки функція була випадково витягнута з сімейства PRF.
Псевдовипадкову функцію можна побудувати з псевдовипадкового генератора.Oded Goldreich, Shafi Goldwasser, Silvio Micali (1986) "How to Construct Random Functions", Journal of the ACM, vol.33, no.4, p.792-807. ; preprint ; web page and preprint Розрізняють PRF зі змінною довжиною вхідних даних () і PRF зі сталою довжиною ().
Математичне підґрунтя
Нехай буде PRF.
Інтуїтивно PRF безпечна, якщо випадкову функцію з неможливо відрізнити від випадкової функції з . Дамо точніше математичне визначення. Для b = 0,1 розглянемо досліди .
Супротивник () виконує запитів і отримує відповідей . По вивчені відповідей ціллю супротивника є вказати з якої саме множини вибрали функцію.
Отже, є захищеною PRF, якщо для будь-якого ефективного супротивника перевага: не вагома.
Див. також Псевдовипадкова перестановка
Примітки