13.05.2014

Вручение бита на хранение (bit commitment)

by Lazy Panda — Categories: КриптографияLeave a comment

- Ты помнишь, о чем я тебя просила?

- Нет.

- Ты обещал пропылесосить.

- Да? Что-то я такого не припомню…

- А я тебе говорю, что было такое!

Эта маленькая зарисовка является, пожалуй, самой нелепой иллюстрацией к алгоритму, которому посвящена эта запись. Но я уверен, что подобные ситуации случались с каждым в той или иной вариации. Целью семейства алгоритмов «вручение бита на хранение» является, как бы банально это не звучало, но именно вручение кому-то бита на хранение. Казалось бы, чего сложного – объяви адресату бит и пусть себе хранит? Но все становится не так просто, если мы хотим сохранить в тайне само значение бита. Более того, впоследствии мы хотим объявить значение бита и доказать, что именно данное значение мы отдали на хранение.

Вот такая вот хитрая цель. Давайте еще раз аккуратно сформулируем задачу:

У абонента Алиса есть некоторый бит b. Она желает передать его абоненту Боб, причем так, чтобы последний не знал его значения. В произвольный момент времени Алиса может объявить значение b и доказать, что Боб хранил именно его. Сам же Боб хочет сделать так, чтобы Алиса не могла изменить свой бит и обмануть его.

Возможно, у читателя уже появился вопрос – а зачем такие сложности? Вариантов использования данного протокола много – опубликование наследства, какого-нибудь предсказания (например, биржевые).

Вариант 1. Использование симметричной криптографии.

1)      Боб создает случайную последовательность битов, назовем ее Random. Он вручает эту строку Алисе.

2)      Алиса некоторым образом соединяет свой бит b с данной строкой, результат назовем RB. Кроме этого, она создает случайный ключ K и шифрует некоторым симметричным  алгоритмом – E(RB, K). Результат она отсылает Бобу.

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

3)      Алиса решает объявить значение b. Она сообщает Бобу значение К, и тот расшифровывает E(RB, K), получая RB. Тут он проверяет честность Алисы.

Может ли Алиса обмануть Боба? Получается что нет – пусть она решила изменить свое мнение и пытается выдать бит за значение b’. Снова соединяя бит с последовательностью Random, получает RB’. Теперь самая сложная часть – ей нужно подобрать такое значение K’, чтобы E(RB’, K’) = E(RB, K). Изменение ключа таким образом, чтобы инвертировался ровно один бит – тоже вычислительно сложная задача. Конечно, все эти рассуждения основаны на той надежде, что алгоритм E достаточно криптостоек.

Вариант 2. Использование однонаправленных функций.

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

1)      Алгоритм начинается с того, что Алиса создает две случайных последовательности бит Random1 и Random2.

2)      Алиса соединяет все, что есть в ее распоряжении в единую последовательность – Random1, Random2 и b – получая новую последовательность RRB.

3)      Далее она высчитывает значение хэш-функции H от RRB.

4)      На опубликовании H(RRB) и, например, Random1 задача Алисы по вручению бита завершена.

Поскольку Боб не знает Random2, то вычислить бит b для него является проблемой – даже если он найдет некоторую последовательность (BobRandom), которая даст тот же хэш, что и RRB, Боб все равно не может быть уверен в том, что это именно та последовательность, что и у Алисы.

5)      Для доказательства значения b, Алисе достаточно сообщить Random2. Боб повторяя ее действия и сравнивая результаты убеждается в истинности ее объявления.

Подменить свой бит Алиса не может, так как это означает, что ей нужно подобрать такую последовательность Random2’, что значение хэш-функции от RRB’ совпадет со значением хэш-функции от RRB. А ведь именно для защиты от таких вещей и используются хэш-функции, не так ли?

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

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

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

© 2019 [Panda Tower] All rights reserved - Powered by [WordPress] and [Wallow]