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

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

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

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

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

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

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

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

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

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

жs : {0, 1}λ (|s|) → {0, 1}λ (|s|), куда s ∈ {0, 1}*, и λ: ℕ → ℕ,

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

  • Учитывая любые s и Икс такой, что |Икс| = λ (|s|), всегда существует алгоритм с полиномиальным временем для вычисления жs(Икс).
  • Позволять Fп быть распределением функций жs куда s равномерно распределен по {0, 1}п, и разреши РФп обозначим равномерное распределение по множеству всех функций из {0, 1}п в {0, 1}п. Тогда нам потребуется Fп и РФп вычислительно неразличимы, где п - параметр безопасности. То есть для любого злоумышленника, который может запросить оракул функции, взятой из любого Fп или же РФп, преимущество, заключающееся в том, что она может отличить, какой вид оракула ей дано, ничтожно.[3]

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

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

Заявление

PRF могут использоваться для:[5]

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

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

Примечания

  1. ^ Гольдрайх, Одед; Гольдвассер, Шафи; Микали, Сильвио (Октябрь 1986 г.). «Как построить случайные функции» (PDF). Журнал ACM. 33 (4): 792–807. Дои:10.1145/6490.6503. веб-страница и препринт
  2. ^ Линделл, Иегуда; Кац, Джонатан (2008). Введение в современную криптографию. Чепмен и Холл / CRC. п. 88. ISBN  978-1-58488-551-1.
  3. ^ FoC Голдрейха, т. 1, деф. 3.6.4. Примечания к проходу, деф. 96,2
  4. ^ М. Белларе; С. Келведи; Т. Ристенпарт (август 2013 г.). Dupless: серверное шифрование для дедуплицированного хранилища (PDF). Материалы 22-го симпозиума по безопасности USENIX. Вашингтон, округ Колумбия, США: Ассоциация USENIX. С. 1–16.
  5. ^ Гольдрайх, О.; Гольдвассер, С.; Микали, С. (1985). «О криптографических приложениях случайных функций (расширенная аннотация)». Достижения в криптологии. Конспект лекций по информатике. 196. п. 276. Дои:10.1007/3-540-39568-7_22. ISBN  978-3-540-15658-1.

Рекомендации