Асимптотические соотношения для вероятностей числа нескомпрометированных ключей в схемах распределения ключей, построенных на основе блочных кодов PDF

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

Антон Алексейчук, Сергей Конюшок

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

Summary: It is considered the probabilistic model of the correspondents compromising process in some broadcast key distribution schemes, built on base of orthogonal arrays of strength 1 or 2. As a result, we obtain proper bounds for binomial moments and asymptotic expressions of probability of the number non-compromising keys in these schemes under condition of random equiprobable t- subset correspondents compromising.

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

В [4, 5] предложены конструкции безусловно стойких схем распределения ключей на основе широковещательного шифрования информации, которые могут быть использованы в случае динамически изменяющегося множества скомпрометированных корреспондентов. В схеме распределения ключей, описанной в [5], применяется так называемая процедура динамического управления ключами, в соответствии с которой осуществляется широковещательная передача зашифрованных сеансовых ключей корреспондентам 1, 2, …, v из центра распределения ключей (ЦРК). При этом предполагается, что на множестве корреспондентов задана некоторая комбинаторная конфигурация (система подмножеств) D так, что каждому блоку B Í {1, 2, …, v} этой конфигурации соответствует определенный секретный ключ, которым обладают корреспонденты, принадлежащие множеству B (и только они). Секретные ключи заранее доставляются корреспондентам из ЦРК по защищенным каналам связи и используются ими в дальнейшем для расшифрования сообщений (сеансовых ключей), передаваемых из центра распределения ключей по открытому широковещательному каналу.

В [5 – 7] получены аналитические оценки ряда числовых параметров, характеризующих эффективность описанной выше, а также близкой к ней, схемы распределения ключей в том частном случае, когда в качестве комбинаторной конфигурации D используется произвольная симметричная неполная сбалансированная блок-схема [8].

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

References

1. Blom R.. An Optimal Class of Symmetric Key Generation System // Lekture Notes in Computer Science. – 1985. –  № 209. – P.335 – 338.

2. Stinson D. R. On Some Methods for Unconditionally Secure Key Distribution and Broadcast Encryption // Designs, Codes and Cryptography. – 1997. – № 12. –  P.215 – 243.

3. Blundo B., De Santis A., Herzberg A., Kutten S., Vaccaro U., Yung M.. Perfectly Secure Key Distribution for Dynamic Conferences // Lecture Notes in Computer Science. – 1993. – № 740. – P.471 – 486.

4. Fiat A., Naor M.. Broadcast Encryption // Lekture Notes in Computer Science. – 1994. – № 773. – P. 480 – 491.

5. Korjik V., Ivkov M., Merinovich Y., Bang A., Van Tilborg H.. A Broadcast Key Distribution Scheme Based on Block Designs // Lecture Notes in Computer Science. – 1995. – № 1025. – P.12 – 21.

6. Алексейчук А.Н., Паничек В.Г. Анализ стойкости ключевых сетей относительно компрометации корреспондентов // Збірник наукових праць КВІУЗ. Вип. 3. Київ. 1998. C. 76 – 83.

7. Конюшок С. М. Алгоритм оцінки параметрів оптимальних ключових структур, побудованих на основі неповних урівноважених блок-схем // Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні. – Київ: 2003. – Вип. 6. – С. 79 – 83.

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

9. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. М.: Связь, 1979. – 743 с.

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

 

Сайт видання: pnzzi.kpi.ua