Введение
Коллекция эффективно вычислимых функций, эмулирующих случайный оракул. В криптографии семейство псевдослучайных функций, сокращенно PRF, представляет собой коллекцию эффективно вычислимых функций, эмулирующих случайный оракул следующим образом: ни один эффективный алгоритм не может различить (с заметным преимуществом) функцию, случайно выбранную из семейства PRF, и случайный оракул (функцию, выходы которой полностью определяются случайным образом). Псевдослучайные функции являются важнейшими инструментами при создании криптографических примитивов, особенно схем безопасного шифрования. Псевдослучайные функции не следует путать с генераторами псевдослучайных чисел (PRG). Гарантия PRG заключается в том, что отдельный выход выглядит случайным, если вход был выбран случайным образом. С другой стороны, гарантия PRF заключается в том, что все его выходы выглядят случайными, независимо от способа выбора соответствующих входов, при условии, что функция была случайно выбрана из семейства PRF. Семейство псевдослучайных функций может быть построено на основе любого генератора псевдослучайных чисел, например, с использованием конструкции "GGM", предложенной Голдрейхом, Голдвассером и Микали. Хотя на практике блочные шифры часто используются там, где требуется псевдослучайная функция, они, как правило, не образуют семейство псевдослучайных функций, поскольку блочные шифры, такие как AES, определены только для ограниченного числа размеров входных данных и ключей.
In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish (with significant advantage) between a function chosen randomly from the PRF family and a random oracle (a function whose outputs are fixed completely at random). Pseudorandom functions are vital tools in the construction of cryptographic primitives, especially secure encryption schemes. Pseudorandom functions are not to be confused with pseudorandom generators (PRGs). The guarantee of a PRG is that a single output appears random if the input was chosen at random. On the other hand, the guarantee of a PRF is that all its outputs appear random, regardless of how the corresponding inputs were chosen, as long as the function was drawn at random from the PRF family. A pseudorandom function family can be constructed from any pseudorandom generator, using, for example, the "GGM" construction given by Goldreich, Goldwasser, and Micali. While in practice, block ciphers are used in most instances where a pseudorandom function is needed, they do not, in general, constitute a pseudorandom function family, as block ciphers such as AES are defined for only limited numbers of input and key sizes.
Мотивация от случайных функций
PRF — это эффективная (т.е. вычислимая за полиномиальное время) детерминированная функция, которая сопоставляет два различных множества (область определения и область значений) и выглядит как истинно случайная функция. По сути, истинно случайная функция представляла бы собой просто таблицу поиска, заполненную случайными значениями, равномерно распределенными. Однако на практике PRF принимает на вход строку из области определения и скрытое случайное зерно, и выполняется многократно с одной и той же входной строкой и зерном, всегда возвращая одно и то же значение. Тем не менее, для любой произвольной входной строки выходные данные выглядят случайными, если зерно взято из равномерного распределения. PRF считается качественной, если её поведение неотличимо от истинно случайной функции. Следовательно, имея на выходе данные либо от истинно случайной функции, либо от PRF, не должно существовать эффективного способа правильно определить, какой функцией был сгенерирован этот выход.
Непонятные псевдослучайные функции
В неоткрывающей псевдослучайной функции, сокращенно OPRF, информация скрыта от двух сторон, участвующих в вычислении PRF. А именно, если Алиса криптографически хеширует свое секретное значение, криптографически маскирует хэш для создания сообщения, которое она отправляет Бобу, а Боб добавляет к нему свое секретное значение и возвращает результат Алисе, которая снимает маскировку, чтобы получить окончательный результат, Боб не может узнать ни секретное значение Алисы, ни окончательный результат, а Алиса не может узнать секретный вход Боба, но Алиса видит окончательный результат, который является PRF от двух входов – PRF от секрета Алисы и секрета Боба. OPRF используется в функциональности мониторинга паролей в Microsoft Edge. Подробности смотрите в основной статье о неоткрывающих псевдослучайных функциях.