Быстрый поиск

Реферат: Распределенные алгоритмы

Доказательство. Завершение и одновременность доказываются, как в предыдущем протоколе, так как каждый корректный процесс принимает решение в конце импульса t + 1. Зависимость выводится так же, как в предыдущем протоколе. Если g правильно “выкрикивает” v в первом импульсе, все корректные процессы принимают v в этом импульсе, и никакое другое значение никогда не принимается; следовательно, все корректные процессы останавливаются на v. Заявленная сложность по сообщениям следует из факта, что каждый (корректный) процесс “выкрикивает” самое большее два сообщения.

Чтобы показать соглашение, мы покажем, что для корректных процессов p и q, и удовлетворяют в конце импульса t + 1 следующему.

(1) Если , то .

(2) Если , то .

Для (1): Предположим, что p принял значение v после получения сообщения <value, v>: g : : ... : в импульсе i, и рассуждаем как в доказательстве Теоремы 14.10:

Случай 1: Если q встречается среди g, , ..., , q точно принял v.

Случай 2: Если q не встречается среди g, , ..., , и , , то p пересылает значение процессу q, который примет его в этом случае.

Случай 3: Если q не встречается и i = t + 1, по крайней мере один из процессов, который подписал сообщение, допустим r, корректен. Процесс r также переслал значение v процессу q, что значит, что v находится в .

Для (2): Предположим, что в конце алгоритма, и пусть w - второе значение, принятое p. Снова подобным рассуждением можно показать, что , что означает, что . (Равенство и не может быть получено, так как процесс p не будет пересылать свое третье принятое значение или более поздние.)

Доказав (1) и (2), предположим, что корректный процесс p останавливается на , то есть . Затем, из (1), v содержится во всех для корректного q, но, следовательно, не шире одиночного элемента {v}; иначе - не одиночный элемент, из (2). Следовательно, каждый корректный процесс q также останавливается на v. Далее, предположим, что корректный процесс p останавливается на значении по умолчанию, так как - не одиночный элемент. Если пуст, каждый корректный q имеет пустой по (1) и если , то по (2); следовательно, q также останавливается на значении по умолчанию.

Долев и Стронг в дальнейшем улучшили алгоритм и получили алгоритм, который решает проблему Византийского-вещания за то же самое число импульсов и всего за О(Nt) сообщений.

14.2.2 Реализация Цифровых Подписей

Так как подпись p должна представлять собой достаточное доказательство того, что p - создатель сообщения, подпись должна состоять из некоторой формы информации, которая

(1) Может быть эффективно вычислена процессом p (подписана);

(2) Не может быть эффективно вычислена любым другим процессом, отличным от p (подделана).

Мы должны немедленно отметить, что, для большинства схем подписи, использующихся сегодня, второе требование не доказано до такой степени, что показана экспоненциальная трудность проблемы подделки. Обычно, проблема подделки, как показывают, связана (или иногда эквивалентна) с некоторой вычислительной проблемой, которая изучалась в течение длительного времени в отсутствие знания о ее полиномиальной разрешимости. Например, подделывание подписей в схеме Фиата-Шамира требует разлагать на множители большие целых числа; так как последняя задача (предположительно) в вычислительном отношении очень сложна, первая, должно быть, также сложна в вычислительном отношении.

Были предложены схемы подписи, основанные на различных, как предполагается, трудных проблемах, типа вычисления дискретного логарифма, разложения на множители больших чисел, проблемы рюкзака. Требования (1) и (2) подразумевают, что процесс p должен иметь вычислительное "преимущество" над другими процессами; это преимущество - некоторая секретная информация во владении p, секретный (или частный) ключ p. Таким образом, вычисление эффективно, когда секретный ключ известен, но (предположительно) трудно без этой информации. Ясно, что если p удается хранить свой ключ в тайне, то только p может с легкостью вычислять .

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

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

14.2.3 Схема Подписи ЭльГамаля

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

все различны и следовательно, перечисляют все элементы . Такое g называется генератором , или также ïåðâîîáðàçíûм êîðíем по модулю P. Генератор не уникален; обычно их много. Имея фиксированное P и генератор g, для каждого имеется уникальное целое число i по модулю P-1 такое, что (равенство в ). Это i называется дискретным логарифмом (иногда индексом) x. В отличие от вышеупомянутых базисных арифметических операций, вычислять дискретный логарифм не просто. Это - хорошо-изученная проблема, для которой до настоящего времени не найдено эффективное общее решение, но также не была доказана ее труднорешаемость; см. [0dl84] для краткого обзора результатов.

Схема подписи ЭльГамаля [EIG85] основана на трудности вычисления дискретных логарифмов. Процессы совместно используют большое простое число P и ïåðâîîáðàçíûй êîðень g из . Процесс p выбирает в качестве своего секретного ключа число d, случайно между 1 и P - 2, и общий ключ p - число ; заметьте, что d - дискретный логарифм e. Подпись p можно эффективно вычислить, зная логарифм e, и следовательно она формирует неявное доказательство того, что подписывающий знает d.