Общая полностью безопасная передача сообщений при помощи линейных кодов

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 13:37, 2 декабря 2015.
General Perfectly Secure Message Transmission Using Linear Codes
General Perfectly Secure Message Transmission Using Linear Codes.png
Авторы Qiushi Yang [@: 1][прим. 1],
Yvo Desmedt [@: 2][прим. 2].
Опубликован 2010 г.
Сайт Department of Computer Science, University College London, UK
Перевели Arseniy Kolobaev
Год перевода 2011-2015 г.
Скачать оригинал

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

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

Вступление

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

Первоначальное исследование Долева и др.[1] показывает, что ПБПС возможна при помощи применения протоколов безопасной передачи. Они предполагают присутствие порогового взломщика, который может контролировать до узлов, и поэтому до каналов. Экстенсивные исследования по пороговой модели с того времени также проводились (например, [2][3][4][5].

Есть много других исследований при более общей модели злоумышленника, которая позволяет ему контролировать узлы менее симметричным способом. Во многих случаях, использование порога для моделирования злоумышленника имеет мало смысла. В самом деле, конкретные платформы гораздо более уязвимы, чем другие. Кроме того, более иерархические структуры не могут быть описаны единственным злоумышленником. Общая модель злоумышленника предполагает, что он характеризуется злоумышленной структурой [6], которая состоит из ряда подгрупп узлов, и злоумышленник может контролировать один из этих подгрупп вместо любых узлов t.

Таблица 1. ПБПС в общей модели взломщика
Сетевые графы КС СП через 1 СП через
Кумар и др.[7]
ненаправленные
Десмет и и др.[8]
направленные-1
Янг-Десмет [9]
направленные-2
эксп. в
эксп. в
Наши результаты
ненаправленные
3 (Раздел 4.1)
2 (Раздел 4.2)
направленные-2
3 (Раздел 5.1)
2 (Раздел 5.2)


КС – круговая сложность, а СП – сложность передачи. "СП через 1" – это СП через протокол ПБПС, который передает одиночное сообщение, а "СП через – это СП протокола, который передает множественные сообщения , где каждое сообщение является элементом поля.

"направленные-1" – направленные графики без обратной связи, в"направленные- 2" - графики с обратной связью. h– длина кодового слова, а n– количество критических путей (см. Раздел 3).


Значительные исследования ПБПС, противостоящей злоумышленным структурам, были проведены Кумаром и др. [7] на двунаправленных каналах, и Десметом и др. [8] на односторонних прямых каналах, а также Патрой и др. [10] и Янгом и Десметом [9] на смешанных прямых и обратных каналах. Однако из-за общности злоумышленной структуры, протоколы в предыдущих исследованиях в большинстве случаев неэффективны касательно количества исполнения кругов[прим. 3] (круговая усложненность) и количества переданных элементов данных (сложность передачи). Также, некоторые предыдущие результаты должны быть охарактеризованы более глубоко. Эти вопросы мы опишем более детально в Разделе 3.

Наш вклад. В этой работе мы показываем, как линейные схемы разделения секретной информации (ЛСРСИ) и линейные коды можно использовать для создания эффективных протоколов ПБПС в общей модели злоумышленника. Прежде, чем мы это сделаем, мы покажем конструкцию ЛСРСИ и обсудим ее свойства (см. Раздел 2.1). Затем мы предложим новый обобщенный линейный код (см. Раздел 2.2) в целях исправления ошибок, а также определения псевдобазиса и псевдо-измерения (см. Раздел 2.3). Тут мы преследуем идею Куросавы и Сузуки [5]. Наше исследование по ЛСРСИ и линейным кодам показано в Разделе 2.

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

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

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

ЛСРСИ и линейные коды

Схемы секретного разделения информации являются ключевыми инструментами при исследовании ПБПС. При наличии набора участников ,экстенсивно исследованные схемы порога (, например, схема Шамира [11]) позволяют иметь любой поднабор участников, чтобы узнать секретное , но не разглашать информацию о любой подгруппе при максимуме участников. Общие непороговые схемы, которые реализуют разделение секретной информации между общими структурами доступа, также представлены в литературе (например, Ито и другие [12] и Бенало и Ляйхтер [13]). Структура монотонного доступа – семейство подгрупп ,при котором для любой группы , если и , то . Без потери общности мы предполагаем, что . Структура злоумышленника может быть определена, как . Поэтому для любой группы , если и , то . Было выяснено, что ЛСРСИ могут быть созданы для любых структур монотонного доступа, так что любая группа участников внутри могут узнать секретную информацию , но любая группа в не может. Далее мы покажем конструкцию и качества такой ЛСРСИ.

Конструирование ЛСРСИ

Всем известно, что монотонные интервальные программы эквивалентны ЛСРСИ [14] (также смотрите [15]).

TemplateDifinitionIcon.svg Определение «Определение 1.»
[14] Монотонная интервальная программа – это тройка , где - конечное поле, - это матрица - это сюръективная функция, которая предлагает несколько рядов в каждому участнику в .

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

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

TemplateDifinitionIcon.svg Определение «Определение 2.»
При наличии монотонной интервальной программы , секретная информация и случайный вектор . Мы рассматриваем ЛС : как функцию, при которой ( обозначает перемещение)

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

Предотвращение раскрытия секретности:

Перестраивание:

Очевидно, что если , то в линейной оболочке ряды , должен существовать целевой вектор [14]. Это делается для удовлетворения условиям перестраивания.

В отношении темпа передачи информации, размер разделителей секретной информации был изучен в литературе (напр., [16][17][18]). Тем не менее, насколько нам известно, не существует результатов касательно жесткой верхней границы для разделителей, которой в нашей ЛСРСИ является . На самом деле нам неизвестно существует ли для какой либо структуры доступа ЛСРСИ с размером полиноминальным в . Те не менее, мы можем иметь ЛСРСИ экспоненциального размера, которую мы называем, как указано далее худший вариант ЛСРСИ. Худший вариант ЛСРСИ определяется монотонной интервальной программой при которой а . таким образом экспонента в т.к. в общем . Эта конструкция, так или иначе, следует [19] (основано на [20]).

Худший вариант ЛСРСИ

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

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

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

End.

См. Доказательства предотвращения раскрытия секретности и параметры перестраивания для худшего варианта ЛСРСИ в полной версии этогй статьи. [21].

Линейные коды

Имеется ЛСРСИ определенная . Мы обозначаем как позицию , соответсвенно . Далее в статье, мы представляем что первые ряды – линейно независимы. Таким образом . Поистине, т.к. в ином случае и участники в могут восстановить все остальные разделители использую линейные комбинации. Это противоречит условиям предотвращения раскрытия секретности Определения 2.

TemplateDifinitionIcon.svg Определение «Определение 3.»
Линейный код определяется производящей матрицей в стандартной форме [22], где определяет матрицу тождественного преобразования и является матрицей.

Кодовые слова кода определяются зашифрованной функцией при котором задается -вектор ,

где - вектор, как кодовое слово , и обозначенный

Очевидно, что имеет кодовых слов.

Мы соединяем ЛСРСИ с линейным кодом, как описано далее. В этом разделе мы рассматриваем как матрицу, состоящую из первых рядов , таким образом позиция это . Мы создаем таким образом, что -колонка , которую мы называем , имеет следующий показатель: где - это -ряд . Это возможно потому, что позиция - это , следовательно rowi находится в линейной оболочке первого ряда Следовательно, группа является подгруппой линейного кода, так как для каждого , мы имеем

TemplateDifinitionIcon.svg Определение «Определение 4.»
Пусть - k-вектор, таким образом , где целевой вектор [прим. 4]. Пусть . Мы определяем зашифрованную функцию таким образом, что . Мы определяем выходную логическую функцию, , как информацию кодового слова .
TemplateTheoremIcon.svg Теорема Теорема 1.
Имеется любое кодовое слово . Можно закодировать информацию c с значений тогда, и только тогда, когда .
Доказательство

Пусть – k-вектор при котором информация - это . Отмечаем, что определяется , который извлекается из ЛСРСИ. Пусть -это при которой для каждого , j-колонка - это -колонка , тогда мы имеем

Где для каждого , ряд --ряд .

Сначала мы показываем, что если , то не может быть зашифровано при помощи Предположим обратное, например, может быть зашифровано при помощи Так как , возможность, что может быть зашифровано при помощи означает, что вектор-столбец в линейной оболочке столбцов . Соответственно, существует при котором так, что

Так как , при умножении на обе части уравнения , мы имеем

Это значит, что целевой вектор находится в линейной оболочке рядов относящихся к участникам , что недопустимо в нашей ЛСРСИ по требованиям предотвращения раскрытия секретности.

Далее, если , тогда прямо противоположно вышеуказанному доказательству и условиям перестраивания ЛСРСИ, мы можем доказать что r может быть зашифровано при помощи


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

  • Декодер может определить, что не является кодовым словом тогда, и только тогда, когда (т.е., ), где – группа всех участников, и
  • Декодер может распознать информацию из тогда, и только тогда, когда (т.е., ).

См. Доказательство этих результатов в полной версии работы [21].

Псевдобазис и псевдо-измерение

В Eurocrypt '08, Куросава и Сузуки предложили идею псевдобазиса и псевдо-измерения в пороговой модели с многократным включением кодовых слов. [5]. Генерализация псевдобазиса и псевдо-измерения возможна если (соответственно в пороговой модели), таким образом, мы предполагаем, что в этом разделе. Далее, мы допускаем, что : - обратная функция . Т.е., допустим, что , тогда отражает все локации в кодовом слове, относящиеся к участникам посредством .

TemplateDifinitionIcon.svg Определение «Определение 5.»
При , мы определяем как размер и как весовое значение разряда . Мы отмечаем, что
размер и весовое значение разряда

Очевидно, что и . Идея генерализации заключается в следующем. Шифратор посылает кодовых слов , а дешифратор получает h-векторов таким образом, что для каждого где - вектор ошибки. Для каждого , при – локатор ошибок, тогда имеет два следующих значения: (1) и (2) и следовательно . Мы допускаем, что например, ошибки во всех кодовых словах вызваны одним и тем же набором Теперь, мы предлагаем следующую конструкцию псевдобазиса.

Схема конструкции псевдобазиса.

Набор Для каждого , мы различаем два следующих случая:

  1. : если , тогда ничего не изменяем, в противном случае, добавляем в .
  2. В противном случае: пусть где , если существует при котором , тогда ничего не изменяем, в противном случае добавляем в

Пусть - псевдобазис. В таком случае - псевдо измерение. End.

Заведомо, псевдо-измерение в нашей схеме не более , т.к. есть по большей мере ненулевых элементов в каждом векторе ошибки. Таким образом, псевдобазис имеет полевых элементов.

TemplateLemmaIcon.svg Лемма «Лемма 1.»
Для любого кодового слова , при . Если и , тогда информация


Доказательство. Пусть . От и , мы можем иметь — . Согласно Теореме 1, информация может быть распознана со всеми элементами таким образом, что . Так как все элементы - 0'и, информация .

Возьмем кодовое слово и вектор , и представим что вектор ошибки при котором - . Если , тогда Согласно Лемме 1, информация является 0, таким образом информация равняется информации Т.е., вектор ошибки на самом деле не вызывает ошибок, и этот вектор ошибки является неверным. Очевидно, что вектор является неверным вектором ошибки.

Пусть - псевдобазис, в котором и – соответствующие локаторы ошибок. Мы отмечаем, что как оконечный локатор ошибок

TemplateTheoremIcon.svg Теорема Теорема 2.
Если известен оконечный локатор ошибок псевдобазиса, то дешифратор может распознать информацию всех кодовых слов.
Доказательство

При оконечном локаторе ошибок псевдобазиса , схема декодирования проста, как описано далее:

Схема декодирования из псевдобазиса

Для каждого , декодируется информация от таким образом, что , тогда j-значение не используется для декодирования.End.

Вполне понятно, что если , то декодированная информация верна. Поистине, и значит, что Таким образом, согласно теореме 1, значения не показанные могут быть использованы для декодирования Так как содержит все локализации ошибок , все значения, используемые для декодирования верны.

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


Предварительные значения ПБПС

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

  1. Ненаправленные графы – в которых все края не направлены, и позволяют двустороннюю связь;
  2. Направленный графы – в которых все края односторонние или биориентированные и позволяют смешанную связь.

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

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

  • НиС-ненаправленные: в ненаправленных графах, и -соединены [7];
  • НиС-нанаправленные 1: в направленных графах с цепью обратной связи, и - соединены [8];
  • НиС-направленные 2: в направленных графах с цепью обратной связи, и соединены с цепями обратной связи от к , и если и - разделены, тогда для любых трех наборов при которых разделяют и , не более чем один из этих трех наборов разделяет и на цепях обратной связи от к [10][9].

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

Критические пути

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

TemplateDifinitionIcon.svg Определение «Определение 6.»
Возьмем граф , в котором и <>mathR d \mathcal {A} ~\,\! </math> - соединены. Набор путей называется критическим, если и - соединены со всеми путями в , но - разделены со всеми путями Допуская, что – набор всех критических путей, мы определяем минимальный критический набор при котором и

Без потери общности, мы допускаем от противного, что не существует защищенного канала между и ; т.е.,

Наблюдение 1. При любом графе, в котором и - соединены, может быть настолько мал, как или настолько велик как экспонента в размер всего графа.

Мы даем два примера на Рис. 1. В примерах мы допускаем, что и - соединены. Сначала рассмотрим граф на Рис. 1(a), в котором только 3 канала между и Злоумышленная структура имеет следующую особенность: все узлы в любом наборе находятся на одном канале. Таким образом, очевидно, что в и - соединены, и все три канала находятся в

Теперь рассмотрим граф на Рис. 1(b). Мы допускаем, что кроме и , в узла. Мы можем видеть, что и соединены уровнями , где каждый уровень является набором из трех узлов, где между каждым узлом в и каждым узлом в есть грань.

Файл:AC 2010 OPBPSPPK.png
Рис. 1 соединения в различных графах.

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

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

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

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

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

Очевидно, что если и -связаны, то они -связаны с В дальнейшем в нашей работе, мы берем как рассматриваемую злоумышленную структуру. Таким образом, и участники злоумышленной структуры – критические пути в графе сети.

Улучшения предыдующих результатов

Далее в нашей статье, мы берем как число критических путей, а – злоумышленная структура с более чем путей.

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

Обобщенные результаты указаны в Таблице 1 в Разделе 1. Заметьте, что протокол Десмета и др. [8] в направленных графах без обратной связи, что значит, что получатель не может посылать сообщения отправителю Таким образом, протокол неинтерактивен и имеет лишь 1 круг. Этот протокол, на самом деле, является альтернативным использованием худшего варианта ЛСРСИ, показанного нами ранее. Таким образом, этот протокол может быть легко преобразован в 1-круговой протокол с СП Протокол Янга и Десмета [9] изпользует настройки в [10], что требует КС и СП быть экспонентами в Как мы уже обсуждали ранее, как так и n в основном полиноминальными в , так что наши улучшения очевидны. Мы также отмечаем, что в изучении общей модели злоумышленника, наши результаты первые, достигнувшие постоянной КС в ненаправленный и направленных-2 графах.

Другие предварительные значения

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

Если и -соединены с , в случае если посылает одно и то же сообщение по разным путям в , то имеет возможность получать сообщения точно и надежно [7]. В наших протоколах мы говорим " передает сообщение через " чтобы отобразить этот вид передачи. Таким образом, СП передачи одного полевого элемента -

Заметьте, что линейный создан рассматривать критические пути как участников. Когда посылает кодовое слово таким образом, что для каждого , если для некоторых , то посылает через , мы говорим « посылает через относительно » чтобы отобразить этот вид передачи. Таким образом, СП передачи одного кодового слова -

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

ПБПС в ненаправленных графах

В этом разделе мы продемонстрируем наши ПБПС протоколы в ненаправленных графах. Согласно НиС-ненаправленных, и должны быть - связаны в ненаправленном графе. Сначала мы предоставим 3-круговые протоколы в разделе 4.1 для передачи одиночных и множественных сообщений, а потом предоставим 2-круговые протоколы в разделе 4.2. Протоколы в этих разделах соответствуют результатам в [5].

3-круговые ненаправленные протоколы

Мы опускаем 3-круговые протоколы в этом разделе из-за недостатка места, а так же потому, что они относительно просты. Тем не менее, СП нашего 3-кругового протокола на одиночное сообщение , нашего 3-кругового протокола на множественные сообщения где Таким образом, СП обоих протоколов практически оптимальна относительно ПБПС в общей модели злоумышленника. Подробнее о 3-круговых ненаправленных протоколах см. в полной версии работы [21].

2-круговые ненаправленные протоколы

Сперва рассмотрим 2-круговые ненаправленные протоколы для передачи одиночных сообщений.

2-круговые ненаправленные протоколы для передачи одиночных сообщений

Круг 1 - к :

  1. выбирает случайных k-векторов , и для каждого шифрует для получения кодового слова
  2. Для каждого посылает вектор через путь , и посылает кодовое слово через относительно

Круг 2 - к :

  1. получает k-векторов и h-векторов от Для каждого , возьмем
  2. Для каждого шифрует для получения кодового слова затем создает набор при котором для каждого , если , тогда
  3. находит k-вектор при котором , и затем шифрует Для каждого , если , то высчитывает наконец задает
  4. передает и через

Фаза восстановления

  1. получает и от
  2. устанавливает Для каждого , если существует пара при которой , далее задает
  3. Для каждого , если , то высчитывает дешифрует как информацию таким образом, что для любого где , значение не используется для дешифрации. End.

Доказательство абсолютной секретности. Опущено. См. Полную версию работы [21].

СП протокола. Пусть СП(i) – СП круга для В этом протоколе:

СП(1)
СП(2)

Мы имеем общую СП полевых элементов.

Далее, перед тем как продемонстрировать 2-круговой ПБПС протокол, который передает множественные сообщения, мы применим широко известную в этом контексте технику: устройство произвольного съема информации [3][4][5]. Представим, что у злоумышленника нет никакой информации о из произвольных элементов Пусть - многочлен степени при котором для каждого то у злоумышленника нет никакой информации о для каждого Мы отмечаем функцию : устройство произвольного съема информации

Эта функция будет использована в следующем 2-круговом ПБПС протоколе.

2-круговой ненаправленный протокол для сообщений

Круг 1 - к :

  1. выбирает произвольных k-векторов и для каждого шифрует для получения кодового слова
  2. Для каждого посылает векторы через путь также посылает кодовые слова через относительно .

Круг 2 - к :

  1. получает k-векторов на каждом пути а также получает h-векторов от Для каждого пусть
  2. Для каждого использует схему создания псевдобазиса для создания псевдобазиса от Пусть – псевдо-измерение тогда
  3. Для каждого шифрует для получения кодового слова также создает набор в котором для каждого только если тогда
  4. Для каждого дешифрует также создает набор таким образом, что только в том случае если тогда использует устройство произвольного съема информации и для каждого высчитывает
  5. передает псевдобазис и Для каждого если тогда передает "ignore i"; иначе же, передает

Фаза восстановления

  1. находит оконечный локатор ошибок от
  2. Для каждого который получает на создает h-вектор таким образом, что для каждого если тогда тогда дешифрует информацию от таким образом, что для каждого не используется для дешифрации. помещает в набор
  3. использует устройство произвольного съема информации для получения и для каждого высчитывает

End.

Доказательство абсолютной секретности. Опущено. См. Полную версию работы [21].

СП протокола. В этом протоколе:

СП(1)
СП(2)

Мы имеем общую СП полевых элементов.

ПБПС в направленных графах

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

В прямом графе без обратной связи должен только отправить кодовое слово информация которого является сообщением к через относительно . Согласно НиС Направленных-1, и -связаны, может дешифровать информацию исправляя ошибки. Таким образом, протокол абсолютно безопасен и его СП - Мы отмечаем, что протокол Десмета и др. [8] на самом деле, является альтернативным использованием худшего варианта ЛСРСИ.

Теперь рассмотрим направленный граф с обратной связью Мы рассматриваем наши 3-круговые протоколы при условии НиС Связанных-2 в разделе 5.1. В разделе 5.2, мы показываем, что НиС Связанных-2 недостаточно для 2 круговых ПБПС протоколов, и поэтому задаем новое НиС условие, и рассматриваем наши протоколы относительно него. Протоколы в этих разделах соответствуют результатам в [23][24].

3-круговые направленные протоколы

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

3-круговой направленный протокол для передачи одиночных сообщений

Круг 1 - к :

  1. выбирает , ~\,\! </math> произвольных k-векторов и для каждого кодирует для получения кодового слова
  2. Для каждого посылает через относительно

Круг 2 - к :

  1. R получает wtA(u + 1) + 1 h-векторы x1,...,xwtA(u + 1) + 1 от W. R использует схему создания псевдобазиса (см. Раздел 2.3) для создания псевдобазиса B от x1,...,xwtA(u + 1) + 1, и затем передает B через все пути q1, . . . , qu ∈ Q.

Круг 3 - к :

  1. Для каждого пусть - псевдобазис который получает по пути и пусть - псевдо-измерение
  2. Для каждого если то передает "ignore v" через ; в ином случае находит оконечный локатор ошибок от Если то передает "ignore v" через ; в противном случае передает и через
  3. устанавливает и Для каждого при котором добавляет все актуальные кодовые слова отвечающие h-векторам в к Таким образом, наконец-таки Для каждого при котором если и то устанавливает Таким образом, наконец-таки, Для каждого дешифрует высчитывает и передает и через

Фаза восстановления

Пусть в то время как :

  1. если получает "ignore v" от , то устанавливает ;
  2. в случае если получает и от , то

(a) если то устанавливает ;

(b) в случае если с и схему декодирования из псевдобазиса (см. Раздел 2.3) для получения информации от для каждого далее восстанавливает , и закрывает протокол.

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

Доказательство абсолютной секретности. Опущено. См. Полную версию работы [21].

СП протокола. В этом протоколе:

СП(1)
СП(2)
СП(3)

Мы имеем общую СП полевых элементов.

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

3-круговой направленный протокол для сообщения

Круг 1 - к : делает то же самое только для произвольных k-векторов.

Круг 2 - к : делает то же самое.

Круг 3 - к : делает то же самое до 3 шага.

  1. устанавливает Для каждого при котором добавляет все актуальные кодовые слова соответствующие h-векторам в к Таким образом, наконец-таки,
  2. устанавливает Для каждого при котором для каждого если и то устанавливает Таким образом, наконец-таки, все одинаковые, и Есть по меньшей мере векторов при которых и [прим. 6] Если - таких векторов, то для каждого устанавливает Таким образом и все разные. Для каждого и дешифрует высчитывает и передает и через

Фаза восстановления

Для каждого делает то же самое для восстановления End.

Доказательство абсолютной секр