Введение
Класс функций в криптографии
В криптографии псевдослучайная перестановка (PRP) — это функция, которую нельзя отличить от случайной перестановки (то есть перестановки, выбранной случайным образом с равномерной вероятностью из множества всех перестановок на области определения функции) при разумных вычислительных затратах.
In cryptography, a pseudorandom permutation (PRP) is a function that cannot be distinguished from a random permutation (that is, a permutation selected at random with uniform probability, from the family of all permutations on the function's domain) with practical effort.
Определение
Пусть F — отображение. F является PRP (псевдослучайной перестановкой), если и только если:
Для любого ключа K, отображение FK является биекцией из {0, 1}^n в {0, 1}^n, где n — размер входных данных.
Для любого ключа K, существует "эффективный" алгоритм для вычисления FK(x) для любого x из {0, 1}^n.
Для всех вероятностных полиномиальных разграничителей D выполняется: |Pr[D(FK(x)) = 1] - Pr[D(π(x)) = 1]| пренебрежимо мало, где K выбирается равномерно случайно, а π выбирается равномерно случайно из множества всех перестановок n-битовых строк.
Семейство псевдослучайных перестановок — это набор псевдослучайных перестановок, в котором конкретная перестановка может быть выбрана с использованием ключа.
For any , is a bijection from to , where For any , there is an "efficient" algorithm to evaluate for any ,. For all probabilistic polynomial time distinguishers : , where is chosen uniformly at random and is chosen uniformly at random from the set of permutations on n bit strings. A pseudorandom permutation family is a collection of pseudorandom permutations, where a specific permutation may be chosen using a key.
Модель блок-шифров
Идеализированная абстракция (ключевого) блочного шифра представляет собой истинно случайную перестановку отображений между открытым текстом и зашифрованным текстом. Если существует алгоритм, способный отличить шифр от случайной перестановки и достигающий существенного преимущества при затратах, меньших, чем определено параметром безопасности блочного шифра (обычно это означает, что требуемые затраты должны быть сопоставимы с полным перебором по пространству ключей шифра), то шифр считается взломанным, по крайней мере, в теоретическом смысле, даже если такой взлом не приводит к немедленному практическому нарушению безопасности. От современных шифров ожидается сверхпсевдослучайность. То есть, шифр должен быть неотличим от случайно выбранной перестановки на том же множестве сообщений, даже если противник имеет доступ к шифрованию и расшифрованию как к "черному ящику".
Связи с псевдослучайной функцией
Майкл Люби и Чарльз Рэккофф показали, что "сильную" псевдослучайную перестановку можно построить из псевдослучайной функции, используя построение Люби–Рэккоффа, которое реализовано на основе шифра Фейстеля.
Непредсказуемая пермутация
Непредсказуемая перестановка (UP) Fk – это перестановка, значения которой нельзя предсказать с помощью быстрого рандомизированного алгоритма. Непредсказуемые перестановки могут использоваться как криптографический примитив, строительный блок для криптографических систем с более сложными свойствами. Противник для непредсказуемой перестановки определяется как алгоритм, которому предоставляется доступ к оракулу для операций прямой и обратной перестановки. Противнику задается входное значение k и требуется предсказать значение Fk. Ему разрешается делать серию запросов к оракулу для помощи в этом предсказании, но запрещается запрашивать само значение k. Рандомизированный алгоритм для генерации перестановок генерирует непредсказуемую перестановку, если его выходные данные представляют собой перестановки на множестве элементов (описанных двоичными строками длиной n), которые нельзя предсказать с точностью, значительно превосходящей случайную, со стороны противника, выполняющего полиномиальное (от n) количество запросов к оракулу до этапа вызова, время работы которого полиномиально от n, а вероятность ошибки для всех случаев меньше 1/2. Иными словами, ее нельзя предсказать в классе сложности PP, релятивизированном оракулом для перестановки. В этой связи доказана теорема, утверждающая, что если существует эффективный противник UP Aπ, имеющий ненулевое преимущество επ в игре непредсказуемости против конструкции UP ψU,k и выполняющий полиномиальное число запросов к проверяющему, то существует и противник UF Af, имеющий ненулевое преимущество в игре непредсказуемости против UF, выбранного из семейства UF F. Из этого следует, что максимальное преимущество противника UP Aπ составляет επ = O(εf * (qk)⁶). Здесь εf обозначает максимальное преимущество противника UF, работающего за время O(t + (qk)⁵), против UF, выбранного из F, где t – время работы противника PRP Aψ, а q – количество запросов, сделанных им. Кроме того, схема подписи, удовлетворяющая свойству непредсказуемости, а не обязательно псевдослучайности, по сути является проверяемой непредсказуемой функцией (VUF). Проверяемая непредсказуемая функция определяется аналогично проверяемой псевдослучайной функции (VRF), но с заменой псевдослучайности на более слабую непредсказуемость. Проверяемые непредсказуемые перестановки являются перестановочными аналогами VUF или непредсказуемыми аналогами VRP. VRP также является VUP, и VUP может быть фактически построен путем создания VRP с использованием конструкции Фейстеля, примененной к VRF. Однако это не считается полезным, поскольку VUF, по-видимому, гораздо проще построить, чем VRF.