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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Математичне підґрунтя[ред.ред. код]

PRF global set n key set.png

Нехай буде PRF.

Інтуїтивно PRF безпечна, якщо випадкову функцію з неможливо відрізнити від випадкової функції з . Дамо точніше математичне визначення. Для b = 0,1 розглянемо досліди .

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

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

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

Примітки[ред.ред. код]

  1. Oded Goldreich, Shafi Goldwasser, Silvio Micali (1986) "How to Construct Random Functions", Journal of the ACM, vol.33, no.4, p.792-807. DOI:10.1145/6490.6503; preprint; web page and preprint