Шифры, стойкие к атакам на основе неупорядоченной совокупности шифртекстов, полученных на одном ключе

Следуя [God90], введем 

Определение 4.2.1. Будем говорить, что шифр  удовлетворяет условию -стойкости (или является -стойким), если для любого  и для любого  выполняется равенство

                                           		               (4.2.1)

Свойство -стойкости можно было назвать точнее свойством неупорядоченной -кратной совершенной стойкости шифра, однако это намного длиннее. Буква  в названии условия  это первая буква слова Unordered (неупорядоченный). 
Далее для упрощения записи будем вместо  использовать запись  имея в виду, что имеется взаимно однозначное соответствие между множествами  и  
Как и совершенные по Шеннону шифры, -стойкие шифры должны быть транзитивными.

Лемма 4.2.2. Если шифр  удовлетворяет условию -стойкости, то для любых  справедливо неравенство 

Доказательство. От противного: предположим, что   для некоторой пары подмножеств  и  любого  Но тогда, очевидно,  в то время как  Получили противоречие с условием  -стойкости. 
Как и в § 2.2, далее будем использовать обозначения 

Лемма 4.2.3. Если шифр  удовлетворяет условию -стойкости, то для числа его ключей  выполняется неравенство 

Более того, если 
то 
(i) 	 для любых 
(ii) 	если  и  для некоторых  то 

Доказательство. Пусть  По лемме 4.2.2 для любого  найдется такой  что   Зафиксировав  и заставив  пробегать все множество  получим, по меньшей мере,  ключей. Отсюда следует, что 
Пусть теперь . Рассуждения, проведенные при доказательстве неравенства, сразу дают единственность соответствующего ключа, что дает  (i).
Пусть  и   такие совокупности, что  и  Тогда, согласно (i),   единственный такой элемент из  По условию

откуда  Так как  то  что и требуется.

Теорема 4.2.4. Если шифр  удовлетворяет условию -стойкости, (), то    

                                                               			    (4.2.2)
Более того, если  

то 
(i) 	при      для любых      выполняется одно из равенств:  или 
(ii) 	если  то  при любом  для которого 

Доказательство. Согласно лемме 4.2.3, достаточно показать, что

Выберем любой шифртекст  Найдутся  такие, что  Для наглядности дальнейших рассуждений приведем рисунок:

                                                                         

                                                                         

Рис. 5

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

то такое множество  можно также представить в виде

,

или, наконец, в виде 

Поэтому

что и требуется.
Обратимся к проверке свойств (i) и (ii). Предположим, что 

Тогда и 

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

Если бы некоторый  содержался более чем в    -множествах, то отсюда следовало бы неравенство 

что не так. Значит каждый  содержится в точности в  разрешенных -множествах. Поэтому если  то обязательно 

В самом деле, мы насчитали  подмножеств в множестве  содержащих  Поэтому, если  то в  можно было найти еще некоторое число подмножеств, чего быть не может. Отсюда следует (i). Условие (ii) сразу следует из леммы 4.2.3. Заметим, что при  утверждение пункта (i) неверно. 
Рассмотрим нижнюю границу из теоремы 4.2.4 применительно к случаю, когда  При этом условии   минимально возможное число ключей, необходимое для обеспечения -стойкости. Заметим, что в случае, когда  изучение -стойких шифров, для которых  сводится по теореме 4.2.4 к случаю, когда 
Пусть для простоты  Тогда каждое правило зашифрования  это некоторая подстановка на  и, согласно условию (ii) теоремы 4.2.4, все ключи -стойкого шифра  равновероятны. В этих условиях можно сформулировать критерий того, что  подстановок на  образуют множество  отвечающее -стойкой шифрсистеме. Заметим,  что  в  таком  случае    состоит  из  всех  -подмножеств  из  то есть что все -подмножества из   разрешенные. В самом деле, 

Так как  то  

Теорема 4.2.5. Пусть  и   множество подстановок на  рассматриваемое как множество правил зашифрования для шифра  с числом ключей  Тогда такой шифр является -стойким тогда и только тогда, когда
(i) 	 для любой пары -подмножеств  (из );
(ii) 	 для любого 

Доказательство. Необходимость следует из условий (ii) теоремы 4.2.4 и (i) леммы 4.2.3. Для проверки достаточности рассмотрим вероятность 

Вместе с тем, 

В результате получаем равенство  что и требуется.

Заметим, что в случае  теорема 4.2.5 в точности совпадает с теоремой Шеннона.

Определение 4.2.6. Множество подстановок  на  называется -однородным  на  если для любых  существует ровно  подстановок  для которых 

Однородные множества подстановок изучались в ряде работ, например [Nom85], [StiTei90], [Bie92], [Bie95].
Согласно пункту (ii) теоремы 4.2.5, задача построения -стойких шифров в случае, когда   эквивалентна задаче построения -однородных множеств подстановок на множестве из  элементов. Эта задача эквивалентна также задаче построения так называемых перпендикулярных массивов специального вида.  

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

Непосредственно из определений 4.2.1, 4.2.7 и теоремы 4.2.5 следует 

Теорема 4.2.8. Если существует перпендикулярный массив  то существует и -стойкий шифр  с параметрами 

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

В случае когда   построение -стойкого шифра эквивалентно построению перпендикулярного массива  Попутно отметим, что если выписать друг под другом подстановки -однородного множества подстановок степени  то получится перпендикулярный массив 
Известно, что при   существуют перпендикулярные массивы  ([Sti90]). Например, существует  при  и  Имеется бесконечный класс массивов  для любой степени простого числа  где  При  и  существуют массивы  Все эти примеры получены на основе -однородных множеств подстановок, являющихся группами. 
Глубокие результаты по теории перпендикулярных массивов изложены в [Bie94].
Далее мы отдельно рассмотрим случай   Используем для построения -стойкого шифра перпендикулярный массив  где   нечетное простое число.

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

Доказательство. Рассмотрим произвольные столбцы матрицы  с номерами  Пусть произвольный элемент  содержится в этих столбцах  раз соответственно. Из определения перпендикулярного массива следует, что в строках подматриц, состоящих из столбцов  и  число пар элементов, содержащих  выражается в виде 

Аналогично 

Из полученных соотношений следует равенство 

что и требуется.
Пусть   нечетное простое число и

 конечное поле. Рассмотрим матрицу  размеров  у которой столбцы занумерованы элементами  а строки  некоторым множеством  из  упорядоченных пар  На пересечении столбца  и строки  в  расположим элемент 

Теорема 4.2.10. Множество  можно выбрать таким образом, что матрица  является перпендикулярным массивом  

Доказательство. Сделаем ряд замечаний.
Поле  содержит единицу  и противоположный к ней элемент  По лемме 4.2.9 в столбце матрицы  с номером  каждый элемент поля встречается ровно  раз. Это касается и нуля поля     Таким образом, среди номеров строк должно быть ровно  пар  таких, что  то есть 
При  соответствующая строка матрицы  состоит из одинаковых элементов (равных ). Поэтому для построения перпендикулярного массива необходимо условие, при котором каждая строка была бы пронумерована парой  в которой 
Покажем, что если для некоторого  пара  принадлежит  и   перпендикулярный массив, то  
В самом деле, пусть, наряду с парой  множество  содержит также пару  в которой  Рассмотрим тогда элементы матрицы  стоящие на пересечении столбца с номером  и строк с номерами  и  Они равны соответственно  и  Аналогично в столбце с номером  на  позициях с теми же  номерами расположены соответственно  и  Это противоречит определению перпендикулярного массива, так как в выделенных строках находятся пары, отличающиеся лишь перестановкой своих элементов. Заметим, что среди “забракованных” пар  содержатся пары вида  Если же  содержит пары  то на пересечении строк матрицы  с этими номерами и столбцов с номерами  и  окажутся пары

 и 

что также невозможно.

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

и 

с помощью которых получаем соотношение 

или 

Так как по условию  то 

 и 

Отсюда следует, что первый случай невозможен.
Во втором случае 

и 

откуда 

или 

Так как по условию  то  что противоречит нашему выбору множества пар 
Тем самым мы показали, что матрица  является перпендикулярным массивом. Теорема доказана.

Вопрос о существовании -стойких шифров с минимальным числом ключей при  является открытым. Если отказаться от условия минимальности числа ключей, то при любом  несложно указать пример -стойкого шифра. Это будет ясно из дальнейших рассмотрений.
Рассмотрим теперь неэндоморфные -стойкие шифры. Ослабим требование  и рассмотрим случай, когда

  и 
Пусть сначала  Тогда 

Для -стойкого шифра по лемме 4.2.3 выполняется неравенство  Но  поэтому 

Согласно утверждению (i) леммы 4.2.3,  тогда и только тогда, когда для любого  и любого  найдется единственный элемент  такой, что  Составим матрицу зашифрования:

		…		
		…		
…	…	…	…	
		…		

Из сказанного следует, что любой столбец матрицы не может содержать совпадающих элементов. Другими словами, каждый столбец матрицы  некоторая перестановка элементов множества  Кроме того, и каждая строка состоит из различных элементов. 
Прямоугольная матрица, составленная из элементов множества  в которой строки и столбцы не содержат одинаковых элементов, называется латинским прямоугольником. Таким образом, в рассматриваемом случае матрица зашифрования -стойкого шифра является латинским прямоугольником. 
Известна приближенная формула для числа  латинских прямоугольников, доказанная в 1946 году П.Эрдешем и И.Капланским ([Коф75]):

имеющая место при условии  Позже К.Ямамото доказал справедливость этой формулы при условии  ([Рио63]).
Пусть теперь  По утверждению (i) теоремы 4.2.4 число ключей  достигает минимального значения  при  причем множество  разбивается на  подмножеств  каждое мощности  и такие, что для любого  имеет место равенство  для некоторого 
Введем обозначение 

Тогда

  разбиение  множества   Согласно утверждению (ii) теоремы 4.2.4, из равенства  следует, что  Легко видеть, что каждая тройка  образует -стойкий шифр,  для которого  
Тем самым, изучение -стойких шифров в случае, когда

 и 

сводится к изучению -стойких шифров, для которых 
В заключение докажем, что совершенная стойкость -стойкого шифра не зависит от распределения вероятностей на множестве открытых текстов.

Теорема 4.2.11. Пусть   шифр с априорным распределением вероятностей  удовлетворяющий условию -стойкости, и   шифр, отличающийся от  лишь распределением вероятностей  Тогда  также удовлетворяет условию -стойкости.

Доказательство. Воспользуемся критерием -стойкости шифра  в форме равенства 

записанного в виде

          		        (4.2.3)

Проверим аналогичное равенство применительно к  шифру  Для этого заметим, что 

       			 (4.2.4)

где   любой фиксированный элемент из  Это следует из того, что  не зависит от 

Согласно (4.2.3), правую часть (4.2.4) можно записать в виде

поскольку 

Отсюда следует

 что и требуется.