Схемы многоадресного распределения ключей, основанные на конфигурациях Стинсона – Ван Транга PDF

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

А.Н. Алексейчук, С.Н. Конюшок

УДК 621.391:517.95

Схемы многоадресного распределения ключей, основанные на конфигурациях Стинсона – ван Транга / Алексейчук А. Н., Конюшок С. Н. // Кибернетика и системный анализ.

Исследуются характеристики эффективности схем многоадресного распределения ключей, основанных на (v, b, r, l)-конфигурациях. Получены оценки устойчивости и связности указанных конфигураций, обобщающие и усиливающие известные оценки характеристик эффективности схем многоадресного распределения ключей, основанных на уравновешенных неполных блок-схемах.  

Библиогр.: 18 назв.

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

УДК 621.391:517.95

Схеми багатоадресного розподілу ключів, що побудовані на конфігураціях Стінсона – ван Транга / Олексійчук А. М., Конюшок С. М. // Кібернетика і системний аналіз.

Досліджуються характеристики ефективності схем багатоадресного розподілу ключів, що основуються на (v, b, r, l)-конфігураціях. Отримані оцінки стійкості та зв’язності зазначених конфігурацій, які узагальнюють та підсилюють відомі оцінки характеристик ефективності схем багатоадресного розподілу ключів, що основуються на урівноважених неповних блок-схемах. 

Бібліогр.: 18 назв.

Схема многоадресного распределения ключей (СМРК) представляет собой криптографический протокол, с помощью которого доверенная сторона, выполняющая функции центра распределения ключей (ЦРК), осуществляет передачу некоторой вспомогательной секретной информации абонентам сети связи так, что со временем абоненты, входящие в определенную привилегированную коалицию, могут восстановить общий секретный ключ, который в зашифрованном виде передается из ЦРК по широковещательному каналу связи (по этой причине СМРК называют также схемами широковещательного шифрования – broadcast encryption schemes).

Схемы многоадресного распределения ключей предложены в [1, 2]. На сегодняшний день список публикаций, посвященных исследованию их свойств и методов построения, насчитывает десятки наименований. Отметим обзорные статьи [3, 4] и работы [5 – 7], содержащие, в частности, информацию о различных аспектах практического применения СМРК.

В [8] (и впоследствии, независимо в [5]) предложен общий подход к построению схем многоадресного распределения ключей на основе покрытий множества V абонентов определенными подмножествами. Каждому такому подмножеству B (блоку покрытия) ставится в соответствие секретный ключ, вырабатываемый в ЦРК. Затем каждому абоненту  по защищенному каналу связи передают набор секретных ключей, соответствующих подмножествам B, содержащим x. Наконец, для передачи общего секретного ключа некоторой привилегированной коалиции  этот ключ зашифровывают на секретных ключах абонентов из P, соответствующих определенным подмножествам , образующим покрытие множества P.

В [8] получены оценки параметров, характеризующих практическую эффективность СМРК, в которых подмножества B определяются как блоки (уравновешенных неполных) блок-схем с множеством элементов V (см. [9, 10]).

Целью данной статьи является исследование характеристик более общего класса схем многоадресного распределения ключей, соответствующих так называемым (v, b, r, l)-конфигурациям, введенным Д. Стинсоном и Т. ван Трангом [11]. Рассматриваемые СМРК имеют безусловную (теоретико-информационную) стойкость и включают в себя, в качестве частных случаев, СМРК, основанные на блок-схемах [8] и блоковых кодах [12].

Полученные в статье результаты показывают, что, хотя схемы многоадресного распределения ключей, основанные на (v, b, r, l)-конфигурациях, уступают по своим характеристикам одной из лучших на сегодняшний день безусловно стойких СМРК (так называемой схеме CST) [5], они являются более эффективными по сравнению со схемами [8]. В частности, общее число секретных ключей в СМРК, соответствующей (v, b, r, l)-конфигурации, может быть меньше числа абонентов сети, что принципиально невозможно для СМРК, основанных на блок-схемах.

Изложенные в статье результаты частично анонсированы в [13].

References

1. Berkovits S. How to broadcast a secret // Advances in Cryptology – EUROCRYPT’91. – № 547. – Berlin: Springer-Verlag, 1992. – P. 536 – 541.

2. Fiat A., Naor M. Broadcast encryption // Advances in Cryptology – CRYPTO’93. – № 773. – Berlin: Springer-Verlag, 1994. – P. 480 – 491.

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

5. Naor D., Naor M., Lotspiech J. Revocation and tracing schemes for stateless receivers // Advances in Cryptology – CRYPTO’01. – № 2139. – Berlin: Springer-Verlag, 2001. – P. 41 – 62.

6. Asano T. A revocation scheme with minimal storage at receivers // ASIACRYPT’02. – № 2501. – Berlin: Springer-Verlag, 2002. – P. 433 – 450.

7. Naor M., Pincas B. Efficient trace and revoke schemes // Financial Cryptogtaphy’00. – № 1962. – Berlin: Springer-Verlag, 2000. – P. 1 – 20.

8. Korjik V., Ivkov M., Merinovich Y., Barg A., van Tilborg H. A broadcast key distribution scheme based on block designs // Cryptography and Coding V. – № 1025. – Berlin: Springer-Verlag, 1995. – P. 12 – 21.

9. Холл М. Комбинаторика: Пер. с англ. – М.: Мир, 1970. – 427 с.

10. Райзер Г. Дж. Комбинаторная математика: Пер. с англ. – М.: Мир, 1966. – 154 с.

11. 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.

12. Алексейчук А. Н., Конюшок С. Н. Асимптотические соотношения для вероятностей числа нескомпрометированных ключей в схемах распределения ключей, построенных на основе блоковых кодов // Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні. – Вип. 8. – Київ, 2004. – С. 85 – 90.

  1. l)-конфигурациях // Праці міжнародної конференції “Питання оптимізації обчислень (ПОО – XXXII)”, присвяченої пам’яті акад. В. С. Михалевича. – Київ: Ін-т кібернетики ім. В. М. Глушкова НАН України, 2005. – С. 22 – 23.

13. Дельсарт Ф. Алгебраический подход к схемам отношений теории кодирования: Пер. с англ. – М.: Мир, 1976. – 136 с.

  1. - М.: Связь, 1979. - 743 с.

15. Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии. – М.: Гелиос АРВ, 2001. – 480 с.

16. Дискретная математика и математические вопросы кибернетики / Васильев Ю.Л., ВетухновскийФ.Я., Глаголев В. В. и др. – Т. 1. – М.: Наука, 1974. – 311 с.

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

 

 

Сайт видання:http://www.kibernetika.org/