Методы и модель пороговой подписи на основе теории решеток тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Кустов Елизар Филаретович

• Кустов Елизар Филаретович
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Кустов Елизар Филаретович

Реферат

Synopsis

Введение

Глава 1. Обзор и анализ существующих схем пороговых подписей

1.1 Схема разделения секрета по интерполяционному многочлену Лагранжа

1.2 Схема разделения секрета по интерполяционному многочлену Ньютона

1.3 Схема разделения секрета на основе китайской теоремы об остатках

1.4 Схемы разделения секрета, основанные на кодах, исправляющих ошибки

1.5 Схемы разделения секрета, основанные на теории решеток

1.6 Схемы разделения секрета, основанные на изогениях эллиптических кривых

1.7 Схемы разделения секрета, основанные на хэш-функциях

1.8 Схемы разделения секрета на основе многомерных уравнений

1.9 Сравнительный анализ схем разделения секрета

1.10 Выводы по главе

Глава 2. Пороговые схемы на основе теории решеток

2.1 Математические задачи

2.1.1 Угрозы современной криптографии, связанные с квантовым алгоритмом Шора

2.1.2 Задачи Learning with Error и Learning with Rounding

2.1.3 Задача Short Integer Solution

2.3 Интерполяционные многочлены

2.3.1 Интерполяционный многочлен Лагранжа

2.3.2 Интерполяционный многочлен Ньютона

2.4 Описание методов пороговой подписи на основе теории решеток

2.4.1 Пороговая подпись на основе интерполяционного многочлена Лагранжа

2.4.1 Пороговая подпись на основе интерполяционного многочлена Ньютона

2.5 Безопасность и выбор параметров разработанных пороговых подписей

2.6 Сравнительный анализ разработанных схем с существующими

2.7 Выводы по главе

Глава 3. Модель интеграции квантового распределения ключей с постквантовыми пороговыми подписями на основе теории решеток

3.1 Обзор протоколов квантовой криптографии

3.1.1 Протокол BB84

3.1.2 Протокол BB84 на фазовом кодировании

3.1.3 Протокол B92

3.1.4 Протокол SARG04

3.1.5 Протокол Lo05

3.1.6 Протокол COW

3.1.7 Протокол E91

3.2 Вопросы и проблемы КРК

3.2.1 Атаки на системы КРК

3.2.2 Ограниченная дальность канала

3.2.3 Эффективное разветвление квантовых сетей

3.3 Архитектура модели и сценарии применения

3.3.1 Модель безопасного подписания транзакций в системе с распределенным управлением ключами

3.3.2 Модель формирования пороговой подписи с несколькими узлами КРК

3.4 Безопасность модели интеграции пороговой подписи и КРК

3.4.1 Модель угроз и модель нарушителя

3.5 Выводы по главе

Заключение

Список литературы

Список рисунков

Приложение А. Свидетельства о регистрации программ для ЭВМ

Приложение Б. Тексты публикаций по теме исследования

Введение диссертации (часть автореферата) на тему «Методы и модель пороговой подписи на основе теории решеток»

Реферат Общая характеристика работы

Актуальность работы. Первый метод разделения секрета был предложен Шамиром [1] и Блейкли [2] независимо друг от друга. Схемы разделения секрета применяются в случаях, когда существует значимая вероятность компрометации хранителей секрета, но вероятность недобросовестного сговора значительной части участников считается пренебрежимо малой.

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

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

После изобретения Питером Шором квантового алгоритма [3] возник вопрос о создании новых криптосистем устойчивых к атаке с использованием квантового компьютера. Традиционные алгоритмы цифровой подписи, такие как RSA и ECDSA, становятся уязвимыми перед квантовыми атаками, что требует разработки новых постквантовых решений. На данный момент компания IBM имеет в своём распоряжении квантовую систему [4], состоящую из 20 кубитов. Ожидается, что к 2035 году появятся машины с 1000+ кубитами, способные реализовать алгоритм Шора для практических атак [5]. Можно предположить, что развитие квантового компьютера, до состояния, которое представляло бы угрозу распространённым сегодня алгоритмам, это вопрос ближайшего времени.

Исследование в этой области дало толчок к развитию криптографии на новых постквантовых криптопримитивах, таких как коды исправляющие ошибки, теория

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

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

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Провести анализ современных пороговых подписей, определить основные достоинства и недостатки.

2. Разработать улучшенные варианты методов пороговой подписи, основанной на задачах постквановой криптографии.

3. Провести сравнительный анализ разработанных схем с существующими аналогами.

4. Разработать модель синергии протоколов квантового распределения ключей (КРК) и постквановых методов пороговой подписи.

Основные положения, выносимые на защиту:

1. Метод постквантовой пороговой подписи, основанной на интерполяционной формуле Лагранжа и теории решёток.

2. Метод постквантовой пороговой подписи, основанной на интерполяционной формуле Ньютона и теории решёток.

3. Модель квантово устойчивого разделения ключа между пользователями, на основе метода пороговой подписи.

Научная новизна:

1. Разработан метод постквантовой пороговой подписи на основе интерполяционного многочлена Лагранжа и математической проблемы из теории решеток Laming with Rounding (LWR). Отличительными особенностями такого метода является защита от квантовых атак и возможность использования в системах с малыми вычислительными мощностями, что достигается за счет использования детерминированной ошибки.

2. Разработан метод постквантовой пороговой подписи на основе интерполяционного многочлена Ньютона и математической проблемы из теории решеток Laming with Rounding (LWR). Отличительными особенностями такого метода является быстрое добавление новых пользователей в систему без необходимости пересчёта всех базисных полиномов.

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

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

Степень достоверности полученных результатов обеспечивается глубоким анализом проблематики, работой на нескольких проектах и грантах по теме диссертационного исследования, апробацией результатов на всероссийских конференциях. Результаты находятся в соответствии с результатами, полученными другими авторами.

Диссертационное исследование было выполнено при поддержке следующих научно-исследовательских проектов:

1. НИР Университета ИТМО №619296: «Разработка методов создания и

внедрения киберфизических систем»

2. НИР Университета ИТМО №620164: «Методы искусственного интеллекта

для киберфизических систем»;

3. НИР АНО НТЦ ЦК «Шифр Крикун»;

4. Государственное задание проект FSER-2025-0003;

Апробация работы. Основные результаты работы представлялись на следующих конференциях:

1. XI, XII Конгресс Молодых Учёных Университета ИТМО. Санкт-Петербург, Россия.

2. 31, 32-я конференция МиТСОБИ. Санкт-Петербург, Россия.

3. 25-я конференция SIBINFO-2025. Томск, Россия

4. XXVIII Международная научная конференция WECONF-2025. Санкт-Петербург, Россия.

5. Пятьдесят первая, пятьдесят вторая научная и учебно-методическая конференция Университета ИТМО. Санкт-Петербург, Россия.

Публикации. Основные результаты по теме диссертации изложены в 7 публикациях, 3 из которых изданы в журналах, индексируемых Scopus [6-8], 2 изданы в журналах, рекомендованных ВАК [9; 10]. Получено 2 свидетельства о государственной регистрации программ для ЭВМ.

В международных изданиях, индексируемых в базе данных Scopus:

1. Давыдов В.В., Беляев В.В., Кустов Е.Ф., Леевик А.Г., Беззатеев С.В. , Современные вариации криптосистем Мак-Элиса и Нидеррайтера //Научно-технический вестник информационных технологий, механики и оптики. - 2022. - Т. 22. - №. 2. - С. 324-331.

2. Кустов Е. Ф., Беззатеев С. В. Анализ применимости существующих схем разделения секрета в условиях постквантовой эры //Научно-технический вестник информационных технологий, механики и оптики. - 2025. - Т. 25. - №. 3. - С. 446-456.

3. Kustov E. A Lattice-Based Threshold Signature Scheme for IoT Applications //2025 Wave Electronics and its Application in Information and Telecommunication Systems (WECONF). - IEEE, 2025. - С. 1-5.

В изданиях из перечня ВАК РФ:

1. Кустов Е.Ф., Беззатеев С.В. Пороговая схема подписи на основе теории решёток и интерполяции Ньютона // Доклады ТУСУР. - 2025. -Т. 28, № 2. - С. 166-171.

2. Кустов Е. Ф. и др. Интеграция квантового распределения ключей с классическими криптографическими схемами: повышение безопасности в условиях постквантовых вызовов //Вестник СибГУТИ. - 2025. - Т. 19. - №. 2. - С. 98-111.

Патенты и свидетельства о регистрации программ для ЭВМ:

1. Кустов Е.Ф., Иогансон И.Д. Свидетельство о государственной регистрации программы для ЭВМ «Программа для создания пороговой подписи на основе решёток и интерполяции Ньютона», охранный документ №2025683055 от 29.08.2025

2. Кустов Е.Ф., Леевик А.Г., Голованов А.А. Свидетельство о государственной регистрации программы для ЭВМ «Программа для создания пороговой подписи на основе схемы Дамгора для произвольного порога пользователей», охранный документ № 2023660455 от 13.06.2023

Личный вклад. Разработка моделей и методов, представленных в настоящей диссертации, выполнена автором лично. Постановка цели и задач, обсуждение планов исследований и полученных результатов выполнены автором совместно с научным руководителем. В работе [6] вклад автора заключается в том, что автором была сделана программная реализация рассматриваемых схем для проведения сравнительного анализа. В работе [10] автор провел исследование интеграции КРК и схемы Шамира, а также формирование выводов по полученным результатам.

В остальных работах, выполненных в соавторстве с научным руководителем Беззатеевым С. В., Кустову Е. Ф. принадлежат соответствующие основные результаты; вклад научного руководителя заключался в постановке задачи и консультировании; также проводились многочисленные обсуждения полученных результатов.

Содержание работы

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

Глава 1 посвящена анализу современных схем разделения секрета, включая классические и постквантовые методы. Актуальность темы обусловлена угрозой квантовых атак, которые могут компрометировать традиционные криптографические системы, такие как RSA и ECDSA. Цель главы - выявить оптимальные схемы, устойчивые к квантовым вычислениям, на основе критериев Шамира: размер доли, возможность повторного использования, безопасность, гибкость добавления участников и обновления секрета.

Рассмотрены следующие схемы разделения секрета: Схема Шамира (Лагранжа): основана на интерполяции многочленов. Уязвима к квантовым

атакам, но проста в реализации. Схема Ньютона: аналогична схеме Шамира, но удобна для динамического добавления участников. Китайская теорема об остатках: использует модульную арифметику. Эффективна, но требует строгого числа участников для восстановления секрета. Коды исправляющие ошибки: устойчивы к квантовым атакам, но требуют больших вычислительных ресурсов. Теория решёток: основана на NP-трудных задачах (SVP, LWE). Обеспечивает высокую безопасность, но сложна в реализации. Изогении эллиптических кривых: устойчивы к квантовым атакам, но требуют тщательного выбора параметров. Хэш-функции: просты и эффективны, но безопасность зависит от стойкости используемой функции. Многомерные уравнения: устойчивы к квантовым атакам, но сложны в вычислениях.

Классические схемы уязвимы к квантовым атакам, но остаются популярными благодаря простоте. Постквантовые схемы демонстрируют высокую устойчивость, но требуют больше ресурсов. Наиболее перспективными признаны схемы на основе теории решёток, сочетающие безопасность и соответствие критериям Шамира, но требуют дальнейших исследований для оптимизации их производительности. Рекомендуется комбинировать классические и постквантовые подходы для достижения баланса между безопасностью и практичностью. Результаты анализа представлены в Таблице 1, 2, где N - параметр безопасности, n - размер кодового слова, р - размер поля, х -число переменных, к - степень многочленов.

Таблица 1. Сравнение схем разделения секрета по критериям Шамира

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

Размер доли не больше секрета + + - + + + + +

Возможность повторного использования секрета - - - - - - - -

Невозможность проанализирова ть секрет + + + + + + + +

Возможность добавления нового участника + + - + + - - -

Возможность обновить секрет + + - + + - + -

Возможность изменения веса долей - - - - - - - -

Таблица 2. Сравнение схем разделения секрета по сложности взлома

Схема Квантовый метод Классический метод

Схема Шамира (RSA) 0((log2N)3) 0(рк-1)

Схема на основе

интерполяции Ньютона (RSA) 0((log2N)3) 0(рк-1)

Схема на китайской

теореме об остатках (RSA) 0((log2N)3) Q(2l°92N)

Схемы на кодах,

исправляющих ошибки О(20,1п) 0(п3)

Схемы на решетках 0(2 01N) 0(2 N)

Схемы на 0 (pi) 0 (pi)

эллиптических кривых

Схемы на хэш-функциях 0(2 N) 0(2 N)

Схемы на

многомерных 0(pm) Q(2Xlogk)

уравнениях

Глава 2. Пороговые схемы на основе теории решеток посвящена исследованию и разработке методов пороговой подписи, устойчивых к квантовым атакам, с использованием математических задач теории решеток. Основное внимание уделено двум методам: пороговой подписи на основе интерполяционного многочлена Лагранжа и пороговой подписи на основе интерполяционного многочлена Ньютона. Оба метода базируются на задачах M-LWR (Module Learning with Rounding) и M-SIS (Module Short Integer Solution), которые считаются устойчивыми к классическим и квантовым атакам.

В разделе 2.1.1 рассмотрены угрозы современной криптографии, связанные с квантовым алгоритмом Шора. Данный раздел диссертации посвящен анализу угроз, которые представляют алгоритмы Шора и Гровера для современных криптографических систем, а также обзору перспективных направлений постквантовой криптографии. В 1994 году Питер Шор предложил квантовый алгоритм, способный решать эти задачи за полиномиальное время, что ставит под угрозу безопасность широко используемых криптографических протоколов. Позднее, в 1996 году, Лов Гровер разработал алгоритм, ускоряющий перебор в неупорядоченных базах данных, что также снижает стойкость криптосистем. Алгоритм Шора обеспечивает экспоненциальное ускорение решения задач факторизации и дискретного логарифмирования.

В разделе 2.1.2 рассмотрены задачи LWE (Learning with Errors), LWR (Learning with Rounding). LWE представляет собой математическую задачу, лежащую в основе многих постквантовых криптографических схем. Впервые предложенна Одедом Регевым в 2005 году.

Задача LWE формулируется следующим образом:

• Дано: А ё ZJ, b = ATs + е mod q

• Задача поиска: найти секретный вектор s ё Z^

• Задача различения LWE: определить, являются ли пары (A, b) LWE-образцами или чисто случайными.

где е ^ х - малая ошибка из гауссового распределения, А - матрица базисов решетки. Если х - дискретное гауссовское распределение с параметром Д, то задача считается сложной при Р > 2 Vn , где п - параметр безопасности.

Задача LWE лежит в основе многих постквантовых криптографических схем. Однако её стандартная форма требует больших размеров ключей и вычислительных ресурсов. Для оптимизации были предложены две важные модификации: Module-LWE (M-LWE) и Ring-LWE (R-LWE).

Learning with Rounding (LWR) - это математическая задача, которая является вариацией задачи LWE. Она была предложена как более эффективная альтернатива LWE, сохраняющая при этом высокий уровень безопасности. Основное отличие LWR от LWE заключается в том, что вместо добавления случайной ошибки (как в LWE) здесь используется детерминированное округление, что упрощает вычисления.

Задача LWR определяется следующим образом. Пусть q > р > 1 целые числа, матрица базисов решетки А ё Z™xn, секретный вектор s ё Z^, тогда

b =

р

-х As

Ч

mod q,

где [*J - операция округления.

Задача поиска: найти секретный вектор s, зная A, b. Задача различения: определить, являются ли пары A, b результатом округления или чисто случайными. В LWR ошибка заменена на детерминированное округление, что исключает необходимость генерации случайных ошибок и упрощает реализацию. Отсутствие гауссовых ошибок снижает вычислительные затраты и уменьшает размеры ключей, что особенно важно для устройств с ограниченными ресурсами

В разделе 2.1.3 рассмотрена задача SIS (Short Integer Solution), которая является одной из фундаментальных математических задач в теории решёток, которая лежит в основе многих постквантовых криптографических схем. Она

была впервые предложена Миккианчио и Регевым в 2006 году и с тех пор стала ключевым элементом в разработке устойчивых к квантовым атакам криптографических протоколов.

Пусть заданы матрица А Е , где п - параметр безопасности, m -размерность решётки, q - модуль, положительное вещественное число fi.

Тогда Задача SIS заключается в нахождении ненулевого целочисленного вектора z ЕЩ такого, что:

Az = 0 mod q, Mœ<P,

где \\z\\œ - бесконечная норма вектора z.

SIS является NP-трудной задачей для определённых параметров, что делает её устойчивой к классическим и квантовым атакам. Сложность решения SIS зависит от выбора параметров n,m,q и fi. Например, при m > nlogq и fi < q/Jm задача считается сложной.

SelfTargetSIS (STSIS) - это модифицированная версия задачи Short Integer Solution (SIS), которая играет ключевую роль в постквантовой криптографии, особенно в схемах цифровых подписей, таких как CRYSTALS-Dilithium, стандартизированный NIST. В отличие от классической SIS, STSIS требует, чтобы решение не только удовлетворяло линейному уравнению над решёткой, но и соответствовало целевому хэш-значению, что делает её идеальной для преобразования интерактивных протоколов в неинтерактивные с помощью парадигмы Fiat-Shamir.

Пусть заданы матрица А Е Щхт, хэш-функция H : {0,1}* ^ (0,1}к, где к -размерность вектора, целевое значение t Е (0,1}к и положительное вещественное число fi.

т

Тогда Задача STSIS заключается в нахождении ненулевого вектора z и сообщение М такие что:

#(Az, М) = t, ||z|L<£,

где ||z||OT - бесконечная норма вектора z.

Задача STSIS обладает свойством односторонности, то есть вычислительно трудно найти решение без знания секретного ключа. Связь с Fiat-Shamir позволяет преобразовать интерактивные протоколы в неинтерактивные. Устойчивость к коллизиям зависит от стойкости хэш-функции.

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

Интерполяционный многочлен Лагранжа - это классический метод аппроксимации функции по заданному набору точек. Он широко применяется в численных методах, криптографии, обработке сигналов и машинном обучении. Основная идея заключается в построении многочлена L(x) степени больше или равном п, который точно проходит через п + 1 точку (xfc, yfc).

Задача восстановления многочлена L(x) определяется следующим образом:

1. Пусть задан набор точек (х0,у0), (х-^уД..., (хп,уп), где все значения различны.

2. Необходимо найти многочлен L(x) минимальной степени, такой что L(xfc) = yfc для всех к = 0,1,..., п.

В общем виде многочлен Лагранжа вырежется следующем образом:

п

L(x) = ^yfc х /fc(x), fc=0

где 1к (х) - базисные полиномы Лагранжа.

п

X — X

I

:(Х)= П

X X ^^ X / 1=0,1Фк К 1

Интерполяционный многочлен Ньютона - это полиномиальное представление, альтернативное форме Лагранжа, основанное на разделённых разностях. Главное преимущество - возможность постепенного наращивания степени полинома при добавлении новых точек без полного пересчёта.

Для любого набора из (п + 1) точки (х0,у0),(х1,у1),...,(хп,уп), где все значения различны существует единственный многочлен Р(х) степени большей или равной п:

п к—1

Р(х) = ^Пх0, .~,хк]х П(* — Х1),

X1

к=0 1=0

где f[x0,..., хк] - разделённая разность к-го порядка.

Разделённые разности вычисляются последовательно: • Нулевой порядок: f[xi] = у{.

_ гЫ-гш

Первый порядок: =

X ^ XI

• к-ый порядок: Г[хь х+к] = т+1..........*1+к]

В разделе 2.4.1 рассмотрена пороговая подпись на основе интерполяционного многочлена Лагранжа и задачах теории решёток, таких как M-LWR и STSIS. Схема обеспечивает постквантовую безопасность.

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

Генерация матрицы:

1. Каждый из N пользователей выбирает случайную матрицу А £ , известную всем участникам, и вычисляет случайное обязательство д^ ^ Я1(А1,у), которое рассылается остальным.

2. После получения всех д^ пользователи публикуют свои матрицы А£.

3. Если д^ ^ Я1(А(, ¿) для любого ¿, процесс прерывается. В противном случае формируется общая публичная матрица:

п

A=[Ai|Ifc]e^Jxi,A = ^Ai

i=i

Генерация ключей и разделение секрета:

1. Каждый пользователь генерирует секретный вектор:

Sj ^Sj

2. Стоит отметить, что в отличие от большинства пороговых подписей в рассматриваемой схеме совокупный секрет s = EI=1 si никогда не хранится явно, а распределяется между участниками с использованием схемы разделения секрета Шамира.

3. Далее каждый пользователь вычисляет свой открытый ключ tj, так как используется модульная решетка (M-LWR), для которой не существует эффективных квантовых алгоритмов, из tj невозможно восстановить Sj:

ti = Round (^xAxSjje flj.

IItj — ASj||OT < 2V-M

4. Пользователи обмениваются обязательствами Vi ^ #2(ti,y) и проверяют их корректность. Если проверка не проходит, процесс прерывается. В противном случае формируется общий публичный ключ:

п

i=Zii

¿=1

5. После того как ключи получены, для разделения секрета каждый пользователь генерирует (к +1) многочленов степени t — 1 со свободными коэффициентами, равными элементам вектора .

6. Затем каждый пользователь вычисляет вектор значений, полеченный подстановкой Ю пользователей в сгенерированный многочлен:

4 = (гт),гКю).....г£+1(10)),

7. где f - это многочлен сгенерированный 1-ым пользователем для у'-ого ввода секретного ключа этого пользователя, Ю - это идентификатор пользователя, которому отправляется значение.

8. Далее они рассылают свое обязательство 01:

9. Получив все 01, каждый пользователь проверяет, что 01 = I), если для некоторого I равенство не соблюдено, то отправляется команда прерывания. Даже если квантовый компьютер вычислит часть долей, восстановление секрета требует решения М^К, что вычислительно трудно. Интерполяция усложняет атаки, так как требует знания > t корректных долей.

10.После этого каждый пользователь вычисляет свою долю секрета х^:

п ]=1

11.Если протокол не прерывается, пользователи получают (Бк^рк) в качестве локального вывода.

(5к0рк) = (х0(А,1)) Генерация и объединение подписей:

Пусть сообщение т берется из пространства М = {0,1}*. Также будем использовать криптографическую хэш-функцию Н3:{0,1}*^БШ. Выводом Н3 является многочлен в , где й коэффициентов равны ±1, а остальные 0.

1. В начале пользователи вычисляют коэффициенты Лагранжа ^:

с

II=(-1)с-1 п

-/я,-

Щ - Ю/

где Ю^ - это идентификатор текущего пользователя.

2. Пользователи выбирают вектор у;:

У; ^ ||У{Ует <7

3. Для того, чтобы в дальнейшем корректно восстановить подпись введем Й:

- л

У* =^-тоД ц

ч

4. После этого пользователи вычисляют первую часть подписи и^:

^ = Ау;,и; £

5. Далее они рассылают свое обязательство р; ^ Н1(и^,у) и проверяют их корректность. Если проверка не проходит, процесс прерывается. В противном случае формируется первая часть агрегированной подписи:

ь

■=ь

1=1

6. Затем пользователь, который будет подписывать сообщение, вычисляет хэш с:

с = Н3 (М5Б (и, ¿),т),т£М

7. После этого каждый пользователь вычисляет вторую часть подписи и параметр для проверки корректности:

= А21 — ^Х 2У-^-1 X с

8. Если следующие неравенства выполняются, то процедура подписи должна быть начата заново, ограничение нормы векторов ||г;||от исключает подбор через квантовый перебор:

ЦЬБВ^у — й)Цт> 2у-а — шх 2у-^+1,

Ыт>у — р

В результате каждый пользователь имеет свою часть подписи = (и, х^) и подписывающий пользователь может сформировать агрегированною подпись а = где ъ:

t

z = ^ZiXli

i=l

Проверка подписи:

1. Для проверки подписи сообщения т, до того, как получить агрегированною подпись о и открытый ключ рк = (A, t), проверяющий должен восстановить хэш с':

с' = H3(MSB(w,d),m), w = Az-tx 2V-^-1 X с

2. Подпись считается корректной, если:

с' = c,\\-l\\w<jn(y-p)

где N - это количество пользователей, подписывавшие сообщение. Если проверка не выполняется, то подпись считается не валидной.

Использование MSB и хэш-функции Н3 устойчиво к коллизиям даже при квантовых атаках. Условие на норму z гарантирует, что подделка потребует решения M-SIS.

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

р1 « ехр

р2 « ехр ( —

У ш X

2v-d+1 — 1

1

Р1Р2 г

Е

¿=0

В разделе 2.4.1 рассмотрена пороговая схема подписи, основанная на интерполяционном многочлене Ньютона и математических задачах M-LWR и STSIS. Пороговые схемы подписи на основе Ньютона обеспечивает быстрое добавление участников и меньшую вычислительную нагрузку.

Пусть имеется N пользователей, и t из них могут подписать сообщение, что соответствует схеме разделения секрета (¿, М). На этапе генерации и объединение подписи, будем считать пространство сообщений т£М,М = {0,1}*.

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

Генерация матрицы:

1. Каждый из N пользователей выбирает случайную матрицу А £ , известную всем участникам, и вычисляет случайное обязательство д^ ^ Я1(А(,у), которое рассылается остальным.

2. После получения всех д^ пользователи публикуют свои матрицы А£.

3. Если д^ ф Я1(А(, ¿) для любого ¿, процесс прерывается. В противном случае формируется общая публичная матрица:

п

А=[А;|1к]£Д*хг,А = ^А;

¿=1

II

=ь

Генерация ключей и разделение секрета:

1. Каждый пользователь генерирует секретный вектор:

Si ^Sls

2. Агрегированный секрет s может быть представлен следующем образом, но в явном виде нигде не хранится:

п

S

i=l

Одним из ключевых преимуществ предлагаемой схемы пороговой подписи является то, что общий секрет s никогда не хранится и не собирается в явном виде. Вместо этого секрет распределяется между участниками с использованием порогового механизма разделения секрета, такого как схема на основе интерполяции полинома Ньютона. Это гарантирует, что секрет не может быть скомпрометирован, если только достаточное количество участников не объединятся для его восстановления.

Список литературы диссертационного исследования кандидат наук Кустов Елизар Филаретович, 2025 год

Литература

L.Shor P.W. AlgoriUi ms Гаг quantum computation: discrete logarithm! and factoring Si Proceedings 35th annual symposium an foundations of computer science. - Santa Fe, NM. USA: IEEE, 1994. P. 124-134.

2.Dehknrdi M il. LWE-based verifiable essential secret image sharing sehen«; ((t, s. k, ft)-'VES]S) : M.II. Dehlairdi. S.T. Farahi. S. Mashhadi!; IET Image Processing. Stevenage. UK: IET, 2024.-Vol. IS, No. 4.-P. 1053-1072.

3. Çalkavur S. Code Based Seeret Sharing Schemes: Applied Combinatorial Coding Theory У s. Çalksvuf, Z. Öitfipriik. O. Yayla. Singapore: World Scientific, 2022. 212 p.

4. Вол eh D. Threshold signatures with private accountability i D. Boneh. С. Knmlo t! Annual International Cryptalogy Conference. Zurich, Switzerland: Springer Nature Switzerland, 2022. P. JJ1-ÍS1.

5. liuiid L. et al. Threshold signatures in (lie multiveree // 202.' IILEE Symposium on Security and Privacy (SP>. - San Francisco, CA, USA: I НЕЕ. 2023. P. 1454-1470.

fi.Fischlin M. BU FF i ng Threshold Signature Schemes / M Fischlin, A. MitrokoLsa, J. Tomy// lAt'R International Cini-ferenee on Public-Key Cryptography. - Lyon. France: Springer. Cham, 2025.- P. 1.'7-I6K.

7. Due A. Better algorithms for LWE and LWR / A. Due, F. Tramer, S. Vaudenay //Annual International Conference on

Дшаады ТУСУР, 2025, том IS, № 2

[lie Theory ami Applications of Cryptographic Techniques Sofia, Bulgaria: Springer Berlin I leidelberg, 2015.-?. 173-202

K. Bez2ij[ijev S. On secret sharing with newton's polynomial for multi-laclcir authentication / S. Bezzateev, V. Davydov, A. Ometov !i Cryptography. - 2020. - Vbl . 4, No. 4. - P. 34.

9.Adi S. How to share a secret H Commun. ACM. -1979 Vol.22.. P 612-613

10. Blakley (i.R. Safeguarding cryptographic keys II Managing requirement) knowledge, international workshop on. - IEEE Computer Society, 1979. - P. 313-313.

11. Shoup V. Practical threshold signatures !t Advances in Cryptoiogy EU ROC RYPT 2000: International Conference on [lie Theory and Application of Cryptographic Techniques Bruges, Belgium May 14-IS, 2000. Proceedings 19. - Springer Berlin I leidelberg, 2000. - P. 207-220.

12. Banerjee A. Pseudorandom functions anil lattices / A. Banerjee, C. Peikert, A. Rosea//Annual International Conference on the Theory and Applications ofCiyptograpliic Techniques. Cambridge. UK: Springer Berlin Heidelberg, 2012.

P. 719-737.

13. Jiang T. Blockchain-based internet of vehicles: Distributed network architecture and performance analysis / T. Jiang, ][. Fang, H. Wang//IEEE Internet of Things Journal. 201S. Vol. 6, No. 3. P. 4640-4649.

14. Danism! I. ei al. Two-round n-nu[-of-n and ran I [¡-signatures and trapdoor comraitmeat from lattices // Journal of Cryptoiogy 2022. Vol. 35, No. 2. P. 14.

If. Killz E. A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model Q. Kiltz, V. Lyu-bashevsky, C. Schallher U Advances in Cryptoiogy EU-RGCRYPT 201Я: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Tel Aviv, Israel, April 29 May 3, 2018. Proceedings, Pari III 37. Springer International Publishing, 201S. - P. S52-586.

16. Проект стандартизации no етквантовой цифровой подписи / Е.А. Кнршанова, II.C. Колесников. Б.С. Ма.ш-гнво, С.А. Новосело»// Прикладная дискретная математика. Приложение. - 2020. - № 13 - С. 44-51.

Кус юв Елизар Филарегонич

Аспирант факультета безопасности информационных

технологий (ФЕИТ) Университета 1ТТМО

Кронверкский пр-т, 49, лит. А.,

г. Санкт-Петербург, Россия. 1971(11

ORCID: 0000-0002-0191-117®

Тел.: 4-7-9SI-S34-14-60

Эл. почта: eIizuiTistovOinail.ni

БюзиеСИ Cepi L-ii Ва. J ей 1IIНОВНЧ

Д-р техн. наук. проф. ФШТ Университета ИТМО:

зав. оф. информационной безопасности

Государе!венного университете

аэрокосмичеекого приборостроения (ГУАШ

Большая Морская ул., 67, лит. А,

г. Санкт-Петербург, Россия. 190000

ORCTD: 0000-0002-0924-6221

Тел.: [phone]

7)л. почта: serge у .hezzateevt® gmail.com

1 [оступuna в редакции!: 07.05.2025. Принята к публикации: 25.06.2025.

Kustoi Ei.F.. Beiiateev S.V.

Lattice-Based Threshold Signature Scheme with Newton 1 ntcrpulaliiiu

This paper presents a novel threshold digital signature scheme that combines lattice-based cryptography with interpolation methods. The scheme is built upon the Learning with Rounding (LWR1 problem and can be applied n> secure loT devices, where the combination of computational efficiency and quantum resistance is particularly valuable, file proposed approach utilises Newion interpolation, which demonstrates advantages over classical Lagrange interpolation in terms or performance and flexibility when working with dynamic participant groups. Key K urds: threshold signature, lattice-based cryptography, Newton interpolation. LWR. SIS. post-quantum cryptography, secret sharing.

1)1)1: 10.21293/1818-0442-2025-28-2-166-171

Referi'fi ces

1. Shor P.W. Algorithms fiiy ¡¡¡milium ajntputtilion: discrete logarithms and factoring. Proceedings 35 th annual symposium on loundations of computer science. Santa Fe. MM. USA: IEEE, 1994, pp. 124-134.

2. Dehkordi M.fL, Farahi ST., MashhadiS. LWE3-based veriliable essential secret image sharing scheme ((t. s, k. n)-VES1S). !ET Image Pmcetsing. Stevenage, UK: I IT, 2024. vol. IK, no. 4. pp. 1053 -1072.

3. Qalkavur S., Qzt&prak Z„ Yayla D. Code Based Secret Sharing Schemes: Applied Combinatorial Coding Theory. Singapore: World Scientific, 2022. 212 p.

4. Boneh D., Komlo C. Thresholdsignatures withprivate atwitniabdiiy. Annual International Cryptoiogy Conference. Zurich, Switzerland: Springer Nature Switzerland, 2022, pp. 551-581.

5. Baind L. et al. Tlavikaitl signatures in the muTiivenc. 2023 IEEE Symposium on Security and Privacy (SP). San Francisco. CA, USA: IEEE, 2023: pp. 1454-1470.

6. Fischlin M.. Mitnokotsa A., Torny J. BUFFrng Threshold Signature Schemes. IACR International Conference an Public-Key Cryptography Lyon. France: Springer, Cham, 2025. pp. 137 168.

7. Due A., Tramer F Vaudenay 5. Belter algorithms far LWE and LWR. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Solia, Bulgaria: Springer Berlin Eleidelherg, 2015, pp. 173-202.

K. Bezzaleev S.. Davydov V.. Ometov A. On secret sharing with Newton's polynomial for multi-factor authentication. Cryptography, 2020, vol. 4. no. 4. pp. 34.

9. Shamir A. How to share a secret. Communications uf the A 197 9, vol. 22. pp. 612-613.

10. Dial.ley G.R. Safeguaidtng cryptographic keys. Managing requirements knowledge, international workshop on, IEEE Computer Society, 1979, p. 213.

11. Shoup V. Practical threshold signatures. Advances in Cryptoiogy -1 :l J ROCR YPT 2000: International Conference oil the Theory and Application of Cryptographic Techniques. Bruges, Belgium: Springer Berlin Heidelberg, 2000, pp. 207- 220.

12. Banerjee A., Peikert C., Rosen A. Pseudorandom functions and lattices .7 Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cambridge, UK: Springer Berlin Heidelberg, 2012, pp. 719-737.

13. Jiang T.. FangH., Wang II. Blockchain-based internet of vehicles: Distributed network architecture and performance analysis. IEEE interna of Things Journal, 201B, vol. 6, no. 3, pp.4640 4649.

14. Damgiird I. et al. Two-round n-out-of-n and multi-signatures and trapdoor commitment from lattices. Journal of Cryptoiogy, 2022, vol. 35, no. 2, pp. 14.

Доклады ТУСУР. 2025. mast 28. 2

DOI: 10.55648/1998-6920-2025-19-2-98-111

УДК 004.056.55

Интеграция квантового распределения ключей с классическими криптографическими схемами повышение безопасности в условиях постквантовых вызовов

Е Ф. Кустов-, А. Ф. Худаем1-5, А. П Кирьянов:!1, И. Д. Иогансон, Ж.-VI. Н. Дакуо12, С. Ь. Беазатеев

1 Университет ИТМО

2Санкт-Петербургский государственный университет аэрокосмического приборостроения

Аннотация: В работе исследуются подходы к обеспечению информационной безопасности с использованием квантового распределения ключей (КРК) в сочетании с классическими криптографическими схемами: схемой Блома, KDP и схемой Лагранжа. Покачано, как квантовые технологии повышают безопасность и эффективность этих методов. Предложенные схемы обеспечивают устойчивость к атакам классических и квантовых ком пью- тсров, устраняя уязвимости традиционных методов генерации ключей. Рассмотрены при- меры применения в :шщищённых сетях loi, облачных вычислениях и распределенных си- стемах. Результаты демонстрируют, что комбинация КРК с криптографическими схемами является перспективным решением для посткБайтовой эры.

Работа выполнена в раикак государственного задания (проект FSER 2O25-0QQ3).

Ключевые сяовв: квантовое распределение ключей, схема Блома, Key Distribution Pattern (KDP), схема Лагранжа, информационная безопасность, распределенные системы

Дня цитирования: Кустов Е. Ф., Хуцаева А. Ф, Кирьянова А. П., Йога неон И. Д., Дакуо Ж - М, П., Беззатеев C.B. Интеграция квантового распределения ключей с классическими криптографическими схемами: повышение безопасности в условиях постквантовых вызовов !! Вестник СибГУТИ. 2025. Т. 19. № 2, С. 98-111.

https://doi.org/10.Ъ5648/1998-Ь920-2025-19-2-93-111.

1. Введение

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

доступен под лицензией Commons Attribution 4.0

Статья поступила в редакцию 0Я. 03.202 5; переработай ¡¡un вариант 30.04.2025; принята к публикации 05.05.2025.

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

В данной работе рассматриваются три основных сценария использования КРК н сочетании с различными криптографическими схемами:

1. КРК и схема Ел ома -для распределения ключей между участниками сети.

2. КРК и KDP (Key Distribution Pattern) для управления ключами н сетях С большим количеством пользователей.

3. КРК и схема Лагранжа - для разделения секрета между несколькими пользователями.

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

Цель данной работы продемонстрировать, как квантовое распределение ключей может быть эффективно интегрировано с классическими криптографическими схемами для создания безопасных н масштабируемых решений. Результаты исследования демонстрируют, ЧТО комбинация КРК с такими методами, как схема Блома, К DP и схема Лагранжа, обеспечивает высокий уровень безопасности и может быть применена в различных сценариях, включая защищенные сети 1оТ, облачные вычисления и распределённые системы В общем виде совмест ное использование КРК и рассматриваемых схем представлено на рисунке I.

2. Совместное использование КРК и схемы Блома

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

квзнтйвыл у мл 2

Рис. 1. Совместное использование КРК и классических схсм

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

Инициализация:

* На первом этапе доверенный центр выбирает конечное ноле GF(c¡} - чем больше д, тем больше участников может быть задействовано.

* Каждый участник выбирает или получает от доверенного центра свой открытый ключ п, где п ё С FU;). При этом г, Ф г\ для í ф],

* Далее доверенным центр генерирует секретный симметричный многочлен:

t i

Í-U í-l)

где t — параметр безопасности, I < t < n . Коэффициенты а берутся из секретной матрицы S1'1, хранящейся у доверенного центра.

Распределение ключей:

* Для каждого участника вычисляется полином от одной переменной:

i i

! —15 j-ü

* Так как ноли ном /"симметричный, то

gf(n> ~ fin, г.) =/(л, rj) - gj (n)

* Для создания общего сеансового ключа яви пользователя передают друг другу свои г i! вычисляют:

gird = &(п)

Добавление НОВОГО участника:

1. Новый участник выбирает r,v, который не должен совпадать с п.

2. Далее доверенный центр вычисляет и передаёт новому участнику. Безопасность схемы основывается на сложности восстановления секретной матрицы.

Для восстановления матрицы необходимо иметь число ключей, равное количеству строк матрицы.

2.1. Связь с КРК

Рассмотрим вариант применения схемы Блома с КРК, где узел КРК будет высыпать в качестве доверенного центра. В начале КРК вырабатывает набор квантовых ключей Q'', полученные ключи используются для заполнения секретной матрицы S. На данный момент для получения матрицы S используется функция формирования ключей (key derivation function, KDF). Данная функция не обладает свойствами доказуемой безопасности, в отличие от способа получения ключей с помощью КРК. Также KDF использует в качестве источника начальной ключевой информации генераторы псевдослучайных чисел (ГСПЧ). Современные ГСПЧ, в отличие от КРК, не могут гарантировать случайное распределение но лученных ключей. Так, в 2010-м году компания Intel, которая является «доверенным центром» для пользователей системы защиты HDCP, подтвердила, что криптоаналитикам удалось найти секретную матрицу (точнее, аналогичную ей}, используемую для генерации ключей в упомянутой системе предотвращения копирования высококачественного видеосигнала, Разработанный алгоритм работает следующим образом:

I. QkeyGenf) ► S: используя квантовый канал связи, доверенные центры вырабатываю т и общих секрет ов длины т и заполняют матрицу S11"1'.

2. ShareKey (S,n,k) = центры генерируют и раздают ключи участникам.

3. RecovecKey ( ?) >gj(r¡): с помощью схемы Блома пользователи могут выработать общий сеансовый ключ g,(rj) = gj(r¡),

Вместо использования традиционных методов генерации ключей секретная матрица S заполняется с использованием квантовых ключей, полученных с помощью КРК. Это обеспечивает случайность и безопасность матрицы S, тан как квантовые ключи обладают свойствами доказуемой безопасности. Это означает, что их случайность и безопасность могут быть математически доказаны, что повышает доверие к схеме Участники сети могут использовать квантовые ключи для генерации Своих открытых и секретных ключей, Это повышает безопасность Схемы, гак как квантовые КЛЮЧИ устойчивы к атакам С использованием квантовых компьютеров. Общий сеансовый ключ, вычисленный с использованием квантовых ключей, также обладает свойствами квантовой безопасности. Это делает его устойчивым к атакам, основанным на перехвате или взломе классических криптографических алгоритмов. В традиционной схеме Блома доверенный центр является единой точкой откача, Использование КРК позволяет распределить генерацию ключей между несколькими узлами, что Снижает риск компрометации системы.

2.2. Пример совместного использования КРК и схемы Блома

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

1. Генерация ключей С ис поль-зова ни ем КРК: Доверенный центр использует протокол КРК (например. TF-QKD [1]. MDI-QKD [2] или CV-QKD [3]) для создания квантовых ключей. Эти квантовые ключи используются для заполнения секретной матрицы S. Каждый элемент матрицы S заполняется с использованием квантовых ключей.

2. Распределение ключей участникам: для каждого участника i доверенный центр вычисляет полином (i) ~ f(x, г;), где f(x, у} - симмет ричный многочлен, построенный на основе матрицы S, Участник i получает свой секретный ключ gif*) и открытый идентификат ор r¡,

3. Обмен ключами между участниками: участники обмениваются своими открытыми идентификаторами г, по незащищённому каналу. Для генерации общего ключа между участниками inj используется формула: Ä*,, ~~ g, (rj) = g, (г,).

Поскольку/(х, у) симметричен, g, (rj) g, (r,)t и оба участника получают одинаковый

ключ.

Квантовые ключи обеспечивают док азу ему ю безопасность, а Схема Блома гарантирует, что КЛЮЧИ могут быть эффективно распределены между участниками. Система устойчива как к классическим, так и к квантовым атакам. Подход может быть адаптирован для различных сетевых конфигураций и требований безопасност и.

3. Совместное использование КРК и KDP

Одной из важных проблем при построении защищенных систем обмена сообщениями между двумя пользователями является управление ключами в схеме с большим количеством участников. Пусть существует" сеть пользователей ри р2, ..., рп которые хотят взаимодействовать только друг с другом но защищенному каналу. Тогда каждая пара пользователей ¡P¡, Р,} должна обладать общим секретным ключом, который используется для шнфрования и расшифрования сообщений, отправляемых между ними. Цикл жизни секрет ного ключа в такой схеме можно разделить на 4 фазы: генерация, обмен, обновление и

уничтожение, Камнем преткновения является вопрос о хранении и обмене сгенерированных секрет ных ключей.

Основным вариантом для обмена ключами является схема распределения ключей {key distribution scheme. KDS). В этом случае предполагается активное участие доверенного центра только ни этапе распространения секретной информации. Такой подход не покрывает вопрос защищённости полностью, так как Сеть может быть небезопасна, и информация, сгенерированная и распространенная доверенным центром, в теории может быть получена любым пользователем сети.

Для устранения данных недостатков были предложена схема предварительного распределения ключей (key predistribution scheme, KPS) Но мри таком подходе в сети из v пользователей требуется порядка О (г2) отдельных ключей для каждой пары {Pi, Р,}, что при достаточно большом v может стать затруднительно.

Одним из вариантов решения данной проблемы является использование KDP-схемы [Key Distribution Pattern). Преимуществом Схем такого типа является минимизация объёма хранилища ключей до О (lg v) и безопасност ь коммуникации между пользователями.

Введём совокупность (-У1 -й', //) такую, что:

* множество пользователей вР — {ри р2, ...,/?,}, где v количество пользователей, принимающих участие в сети.

* множество подключей [ii, fe, .„, Jtm},

* отношение принадлежности У такое, что $ С .У* ,'Я.

Если (р, к) е У для р t SPh к € .'Я, то можно сказать, что р инцидентно к. Отметим обозначения:

* р — конКретный noj I ьзов атеи i ь;

* к — подключ;

* (р) - множество инциденты?: пользователю р подключен к,

* (&} множество инцидент ых подключу к пользователем р\

* r (f) " |(fi)| (i 6 {I, ..., v}) - количество инцидентных пользователю р подключен к\

* ^ (/) = №)| С/ е {l;i ">}) — количество инцидентных подключу к пользователей;

Наконец, положим, что Л (i,/) = П и х О",./) = |(Jfe) П

Совокупность Ж, 'V) будет являться KDP [5] тогда и только тогда, когда выполняется:

V pbpj е (р,) П (р¡) с (р„,} «н. (j»i = i V т -./)

То есть для построения подобной схемы необходимо построить семейство подмножеств Ж, что для любой пары подмножеств их пересечение не содержится ни в одном другом подмножестве. Такие семейства называются семействами Ш пер н ера - это семейство

подмножеств S — .....таких , что при выполнении условия S, П Sj С Si обязательно

следует t ~ i или t —j.

Теорема 1 [6]. Если !В - это множество подмножеств множества Ж, и Щ образует семейство Шпернера, то

где С/ - - биномиальный коэффициент, а т —

В КDP-схемах каждый пользователь знает только инцидентные ему подключи, а отношение принадлежности -У, хранящее индексы пользователей и соответствующих подключ ей, открыто и известно всем пользователям. Тогда если пара пользователей р. и р, захочет выработать общий ключ га они должны вычислить Sg С {1, .„, ш} — пересечение множеств индексов, инцидентных подключай пользователем р, и р{. Далее вычисляется Kjj=f({k, 11 е где/() - некая односторонняя функция, принимающая на вход множество подключен и дающая на выходе ключ определённой длины.

Примером такой KDP-схемы является подход, предложенный Чэнем и Вэй в [7]. Один из описанных ими алгоритмов строится следующим образом:

Пусть <Ж - (&*, --/у, -/} - :зто структура конечного инцидента, представленная в виде двоичной матрицы 5*5

щ л2

Р, / J о

р, 1 1

P.J 0 1

Рл 1 о

рЛ i i

0 1 о

1 1 о

1 О I

0 0 I J

Тогда .'Н — ЭТО схема (í?, ,y}-EÍ.DP, где

% = {{Л,Pi, ft, ft}, {Р., ft,PS}t {Pi,ft, ft}, {ft, Л, ft}, (Pi, Pj, Pil, {Pi, ft}, {Pi, Pj} {ft, ft}, {ft, Pi}, {Рг, ft}, ÍPl}. {Ps}> {ft}, {Pi}}

{{Pi¡, {p,}, {P.1 }, {Ps}, {Pi, Pi), {pj,ps}, {PI,Ps}. {ft, ft};

3.1. Связь с kTK

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

Пуст ь имеется два доверенных центра распределения ключей (Key Distribution Center, KDC), соединенных квантовым каналом связи, которые управляют KDP-схемой, Чисть пользователей lio классическому каналу подключена к доверительному центру №1, а другая часть - к доверительному центру №2. Тогда два доверенных центра могут совместно выработать общее множество подключен К, используя протоколы квантового распределения ключей. Выработав таким образом ключи, они смогут избежать необходимости передавать подключи пользователям, находящимся на большом расстоянии ОТ них, через внешние сети, что позволит Снизит ь риск утечки информации.

Разработанный алгоритм работает следующим образом:

1. QkeyGen () Используя квантовый канал связи, доверенные центры вырабатывают" общее множество случайных подключен .'f{.

2. In с i de п с yRe la ti on Gen ►Si: Центры генерируют отношение принадлежности Д определяющие инцидентность индексов ключей и пользователей, и публикуют /}

3. SubkeyDistribution (-'Л, -fJ) : Доверенные центры распределяют подключи в соответствии с отношением принадлежности между своими локальными пользователями.

4. кор {3, (pi), (р/)) * Ку\ С помощью KDP-схемы пользователи p¡ и p¡ вырабатывают конечный сессионный ключ.

При совместном использовании схемы КРК и KDP-схемы обеспечивается большая безопасность за счёт" законов физики при выработке ключей между доверенными центрами, а KDP-подход к созданию общей сети пользователей поможет снизить общий объём ключей, хранимый для каждой пиры (р,. pj). Таким образом, квантовая часть обеспечивает безопасность и аутентифицируемость доверенных центров, а схема распределения ключей KDP обеспечит более выгодное (с точки зрения памяти) хранение всего объёма ключевой информации.

В случае, если пользователи хотят выработать общий КЛЮЧ, но у них нет возможности получить его от доверенно! о центра, ИЛИ они не хотят" делиться им с доверенным центром, то КРК обеспечивает возможность генерации защищенных ключей в схеме «точка-точка», а масштабируемость данного подхода от двух до л пользователей поможет организовать KDP-cxeMV.

3.2. Пример совместного не пользования КРК и KDP-схемы

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

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

После Этого используется КDP-схема для эффективного управления ключами. Применяя Схему KDP, каждая пара пользователем периодически обновляет свои общие ключи. Например, они могут решить генерировать новый ключ каждый час или после каждых 100 сообщений. Процесс генерации квантовых ключей повторяется для генерации новых ключей в соот ветствии с графиком KDP-схемы.

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

4. Совместное использование КРК и схемы Лагранжа

Схема разделения секрета на основе интерполяционного многочлена Лагранжа - что криптографический метод, предложенный Ади Шамиром в 1979 году, Она обеспечивает безопасное разделение секретной информации на несколько частей (допей), при этом для восстановления оригинала требуется лишь заранее определённое минимальное их количество. Схема основывается на интерполяции полиномов над конечными полями, что гарантирует её стойкость к атакам и возможность гибкого управления доступом к секретной информации. Этот метод активно применяется в системах, где необходимо распределить доступ к данным между несколькими участниками пли разделить ключ для надежного хранения и применения.

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

Эффективность схемы Лагранжа в условиях возрастающих угроз кибербезопасности делает её одним из ключевых инструментов в современном криптографическом арсенале. Она позволяет минимизировать риск един и й точки отказа, что особенно важно для организаций, работающих с конфиденциальными данными. Среди направлений дальнейшего развития - улучшение производительности и расширение применения в таких областях, как инт ерне т вещей (1оТ), распределённые реестры и облачные вычисления.

Опишем работу схемы Лагранжа,

Подготовительный этап. Пусть необходимо разделить секрет S между п пользователями, чтобы к из них смогли восстановить его (пороговая схема к - я). Выбирается простое число р > S. Оно задает ноле GF(p). Над этим полем строится многочлен степени А - I:

F(x) = д*"1 + ак-2 ^ : + ... + di X + S (mod р)

В этом многочлене 5 - :)то разделяемый секрет, а остальные коэффициенты я; -некоторые случайные числа, которые нужно будет «забыть» после того, как процедура разделения секрета будет' завершена.

Генерации долей секрета. Вычисляются доли следующим образом в jí различных точках, при условии, что х = 0.

к, =F (1) = яц - V^+at-i - + ... +ÍJ, ■ I + .S1 (modр) k2 = F (2) = an ■ 21"1 + аь-s ■ + ... + ai • 2 + S (modp)

fc = F (/) - at-1 ■ + an-2 ■ t2 + ... - £j[ f + S (mod/j) k„ = F (n) = At-1 ■ n" 1 + аь-2 ■ a1,2 + ... + a i • n+ S (mod p)

Аргументы могут Сыгь любыми, а главное, разными ПО модулю р. После формирования каждый участник получает пару (it,, .х), где- í, а а, и S «забывается».

Bocel анйвленне секрета, Собираются любые А- и больше участников, которые могут восстановить секретное значение. Это происходит с помощью вычисления интерполяционного многочлена Лагранжа. Формула выглядит следующим образом:

(mod р)

i

(mod р)

4.1. Связь с КРК

Рассмотрим сценарий с двумя доверенными центрами, каждый из которых способен генерировать квантовый ключ, tí этом случае оба центра могут совместно выработать секрет" S, представляющий собой квантовый ключ, и затем разделить его между л пользователями с помощью схемы Лагранжа, При этом устанавливается порог что означает: для восстановления исходного секрета потребуется объединение как минимум к долей. Такая структура позволяет гарантировать высокий уровень безопасности, гак как восстановление секрет а невозможно при отсутст вии минимально необходимого количес тва долей.

Важно отметить, что данная схема применима и в контексте квантовых ключей. Пользователи могут объединить свои доли и восстановить секрет S, сохранив квантовые свойства ключа, даже если его передача происходит вне квантовой сети. Это становится возможным благодаря тому, что процесс разделения и восстановления ключа но Схеме не изменяет квантовую природу секретных данных, обеспечивая их целостность и конфиденциальность в условиях классических каналов связи. Таким образом, использование схемы Лагранжа в комбинации с квантовой криптографией обеспечивает" надежный способ управления доступом к секретным квантовым данным в распределенных системах.

Разработанный алгоритм работает следующим образом:

1. QkeyGen() -»S: Используя квантовый канал связи, доверенные центры вырабатывают" общий секрет Л'

2. ShareKey [St ntk) > Р = х: Центры генерируют и раздаются доли секретов участникам.

3. RecoverKey (Р) > S. С помощью схемы Лагранжа пользователи восстанавливают секрет S.

4.2, Примеры использования К Г К и схемы Л su ринжл

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

или атаки на хранилище. Для защиты ключа можно использовать комбинацию КРК и схемы Лагранжа:

1. Два квантовых узла (например, в дата-центрах разных провайдеров) приводят квантовое распределение ключа, формируя общий секретный ключ 5.

2. Разделение ключа: ключ 5 разделяется на п частей с порогом восстановления к с использованием схемы Лагранжа.

3. Распределённое хранение: доли секретного ключа хранятся в разных облачных провайдерах или распределённых узлах сети.

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

Преимущества подобного подхода:

* Квантовая безопасность за счет использования ключей, переданных но КРК.

* Защита От компрометации облачного провайдера, гак как утечка одной или нескольких частей ключа не приведёт к его раскрытию.

* Гибкость в управлении доступом, поскольку можно менят ь порог восстановления к в зависимости от уровня доверия к участникам системы.

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

Другим примером использования предложенного подхода может- быть система управления доступом к квантовым данным, и требуется гарантировать, что доступ к секрет ной информации возможен только при наличии нескольких доверенных лиц. Простая аутентификация пользователя (например, паролем или биометрией) недостаточна, гак как в случае компрометации учётных данных злоумышленник сможет получить ПОЛНЫЙ доступ к данным.

1. Генерация квантового ключа: квантовые узлы выполняют распределение квантового ключа 5 между участниками системы безопасности. Этот ключ предназначен для рас ш иф рова н ия конф иде н циаль н ы х дан ны х.

2. Разделение ключа но схеме Лагранжа: ключ делится на п частей, например, между ГЛАВНЫМ администратором, начальником отдела безопасности и независимым аудитором Устанавливается порог к, например 2 из 3, что означает, что для доступа к данным необходимо участие минимум двух из трёх доверенных лиц.

3. Авторизация и доступ к данным: когда ЮгО-ТО из сотрудников требуег доступ к квашово-защищённым данным, система проверяет, есть ли у него необходимые части ключа Если у него только одна доля, доступ заблокирован. Если два или более участника вводят свои части ключа, система восстанавливает секретный ключ и предоставляет" доступ.

Преимущества подобного подхода такие же как и у предыдущего варианта.

5. Безопасность

Безопасность предложенных схем, объединяющих квантовое распределение ключей и криптографические методы (схема Б.тома, КОР и Схема Лагранжа), основывается на безопасности их составных частей. Рассмотрим каждый из компонентов и их вклад в общую безопасность системы,

КРК обеспечивает" безопасность на уровне квантовой механики, ЧТО делает его устойчивым к атакам с использованием классических и квантовых компьютеров. Основные принципы безопасности КРК:

I. Теорема О запрете клонирования: злоумышленник не может Скопировать неизвестное квантовое Состояние без разрушения его Суперпозиции. Это исключает возможность скрыт ого перехвата квантовых ключей.

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

3. Информационно-теоретическая безопасность: К Г1 К обеспечивает абсолютную безопасность, так как любая попытка перехвата ключа нарушает квантовое состояние и может быть обнаружена.

Схема Б лома обеспечивает безопасность за счёт сложности восстановления секретной матрицы S. Основные аспекты безопасности:

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

2. Использование квантовых ключей: заполнение матрицы S с использованием квантовых ключей, полученных через К PK, обеспечивает случайность и доказуемую безопасность.

3. Минимизация риска единой точки отказа: использование КРК позволяет распределить генерацию ключей между несколькими узлами, что снижает риск ком: i рометации системы.

К DP обеспечивает безопасность за счёт использования семейства Шнернера и минимизации объёма хранилища ключей. Основные аспекты безопасности:

1. Семейство Шнернера: пересечение любых двух подмножеств подключей не содержится в других подмножествах, что делает невозможным восстановление ключа без необходимого количества подключей.

2. Использование квантовых ключей: квантовые ключи, полученные через КРК, обеспечивают случайность и безопасность подключей К.

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

Схема JIai ранжа обеспечивает безопасность за счё т интерполяции полиномов над конечными нолями. Основные аспекты безопасности:

1. Информационно-теоретическая безопасность: любое количество долей меньше порога А" не даёт никакой информации о секрете Л', так как соответствующие уравнения недоопределены.

2. Использование квантовых ключей: квантовые ключи, полученные через КРК, обеспечивают случайность и безопасность секрета S.

Безопасность всей системы, объединяющей КРК и криптографические схемы {Блома, KDP И Лагранжа), строится на общих принципах. Каждый из компонентов системы (КРК, схема Блома, KDP и Схема Лагранжа) обладает доказанной безопасностью, что делает вею систему устойчивой к атакам. Использование квантовых ключей делает систему устойчивой к атакам с использованием квантовых компьютеров Распределение ключей и секретов между несколькими узлами снижает риск единой точки отказа,

Предложенные схемы, объединяющие КРК и криптографические методы (схему Блома, К DP н схему Лагранжа), обеспечивают высокий уровень безопасности благодаря использованию квантовых ключей и информационно-теоретически безопасных криптографических протоколов. Это делает их пригодными для использования в ноет квант овую эпоху, где традиционные методы шифрования с тановятся уязвимыми.

Заключение

В данной работе рассмотрены три основных сценария совместного использования КРК с криптографическими схемами: схемой Блома, К DP (Key Distribution Faltern) и схемой Лагранжа. Каждый из этих подходов демонстрирует, как квантовые технологии могут быть

интегрированы в существующие криптографические протоколы для повышения их безопасности и эффективности.

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

Комбинация КРК с криптографическими схемами (Блома, KDP и Лагранжа) является перспективным решением для обеспечения безопасности в эпоху постквантовой криптографии. Эти подходы сочетают в себе преимущества квантовой криптографии и эффективных методов распределения ключей, что делает их пригодными для защиты данных в современных распределённых системах. Дальнейшие исследования в ЭТОЙ области позволят расширить область применения и повысить эффективность предложенных методов.

Литература

1. Lucamarini М. et al. Overcoming the rate-distance limit of quantum key distribution Without quantum repeaters //Nature. - 2018, - T. 557. -№, 7705. - C. 400-403.

2. Lo И. К., Curty M., Qi B. Measurement-device-in dependent quantum key distribution //Physical review letters.- 2012. - T. 108.- Ж 13.-С. 130503.

3. Zhang Y. et al. Long-distance continuous-variable quantum key distribution over 202.81 km of fiber//Physical review letters. - 2020. - T. 125.-Na. 1 -C. 010502.

4. Dver M. et al. On key storage in secure networks //Journal of Crvptology. 1995. T. 8. C. 189-200.

5. Mitchell С J. Piper F. С Key storage in secure networks //Discrete applied mathematics. -1988,- T. 21. -№. 3. -C. 215-228.

6. Spemer E. Ein satz über untermengen einer endlichen menge //Mathematische Zeitschrift. 1928. - T. 27. - №. [.-C. 544-548.

7. Chen S., Wei И Constructions for key distribution patterns //Frontiers of Mathematics in China.-2017.-T. 12.-C. 301-323.

8. Shamir A. How to share a secret //CoramLin. ACM. - 1979, — T. 22. — C. 612-613.

9. Nakampto S. Bitcoin: A peer-to-peer electronic cash system, - 2008.

10. Majyp Э. M. Распределенные системы хранения данных; анализ, классификация и выбор //Перспективы развития информационных технологий. - 2015. .Na. 26. - С. 3360.

I I. Вашкевич Л. М. Смарт-кон тракты: что, зачем И как //М.: Симплоер. - 2018. Т. 89.

12. Wootters W. К., Zurek W. И. A single quant Lim cannot be cloned //Nature. - 1982. - T. 299. -№. 5886.-C. 802-803.

13. Ekert A. K. Quantum cryptography based on Bell's theorem //Physical review letters. -1991. T. 67, - №. 6. -C. 661.

14. Gisin N. et al. Quantum cryptography //Reviews of modem physics. - 2002. - T. 74. - №. I. -C. 145.

15. Golub G. H., Van Loan C. F. Matrix computations, 4th//Johns Hopkins. - 2013.

16. Bennett С. H., Brassard G. Quantum cryptography: Public key distribution and coin tossing//Theoretical computer science, - 2014. - T. 560. - C. 7-11.

17. Shannon С. E. Communication theory of secrecy systems //The Bell system technical journal. - 1949. - T. 28. - №. 4. - C. 656-715,

Кустов Е.жзлр Филаретович

аспирант факультета безопасности информационных технологий, федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет ИТМО» (Университет ИТМО, 197101, Санкт-Петербург, Кронверкский пр., д. 49, лит. А), тел. [phone], e-mail:

kustov[;ia_i . eu, ORC1D ID: 0000-0002-0191-1 178.

Хуцаевд Алтай* Феликсовна

аспирант факультета безопасности информационных технологий, федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет ИТМО» (Университет ИТМО, 197101, Санкт-Петербург, Кронверкский пр., д. 49, лит. A), e-mail: afkhutsaevagitmo, ru, О ROD ID: ОООО-ОСЮ1-5494-7142.

Кирьянова Анастасии Павлин на

аспирант факультета безопасности информационных технологий, федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет ИТМО» (Университет ИТМО, 197101, Санкт-Петербург, Кронверкский и р., д. 49, лит. A), e-mail:

anastacia, leiryanovagitmo - ru, ORC1D ID: 0009-0006-0344- 5111.

lloi ancnii Иван Дмитриевич

аспирант факультета безопасности информационных технологий, федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет ИТМО» (Университет ИТМО, 197101, Санкт-Петербург, Кринаеркский нр., д. 49, лит. А), тел. [phone], e-mail: ivaiL-ioganaonliyandeK.ru, ORC1D1D: 0000-0002-0856-2249.

Дакуо Жан-Мишель Никол шшшч

аспирант факультета безопасности информационных технологий, федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет ИТМО» (Университет ИТМО, 197101, Санкт-Петербург, Кронверкский нр., д. 49, лит. А), тел, [phone], e-mail: jeandakuoinail, ru, ORC1D ID: 0000-00024084-8829.

Бе ¿затеен Сергей Валентинович

д.т.н., профессор, заведующий кафедрой информационной безопасности, института кибернетических систем Санкт-Петербургского университета а э рокосмиче с кого приборостроения, директор лаборатории криптографических методов защит ы информации, ФБИТ, федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет ИТМО:» (Университет ИТМО, 197101, Санкт-Петербург, Кронверкский lip,, д. 49, лит. A), e-mail: sergey. bezsateevEgmail. com, ORCID ID: 0000-0002- 0924-6221.

Авторы прочитали и одобрили окончательный вариант рукописи.

Авторы заявляют об отсутствии конфликта интересов.

Вклад Соавторов: Каждый автор внёс равную долю участия как во все этапы проводимого теоретического исследования, так и при написании разделов данной статьи.

Integration of Quantum Key Distribution with Classical Cryptographic Schemes: Enhancing Security in the Face of Post-Quantum Challenges

E. Kustov , Л. Khvtiim1', A. Klryanova1, I. log an son1, Z.-M. DakuoIJ, S. Bcz/atecvIJ

1 ITMO University 2 Saint-Petersburg State University of Aerospace Instrumentation

Abstract The paper explores approaches, to ensuring information security using quantum key distribution (QKD) in combination with classical cryptographic schemes: the Blon: scheme. Key Distribution Pattern (kdp), and the Lagrange scheme. It demonstrates htrw quantum technologies enhance the security and efficiency of these methods. The proposed schemes provide resilience against attacks by botli classical and quantum computers, addressing vulnerabilities in traditional key generation methods. Examples of applications in secure loT networks, cloud computing, and distributed systems arc discussed. The results show that the combination of qkd with cryptographic schemes is a promising solution for the post-quantum era.

Keywords-, Quantum key distribution (QKD), Blum's scheme. Key Distribution Pattern (KDP), Lagrange scheme, information security, distributed systems.

For citation: Knstov E. F., Khutsaeva А. Г., Kiryanova A. P., loganson 1. D., Dakuo Z.-M. N. P., Bezzateev S. Integration of Quantum Key Distribution with Classical Cryptographic Schemes: Enhancing Security in the Face of Post-Quantum Challenges // Vestnik SibCUTl. 2025, vol. 19, no. 2, pp. 58-111.

https://doi.org/10,55648/1998-6920-2025-19-2-98-111.

© Kustov E. F,, Kliutsacva A. F., Kiryanova A. P., loganson I. D.. Dakuü Z.-M.

N. P., liczzatccv S.V., 2025

The article was submitted: 08.03.2025;

revised ч'сгйion: 30.04.2025; acccplcd for publication 05.05.2025.

J. Lucamaritii M. et al. Overcoming the rate-distance limit of quantum key distribution without quantum repeaters. Nature, 2018, vol. 557, no. 7705, pp. 400-403.

2. Lo H, C., Curty M., Qi B. Measurement-deviee-independent quantum key distribution. Physical review letters. 2012, vol. 108, no. 13, pp. 130503.

3. Zhang V. et al. Long-distance continuous-variable quantum key distribution over 202.8! km of fiber. Physical review letters, 2020, vol. 125, no. 1, pp. 010502,

4. Dyer M. et al. On key storage in secure networks. Journal of Cryptology, 1995, vol. 8, pp. I 89-200.

5. Mitchell C. L Piper f. C. Key storage <n secure networks. Discrete applied mathematics. I98R, vol. 21, no. 3, pp. 215-228.

6. Sperner E. Ein satz über untermengen einer endlichen menge. Mathematische Zeitschrift. 1928, vol. 27, no. l.pp. 544-548.

7. Clicn S., Wei II. Constructions for kev distribution patterns. Frontiers, of Mathematics in China, 2017, vol. 12, pp. 301-323

8. Adi S. How to share a secret. Commun. ACM, 1979, vol. 22, pp. 612-613.

9. Nakamoto S. Bitcoin: A peer-to-peer electronic cash system .2008.

10. Mazur E. M, Raspredelemtye sistemy ftraneniya dannyh: analiz, ktassiftkaciya i vybor. Perspektive razvitiya informaciotinyh tek lino log ij, 2015, no. 26, pp. 33-60.

11. Vashkevieh A. M, Smart-kontrakiy: chio, zachem ikak. M.: Simploer, 2018, vol. 89.

12. Wootters W. K., Zurek W. II. A single quantum cannot be cloned. Nature, 1982, vol. 299, no. 5886, pp. 802-803.

13. Ekert А. К. Quantum cryptography based on Bell's theorem. Physical review letters, 1901, vol. 67,

no. 6, pp. 661.

14. Gisin N. et al. Quantum cryptography. Reviews of modern physics, 20(12, vol. 74, no. I, pp. 145.

15. GolubCi. [[., Van Loan C. F Matrix computations, 4th. Johns Hopkins, 2013.

1Й. Bennett С. H,, Brassard П. Quantum cryptography: Public key distribution and coin tossing.

Theoretical computer science, 2014, vol. 560, pp. 7-11.

J 7. Shannon С E. Communication theory of secrecy systems. The Bell system technical journal, 1949,

vol. 28,no. 4, pp. 656-715.

Eliza г F. Kustov

PhD student. Faculty of Information Security Technologies, Federal State Autonomous Educational Institution of Higher Education "National Research University ITMO"{ITMO University, 197101, Saint Petersburg, Kronverksky Ave., 49, lit. A), phone [phone], e-mail: [e-mail], ORCID ID: 0000-0002-0191-1178.

Altan к F. khut sacra

PhD student. Faculty of Information Security Technologies, Federal State Autonomous Educational Institution of Higher Education "National Research University ITMO"{ITMO University, 197101, Saint Petersburg, Kronverksky Ave., 49. lit. A), e-mail: [e-mail],ORC ID ID: 0000-0001-5494-7142.

Alia stasia P. Kiryaimva

PhD student. Faculty of Information Security Technologies, Federal State Autonomous Educational Institution of Higher Education "National Research University ITMO"{ITMO University, 197101, Saint Petersburg, Kronverksky Ave.. 49, lit. A), e-mail: [e-mail], ORCID ID: 0009-00060344-5111.

Ivan D. loganson

PhD student. Faculty of Information Security Technologies, Federal State Autonomous Educational Institution of Higher Education "National Research University ITMO"{ITMO University, 197101, Saint Petersburg, Kronverksky Ave., 49, lit. A), phone [phone], e-mail: [e-mail], ORCID ID: 0000-0002-08562249.

Zhao-Michel N. Dakun

PhD student. Faculty of Information Security Technologies, Federal State Autonomous Educational Institution of Higher Education "National Research University ITMO"(ITMO University, 197101, Saint Petersburg, Kronverksky Ave., 49, lit. A), phone +7 921 78й 3 1 22, e-mail; [e-mail], ORCID ID: 0000-0002 -40 84-8 829.

Sergey V. Bezzatecv

PhD, Professor, Head of the Department of Information Security, Institute of Cybernetic Systems, St. Petersburg University of Acrospace Instrumentation, director of Laboratory of Cryptographic methods for information security, FSIT, Federal State Autonomous Educational Institution ol" Higher Education "National Research University ITMCC"(ITMD University, 197101, Saint Petersburg, Kronverksky Ave., 49. lit. A), e-mail:

sergey . bezzateevii gniai i .con, ORCID ID: 0000-0002-0924-622].

M ЛТ-ИС?-ТЕХНИЧЕСКИЙ ВЕСТИ И К циаэдрьгйштоичи* ТЭИЙЛОГИЙ. МЕХАНИКИ и OTPftfWl

I/ÎTMO

«»»-»oHsadzs

Tow В № 3

SCIENTIFIC AND TEÛHMCAL JOuflMAL OF INFORMATION TECHNOLOGIES MECHANICS AND OPTCS

'HOQFVJEB JHD- lb'< 1ЕШШ11, MBUHIIIIППЛЯН

IVUv-Jund L'lCl

тИ./'.'ПТ^ГГПй.ГцШГи'

щ^гкчитз^и*)

doi: 10.175 &5Д226-1494-2025-25-3-446-456 УДК 004.0%. 5 5

Анализ применимости существующих схем разделении секрета н условиях посткван i оной >ры К.тн ¡ар Фи ларет оuu11 Кус I об1 , Сергеи В j .'icii i'iiiio is и11 EejjarceK'

1 : Университет ИТМО, Санкт*11етербур<; 197101, Российская Федерация

2 Санкт-Петербургский государственный университет а.чрокоеми ческого приборостроении, Санкт-Петербург 190000. Pimc нйсьал Федерация

1 el¡2arliijs[ov(a;mail.га-httpq://orcid.org/0000-0002-0191-l I7& 1 sergey.bezzaieevfiiigraail coin, httpsJ/oreutDi^.'0000-0002-0924-622 I

Рассмотрены современные подходы к разделению секрета включая ki>: классические, так и поегевантовыг криптографические схему. Исследованы методы распределения секретной информации между несколькими участниками с использованием математических примитивов, таких как многочлены Лнтранжа и Ньютона, китайская теорема ой остатках, коды исправляющие ошибки, теория решеток, то гении эллиптических кривых, многомерные уравнения и хэш-функции. Приведен сравнительный анализ различных схем с точки зрения их устойчивости к квантовым атакам, эффективности и соответствия критериям [Памира. Особое внимание уделено оценке устойчивости схем к этапам с использование квантовых компьютеров, что особе «но актуально в условиях развития квантовых технологий. Рассмотрены преимущества и недостатки каждой на схем. включая их вычислительную сложность, гибкость н возможность адаптации к различным условии. Потаено, что классические схемы, такие как схемы Швывра н Ньютона, остаются эффективными и простыми в реализации, но уязвимы к квантовым атакам. В то же время псьстквантовые схемы, основанные на теории решеток, демонстрируют высокий уровень безопасности, но требунит более сложных вычислений. Ключевые слов*

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

Работа выполнена в рамках государственного задания (проект№ FSER-2025-0003).

Ссылка для цитирования! Кустов П.Ф., Бсазатсев C.B. Анализ применимости существующих схем разделении секрета в условия к постквантовой эры /I НаучнотехшшескиН вестник информационных технологий, механики н оптики. 2025. Т. 25, № 3. С. +46-456. (loi: 10.17Ж/2226Л 494-202 5-2 5-S-44fr456

ГГМО University, Saim Petersburg, 197101, Russian Federation - SaLtw-Petersburg Slate University of Aerospace Instrumentation (SUAI), Saint Petersburg, 190000, Russian Federation

1 [e-mail]: -, h[lp.q://oiCLd.org/0000-0Q02-0191-ll7B

2 sergey.be [e-mail], imps:/;Wid.org/0000-0002-0924-6221

Modem approaches to secret sharing have been examined, encompassing both classical and post-«] uantum cryptographic schemes. The study explores methods for dislribucing secret information among multiple participants using variotw mathematical primitives, such as Lagrange and Newton polynomials, the Chinese remainder theorem, error-correcting

S3 Кустов Е.Ф., Беззатссв C.B.. Î1Û5

All IIO I JII LIU

Analysis of the' applicability of existing secret separation schemes in the post-quaternary era Elizar F. Klistov1 -, Sergey V. Bezztleev1

Abstract

Научно-гахничаскийнастник: информационных технологий, моканикм и оптики 2Ù2S. том 25, № 3 Scientific and Technical Journal of Information Technologies. Mechanics and Optics. 2025, vol. 25, no 3

codes. lattice theory, elliptic curve isogenics, multivariate equations. and lush functions. A comparative analysis of different schemes is provided In terms of their resistance to quantum altars, eiliciency. and compliance with Shamir's criteria. Special attention is given to assessing the schemes resilience against attacks using quantum computers, which is particularly relevant given the advancement of quantum technologies, The advantages and disadvantages of each scheme are discussed, including their computational complexity, flexibility, and adaptability to various conditions, li is shown Lliat classical schemes, such as [hose by Shamir and Newton, remain efficient and easy to implement but are vulnerable to quantum attacks. Meanwhile, post-quantum schemes based on lattice theory demonstrate a high level of security but require more complex compulations.

Keywords

post-quantum cryptography, secret sharing scheme, threshold scheme, public-key cryptography, lattice theoiy. elliptie

curves, multivariate equations, error-correcting codes, hash functions

Acknowledgments

The work was carried out within the framework of the State Assignment [project No. F5ER-202 5-0003}.

Foi- citnliuii: Kustov E.F., Beuateev S.V. Analysis of the applicability of existing secret separation schemes in the post-quaternary era. Scientific and Tcchmcat Journal of tnfbrmitlian Tcchiioliigtcs. Mechanics and Optics, 2025, vol. 25. no. 1. pp. 44S- 45ft (in Russian), doi: 10.17586.,222(i-1494-2025-25-3-446-456

Ввезенне

Первый метод разделения секрета пыл предложен еще в 1974 году Шамиром [1] и Блейкли [2] независимо друг от друга. Схимы разделения сскрста применяются в случаях, когда существует значимая вероятности компрометации хранителей сскрста, но вероятность недобросовестного сговора значительной части участников Считается пренебрежимо малой.

Появление алгоритма Шора для квантового компьютера, поставила под угро зу классические криптосистемы. Основанные на проблемах факторизации числа И ДНСКрСТПОГО логарифма. Возник вопрос о создании новых систем, устойчивых к атаке с использованием квантового компьютера.

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

В настоящей работе выполнен анализ и сравнение между собой новых посткваптовык и классических схем разделения секрета для поиска оптимальных схем. Сравнение происходит по критериям Шамира: размер доли меньше или равен самому секрету, возможности повторного использовании сскрста, невозможность проанализировать секрет, ВОЗМОЖНОСТЬ добавления нового участника, возможность обновить секрет, возможность изменения веса долей.

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

Схема разделения секрет* но Интерпола и но иному щ I пи ичлен у Л а гра нжа

Схема разделения секрета по и н тер полян нон ному многочлену Лаграижа, также известная как схема

Шамира [] J. является одной из самых популярных пороговых схем разделения секрета. Она основана па интерполяции многочленов [3] н позволяет разделить секрет между н участниками так, что для ело восстановлен ия требуется как минимум Одолей \к< ri).

В этой схеме секретная информация, представленная целым числом S, распределяется между п участниками н может быть восстановлена при наличии как минимум к долей. Доверенный центр, называемый дилером, выбирает простое число р > S и генерирует многочлен q(x) степени к 1 над GF{py.

q(s) = S-щж + +

где а,, ..., at , выбираются дилером случайным образом из равномерно распределенных элементов GF[p).

Участник P¡ (i = 1,____п) получаст толико целое число

D¡ = ij(î) в качестве доли, где i — уникальный идентификатор участника P¡\ q{i) — значение многочлена в точке г. При наличии Одолей можно восстановить q(jc) с использованием интерполяции Лаграижа и, следовательно, восстановить секрет S - <у(0).

В ехсмс по интерполяционному многочлену ЛаграЕ]жп, при наличии к I долей для любого сскрста S'. невозможно восстановить соответствующий ему многочлен. Таким образом, к I долей не лают в и какой ni [формации о секрете.

Злоумышленник не сможет восстановить секрет S при условии, что он не имеет доступа к к или более долям, так как многочлен степени к - I однозначно определяется Сточками. Схема устойчива к атакам, основанным на переборе, благодаря использованию конечного поля GFip) при выборе большого значения р. Также благодаря использованию интерполяционного многочлена Лагранжа можно добавить нового у част инка.

В табл. I представлены значения размеров ключей и долей секрета для 128-битной и 256-битной безопасности для схемы Шамира. В качестве ключей были использованы RSA{RivcM, íliamir, Adleman) из рекомендации NIST [4]. 128-битная и 25fi-битная безопасность — уровни криптографической стойкости, которые показывают, насколько сложно взломати систему перебором илн другими атаками и означают, что для

научно- юхиичвекий вестник информационных юхыологий, механики и оптики, 2025, тон 25, № 3 Scientific ano Technical Journal or Information Technologies, Mechanics and Optics, 2025, vol. 25, no 3

Анал чзпрпменимистч су щесг вую щих ске м раздел ен и я ое крета а уел ов н як п и сткванто вой эр ы

Таблица 1. Сравнение размера ключевых элементов схемы Шамнра, бит

Table !. Comparison of the key elements size о Г the Shamir scheme, hit

Париметр 12Й-Снпзля 256-í нти

бс:м]]асниеть сч.":шнасноетъ

Секрет .7 3072 15 360

Доля D¡ 3072 15 360

Коэффициенты 3072 X (i 1) 15 360 ■ (i 1)

взлома потребуется о среднем 2'-s и 2-íí операций

cootbctctbc] mo.

Как видно из табл. 1 размер сскрста л сто долей равны. что позволяет использовать доли сскрста в качестве секрета в криптосхсмах без дополнительных модификаций, Отмстим, что наиболее затратным для хранения данных, является размер коэффициентов многочлена.

[I одчеркнем, что рассматриваемая схсма не обеспечивает безопасность самого сскрста S н ело долей D¡, для зтого сегодня используются вариации схемы Шамнра с криптосистемами R5A [5], ЕС DC А [6] и Эль-Гамаль [7]. В этим варианте реализации общая криптосистема становится уязвима к атаке с применением квантового компьютера, е отличии от криптосистем, основанных на постквантовых крнптопрнмнтнвах. Также к недостаткам схемы можно отнести не надежность дилера, так как предполагается, чти вес участники могут доверять выбранному центру, что не всегда верно.

Схема разделении секрета

но ни i ернолицпшпншу многочлену Пышопи

Схема разделения секрета на основе интерполяционного многочлена Ньютона метод разделения секрета, который использует интерполяцию многочлена Ньютона для восстановлен ля секрета. Этот подход похож на схему [Памира, по вместо интерполяции Лагранжа применяется интерполяция Ньютона. Многочлен Ньютона стспепн í I имеет вид:

J[x) = do + Ol(jf - Jt|) + - -Ti )t* - -Tj) + - ■ -

i(jt - jc])fjr - jt2> (j:-

где íTj,, a i.....a. i - коэффициенты; jrt, ,v2, —

заранее выбранные точки.

В начале дилер выбирает jtj, .V;, где п ко-

личество участников. Дзя каждой) участника Р. вычисляется значение многочлена в точке x¡. т. е. /(.тД Это значение является долей участника.

Для восстановления сскрста необходимо собрать как минимум г долей. Используя интерполяцию Ньютона, строится многочлен _/(jt) по I точкам {д„ /(.т,)}. Секрет S восстанавливается как значение многочлена л точке х = 0, т. е. S = /(0).

Схема разделения секрета на основе многочлена Ньютона обладает теми же свойствами, что и схсма разделения сскрста по Лагранжу. Это значит, что она также уязвима к атаке с использованием квантового компьютера, если не добавить в схему постквапто-

выс криптопримнтлвы. Размеры ключей схемы подобны значениям, что и в схеме разделения сскрста ло Лагранжу, представленные в табл. I.

Схема разделении секрета на основе кит айской георемы oft остатках

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

Как и в схем с Шамнра. в работе [Я] присутствует доверенный дилер, который определяет общий секретS и попарно взаимно простые числа ____mlr, такие что:

Л1л-*+! * * ... w„<S<m| х т-у к in*,