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

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

Определение

Пусть F — отображение $\left\{0,1\right\}^{n}\times \left\{0,1\right\}^{s}\rightarrow \left\{0,1\right\}^{n}$ . F является PRP тогда и только тогда, когда

Для любого $K\in \left\{0,1\right\}^{s}$ , $F_{K}$ является биекцией из $\left\{0,1\right\}^{n}$ к $\left\{0,1\right\}^{n}$ , где $F_{K}(x)=F(x,K)$ .
Для любого $K\in \left\{0,1\right\}^{s}$ , существует «эффективный» алгоритм оценки $F_{K}(x)$ для любого $x\in \left\{0,1\right\}^{n}$ ,.
с полиномиальным временем Для всех вероятностных различителей $D$ : $\left|Pr\left(D^{F_{K}}(1^{n})=1\right)-Pr\left(D^{f_{n}}(1^{n})=1\right)\right|<\varepsilon (s)$ , где $K\in \left\{0,1\right\}^{s}$ выбирается равномерно случайным образом и $f_{n}$ выбирается равномерно случайным образом из множества перестановок n -битных строк. ^[1]

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

Модель блочных шифров

Идеализированная абстракция (ключевого) блочного шифра представляет собой поистине случайную перестановку отображений между открытым текстом и зашифрованным текстом. Если существует алгоритм различения, который дает значительное преимущество блочного шифра с меньшими усилиями, чем указано в параметре безопасности (обычно это означает, что требуемые усилия должны быть примерно такими же, как и при переборе ключевого пространства шифра), то шифр считается взломанным. по крайней мере, в сертификационном смысле, даже если такое нарушение не приведет немедленно к практическому сбою в системе безопасности . ^[2]

Ожидается, что современные шифры будут обладать суперпсевдослучайностью.То есть шифр должен быть неотличим от случайно выбранной перестановки в том же пространстве сообщений, даже если у злоумышленника есть доступ к «черному ящику» для прямого и обратного направлений шифра. ^[3]

Связи с псевдослучайной функцией

Майкл Луби и Чарльз Ракофф ^[4] показал, что «сильная» псевдослучайная перестановка может быть построена из псевдослучайной функции с использованием конструкции Люби – Ракоффа , которая построена с использованием шифра Фейстеля .

Связанные понятия

Непредсказуемая перестановка

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

Противником . непредсказуемой перестановки считается алгоритм, которому предоставляется доступ к оракулу как для прямых, так и для обратных операций перестановки Противнику дается входной запрос k и его просят предсказать значение F _k . Разрешается сделать серию запросов к оракулу, чтобы помочь ему сделать этот прогноз, но не разрешается запрашивать значение самого k . ^[5]

Рандомизированный алгоритм генерации перестановок генерирует непредсказуемую перестановку , если его выходные данные представляют собой перестановки на наборе элементов (описанных двоичными строками длины n ), которые не могут быть предсказаны с точностью, значительно лучшей, чем случайная, противником, который создает полином (от n ). количество запросов к оракулу перед раундом вызова, время выполнения которых полиномиально от n и вероятность ошибки которого меньше 1/2 для всех экземпляров. То есть его нельзя предсказать в классе сложности PP , релятивизированном оракулом для перестановки. ^[5]

Свойства непредсказуемых перестановок

Можно показать, что функция F _k не является кодом аутентификации безопасного сообщения (MAC), если она удовлетворяет только требованию непредсказуемости. Также можно показать, что невозможно построить эффективный MAC переменной входной длины из блочного шифра, который моделируется как UP из n бит. Было показано, что выходные данные раунда конструкции Фейстеля a k = n / ω (log λ ) с непредсказуемыми округленными функциями могут привести к утечке всех промежуточных округленных значений. ^[5] Даже для реалистичных непредсказуемых функций (UF) некоторая частичная информация о промежуточных значениях округления может просочиться через выходные данные. Позже было показано, что если в конструкции Фейстеля используется суперлогарифмическое количество раундов, то результирующая конструкция UP безопасна, даже если противник получает все промежуточные значения раундов вместе с выходными данными перестановки. ^[6]

В этом отношении также доказана теорема, которая утверждает, что если существует эффективный противник UP A _π , который имеет немалое преимущество ε _π в игре на непредсказуемость против конструкции UP ψ _U,k и который делает полиномиальное число запросы к претенденту, то также существует противник UF A _f , который имеет немалое преимущество в игре с непредсказуемостью против UF, выбранного из семейства UF F . Отсюда можно показать, что максимальное преимущество противника UP A _π равно ε _π = O ( ε _{f .} ( qk ) ⁶). Здесь ε _f обозначает максимальное преимущество бега противника УФ за время O( t + ( qk ) ⁵) против UF, выбранного из F , где t — время работы противника PRP A _ψ , а q — количество сделанных им запросов. ^[6]^[7]

Кроме того, схема подписи, которая удовлетворяет свойству непредсказуемости и не обязательно псевдослучайности, по сути, является проверяемой непредсказуемой функцией (VUF). Верифицируемая непредсказуемая функция определяется аналогично проверяемой псевдослучайной функции (VRF), но псевдослучайность заменяется более слабой непредсказуемостью. Верифицируемые непредсказуемые перестановки — это перестановочные аналоги VUF или непредсказуемые аналоги VRP. VRP также является VUP, и VUP фактически может быть построен путем построения VRP с помощью конструкции Фейстеля, примененной к VRF. Но это не считается полезным, поскольку VUF построить гораздо проще, чем VRF. ^[8]

Приложения

ПРИНАДЛЕЖАЩИЙ

К x X → X ∀ X={0,1} ⁶⁴, К={0,1} ⁵⁶

АЭС-128

К x X → X ∀ k=X={0,1} ¹²⁸

См. также

Блочный шифр (семейства псевдослучайных перестановок, работающие с блоками бит фиксированного размера)
Шифрование с сохранением формата (семейства псевдослучайных перестановок, работающие с произвольными конечными множествами)

Ссылки

^ Кац, Джонатан; Линделл, Иегуда (2007). Введение в современную криптографию: принципы и протоколы . Чепмен и Холл/CRC. ISBN 978-1584885511 .
^ Михир Белларе , Филип Рогауэй (11 мая 2005 г.). «Глава 4: Псевдослучайные функции» (PDF) . Введение в современную криптографию . Проверено 18 мая 2020 г.
^ Крейг Джентри и Зульфикар Рамзан. «Устранение оракулы случайной перестановки в шифре четного Мансура» .
^ Луби, Майкл; Ракофф, Чарльз (1988). «Как построить псевдослучайные перестановки из псевдослучайных функций» . СИАМ Дж. Компьютер . 17 (2): 373–386. дои : 10.1137/0217022 .
^ Перейти обратно: ^а ^б ^с Пуния, Прашант (2007), Новые критерии проектирования хеш-функций и блочных шифров (PDF) , доктор философии. диссертация на факультете компьютерных наук Нью-Йоркского университета .
^ Перейти обратно: ^а ^б Достижения в криптологии – EUROCRYPT 2007: 26-я ежегодная международная конференция по теории и применению криптографических методов – Мони Наор, Международная ассоциация криптологических исследований
^ Стейнбергер, Джон П. (2007). «Неразрешимость конфликтов MDC-2 в модели идеального шифрования» (PDF) . Достижения в криптологии – EUROCRYPT 2007 . Конспекты лекций по информатике. Том. 4515. стр. 34–51. Бибкод : 2007LNCS.4515...34S . дои : 10.1007/978-3-540-72540-4_3 . ISBN 978-3-540-72539-8 . S2CID 33464561 . Архивировано из оригинала (PDF) 25 марта 2007 года . Проверено 27 февраля 2023 г.
^ Микали, Сильвио ; Рабин, Майкл ; Вадхан, Салил (1999), «Проверяемые случайные функции», 40-й ежегодный симпозиум по основам информатики (Нью-Йорк, 1999) , IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 1–11. стр. 120–130, CiteSeerX 10.1.1.207.6638 , doi : 10.1109/SFCS.1999.814584 , ISBN 978-0-7695-0409-4 , МР 1917552 , S2CID 221565852 .

[1] Кац, Джонатан; Линделл, Иегуда (2007). Введение в современную криптографию: принципы и протоколы . Чепмен и Холл/CRC. ISBN 978-1584885511 .

[2] Михир Белларе , Филип Рогауэй (11 мая 2005 г.). «Глава 4: Псевдослучайные функции» (PDF) . Введение в современную криптографию . Проверено 18 мая 2020 г.

[3] Крейг Джентри и Зульфикар Рамзан. «Устранение оракулы случайной перестановки в шифре четного Мансура» .

[4] Луби, Майкл; Ракофф, Чарльз (1988). «Как построить псевдослучайные перестановки из псевдослучайных функций» . СИАМ Дж. Компьютер . 17 (2): 373–386. дои : 10.1137/0217022 .

[puniya07-5] Перейти обратно: ^а ^б ^с Пуния, Прашант (2007), Новые критерии проектирования хеш-функций и блочных шифров (PDF) , доктор философии. диссертация на факультете компьютерных наук Нью-Йоркского университета .

[eurocrypt07-6] Перейти обратно: ^а ^б Достижения в криптологии – EUROCRYPT 2007: 26-я ежегодная международная конференция по теории и применению криптографических методов – Мони Наор, Международная ассоциация криптологических исследований

[puniya-7] Стейнбергер, Джон П. (2007). «Неразрешимость конфликтов MDC-2 в модели идеального шифрования» (PDF) . Достижения в криптологии – EUROCRYPT 2007 . Конспекты лекций по информатике. Том. 4515. стр. 34–51. Бибкод : 2007LNCS.4515...34S . дои : 10.1007/978-3-540-72540-4_3 . ISBN 978-3-540-72539-8 . S2CID 33464561 . Архивировано из оригинала (PDF) 25 марта 2007 года . Проверено 27 февраля 2023 г.

[8] Микали, Сильвио ; Рабин, Майкл ; Вадхан, Салил (1999), «Проверяемые случайные функции», 40-й ежегодный симпозиум по основам информатики (Нью-Йорк, 1999) , IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 1–11. стр. 120–130, CiteSeerX 10.1.1.207.6638 , doi : 10.1109/SFCS.1999.814584 , ISBN 978-0-7695-0409-4 , МР 1917552 , S2CID 221565852 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]