Построение - и -стойких шифров

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

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

Лемма 7.2. Если шифр  удовлетворяет условию -стойкости, то 

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

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

Более того, если

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

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

  					                                		    (7.1)

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

и, следовательно, 

Так как каждый  является первым элементом в не менее чем  разрешенных -строках, и всего их ровно

то ясно, что  начинает в точности  разрешенных -строк. 
Пусть  Если  то в  и  можно построить больше, чем  разрешенных -строк, чего быть не может. Следовательно,  откуда следует (i). Свойство (ii) следует из утверждения (ii) леммы 7.2.
Нижняя оценка числа ключей -стойкого шифра приводится в теореме 7.3. Рассмотрим сначала случай, отвечающий минимальным значениям параметров, когда 

 и 

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

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

Доказательство. Необходимость (i) следует из (ii) теоремы 7.3, а необходимость (ii) следует из (i) леммы 7.2. 
Пусть выполняются (i) и (ii) и  Тогда

Кроме того,

В последнем равенстве используется то обстоятельство, что для любого  сущеcтвует единственная подстановка , для которой , поэтому в сумме 

будет учтен каждый  и ровно один раз. Отсюда получаем равенство  что и требуется.

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

подстановок  для которых 

Доказательство. Согласно лемме 5.5, любой эндоморфный -стойкий шифр является и -стойким при  Пусть  и пусть, как и ранее, 
Из условия  -стойкости имеем равенство 

                                  (7.2)

Если зафиксировать  и заставить  пробегать все  возможных значений элементов из  то получим разбиение

множества  А так как левая часть в (7.2) постоянна, то

и

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

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

Согласно теореме 7.4, выяснение свойства -стойкости шифра с  ключами в точности эквивалентно выяснению свойства -транзитивности множества подстановок на множестве из  элементов. Поэтому задача построения -стойкого шифра с минимальным числом ключей (а по лемме 5.9  и -стойкого шифра) равносильна задаче построения -транзитивного множества подстановок мощности  Из теоремы 7.5 следует также, что всякое -транзитивное множество подстановок является и

 -транзитивным

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

точки  в группе  и разложим  в смежные классы по подгруппе 

где 

Тогда 

и 

Свойство -транзитивности отвечает точно -транзитивной группе. Известны два семейства простых примеров -транзитивных групп  это группы  и  Симметрическая группа  точно -транзитивна. Она дает примеры минимальных по ключам - и -стойких шифров. Знакопеременная группа  точно -транзитивна и дает примеры минимальных по ключам - и -стойких шифров. 
Точно - и -транзитивные группы известны для бесконечного множества значений  Например (см. [Глу90]), при  где   простое число, полная аффинная группа  точно -транзитивна, а проективная линейная группа  точно -транзитивна. 
 Ситуация резко меняется для  Кроме  и  -транзитивными группами являются только группы Матье:   (группа  действует на множестве из  элементов). Группы   -транзитивны, группы   -транзитивны. При этом   точно -транзитивна,   точно -транзитивна,  не являются точно -транзитивными (и -транзитивными). 
В 1873 г. К.Жорданом доказано, что при  точно -транзитивных групп, отличных от  не существует. Таким образом,  и  (порядков  и )  единственные нетривиальные примеры точно -транзитивных групп для 
Укажем задание групп Матье образующими элементами, как подгрупп симметрических групп соответствующих степеней ([Хол62]): 

, где

 причем стабилизатор точки  в  совпадает с 

где

где

причем стабилизатор точки  в  совпадает с  

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

Рассмотрения в случае  совпадают с проведенными ранее рассуждениями для -стойких шифров. При   для  согласно пункту (i) теоремы 7.3. Кроме того, 

 разбиение множества  такое что  для любого  и 
Если  то 

 разбиение множества  Согласно (ii) теоремы 7.3, из равенства  следует, что  Тогда каждая тройка   образует -стойкий шифр. Поэтому изучение -стойких шифров с параметрами 

 и 

сводится к уже рассмотренному случаю 
Для -стойких шифров справедлив аналог теоремы 4.3.16 ([Cas98]).

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

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

Теорема 7.8. Число ключей  -стойкого шифра удовлетворяет неравенству