В криптографии , А функция семейства псевдослучайных , сокращенно ЧПИ , представляет собой совокупность эффективно-вычислимых функций , которые эмулируют случайный оракул следующим образом: не эффективный алгоритм не может различать (со значительным преимуществом ) между функцией выбранной случайным образом из семейства PRF и а random oracle (функция, выходы которой фиксируются полностью случайным образом). Псевдослучайные функции являются жизненно важными инструментами при построении криптографических примитивов , особенно схем безопасного шифрования .
Псевдослучайные функции не следует путать с псевдослучайными генераторами (PRG). Гарантия PRG заключается в том, что единственный выход будет казаться случайным, если вход был выбран случайным образом. С другой стороны, гарантия PRF заключается в том, что все ее выходы выглядят случайными, независимо от того, как были выбраны соответствующие входы, до тех пор, пока функция была выбрана случайным образом из семейства PRF.
Семейство псевдослучайных функций может быть построено из любого псевдослучайного генератора, используя, например, конструкцию «GGM», данную Голдрайхом , Голдвассером и Микали . [1] Хотя на практике блочные шифры используются в большинстве случаев, когда требуется псевдослучайная функция, они, как правило, не составляют семейство псевдослучайных функций, поскольку блочные шифры, такие как AES , определены только для ограниченного количества входных и ключевых размеры. [2]
Мотивации от случайных функций
PRF - это эффективная (т.е. вычисляемая за полиномиальное время) детерминированная функция, которая отображает два различных набора (область и диапазон) и выглядит как действительно случайная функция.
По сути, действительно случайная функция будет просто составлена из таблицы поиска, заполненной равномерно распределенными случайными записями. Однако на практике PRF получает входную строку в домене и скрытое случайное начальное число и запускается несколько раз с одной и той же входной строкой и начальным значением, всегда возвращая одно и то же значение. Тем не менее, учитывая произвольную входную строку, выходные данные выглядят случайными, если начальное значение взято из равномерного распределения.
PRF считается хорошей, если ее поведение неотличимо от действительно случайной функции. Следовательно, учитывая результат либо от истинно случайной функции, либо от PRF, не должно быть эффективного метода для правильного определения того, был ли вывод произведен истинно случайной функцией или PRF.
Формальное определение
Семейство функций,
, где , а также
является псевдослучайным, если выполняются следующие условия:
- Учитывая любые а также такой, что , всегда существует алгоритм с полиномиальным временем для вычисления .
- Позволять быть распределением функций где равномерно распределяется по , и разреши обозначим равномерное распределение по множеству всех функций из к . Тогда нам потребуется а также вычислительно неразличимы, где n - параметр безопасности. То есть для любого злоумышленника, который может запросить оракул функции, выбранной из любого или же , преимущество, заключающееся в том, что она может отличить, какой вид оракула ей дано, ничтожно. [3]
Забывчивые псевдослучайные функции
В скрытой псевдослучайной функции, сокращенно OPRF, информация скрывается от двух сторон, участвующих в PRF. [4] То есть, если Алиса криптографически хеширует свое секретное значение, криптографически слепит хэш для создания сообщения, которое она отправляет Бобу, а Боб подмешивает свое секретное значение и возвращает результат Алисе, которая отключает его, чтобы получить окончательный результат. , Боб не может видеть ни секретное значение Алисы, ни окончательный вывод, а Алиса не может видеть секретный ввод Боба, но Алиса видит окончательный вывод, который является PRF двух входов - PRF секрета Алисы и PRF секрета Боба. секрет. [5] Это обеспечивает безопасность транзакций с конфиденциальной криптографической информацией даже между ненадежными сторонами.
OPRF используется в некоторых реализациях соглашения о ключах с аутентификацией паролем . [5]
OPRF используется в функции монитора паролей в Microsoft Edge . [6]
Заявление
PRF могут использоваться для: [7]
- динамическое идеальное хеширование ; даже если злоумышленник может изменить распределение ключей в зависимости от значений, которые хеш-функция присвоила предыдущим ключам, противник не может вызвать коллизии.
- Создание детерминированных схем аутентификации без памяти (на основе кода аутентификации сообщений ), которые доказуемо защищены от выбранной атаки сообщения.
- Распространение неповторимых идентификационных номеров , которые могут быть проверены локально станциями, имеющими лишь небольшой объем памяти.
- Построение систем идентификации друга или врага .
Смотрите также
Заметки
- ^ Голдрайх, Одед ; Гольдвассер, Шафи ; Микали, Сильвио (октябрь 1986 г.). «Как построить случайные функции» (PDF) . Журнал ACM . 33 (4): 792–807. DOI : 10.1145 / 6490.6503 . веб-страница и препринт
- ^ Линделл, Иегуда; Кац, Джонатан (2008). Введение в современную криптографию . Чепмен и Холл / CRC. п. 88. ISBN 978-1-58488-551-1.
- ^ Голдрейха Foc, т. 1, деф. 3.6.4. Примечания к проходу, деф. 96,2
- ^ М. Белларе ; С. Келведи; Т. Ристенпарт (август 2013 г.). Dupless: серверное шифрование для дедуплицированного хранилища (PDF) . Материалы 22-го симпозиума по безопасности USENIX. Вашингтон, округ Колумбия, США: Ассоциация USENIX. С. 1–16.
- ^ a b Мэтью Грин. «Давайте поговорим о PAKE» . 2018.
- ^ Лаутер, Кристин; Каннепалли, Шрикант; Лайне, Ким; Круз Морено, Радамес (1 января 2021 г.). «Монитор паролей: защита паролей в Microsoft Edge» . Блог Microsoft Research . Проверено 1 января 2021 года .
- ^ Goldreich, O .; Goldwasser, S .; Микали, С. (1985). «О криптографических приложениях случайных функций (расширенная аннотация)». Достижения в криптологии . Конспект лекций по информатике. 196 . п. 276. DOI : 10.1007 / 3-540-39568-7_22 . ISBN 978-3-540-15658-1.
Рекомендации
- Гольдрайх, Одед (2001). Основы криптографии: основные инструменты . Кембридж: Издательство Кембриджского университета. ISBN 978-0-511-54689-1.
- Пасс, Рафаэль, Курс криптографии (PDF) , получено 22 декабря 2015 г.