Коды для локального и конфиденциального восстановления информации тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Круглик Станислав Александрович

• Круглик Станислав Александрович
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Круглик Станислав Александрович

Введение

Глава 1. Коды с локальным восстановлением и их обобщения

1.1 Введение

1.2 Коды с локальным восстановлением

1.3 Верхние границы на минимальное кодовое расстояние (г,£) - ЛВ кодов

1.4 Нижние границы на минимальное кодовое расстояние (г,£)-ЛВ кодов

1.5 Максимальная длина оптимальных (г,£)-ЛВ кодов

1.6 Границы на параметры (г,Ь,х)-ЛВ кодов

1.7 Анализ результатов

1.8 Выводы к главе

Глава 2. Коды для распределенных систем при наличии

злоумышленника

2.1 Введение

2.2 Конфиденциальность данных в распределенных системах

2.3 Коды с локальным восстановлением и несколькими восстанавливающими множествами, устойчивые к злоумышленнику с доступом к ограниченному числу серверов

2.4 Коды со свойством регенерации

2.5 Коды со свойством регенерации, устойчивые к злоумышленнику

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

2.6 Анализ результатов

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

Глава 3. Локальный доступ к данным при наличии

злоумышленника

3.1 Введение

3.2 Задача локального доступа к данным

3.3 Границы на параметры схем локального доступа к данным

3.4 Линейные схемы

3.5 Оптимальные конструкции

3.6 Задача балансировки нагрузки на сервера

3.7 Конструкции над полями малой мощности

3.8 Граница случайного кодирования

3.9 Анализ результатов

3.10 Выводы к главе

Заключение

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

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

Введение

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

Для решения данных задач используются специальные классы кодов, исправляющих стирания, а также их модификации на случай возможного наличия в системе злоумышленника. При этом, в связи с распределенным характером рассматриваемых систем, ставится задача оптимизации процедуры восстановления информации, хранимой на малом числе серверов. Выделяют два критерия, по которым проводится оптимизация. В первом случае минимизируется число задействованных серверов, называемое локальностью. Соответствующие коды называются кодами с локальным восстановлением. Их важным обобщением являются коды с несколькими восстанавливающими множествами для каждого кодового символа, позволяющие получать данные с недоступного сервера сразу несколькими способами. Во втором же случае оптимизируемым параметром является суммарный объем передаваемой информации, а соответствующие коды называются кодами со свойством регенерации [3]. При наличии в системе пассивного злоумышленника-подслушивателя ставится задача восстановления информации, хранимой на малом числе серверов таким образом, чтобы он не получил никакой дополнительной информации о пользовательских данных. Решение последних задач тесным образом связано с теорией каналов с подслу-шивателем, а также схемами разделения секрета [4—6]. Исследованию кодов для распределенных систем, а также способов защиты информации в них посвящено множество работ отечественных и зарубежных ученых, среди которых следует особенно выделить А.М. Барга, Р.Г. Блейкли, Д. Брука, А. Димакиса, П.В. Кумара, А. Мазумдара, Н. Сильберштейн, А. Спринтсона, И. Тамо, А.А. Фролова, А. Шамира, Э. Яакоби.

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

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

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

1. Исследовать свойства кодов с локальным восстановлением и несколькими восстанавливающими множествами.

2. Исследовать свойства кодов с локальным восстановлением и несколькими восстанавливающими множествами, пересекающимися в малом числе позиций.

3. Исследовать свойства кодов с локальным восстановлением и несколькими восстанавливающими множествами при наличии в системе злоумышленника с доступом к ограниченному числу серверов.

4. Исследовать свойства кодов со свойством регенерации при наличии в системе злоумышленника с ограниченным доступом ко всем серверам.

5. Исследовать задачу локального доступа к пользовательским данным при наличии в системе злоумышленника с доступом к ограниченному числу серверов.

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

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

2. Найдена верхняя граница на максимальную длину оптимальных кодов с несколькими восстанавливающими множествами.

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

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

множествами в системе с подслушивателем, имеющим доступ к ограниченному числу серверов.

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

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

7. Разработаны конструкции кодов с локальным доступом к данным и свойством балансировки нагрузки для систем с подслушивателем.

8. Предложены конструкции кодов с локальным доступом к данным над полями малой мощности для систем с подслушивателем.

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

1. Для кодов с несколькими восстанавливающими множествами предложены новые верхние и нижние границы на минимальное расстояние кода и новая граница на максимальную длину кода.

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

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

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

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

6. Впервые предложены конструкции кодов с локальным доступом к данным при наличии подслушивателя с доступом к ограниченному числу серверов над полями малой мощности.

Практическая значимость подтверждается использованием результатов, полученных в рамках диссертационной работы, при выполнении грантов РФФИ 19-37-90022 «Обеспечение конфиденциальности в системах распределенного хранения информации», РФФИ 19-17-50094 «Теоретико-информационный подход в задаче построения систем распределенного хранения информации» и РФФИ 18-37-00459 «Исследование методов кодового восстановления данных в высоконагруженных системах распределенного и облачного хранения».

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

Апробация работы. Основные результаты работы докладывались на следующих конференциях: IEEE Global Communications Conference (Globecom 2020), IEEE 21st International Symposium on «A World of Wireless, Mobile and Multimedia Networks» (2020), 2019 IEEE 90th Vehicular Technology Conference (2019), IEEE International Symposium on Information Theory (2017-2018), IEEE Information Theory Workshop (2017). Кроме того, основные результаты докладывались на семинарах по теории кодирования ИППИ РАН и кафедры радиотехники и систем управления МФТИ.

Личный вклад. Данное диссертационное исследование является законченным трудом автора. Верхние и нижние границы на минимальное кодовое расстояние кода с несколькими восстанавливающими множествами, а также предложенное обобщение на случай пересекающихся восстанавливающих множеств, были получены совместно с научным консультантом А.А. Фроловым. Конструкции кодов с локальным доступом к данным при наличии подслуши-вателя с доступом к ограниченному числу серверов, а также их обобщение на случай балансировки нагрузки на сервера, были получены совместно с научным консультантом А.А. Фроловым и соавторами Л. Хольцбауром и А. Вахтер-Цех. В остальных совместных работах соавторам принадлежит общая постановка задач, включая анализ литературы.

Публикации. Основные результаты по теме диссертации изложены в 13 печатных изданиях [7—19], 11 из которых изданы в изданиях, рекомендованных ВАК [7—11; 14—19], 1 в журналах из перечня РИНЦ [12], 1 в тезисах докладов

Объем и структура работы. Диссертация состоит из введения, трех глав и заключения. Полный объём диссертации составляет 112 страниц с 18 рисунками и 5 таблицами. Список литературы содержит 83 наименования.

Глава 1. Коды с локальным восстановлением и их обобщения

1.1 Введение

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

1.2 Коды с локальным восстановлением

Определим конечное поле ^ из д элементов и множество координат [п] = {1,2,... ,п}. В данном поле, в соответствии с работами [20—22], определим код с локальностью следующим образом.

Определение 1.1. Код С С ^ называется кодом с локальностью г и обозначается как г-ЛВ код, если каждый символ любого кодового слова е е С является функцией от не более чем г других его координат.

Замечание 1.1. Данное определение эквивалентно наличию восстанавливающих множеств ограниченного размера для каждой координаты % е [п] кодового слова. Понятие восстанавливающего множества определено ниже.

Определение 1.2. Подмножество координат ^ С [п] \ {г}, < г кодового слова е е С называется восстанавливающим множеством для координаты % е [п] если сужение кода С на данное множество позволяет однозначно восстановить значение координаты кодового слова С{.

Естественным обобщением кодов с локальным восстановлением являются коды с локальным восстановлением и несколькими не пересекающимися восстанавливающими множествами, введенное в работах [23; 24]. Отметим, что одновременное наличие нескольких восстанавливающих множеств для каждого кодового символа позволяет параллельно обрабатывать запросы на их восстановление. В случае применения данных кодовых конструкций в системах распределенного хранения данных, когда каждый сервер хранит один кодовый символ, это свойство особенно важно для данных, одновременно запрашиваемых множеством пользователей. При этом большинство работ рассматривает данное свойство применительно только к информационным символам [23—26], мы же, в отличие от них, рассматриваем его в применении ко всем символам, что, в свою очередь, позволяет унифицировать процесс построения данных систем. Формальное определение кодов с локальным восстановлением и несколькими не пересекающимися восстанавливающими множествами или, для простоты, кодов с несколькими восстанавливающими множествами, дано ниже.

Определение 1.3. Код С С ^ называется кодом с локальностью г и £ не пересекающимися восстанавливающими множествами и обозначается как (г, ¿)-ЛВ код если для каждой координаты г Е [п] существует Ь не пресекающихся восстанавливающих множеств ... С [п] \ {¿} размера не более чем г. Причем для всех ] = 1,... и любых двух различных символов а, а' Е ^ справедливо что С(г,а)^ П С(г,а')пз = 0, где С(¿,а)-множество кодовых слов кода С таких что значение координаты % в них равно а. С/ в свою очередь обозначает сужение кода С на подмножество координат I С [п].

Первая граница на минимальное кодовое расстояние (г,£)-ЛВ кодов, которое, в свою очередь, определяет их корректирующую способность при исправлении ошибок и стираний методом максимального правдоподобия, была представлена в работах [27; 28]

& < п - к + 2 - --{—

Ч(г - 1) + 1 1

В дальнейшем данная граница была улучшена в работе [25]

Л к- 1

* <п - Е^н. м

гр ь i=0

Алфавитозависимая граница на минимальное кодовое расстояние (г,t)-ЛВ кодов была получена в работе [24] и имеет форму

d < min [tf. (п — В,к -А)}, (1.2)

1<х<\1^+1\;1<Уз <t;je[x] F А<к ; x,yj +

где А = Xj=i(r — 1)Уз + х и В = YhXj=i гУз + х. dql_opt(n, к) обозначает макси-

мально возможное минимальное кодовое расстояние линейного кода длины п и размерности к над полем ^.

Граница на кодовую скорость (г^)-ЛВ кода была получена в работе [25] и имеет форму

к Л 1

- <я*(г*) = П т+т. (°)

г=1 гг

Отметим, что данная граница верна как для нелинейного так и для линейного случая. Улучшение данной границы для последнего было получено в работе [29] и имеет вид.

к . _ , . t t 1 п

- < ) = 1--+--+---. (1.4)

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

Определение 1.4. Код Се ^ называется (г ,£,х)-ЛВ кодом если для каждой координаты г е [п] существует Ь восстанавливающих множеств К1,...," С [п] \{г} размера не более чем г. Причем для любых различных индексов I,I' е Щ справедливо что П " | < х. Кроме того для всех ] = 1,... и любых двух различных символов а, а' е ^ справедливо что С (г ,а)" П С (г ,а')пз = 0, где С (г ,а)пз введены в определении 1.3.

1.3 Верхние границы на минимальное кодовое расстояние (r,t) -

ЛВ кодов

В этом разделе будут выведены верхние границы на минимальное кодовое расстояние (г,£)-ЛВ кода. Для выводов была использована известная граница укорочения кода, а также идея применения аппарата обобщенных весов Хэм-минга к кодам с локальностью [30; 31]. Так как в ходе вывода границ мы модифицируем данные техники, приведем полностью все необходимые для этого доказательства и промежуточные выкладки.

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

Определение 1.5. Множество координат С1(1) 1Э I кода С называется замыканием подмножества I С [п] если для любого кодового слова c £ С значения координат Ci, г £ С1(1) являются функцией от с/. Последнее, как и ранее, обозначает сужение кода С на подмножество координат I С [п].

Обозначим через k*(q,n,d) верхнюю границу на размерность линейного кода длины п над полем Fg с минимальным кодовым расстоянием d, а через d*(q,n,k) верхнюю границу на минимальное кодовое расстояние линейного кода длины п и размерности к над полем Fg.

Теорема 1.1. Для параметров линейного кода С над полем Fg справедливы следующие границы

к < min {\I| + k*(q,n -\Cl(I)\,d)} (1.5)

1 :\Cl(l )\<n—d

d < min {d*(q,n -\Cl(I)\,k - \I\)}. (1.6)

I :\I\<k

Доказательство. Начнем доказательство с вывода неравенства (1.5). Зафиксируем такое подмножество координат I С [п] что \Cl(I)\ < п — d и разделим множество всех кодовых координат на А = С1(1) и В = [п] \ С1(1). Легко видеть что для кода С верно неравенство

юакяw,

где Са как и ранее обозначает сужение кода С на множество координат А. Отметим, что неравенство выше не является строгим ввиду того, что множество I может содержать ряд зависимых координат.

Зафиксируем теперь значения кодовых слов на множестве А. При этом код С имеет не более чем qk*(n,\B\,d) различных кодовых слов с данным свойством. Т.к. при этом минимальное кодовое расстояние кода равно d, а рассматриваемые слова отличаются только на множестве В верна следующая оценка на мощность исходного кода

\С\ < CAqk*(n\B\A) < q\i\qk*(n,\B\,d)_

Логарифмируя полученное неравенство получаем требуемое выражение

1.5.

Перейдем теперь к выводу неравенства 1.6. Зафиксируем подмножество координат I С [п] такое что \1\ < к и выберем кодовые слова кода С для которых сужение на подмножество I является нулевым словом. Так как рассматриваемый код является линейным, то сужение на множество А = CI(I) также является нулевым словом. Отметим, что фиксируя данное сужение мы имеем дело с подкодом С С С исходного кода.

Рассмотрим теперь код С" являющийся сужением С на подмножество координат В = [п] \ CI(I). Данный код имеет не более чем gk-\J\ кодовых слов из чего следует, что для его минимального расстояния верна оценка

d(C) <d*(q,\В\,к -\1\).

Из свойств проведенных выше процедур заключаем, что d(C) < d(C') = d(C"). Это, в свою очередь, приводит к требуемому выражению 1.6 и завершает доказательство. ▲

Замечание 1.1. Отметим, что Теорема 1.1. также верна и для нелинейного случая. В последнем под к будем понимать log \ С\.

Используя технику укорочения применительно к структуре (г,t)-ЛВ кода получим верхние границы на параметры последнего в линейном случае. Данный

результат сформулирован в виде Теоремы 1.2. Перед ее доказательством введем следующее определение.

Определение 1.6. Множество supp(v) ненулевых координат вектора v называется его носителем.

Теорема 1.2. Для параметров линейного (r,t)-.RB кода С над полем справедливы следующие границы

к < min {1 + (г — 1)s + k*(q,n — 1 — sr,d)} (1.7)

sr+1<n—d

d < min {d*(n — 1 — sr,k — 1 — (r — l)s)}. (1.8)

1+(r-l)s<k

Доказательство Определим код, двойственный к коду С через С1, а через С^т+1 обозначим множество кодовых слов кода С1 имеющих не более чем г + 1 ненулевых координат. Отметим, что число ненулевых координат кодового слова также называется весом Хэмминга. В дальнейшем будем обозначать последнее как wt. Множество С1 = {h £ С1 : wt(h) < г + 1} будем называть локальным проверками. С помощью последних построим множество координат I, \I\ = 1 + (г — 1)s), обладающих свойством что \С1(1 )\ > 1 + rs. Для этого применим Алгоритм 1 с входными параметрами С11 и s. Опишем его более детально. На каждом шаге алгоритм добавляет к множеству X новую локальную проверку из множества С^. Это происходит до того момента как мы добавили s таких линейно-независимых локальных проверок. Набор позиций, покрытых такими проверками мы обозначаем через J. На шаге 8 алгоритм из всего множества локальных проверок выбирает ту, которая имеет максимальное пересечение с J. При этом возможны два случая:

— существует локальная проверка, пересекающаяся с J.

— не существует локальной проверки, пересекающейся с J.

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

Алгоритм 1 Построение множества I, используемого в доказательстве Теоремы 1.2._

Вход:

Г1 я Выход:

X, I, 5-, з 1: Н ^ Сг.+ 1

2: Выбрать любую локальную проверку Ь е Н 3: 3 ^вд^), X ^ {Ь}, Н ^ Н \ Ь

4: I ^ 1 > Число добавленных локальных проверок

5: г ^ 1 > Число добавленных линейно-независимых локальных проверок 6: 0

7: Пока верно г <8 выполнять

8: Найти локальную проверку Ь е Н с наибольшим ^3 Пsupp(h)| 9: Если ^Пsupp(h)| = 0 выполнять 10: ] ^ I 11: Й1 ^ г 12: г ^ 1 + 1 13: В противном случае 14: Если Ь еspan{X} выполнять 15: г ^ г + 1

16: В противном случае 17: 3 ^ 3^вд^), X ^ X и {Ь}, Н ^ Н \ Ь 18: 1 + 1

19: Выбрать множество I из X > При этом 3 = С1 (I)

20: Если | Ц < 1 + (г — 1)й выполнять

21: Добавить любые 1 + (г — 1)й — Щ из оставшихся координат

множеств, формирующих данный код, сохраняется в переменной 3, а число проверочных символов в нем в переменной 1.

Из описания алгоритма становится ясно, что с его помощью нами было построено множество такое что | С ( ) \ | = . Остается проверить, что размер данного множества не может быть больше чем 1 + (г — 1)й. Известно, что первые 3 элементов множества X формируют (г3)-ЛВ код, содержащий й1 проверку. Наихудшим случаем с точки зрения возможного размера множества является пересечение оставшихся й — й1 элементов X по одной позиции. В данном случае может быть получена следующая оценка

И < 1 — щг^) — «1 + 1 + (* — *1)(г — 1) < 1+8(г — 1),

где последний переход следует из границы 1.3 для t > 2.

Подстановка полученной оценки в Теорему 1.1. дает необходимый результат. ▲

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

Следствие 1.1. Для минимального кодового расстояния линейного (г^)-ЛВ кода верна оценка

k — 2

d < п — (к — 1) — L| (1.9)

Доказательство Подстановка границы Синглтона в выражение 1.8 дает d < min {п — 1 — sr — к + 1 + (г — 1)s + 1} = п — (к — 1) — smax.

1+(r—1)s<k

Т.к. число линейно независимых символов рассматриваемого кода равно к, то верна оценка 1 + (г — 1)s < к из которой следует, что smax = [^—f_|. Подстановка последнего выражения в формулу выше приводит к требуемому результату. ▲

Коды, достигающие данной границы, также будем называть МДР-ЛВ кодами.

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

Следствие 1.2. Для кодовой скорости (г,£)-ЛВ кода в при п ^ ж верна следующая оценка

г — 1

R < (1 — Ö) — о(1), (1.10)

где ö = d/n - относительное минимальное кодовое расстояние.

Объединим представленную выше технику укорочения и идею применения обобщенных весов Хэмминга к оценке минимального кодового расстояния кода с локальностью, представленную в работе [31]. Перед тем, как начать непосредственный вывод границ, дадим необходимые предварительные сведения.

Определение 1.7. Носителем кода С называется множество х(С) определяемое следующим образом

Х(С) = [г : Э(а,с2,...,сп) еС,сг = 0}.

Определение 1.8. Для любого 1 < г < к г-ый обобщенный вес Хэмминга ^ линейного кода С определяется выражением

¿г = тт[1х(В)1 : В С С, &ш(П) = г}.

Связь обобщенных весов Хэмминга и проверочной матрицы линейного кода может быть представлена в виде следующей Теоремы ([30]).

Теорема 1.3. Обобщенные веса Хэмминга линейного кода С с проверочной матрицей Н определяются с помощью следующего выражения

^ = шт[|Х| : IXI — гапк(Нх) > г1},

где X С [п]-подмножество координат, Нх - столбцы матрицы Н, с номерами из множества X, гапк-ранг матрицы.

Отметим, что первый обобщенный вес Хэмминга (!1 равен минимальному кодовому расстоянию линейного кода. При этом верна обобщенная граница Синглтона [30] сформулированная в виде Теоремы 1.4.

Теорема 1.4. Для обобщенных весов Хэмминга любого линейного кода длины п и размерности к верна следующая оценка

(1г < п — к + г, (1.11)

где 1 < % < к.

Определение 1.9. Иерархией обобщенных весов Хэмминга линейного кода С называется набор чисел 1 < г < к}.

Для иерархии обобщенных весов Хэмминга любого линейного кода С длины п и ненулевой размерности к верна оценка [30; 32]

1 < (11 <¿2 < ... < = п. (1.12)

Перейдем теперь к непосредственному доказательству теоремы о минимальном кодовом расстоянии (г,£)-ЛВ кода.

Теорема 1.5. Для обобщенных весов Хэмминга di линейного (г^)-ЛВ кода С длины п и размерности к над ^ верна следующая оценка

di < min {d*(q,п — 1 — sr,k — 1 — (г — 1)s)}, 1 <i<k — г, (1.13) i<<L W J

где d*(q,п,к) - верхняя граница на г-ый обобщенный вес Хэмминга линейного кода.

Доказательство Рассмотрим процедуру укорочения, описанную в алгоритме 1. На шаге s мы получаем линейный код Cs над F q длины не более чем п — 1 — sг и размерности к — 1 — (г — 1) s. При этом из связи обобщенных весов Хэмминга и проверочной матрицы коды, сформулированной в Теореме 1.3. следует, что di(Cs) > di(C) для 1 < i < к — г. Непосредственное применение определения обобщенных весов Хэмминга к последнему выражению дает утверждение доказываемой теоремы. ▲

Замечание 1.2. Данная граница в случае i = 1 совпадает с границей 1.8.

Применение обобщенной границы Синглтона, сформулированной в Теореме 1.4, к Теореме 1.5. позволяет получить явный вид верхней границы на обобщенные веса Хэмминга линейного (г,t)-ЛВ кода, сформулированный в следующей теореме.

Теорема 1.6. Для обобщенных весов Хэмминга линейного (г,t)-ЛВ кода С длины п и размерности к над полем Fg верна оценка

1

di < п — (к — i) — [ r_1 J, (1.14)

где 1 < i < к — г.

Доказательство В соответствии с обобщенной границей Синглтона di < п — к + i. Подставляя данное выражение в формулу 1.13 получаем

di < min {п — 1 — sr — к + 1 + (г — 1)s + i}

i< S<L W J

= min {п — к — s + i}

i< S<L W J

= п — (k — i) — Lk r г J,

что завершает доказательство теоремы. ▲

В работе [31] было показано, что обобщенный вес Хэмминга ^ и минимальное расстояние линейного кода ё, связаны соотношением

г—1 й

ъ - ] (1.15)

з =0 4

Отметим, что данный факт является результатом применения границы Грисмера к подкоду V кода С, размер носителя которого равен [33].

Используя данную связь мы можем сформулировать следующую лемму. Лемма 1.1. Для линейного (г,£)-ЛВ кода С длины п и размерности к над полем ^ верна оценка

А < шт К. 9 [ п — (к — г) — У -—1—- И У (1.16)

- 1<г<к—Л д* — V У 1 г — ^ 1

Доказательство Подставляя выражение 1.15 в границу 1.14 получаем

£ г 4 к« — (ку -1 ^

3=0 4 1

откуда следует утверждение леммы. ▲

Замечание 1.3. Асимптотический вид выведенной границы при п ^ <ж совпадает с видом границы из Теоремы 1.2.

1.4 Нижние границы на минимальное кодовое расстояние (г,£)-ЛВ

кодов

В данном разделе будет доказано существование (г^)-ЛВ кодов с большим минимальным кодовым расстоянием над конечными полями ¥дт большой мощности. При этом поле ^ будем называть основным, а поле ¥дш расширенным.

Список литературы диссертационного исследования кандидат наук Круглик Станислав Александрович, 2021 год

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

1. Aftab U., Siddiqui G. F. Big Data Augmentation with Data Warehouse: A Survey // 2018 IEEE International Conference on Big Data (Big Data). — 2018. — P. 2785-2794.

2. Reinsel D., Gantz J., J. R. The Digitization of the World From Edge to Core: IDC White Paper no. US44413318. — 2018.

3. Erasure coding for distributed storage: an overview / S. B. Balaji [et al.] // Science China Information Sciences. — 2018. — Vol. 61, no. 10. — P. 100301.

4. Ozarow L. H., Wyner A. D. Wire-tap channel II // AT&T Bell Laboratories Technical Journal. — 1984. — Vol. 63, no. 10. — P. 2135-2157.

5. Shamir A. How to Share a Secret // Commun. ACM. — New York, NY, USA, 1979. — Nov. — Vol. 22, no. 11. — P. 612-613.

6. Blakley G. R. Safeguarding Cryptographic Keys // Proceedings of AFIPS National Computer Conference. Vol. 48. — Arlington, VA, USA, 06/1979. — P. 313-317.

7. Круглик С. А. Коды с минимальным хранением, устойчивые к атакам специального типа // Информационно-управляющие системы. — 2021. — фев. — № 1. — с. 38—44.

8. Secrecy and Accessibility in Distributed Storage / L. Holzbaur [et al.] // GLOBECOM 2020 - 2020 IEEE Global Communications Conference. — 2020. — P. 1-6.

9. Kruglik S., Frolov A. An Information-Theoretic Approach for Reliable Distributed Storage Systems // Journal of Communications Technology and Electronics. — 2020. — Vol. 65, no. 12. — P. 1505-1516.

10. Kruglik S. Security Issues in Distributed Storage Networks // 2020 IEEE 21st International Symposium on "A World of Wireless, Mobile and Multimedia Networks" (WoWMoM). — 2020. — P. 62-63.

11. Kruglik S. Secure MBR array codes in the presence of special type eavesdropper // Lecture Notes in Computer Sciecne. — 2020. — Vol. 12526. — P. 56-66.

12. Круглик С.А. и Фролов А. А. Теоретико-информационный подход в задаче надежного распределенного хранения информации // Информационные процессы. - 2020. - т. 20, № 1. - с. 22-40.

13. Круглик С. А. О применении схем разделения секрета в распределенных системах хранения информации // Вероятностные методы в дискретной математике. Расширенные тезисы. — 2019.

14. Kruglik S., Rybin P., Frolov A. On the Secrecy Capacity of Distributed Storage with Locality and Availability // 2019 IEEE 90th Vehicular Technology Conference (VTC2019-Fall). — 2019. — P. 1-5.

15. Kruglik S., Nazirkhanova K., Frolov A. New Bounds and Generalizations of Locally Recoverable Codes With Availability // IEEE Transactions on Information Theory. — 2019. — Vol. 65, no. 7. — P. 4156-4166.

16. Kruglik S., Nazirkhanova K., Frolov A. On Distance Properties of (r,t,x)-LRC Codes // 2018 IEEE International Symposium on Information Theory (ISIT). — 2018. — P. 1336-1339.

17. Kruglik S., Nazirkhanova K., Frolov A. On the Maximal Code Length of Optimal Linear LRC Codes with Availability // 2018 Engineering and Telecommunication (EnT-MIPT). — 2018. — P. 54-57.

18. On one generalization of LRC codes with availability / S. Kruglik [et al.] // 2017 IEEE Information Theory Workshop (ITW). — 2017. — P. 26-30.

19. Kruglik S., Frolov A. Bounds and constructions of codes with all-symbol locality and availability // 2017 IEEE International Symposium on Information Theory (ISIT). — 2017. — P. 1023-1027.

20. On the Locality of Codeword Symbols / P. Goplan [et al.] // IEEE Transactions on Information Theory. — 2011. — Nov. — Vol. 58, no. 11. — P. 6925-6934.

21. Yekhanin S. Locally Decodable Codes // Found. Trends Theoretical Com-put. Sci. — 2012. — Vol. 6, no. 3. — P. 139-255.

22. Tamo I., Barg A. A Family of Optimal Locally Recoverable Codes // IEEE Transactions on Information Theory. — 2014. — Vol. 60, no. 8. — P. 46614676.

23. Optimal Locally Repairable and Secure Codes for Distributed Storage Systems / A. S. Rawat [et al.] // IEEE Transactions on Information Theory. —

2014. — Jan. — Vol. 60, no. 1. — P. 212-236.

24. Linear Locally Repairable Codes with Availability / P. Huang [et al.] // Proceedings IEEE International Symposium on Information Theory (ISIT). —

2015. — P. 1871-1875.

25. Tamo I., Barg A., Frolov A. Bounds on the Parameters of Locally Recoverable Codes // IEEE Transactions on Information Theory. — 2016. — June. — Vol. 62, no. 6. — P. 3070-3083.

26. Prakash N., Lalitha V., Kumar P. V. Codes with Locality for Two Erasures // Proceedings IEEE International Symposium on Information Theory (ISIT). — 2014. — P. 1962-1966.

27. Wang A., Zhang Z. Repair Locality With Multiple Erasure Tolerance // IEEE Transactions on Information Theory. — 2014. — Nov. — Vol. 60, no. 11. — P. 6979-6987.

28. Locality and Availability in Distributed Storage / A. S. Rawat [et al.] // Proceedings IEEE International Symposium on Information Theory (ISIT). — 2014. — P. 681-685.

29. Balaji S. B., Kumar P. V. Bounds on the rate and minimum distance of codes with availability // 2017 IEEE International Symposium on Information Theory (ISIT). — 2017. — P. 3155-3159.

30. Wei V. K. Generalized Hamming weights for linear codes // IEEE Transactions on Information Theory. — 1991. — Sept. — Vol. 37, no. 5. — P. 1412-1418.

31. Abdel-Ghaffar K. A. S., Weber J. H. Bounds for cooperative locality using generalized hamming weights // 2017 IEEE International Symposium on Information Theory (ISIT). — 2017. — P. 699-703.

32. On the Weight Hierarchy of Locally Repairable Codes / J. Hao [et al.] // 2017 IEEE Information Theory Workshop (ITW). — 2017. — P. 1-5.

33. Pless V., Huffman W. Handbook of Coding Theory. — Amsterdam : Elsevier, 1998.

34. Габидулин Э. Лекции по Алгебраическому Кодированию. — Москва : МФТИ, 2015.

35. Габидулин Э. М. Теория кодов с максимальным ранговым расстоянием // Проблемы Передачи Информации. — 1985. — т. 21, № 1. — с. 1—12.

36. Alan N. Eigenvalues and Expanders // Combinarorica. — 1986. — Vol. 6. — P. 83-96.

37. Chung F. Spectral Graph Theory. — New York : AMS, 1992.

38. Kahale N. On the Second Eigenvalue and Linear Expansion of Regular Graphs // Proc. IEEE Symp on Foundations of Computer Science. — 1992. — P. 296-303.

39. Burshtein D., Miller G. Expander Graph Arguments for Message-Passing Algorithms // IEEE Transactions on Information Theory. — 2001. — Vol. 47, no. 2. — P. 782-790.

40. Richardson T., Urbanke R. Modern Coding Theory. — U.K. : Cambridge Univ. Press, 2008.

41. Wang A., Zhang Z, Liu M. Achieving Arbitrary Locality and Availability in Binary Codes // Proceedings IEEE International Symposium on Information Theory (ISIT). — 2015. — P. 1866-1870.

42. Assmus E. F., Key J. D. Designs and Their Codes. — U.K. : Cambridge Univ. Press, 1992.

43. Diestel R. Graph Theory. — Germany : Springer-Verlag, 2005.

44. McKay B. D., Warmald N. C., Wysacka B. Short cycles in random regular graphs // Electron. J. Combinat. — 2004. — Vol. 11, no. 1. — P. 66.

45. On the Maximal Code Length of Optimal Linear Locally Repairable Codes / J. Hao [et al.] // 2018 IEEE International Symposium on Information Theory (ISIT). — 2018. — P. 1326-1330.

46. Faldumand A., Willems W. Codes of small defect // Design,Codes and Cryptography. — 1997. — No. 10. — P. 341-350.

47. Питерсон У. и Уэлдон Э. Коды, исправляющие ошибки. — Москва : Мир, 1976.

48. Ben-Haim Y., Litsyn S. Upper Bounds on the Rate of LDPC Codes as a Function of Minimum Distance // IEEE Transactions on Information Theory. — 2006. — May. — Vol. 52, no. 5. — P. 2092-2100.

49. Secure locally repairable codes for distributed storage systems / A. S. Rawat [et al.] // 2013 IEEE International Symposium on Information Theory. — 2013. — P. 2224-2228.

50. Agarwal A., Mazumdar A. Security in Locally Repairable Storage // IEEE Transactions on Information Theory. — 2016. — Vol. 62, no. 11. — P. 62046217.

51. Kadhe S., Sprintson A. Universally weakly secure coset coding schemes for minimum storage regenerating (MSR) codes // 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton). —

2017. — P. 25-30.

52. Shah N. B., Rashmi K. V., Kumar P. V. Information-Theoretically Secure Regenerating Codes for Distributed Storage // 2011 IEEE Global Telecommunications Conference - GLOBECOM 2011. — 2011. — P. 1-5.

53. Optimal Weakly Secure Minimum Storage Regenerating Codes Scheme / J. Bian [et al.] // IEEE Access. — 2019. — Vol. 7. — P. 151120-151130.

54. Kadhe S., Sprintson A. Security for minimum storage regenerating codes and locally repairable codes // 2017 IEEE International Symposium on Information Theory (ISIT). — 2017. — P. 1028-1032.

55. Information-Theoretically Secure Erasure Codes for Distributed Storage / K. V. Rashmi [et al.] // IEEE Transactions on Information Theory. —

2018. — Vol. 64, no. 3. — P. 1621-1646.

56. Cover T. M., Thomas J. A. Elements of Information Theory. — New Jersey : Wiley, 2006.

57. Network Coding for Distributed Storage Systems / A. G. Dimakis [et al.] // IEEE Transactions on Information Theory. — 2010. — Sept. — Vol. 56, no. 9. — P. 4539-4551.

58. A Survey on Network Codes for Distributed Storage / A. G. Dimakis [et al.] // Proceedings of the IEEE. — 2011. — Mar. — Vol. 99, no. 3. — P. 476-489.

59. Rashmi K. V., Shah N. B., Kumar P. V. Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction // IEEE Transactions on Information Theory. — 2011. — Vol. 57, no. 8. — P. 5227-5239.

60. Ye M., Barg A. Explicit Constructions of High-Rate MDS Array Codes With Optimal Repair Bandwidth // IEEE Transactions on Information Theory. — 2017. — Vol. 63, no. 4. — P. 2001-2014.

61. Pawar S., El Rauayheb S., Ramchandran K. On secure distributed data storage under repair dynamics // 2010 IEEE International Symposium on Information Theory. — 2010. — P. 2543-2547.

62. Габидулин Э., Пилипчук Н. Лекции по Теории Информации. — Москва : МФТИ, 2007.

63. Liu S., Oggier F. An Overview of Coding for Distributed Storage Systems // Signals and Communication Technology. — 2018. — P. 363-383.

64. Huang W., Bruck J. Secure RAID schemes from EVENODD and STAR codes // 2017 IEEE International Symposium on Information Theory (ISIT). — 2017. — P. 609-613.

65. Huang W. Coding for Security and Reliability in Distributed Systems : PhD thesis / Huang Wentao. — California Institute of Technology, 2017.

66. Huang W., Bruck J. Secure RAID schemes for distributed storage // 2016 IEEE International Symposium on Information Theory (ISIT). — 2016. — P. 1401-1405.

67. Криптографические методы защиты информации / Э. Габидулин [и др.]. — Москва : МФТИ, 2017.

68. McEliece R., Sarwate D. V. On Sharing Secrets and Reed-Solomon Codes // Commun. ACM. — New York, NY, USA, 1981. — Sept. — Vol. 24, no. 9. — P. 583-584.

69. Massey J. L. Minimal Codewords and Secret Sharing // Proceedings of the 6th Joint Swedish-Russian International Workshop on Information Theory. — 1993. — P. 276-279.

70. Блейкли Р., Кабатянский Г. Обобщенные идеальные схемы, разделяющие секрет, и матроиды // Проблемы передачи информации. — 1997. — т. 33, № 3. - с. 277-284.

71. Jackson W.-A., Martin K. M., O'Keefe C. M. Multisecret threshold schemes // Annual International Cryptology Conference. — Springer. 1993. — P. 126-135.

72. Jackson W.-A., Martin K. M., O'Keefe C. M. Ideal secret sharing schemes with multiple secrets // Journal of Cryptology. — 1996. — Vol. 9, no. 4. — P. 233-250.

73. An ideal multi-secret sharing scheme based on MSP / C.-F. Hsu [et al.] // Information Sciences. — 2011. — Vol. 181, no. 7. — P. 1403-1409.

74. Private information retrieval / B. Chor [et al.] // Proceedings of IEEE 36th Annual Foundations of Computer Science. — IEEE. 1995. — P. 41-50.

75. Pawar S., El Rouayheb S., Ramchandran K. Securing dynamic distributed storage systems against eavesdropping and adversarial attacks // IEEE Transactions on Information Theory. — 2011. — Vol. 57, no. 10. — P. 67346753.

76. Ye F., Shum K. W, Yeung R. W. The rate region of secure exact-repair regenerating codes for 5 nodes // 2016 IEEE International Symposium on Information Theory (ISIT). — IEEE. 2016. — P. 1406-1410.

77. Tandon R., Mohajer S. New bounds for distributed storage systems with secure repair // 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton). — IEEE. 2014. — P. 431-436.

78. Toward optimal secure distributed storage systems with exact repair / R. Tandon [et al.] // IEEE Transactions on Information Theory. — 2016. — Vol. 62, no. 6. — P. 3477-3492.

79. MacWilliams F. J., Sloane N. J. A. The theory of error correcting codes. — North-Holland Pub. Co., 1977. — P. 762.

80. Roth R. M. Introduction to Coding Theory. — Cambridge University Press, 2006. — P. 566.

81. On algebraic construction of Gallager and circulant low-density parity-check codes / Heng Tang [et al.] // IEEE Transactions on Information Theory. — 2004. — Vol. 50, no. 6. — P. 1269-1279.

82. Lin S., Kou Y, Fossorier M. P. C. Finite Geometry Low Density Parity-Check Codes: Construction, Structure, and Decoding // Codes, Graphs, and Systems: A Celebration of the Life and Career of G. David Forney, Jr. on the Occasion of his Sixtieth Birthday / ed. by R. E. Blahut, R. Koetter. — Boston, MA : Springer US, 2002. — P. 359-413.

83. New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities / R. McEliece [et al.] // IEEE Transactions on Information Theory. — 1977. — Mar. — Vol. 23, no. 2. — P. 157-166.