Войти
В криптографии, псевдослучайная функция Семейство, сокращенно PRF, представляет собой набор эффективно вычислимых функций, которые имитируют случайный оракул следующим образом: ни один эффективный алгоритм не может отличить (со значительным преимуществом ) между функцией, случайно выбранной из семейства PRF, и случайным оракулом (функцией, выходы фиксируются полностью случайным образом). Псевдослучайные функции являются жизненно важными инструментами при построении криптографических примитивов, особенно безопасных схем шифрования.
. Псевдослучайные функции не следует путать с генераторами псевдослучайных (PRG). Гарантия PRG заключается в том, что единственный выход будет выглядеть random, если вход был выбран случайным образом. С другой стороны, гарантия PRF заключается в том, что все ее выходы выглядят случайными, независимо от того, как были выбраны соответствующие входы, до тех пор, пока функция была выбрана случайным образом из семейства PRF.
Семейство псевдослучайных функций может быть построено из любого псевдослучайного генератора, используя, например, конструкцию «GGM», данную Goldreich, Goldwasser и Микали. Хотя на практике блочные шифры используются в большинстве случаев, когда требуется псевдослучайная функция, они, как правило, не составляют семейство псевдослучайных функций, поскольку блочные шифры, такие как AES, являются определено только для ограниченного числа вводов и размеров клавиш.
PRF - это эффективная (т.е. вычисляемая за полиномиальное время), детерминированная функция, которая отображает два различных набора (область и диапазон) и выглядит как действительно случайная функция.
По сути, действительно случайная функция будет просто составлена из таблицы поиска, заполненной равномерно распределенными случайными записями. Однако на практике PRF получает входную строку в домене и скрытое случайное начальное число и запускается несколько раз с одной и той же входной строкой и начальным числом, всегда возвращая одно и то же значение. Тем не менее, для произвольной входной строки выходные данные выглядят случайными, если начальное значение взято из равномерного распределения.
PRF считается хорошей, если ее поведение неотличимо от действительно случайной функции. Следовательно, учитывая результат либо от истинно случайной функции, либо от PRF, не должно быть эффективного метода для правильного определения того, был ли вывод произведен истинно случайной функцией или PRF.
Семейство функций,
является псевдослучайным, если выполняются следующие условия:
В псевдослучайной функции не обращая внимания, информация скрывается от двух сторон, участвующих в PRF. То есть, если Алиса передает входные данные для псевдослучайной функции Бобу, а Боб вычисляет PRF и передает выходные данные Алисе, Боб не может видеть ни вход, ни выход, а Алиса не может видеть секретный ключ. Боб использует с псевдослучайной функцией. Это обеспечивает безопасность транзакций конфиденциальной криптографической информации даже между ненадежными сторонами.
PRF могут использоваться для:
