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

Коллекция эффективно вычисляемых функций, которые эмулируют случайный оракул

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

OPRF используется в некоторых реализациях соглашения о ключах с аутентификацией по паролю . ^[5]

OPRF используется в функции Password Monitor в Microsoft Edge . ^[6]

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

Приложение

PRF могут быть использованы для: ^[7]

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

Смотрите также

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

Примечания

1. Goldreich, Oded ; Goldwasser, Shafi ; Micali, Silvio (октябрь 1986 г.). "How to Construct Random Functions" (PDF) . Journal of the ACM . 33 (4): 792–807. doi : 10.1145/6490.6503 . веб-страница и препринт
2. Линделл, Йехуда; Кац, Джонатан (2008). Введение в современную криптографию . Chapman & Hall/CRC. стр. 88. ISBN 978-1-58488-551-1.
3. FoC Голдрайха, т. 1, определение 3.6.4. Заметки Пасса, определение 96.2
4. M. Bellare ; S. Keelveedhi; T. Ristenpart (август 2013 г.). Dupless: серверное шифрование для дедуплицированного хранилища (PDF) . Труды 22-го симпозиума по безопасности USENIX. Вашингтон, округ Колумбия, США: Ассоциация USENIX. стр. 1–16.
5. Мэтью Грин. «Давайте поговорим о PAKE». 2018.
6. Лаутер, Кристин; Каннепалли, Шрикант; Лайн, Ким; Круз Морено, Радамес (1 января 2021 г.). «Монитор паролей: защита паролей в Microsoft Edge». Блог Microsoft Research . Получено 1 января 2021 г.
7. Goldreich, O. ; Goldwasser, S. ; Micali, S. (1985). "О криптографических применениях случайных функций (расширенный реферат)". Advances in Cryptology . Lecture Notes in Computer Science. Vol. 196. p. 276. doi :10.1007/3-540-39568-7_22. ISBN 978-3-540-15658-1.

Ссылки

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