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

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

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

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

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

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

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

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

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

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

Коллизии

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

Нарушения

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

Сложность

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

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

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

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

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

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

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

• 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.