ref (664672), страница 51

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 51)

Секретные и общие ключи. В качестве секретного ключа p даны квадратные корни с по k чисел по модулю n, а именно , где . можно считать общими ключами p, но поскольку они могут быть вычислены из идентификатора p, их не нужно хранить. Чтобы избежать технических неудобств, мы предположим, что эти k чисел - квадратичные остатк по модулю n. Квадратные корни могут быть вычислены центром, который знает множители n.

Подписавание сообщений: первая попытка. Подпись p неявно доказывает, что подписывающий знает корни , то есть, может выдать число s такой, что . Такое число - , но посылка самого раскрыла бы секретный ключ; чтобы избежать раскрытия ключа, схема использует следующую идею. Процесс p выбирает произвольное число r и вычисляет . Теперь p - единственный процесс, который может выдать число y, удовлетворяющее , а именно, . Таким образом, p может показывать свое знание без их раскрытия, посылая пару (x, y), удовлетворяющую . Так как p не посылает число r, вычислить из этой пары не возможно без вычисления квадратного корня.

Но имеются две проблемы с подписями, состоящими из таких пар. Во-первых, любой может произвести такую пару, жульничая следующим образом: сначала выбрать y, и впоследствии вычислить . Во-вторых, подпись не зависит от сообщения, так что процесс, получивший подписанное сообщение от p, может скопировать подпись на любое поддельное сообщение. Трудный вопрос этой схемы подписи - сделать так, чтобы p показывал знание корня произведения из подмножества , где подмножество зависит от сообщения и произвольного числа. Шифрование сообщения и произвольного числа с помощью f не дает подделывающему сначала выбрать y. Чтобы подписать сообщение М, p действует следующим образом.

1. P выбирает произвольное число r и вычисляет .

2. P вычисляет f (М, x), назовем первые k бит с по .

3. P вычисляет .

Подпись состоит из кортежа ( ,..., , y).

Чтобы проверить подпись ( ,..., , y) процесса p для сообщения М, надо действовать следующим образом.

1. Вычислить и

2. Вычислить f (М, z) и проверить, что первые k бит - по .

Если подпись истинна, значение z, вычисленное на первом шаге проверки равняется значению x, используемому в подписывании и следовательно первые k бит f (М, z) равны ... .

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

1. Выбрать k произвольных бит ... .

2. Выбрать произвольное число y и вычислить

3. Вычислить f (М, x) и посмотреть, равняются ли первые k бит значениям ... , выбранным ранее. Если это так, то ( ,..., , y) - подделанная подпись для сообщения M.

Поскольку вероятность равенства в шаге (3) может быть принята , подделка становится успешной после ожидаемого числа испытаний.

При k = 72 и принятым временем секунд для опробования одного выбора , ожидаемое время подделки (с этой стратегией) - секунд или 1,5 миллиона лет, что делает схему вполне безопасной. Однако, каждый процесс должен хранить k корней, и если k должен быть ограничен из-за ограничений пространства, ожидаемое время подделки может быть неудовлетворительно. Мы покажем сейчас как изменить схему, чтобы использовать k корней, и получать ожидаемое время подделки для выбранного целого числа t. Идея состоит в том, чтобы использовать первые kt бит f-результата, чтобы определить t подмножеств от , и заставить p показывать свое знание t этих произведений. Чтобы подписать сообщение М, p действует следующим образом.

1. p выбирает произвольные ,..., и вычисляет .

2. p вычисляет f (М, , ..., ); назовем первые kt бит . ( и ).

3. p вычисляет для . Подпись состоит из ( , ..., , , ..., ).

Чтобы проверить подпись ( , ..., , , ..., ) процесса p для сообщения М, надо действуовать следующим образом.

1. Вычислить и .

2. Вычислить f (М, , ..., ), и проверить, что первые kt бит - , ..., .

Подделывающий, пытающийся произвести действительную подпись с той же самой стратегией, что приведена выше, теперь имеет вероятность успеха в третьем шаге , что означает ожидаемое число испытаний . Фиат и Шамир показывают в своей работе, что если разложение n на множители не оказывается простым, то существенно лучшего алгоритма подделки не существует, следовательно схему можно сделать произвольно безопасной, выбирая k и t достаточно большими.

14.2.6 Резюме и Обсуждение

В этом и предыдущем разделе было показано, что в синхронных системах существуют детерминированные решения для проблемы Византийского вещания. Максимальная способность восстановления таких решений - t < N/3, если не используется проверка подлинности (Раздел 14.1), и неограничена, если она используется (этот раздел). Во всех решениях, представленных здесь, синхронность была смоделирована с помощью (довольно сильных) предположений модели импульса; отказоустойчивая реализация модели импульса обсуждается в Разделе 14.3.

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

1. Обоснованность. Никакой корректный процесс не стреляет, если никакой процесс не инициировал.

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

3. Завершение. Если корректный процесс инициирует, то все корректные процессы стреляют в течение конечного числа импульсов.

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

Временная сложность и рано останавливающиеся протоколы. В этой главе мы представили протоколы, использующие t + 1 или 2t + 3 импульсов, или раундов связи. Фишером и Линчем [FL82] показано, что t + 1 раундов связи - оптимальное число для t-устойчивых протоколов согласия, и результат был расширен, чтобы охватить протоколы с установлением подлинности, Долевом и Стронгом [DS83].

Тонкий момент в этих доказательствах - то, что в использованных сценариях процесс должен отказывать в каждом из импульсов с 1 по t, поэтому нижние границы в худшем случае - число фактических сбоев в течение выполнения. Так как в большинстве выполнений фактическое число сбоев намного ниже способности восстановления, изучалось существование протоколов, которые могут достигать соглашения ранее в тех выполнении, которые имеют маленькое число сбоев. Протоколы вещания с таким свойством называются рано останавливающимися. Долев, Райсчук и Стронг [DRS82] продемонстрировали нижнюю границу в f + 2 раунда для любого протокола в выполнении с f сбоями. Обсуждение нескольких рано останавливающихся протоколов вещания и согласия есть в [BGP92].

Рано останавливающиеся протоколы принимают решение в течение нескольких импульсов после того, как корректные процессы заключают, что был импульс без новых сбоев. Однако, нельзя гарантировать, что все корректные процессы достигают этого заключения в одном и том же импульсе. (Если, конечно, они не достигают его в импульсе t + 1; так как самое большее t процессов отказывают, среди первых t + 1 имеется один раунд, в котором никакого нового сбоя не происходит.) Как следствие, рано останавливающиеся протоколы не удовлетворяет одновременности. Коун и Дворк показали [CD91], что, чтобы достигнуть одновременности, в выполнении, где никаких сбоев не происходит, необходимо также t + 1 раунд, даже для рандомизированных протоколов и в (очень слабый) модели аварий. Это означает, что протоколам с установлением подлинности также нужно t + 1 импульсов для одновременного соглашения.

Характеристики

Список файлов реферата