Проблема обедающих криптографов

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

Несмотря на слово «обедающий», проблема обедающих криптографов не имеет никакого отношения к проблеме обедающих философов.

Описание

Иллюстрация проблемы обедающих криптографов

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

На первом этапе каждые два криптографа определили общий секрет весом в один бит, договорившись бросать монету. Они спрятались за меню таким образом, что только два бросающих криптографа могут видеть результат подбрасывания. Предположим, после подбрасывания монеты криптографы A и B имеют общий секрет — $1$, криптографы А и С — $0$, В и С — $1$.

На втором этапе каждый криптограф публично объявляет бит, который вычисляется следующим образом:

• если он не платил за еду, то объявляется результат операции «Исключающее ИЛИ (XOR)» тех битов, которые он получил с двумя своими соседями;
• если он заплатил за еду, то объявляется результат, противоположный операции XOR.

Предположим, что ни один из криптографов не платил, тогда криптограф А объявит $1\,\oplus \,0\;=\;1$, В объявит $1\,\oplus \,1\;=\;0$, С — $0\,\oplus \,1\;=\;1$. С другой стороны, если криптограф А совершил оплату, то он объявит $\lnot {(1\,\oplus \,0)}\;=\;0$.

По завершении второго этапа выявляется истина. Один из криптографов выполняет операцию XOR всех заявленных бит. Если в результате получается $0$, то это означает, что никто из криптографов не платил (поэтому можно сделать вывод, что оплата была совершена NSA). В противном случае, если заплатил один из криптографов, то его личность остается неизвестной для всех других коллег.

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

Ограничения

В оригинальной работе Дэвида Чаума постулируется несколько ограничений, которые могут влиять на практическое использование протокола DC-сетей.

Коллизии

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

Нарушения

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

Сложность

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

Обобщения

DC-сети обобщаются для обеспечения передач, больших, чем размером в один бит для более чем трех участников, и для произвольных букв алфавита, отличных от двоичных 0 и 1.

Передача длинных сообщений

Для того, чтобы анонимный отправитель мог передать более одного бита информации за один раунд исполнения протокола DC-сети, группа криптографов может просто повторить протокол столько раз, сколько необходимо, чтобы создать нужное количество бит (исходя из пропускной способности канала). В DC-сетях пары участников имеют возможность заранее договориться об одном общем ключе, используя, например, ключ полученный с помощью протокола Диффи-Хеллмана. Затем каждый участник локально устанавливает этот общий ключ в генератор псевдослучайных чисел для того, чтобы произвести как можно больше общих «бросков монеты», что позволит анонимному отправителю передать несколько бит информации.

Бо́льшее количество участников

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

Граф разграничения общего доступа

Протокол может быть запущен с использованием неполного графа общих ключей, который может улучшить производительность и масштабируемость реализованных на практике DC-сетей. Однако, в случае использования неполного графа появляется риск того, что участники сговора могут разделить граф совместного доступа на отдельные компоненты связности и добиться нарушения анонимности. Например, для группы из более чем трёх участников привлекателен вариант с использованием кольцевой топологии, где каждый сидящий за столом криптограф имеет общий секретный ключ только с коллегами, сидящими непосредственно слева и справа от него. Такая топология привлекательна, так как каждый криптограф должен координировать два броска монеты за один раунд, а не $n$ бросков, как в случае с оригинальным полным графом ключей. Тем не менее, если бы агенты NSA Адам и Чарли, сидящие непосредственно слева и справа от простолюдина Боба, тайно вступили в сговор и раскрыли свои секретные ключи друг другу, то они могли бы с уверенностью определить, является ли Боб отправителем текущего бита-сообщения в рамках рассматриваемого раунда, независимо от общего количества участников. Такой эффект возникает по причине того, что сговорившиеся участники, Адам и Чарли, «раскололи» граф общего доступа на два независимых разрозненных компонента, один из которых состоит только из Боба, другой — из всех остальных честных участников.

Другая топология DC-сети общего доступа, используемая в системе Dissent для масштабирования, может быть описана как клиент-серверная топология. В этом варианте определено два типа участников, играющих разные роли: потенциально большое количество пользователей $n$, которые желают остаться анонимными, и гораздо меньшее число $m$ доверенных лиц, чья роль заключается в обеспечении анонимности всех пользователей. В такой топологии каждый из $n$ пользователей имеет общий секретный ключ с каждым из $m$ доверенных лиц, но пользователи не имеют общих секретных ключей друг с другом непосредственно, так же как и доверенные лица не имеют общих секретных ключей друг с другом — результатом является матрица взаимодействия $n*m$ . Если число доверенных лиц $m$ мало, то каждый пользователь должен владеть сведениями только о нескольких общих секретных ключах, что улучшает эффективность взаимодействия пользователей таким же образом, как это было осуществлено в кольцевой топологии. Тем не менее, до тех пор, пока хотя бы один участник из числа доверенных лиц ведет себя честно и не выдает свои секреты или не вступает в сговор с другими участниками, это честное доверенное лицо становится хабом, который соединяет всех честных пользователей в одну взаимодействующую со всеми своими частями компоненту, независимо от того, вступили ли другие пользователи или доверенные лица в нечестный сговор. Пользователям не нужно знать или угадывать, какие доверенные лица честны; их безопасность, по мнению авторов протокола, зависит только от существования по крайней мере одного честного, не участвующего в сговоре доверенного лица.

Альтернативные алфавиты и операторы

Хотя простой протокол DC-сети использует двоичный код в качестве алфавита передачи и оператор XOR для объединения шифротекстов, основной протокол вводит в употребление любой из алфавитов и использует операторы, аналогичные XOR, допустимые для использования в шифровании Вермана. Такая гибкость возникает естественно, поскольку секреты распределены между многими парами участников, которые, по факту, реализуют между собой шифрование Вермана в пределах одного раунда DC-сети.

Одним из альтернативных выборов алфавита DC-сети является использование конечной группы, подходящей для использования в криптографии с открытым ключом. Например, допустимо использовать группы Шнорра или эллиптические кривые. Такой выбор алфавита позволяет участникам использовать доказательство с нулевым разглашением для проверки производимого протоколом шифротекста. В частности проверяется, не нарушает ли один из участников протокол, причем при проверке соблюдается анонимность предусмотренная DC-сетью. Эта техника была впервые предложена Голлем и Джуэлсом и реализована в Verdict, имплементации Dissent.

Предотвращение и обработка коллизий

В оригинальной работе Чаума предлагается следующий метод обработки коллизий. Пользователь, занимающийся в данный момент отправкой сообщения в DC-сети, в каждом раунде своей передачи получает результирующий бит. Если результирующий бит не совпадает с тем, который он хочет передать в текущем раунде, пользователь делает вывод, что происходит коллизия. Он ждет случайное число раундов, и вновь пересылает своё сообщение. Конкретные параметры пересылки Чаум предлагает выбирать на основе анализа трафика в сети.

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

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

Противодействие нарушениям протокола

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

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

Литература

• David Chaum. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability (англ.) // Journal of Cryptology : журнал. — 1988. — Iss. 1. — P. 66—75. — doi:10.1007/BF00206326.
• David Isaac Wolinsky, Henry Corrigan-Gibbs, Bryan Ford, Aaron Johnson. Dissent in numbers: making strong anonymity scale (англ.) // OSDI'12 Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation. — USENIX Association Berkeley, CA, USA ©, 2012. — P. 179—192. — ISBN 978-1-931971-96-6.
• Philippe Golle, Ari Juels. Dining Cryptographers Revisited (англ.) // Advances in Cryptology - EUROCRYPT 2004. — 2004. — P. 456–473. — ISBN 978-3-540-24676-3.
• Henry Corrigan-Gibbs, David Isaac Wolinsky, and Bryan Ford. Proactively Accountable Anonymous Messaging in Verdict (англ.) // SEC'13 Proceedings of the 22nd USENIX conference on Security. — USENIX Association Berkeley, CA, USA, 2013. — P. 147–162. — ISBN 978-1-931971-03-4.
• Henry Corrigan-Gibbs, Bryan Ford. Dissent: Accountable Anonymous Group Messaging (англ.) // CCS '10 Proceedings of the 17th ACM conference on Computer and communications security. — ACM New York, NY, USA, 2010. — P. 340–350. — ISBN 978-1-4503-0245-6. — doi:10.1145/1866307.1866346. Архивировано 29 ноября 2012 года.
• Emin Gün Sirer, Sharad Goel, Mark Robson, Doğan Engin. Eluding Carnivores: File Sharing with Strong Anonymity (англ.) // EW 11 Proceedings of the 11th workshop on ACM SIGOPS European workshop. — ACM New York, NY, USA, 2004. — No. 19. — doi:10.1145/1133572.1133611.
• Nikita Borisov, George Danezis, Prateek Mittal, Parisa Tabri. Denial of service or denial of security? (англ.) // CCS '07 Proceedings of the 14th ACM conference on Computer and communications security. — ACM New York, NY, USA, 2004. — P. 92–102. — ISSN 978-1-59593-703-2. — doi:10.1145/1315245.1315258.
• Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. 2-е издание. — Триумф, 2002. — 816 с. — ISBN 978-5-89392-527-2.
• Feng Hao and Piotr Zielinski. A 2-Round Anonymous Veto Protocol (англ.) // Volume 5087 of the series Lecture Notes in Computer Science. — ACM New York, NY, USA, 2009. — P. 202-211. — ISBN 978-3-642-04904-0.
• Sharad Goel, Mark Robson, Milo Polte, Emin G¨un Sirer. Herbivore: A Scalable and Efficient Protocol for Anonymous Communication (англ.). — Cornell University, Ithaca NY 14850, USA, 2003.