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

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

Определение

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

Для любого , является биекцией из в , где . $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}$
Для всех вероятностных полиномиальных по времени различителей : , где выбирается равномерно случайным образом и выбирается равномерно случайным образом из набора перестановок на n -битовых строках. ^[1] $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}$

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

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

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

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

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

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

Связанные концепции

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

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

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

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

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

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

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

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

Приложения

ДЕС

К х Х → Х ∀ Х={0,1} ⁶⁴ , К={0,1} ⁵⁶

АЕС-128

К х Х → Х ∀ к=Х={0,1} ¹²⁸

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

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

Ссылки

^ Кац, Джонатан; Линделл, Йехуда (2007). Введение в современную криптографию: принципы и протоколы . Chapman and Hall/CRC. ISBN 978-1584885511.
^ Михир Белларе , Филлип Рогауэй (2005-05-11). "Глава 4: Псевдослучайные функции" (PDF) . Введение в современную криптографию . Получено 2020-05-18 .
^ Крейг Джентри и Зульфикар Рамзан. «Устранение оракулов случайной перестановки в шифре Эвен-Мансура».
^ Luby, Michael; Rackoff, Charles (1988). «Как построить псевдослучайные перестановки из псевдослучайных функций». SIAM J. Comput . 17 (2): 373–386. doi :10.1137/0217022.
^ abc Puniya, Prashant (2007), Новые критерии проектирования хэш-функций и блочных шифров (PDF) , докторская диссертация, кафедра компьютерных наук, Нью-Йоркский университет.
^ ab Advances in Cryptology – EUROCRYPT 2007: 26-я ежегодная международная конференция по теории и применению криптографических методов – Мони Наор, Международная ассоциация криптологических исследований
^ Steinberger, John P. (2007). "The Collision Intractability of MDC-2 in the Ideal-Cipher Model" (PDF) . Advances in Cryptology - EUROCRYPT 2007 . Lecture Notes in Computer Science. Vol. 4515. pp. 34–51. Bibcode :2007LNCS.4515...34S. doi :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., Лос-Аламитос, Калифорния, стр. 120–130, CiteSeerX 10.1.1.207.6638 , doi : 10.1109/SFCS.1999.814584, ISBN 978-0-7695-0409-4, MR 1917552, S2CID 221565852.