Безусловно стойкие схемы распределения ключей, Построенные по конгруэнциям универсальных алгебр PDF

Автори:Алексейчук А.Н., Конюшок С.Н., Скрыпник Л.В.

Алексейчук А.Н., Конюшок С.Н., Скрыпник Л.В.

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

Одним из перспективных направлений современной криптографии, активно развивающихся на протяжении последних 15 – 20 лет, является построение криптографически стойких протоколов (схем) распределения ключей в системах защищенной многоадресной связи. Характерная особенность таких систем заключается в наличии большого числа авторизованных абонентов, образующих наделенные различными правами группы (коалиции), состав которых может динамически изменяться [1, 2]. 

Говоря неформально, схема распределения ключей (СРК) представляет собой криптографический протокол, с ипользованием которого доверенная сторона (центр распределения ключей (ЦРК) или дилер) передает абонентам сети связи некоторую вспомогательную секретную информацию так, что со временем абоненты, входящие в определенную привилегированную коалицию, могут вычислить общий (групповой) ключ. Схема распределения ключей называется безусловно стойкой, если каждая запрещенная (для данной привилегированной) коалиция абонентов не может получить никакой информации об этом ключе даже при наличии неограниченных вычислительных ресурсов [3, 4].

Подробные сведения об известных методах построения, анализа и различных аспектах практического применения СРК можно найти в обзорных работах [3, 5, 6].

Настоящая статья посвящена изучению специального класса безусловно стойких СРК, а именно, схем предварительного распределения ключей (СПРК). Центральной задачей исследования таких схем является разработка конструктивных методов синтеза СПРК, имеющих оптимальные или близкие к оптимальным характеристики эффективности (так называемые информационную скорость и полную информационную скорость) [3 – 7].

В настоящее время конструкции оптимальных СПРК известны лишь для отдельных типов структур спецификаций (совокупностей пар привилегированных и запрещенных коалиций участников схемы) [3, 7]. При этом, несмотря на разнообразие конкретных видов СПРК, общая теория построения и анализа схем предварительного распределения ключей для произвольных структур спецификаций находится в состоянии становления. Отметим статью [7], в которой предложена конструкция так называемых линейных СПРК, включающих в себя большинство известных видов схем предварительного распределения ключей. 

В настоящей статье предложена комбинаторная модель СПРК, позволяющая, по мнению авторов, более наглядно и, практически, без потери общности выразить существенные свойства произвольной схемы предварительного распределения ключей. С использованием данной модели получено формальное описание СПРК в терминах определенных систем отношений эквивалентности (ОЭ) на конечном множестве. Предложен метод построения СПРК по системам конгруэнций конечных универсальных алгебр, обобщающий конструкцию линейных схем предварительного распределения ключей [7]. Отметим, что решения аналогичных задач для другого класса протоколов распределения ключей (так называемых совершенных схем разделения секрета) получены ранее в [8].

References

1. Canetti R., Malkin T., Nissim K. Effcient communication-storage tradeoffs for multicast encryption // Advances in Cryptology – EUROCRYPT’99, Lecture Notes in Computer Science. – 1999. – P. 459 – 474.

2. Canetti R., Garay J., Itkis G., Micciancio D., Naor M., Pinkas B. Issue in multicast security: a taxonomy and efficient constructions // INFOCOM’99. – 1999. – P. 708 – 716.

3. Stinson D.R. On some methods for unconditionally secure key distribution and broadcast encryption // Designs, Codes and Cryptography. – 1997. – Vol. 12. – P. 215 – 243.

4. Stinson D.R., van Trung T. Some new results on key distribution patterns and broadcast encryption // Designs, Codes and Cryptography. – 1998. – Vol. 15. – P. 261 – 279.

5. Конюшок С.М., Олексійчук А.М. Безумовно стійки схеми розподілу ключів в інформаційних та телекомунікаційних системах з великою кількістю абонентів: І. Схеми попереднього розподілу й узгодження ключів // Прикладная радиоэлектроника. – 2006. – Т. 5. – № 1. – С. 83 – 93.   

6. Конюшок С.М., Олексійчук А.М. Безумовно стійки схеми розподілу ключів в інформаційних та телекомунікаційних системах з великою кількістю абонентів: ІІ. Схеми багатоадресного розподілу ключів // Прикладная радиоэлектроника. – 2006. – Т. 5. – № 1. – С. 94 – 104.   

7. Padro C., Gracio I., Martin S., Morillo P. Linear key predistribution schemes // Designs, Codes and Cryptography. – 2002. – Vol. 25. – P. 281 – 298.

8. Алексейчук А.Н. Схемы разделения секрета и конечные универсальные алгебры // Реєстрація, зберігання і обробка даних, 2005. – Т. 7. – №  2. – С. 55 – 65.

9. Кон П. Универсальная алгебра / Пер. с англ. – М.: Мир, 1968. – 351 с.

10. Биркгоф Г. Теория решеток / Пер. с англ. – М.: Наука, 1984. – 568 с.

11. Сачков В.Н. Введение в комбинаторные методы дискретной математики. – М.: Наука, 1982. – 384с.

 

 

Сайт видання:snu.lg.ua/visniksnu/