Семейство псевдослучайных функций

В криптографии семейство псевдослучайных функций , сокращенно PRF , представляет собой набор эффективно вычислимых функций , которые имитируют случайный оракул следующим образом: ни один эффективный алгоритм не может отличить (со значительным преимуществом ) между функцией, случайно выбранной из семейства PRF, и функцией, выбранной случайным образом из семейства PRF. случайный оракул (функция, выходные данные которой фиксируются совершенно случайным образом). Псевдослучайные функции являются жизненно важными инструментами в построении криптографических примитивов безопасного , особенно схем шифрования .

Псевдослучайные функции не следует путать с генераторами псевдослучайных чисел (PRG). Гарантия PRG заключается в том, что один выходной сигнал будет случайным, если входной сигнал был выбран случайным образом. С другой стороны, гарантия PRF заключается в том, что все его выходные данные кажутся случайными, независимо от того, как были выбраны соответствующие входные данные, при условии, что функция была выбрана случайным образом из семейства PRF.

Семейство псевдослучайных функций может быть построено из любого генератора псевдослучайных чисел, используя, например, конструкцию «GGM», данную Голдрейхом , Гольдвассером и Микали . Хотя на практике блочные шифры используются в большинстве случаев, когда требуется псевдослучайная функция, они, как правило, не составляют семейство псевдослучайных функций, поскольку блочные шифры, такие как AES, определены только для ограниченного количества входных данных и размеров ключей.

Мотивации от случайных функций

PRF — это эффективная (т. е. вычислимая за полиномиальное время) детерминированная функция, которая отображает два различных набора (домен и диапазон) и выглядит как действительно случайная функция.

По сути, действительно случайная функция будет состоять из таблицы поиска, заполненной равномерно распределенными случайными элементами. Однако на практике PRF получает входную строку в домене и скрытое случайное начальное число и запускается несколько раз с одной и той же входной строкой и начальным числом, всегда возвращая одно и то же значение. Тем не менее, учитывая произвольную входную строку, выходные данные выглядят случайными, если начальное число взято из равномерного распределения.

PRF считается хорошим, если его поведение неотличимо от истинно случайной функции. Следовательно, учитывая выходные данные истинно случайной функции или PRF, не должно быть эффективного метода, позволяющего правильно определить, был ли результат получен истинно случайной функцией или PRF.

Формальное определение

Псевдослучайные функции принимают входные данные $x\in \{0,1\}^{*}$. Оба входных размера $I=|x|$ и размер вывода $\lambda$ зависят только от размера индекса $n:=|s|$.

Семейство функций,

$f_{s}:\left\{0,1\right\}^{I(n)}\rightarrow \left\{0,1\right\}^{\lambda (n)}$

является псевдослучайным, если выполняются следующие условия:

• Существует алгоритм с полиномиальным временем, который вычисляет $f_{s}(x)$ учитывая любой $s$ и $x$.
• Позволять $F_{n}$ быть распределением функций $f_{s}$ где $s$ равномерно распределен по $\{0,1\}^{n}$, и пусть $RF_{n}$ обозначаем равномерное распределение по множеству всех функций из $\{0,1\}^{I(n)}$ к $\{0,1\}^{\lambda (n)}$. Тогда мы требуем $F_{n}$ и $RF_{n}$ вычислительно неразличимы, где n — параметр безопасности. То есть для любого противника, который может запросить оракул функции, выбранной из любого $F_{n}$ или $RF_{n}$преимущество, заключающееся в том, что она может отличить, какой тип оракула ей дан, незначительно $n$.

Забывчивые псевдослучайные функции

В забывчивой псевдослучайной функции, сокращенно OPRF, информация скрывается от двух сторон, участвующих в PRF. То есть, если Алиса криптографически хеширует свое секретное значение, криптографически скрывает хеш для создания сообщения, которое она отправляет Бобу, а Боб подмешивает свое секретное значение и возвращает результат Алисе, которая разоблачает его, чтобы получить окончательный результат, Боб не может видеть ни секретное значение Алисы, ни окончательный вывод, а Алиса не может видеть секретный ввод Боба, но Алиса видит окончательный результат, который представляет собой PRF из двух входов — PRF секрета Алисы и секрета Боба. Это позволяет обеспечить безопасность транзакций конфиденциальной криптографической информации даже между ненадежными сторонами.

OPRF используется в некоторых реализациях соглашения о ключах, проверяемых паролем .

OPRF используется в функции монитора паролей в Microsoft Edge .

См. основную статью о забывчивых псевдослучайных функциях .

Приложение

PRF можно использовать для:

1. динамическое идеальное хеширование ; даже если злоумышленник может изменить распределение ключей в зависимости от значений, которые хеш-функция присвоила предыдущим ключам, злоумышленник не сможет вызвать коллизии.
2. Построение детерминированных схем аутентификации без памяти ( на основе кода аутентификации сообщений ), которые доказуемо защищены от атаки по выбранному сообщению.
3. Распространение неподдельных идентификационных номеров , которые могут быть проверены локально станциями, имеющими лишь небольшой объем памяти.
4. Построение систем идентификации «свой-чужой» .

См. также

• Псевдослучайная перестановка

Ссылки

• Гольдрейх, Одед (2001). Основы криптографии: основные инструменты . Кембридж: Издательство Кембриджского университета. ISBN  978-0-511-54689-1 .
• Пасс, Рафаэль, Курс криптографии (PDF) , получено 22 декабря 2015 г.