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

В криптографии задача обеденных криптографов изучает, как выполнить безопасное многостороннее вычисление логической функции XOR. Дэвид Чаум впервые предложил эту проблему в начале 1980-х годов и использовал ее в качестве наглядного примера, чтобы показать, что можно отправлять анонимные сообщения с безусловной неотслеживаемостью отправителя и получателя. Сети анонимной связи, основанные на этой проблеме, часто называют DC-сетями (где DC означает «обедающие криптографы»). ^[1]

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

Описание

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

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

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

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

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

Три публичных заявления вместе дают ответ на их вопрос. Просто вычисляется XOR трех объявленных битов. Если результат равен 0, это означает, что ни один из криптографов не заплатил (поэтому АНБ должно было оплатить счет). В противном случае один из криптографов заплатил, но его личность остается неизвестной другим криптографам.

Дэвид Чаум придумал для этого протокола термин «сеть столовых криптографов» или DC-net.

Ограничения

Протокол DC-net прост и элегантен. Однако у него есть несколько ограничений, некоторые решения которых были изучены в последующих исследованиях (см. раздел «Ссылки» ниже).

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

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

Сложность: Протокол требует попарного совместного использования секретных ключей между участниками, что может быть проблематичным, если участников много. Кроме того, хотя протокол DC-net является «безусловно безопасным», на самом деле он зависит от предположения, что между парами участников уже существуют «безусловно безопасные» каналы, чего на практике добиться непросто.

Соответствующий алгоритм анонимной сети вето вычисляет логическое ИЛИ для входных данных нескольких пользователей, а не логическое исключающее ИЛИ, как в DC-сетях, что может быть полезно в приложениях, для которых естественным образом подходит операция объединения логического ИЛИ.

История

Дэвид Чаум впервые задумался об этой проблеме в начале 1980-х годов. Его первая публикация, в которой излагаются основные идеи. ^[3] Журнальная версия появилась в самом первом номере Journal of Cryptology . ^[4]

Обобщения

Сети постоянного тока легко обобщаются, чтобы обеспечить передачу более одного бита за раунд, для групп размером более трех участников и для произвольных «алфавитов», отличных от двоичных цифр 0 и 1, как описано ниже.

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

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

Большие размеры групп

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

Редкие графики обмена секретами

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

Еще одна компромиссная топология DC-сети с разделением секретов, используемая в системе Dissent для масштабируемости. ^[5] может быть описана как топология клиент/сервер или пользователь/доверенное лицо . В этом варианте мы предполагаем, что есть два типа участников, играющих разные роли: потенциально большое количество n пользователей, желающих анонимности, и гораздо меньшее количество. $m$ , доверенных лиц роль которых заключается в том, чтобы помочь пользователям получить анонимность. В этой топологии каждый из $n$ пользователи делятся секретом с каждым из $m$ доверенные лица, но пользователи не делятся секретами напрямую с другими пользователями, а доверенные лица не делятся секретами напрямую с другими доверенными лицами, что приводит к $n\times m$ матрица обмена секретами. Если число доверенных лиц $m$ мала, то каждому пользователю необходимо управлять лишь несколькими общими секретами, что повышает эффективность пользователей так же, как это делает кольцевая топология. Однако до тех пор, пока хотя бы один доверенный человек ведет себя честно, не разглашает свои секреты и не вступает в сговор с другими участниками, этот честный доверенный человек образует «хаб», соединяющий всех честных пользователей в единый полностью связанный компонент, независимо от того, какой и каким образом. многие другие пользователи и/или доверенные лица могут вступать в нечестный сговор. Пользователям не нужно знать или догадываться, какой доверительный управляющий честен; их безопасность зависит только от существования хотя бы одного честного, не вступающего в сговор доверительного управляющего.

Альтернативные алфавиты и операторы объединения

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

Одним из полезных альтернативных вариантов алфавита DC-сетей и оператора объединения является использование в качестве алфавита конечной группы , подходящей для криптографии с открытым ключом, такой как группа Шнорра или эллиптическая кривая , и использование соответствующего группового оператора в качестве комбинирующего DC-сети. оператор. Такой выбор алфавита и оператора позволяет клиентам использовать методы доказательства с нулевым разглашением для доказательства свойств правильности шифртекстов DC-сети, которые они создают, например, что участник не «глушит» канал передачи, не ставя под угрозу анонимность, предлагаемая DC-net. Впервые этот метод был предложен Голле и Джуэлсом. ^[6] далее развитый Франком, ^[7] и позже реализован в Verdict , криптографически проверяемой реализации системы Dissent . ^[8]

Обработка или предотвращение столкновений

Мера, первоначально предложенная Дэвидом Чаумом для предотвращения коллизий, заключается в повторной передаче сообщения после обнаружения коллизии, но в документе не объясняется, как именно организовать повторную передачу.

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

Противодействие разрушительным атакам

Herbivore делит большую анонимную сеть на более мелкие группы DC-net, позволяя участникам избегать попыток нарушения, покидая нарушенную группу и присоединяясь к другой группе, пока участник не найдет группу, свободную от нарушителей. ^[10] Такой подход уклонения создает риск того, что злоумышленник, владеющий многими узлами, может выборочно нарушить работу только тех групп, которые противник не скомпрометировал полностью , тем самым «сгоняя» участников к группам, которые могут быть функциональными именно потому, что они полностью скомпрометированы. ^[11]

Dissent реализует несколько схем противодействия сбоям. Оригинальный протокол ^[9] использовал поддающееся проверке криптографическое перемешивание для формирования расписания передачи в сети постоянного тока и распределения «назначений передачи», позволяя проверять правильность последующих зашифрованных текстов в сети постоянного тока с помощью простой криптографической проверки хеш- функции. Однако этот метод требовал новой проверки перед каждым раундом сети постоянного тока, что приводило к высоким задержкам. Более поздняя, более эффективная схема позволяет проводить серию раундов DC-net без промежуточных перетасовок при отсутствии сбоев, но в ответ на событие сбоя использует перетасовку для распространения анонимных обвинений, позволяя жертве сбоя раскрыть и доказать личность преступник. ^[5] Наконец, более поздние версии поддерживают полностью проверяемые сети постоянного тока (со значительными затратами на эффективность вычислений из-за использования криптографии с открытым ключом в сети постоянного тока), а также гибридный режим, в котором используются эффективные сети постоянного тока на основе XOR. нормальный случай и проверяемые сети постоянного тока только в случае нарушения, чтобы распределить обвинения быстрее, чем это возможно с помощью проверяемых перетасовок. ^[8]

Ссылки

^ Чаум Д.Л. (1988). «Проблема обедающих криптографов: безусловная неотслеживаемость отправителя и получателя». Дж. Криптол . 1 (1): 65–75.
^ Рыцари и лжецы .
^ Дэвид Чаум (1985). «Безопасность без идентификации: системы транзакций сделают старшего брата устаревшим» (PDF) . Коммуникации АКМ . 28 (10): 1030–1044. CiteSeerX 10.1.1.319.3690 . дои : 10.1145/4372.4373 . S2CID 15340054 .
^ Дэвид Чаум (1988). «Проблема обедающих криптографов: безусловная неотслеживаемость отправителя и получателя» . Журнал криптологии . 1 (1): 65–75. CiteSeerX 10.1.1.127.4293 . дои : 10.1007/BF00206326 . S2CID 2664614 .
^ Перейти обратно: ^а ^б Дэвид Исаак Волински; Генри Корриган-Гиббс; Брайан Форд; Аарон Джонсон (8–10 октября 2012 г.). Несогласие в цифрах: создание сильной шкалы анонимности . 10-й симпозиум USENIX по проектированию и внедрению операционных систем (OSDI). Голливуд, Калифорния, США.
^ Филипп Голле; Ари Джулс (2–6 мая 2004 г.). Возвращение к обедающим криптографам (PDF) . Eurocrypt 2004. Интерлакен, Швейцария. ^{[ постоянная мертвая ссылка ]}
^ Франк, Кристиан (2008). Новые направления для обедающих криптографов (PDF) (магистерская диссертация).
^ Перейти обратно: ^а ^б Генри Корриган-Гиббс; Дэвид Исаак Волински; Брайан Форд (14–16 августа 2013 г.). Проактивная подотчетность анонимных сообщений в приговоре . 22-й симпозиум USENIX по безопасности. Вашингтон, округ Колумбия, США.
^ Перейти обратно: ^а ^б Генри Корриган-Гиббс; Брайан Форд (октябрь 2010 г.). Несогласие: Подотчетная групповая анонимность . 17-я конференция ACM по компьютерной и коммуникационной безопасности (CCS). Чикаго, Иллинойс, США. Архивировано из оригинала 29 ноября 2012 г. Проверено 9 сентября 2012 г.
^ Эмин Гюн Сирер; Шарад Гоэль; Марк Робсон; Доган Энгин (19–22 сентября 2004 г.). Ускользая от хищников: обмен файлами со строгой анонимностью (PDF) . Европейский семинар ACM SIGOPS. Левен, Бельгия.
^ Никита Борисов; Джордж Данезис; Пратик Миттал; Париса Тебриз (октябрь 2007 г.). Отказ в обслуживании или отказ в безопасности? Как атаки на надежность могут поставить под угрозу анонимность (PDF) . Конференция ACM по компьютерной и коммуникационной безопасности (CCS). Александрия, Вирджиния, США.

[1] Чаум Д.Л. (1988). «Проблема обедающих криптографов: безусловная неотслеживаемость отправителя и получателя». Дж. Криптол . 1 (1): 65–75.

[2] Рыцари и лжецы .

[3] Дэвид Чаум (1985). «Безопасность без идентификации: системы транзакций сделают старшего брата устаревшим» (PDF) . Коммуникации АКМ . 28 (10): 1030–1044. CiteSeerX 10.1.1.319.3690 . дои : 10.1145/4372.4373 . S2CID 15340054 .

[4] Дэвид Чаум (1988). «Проблема обедающих криптографов: безусловная неотслеживаемость отправителя и получателя» . Журнал криптологии . 1 (1): 65–75. CiteSeerX 10.1.1.127.4293 . дои : 10.1007/BF00206326 . S2CID 2664614 .

[WCFJ12-5] Перейти обратно: ^а ^б Дэвид Исаак Волински; Генри Корриган-Гиббс; Брайан Форд; Аарон Джонсон (8–10 октября 2012 г.). Несогласие в цифрах: создание сильной шкалы анонимности . 10-й симпозиум USENIX по проектированию и внедрению операционных систем (OSDI). Голливуд, Калифорния, США.

[GJ04-6] Филипп Голле; Ари Джулс (2–6 мая 2004 г.). Возвращение к обедающим криптографам (PDF) . Eurocrypt 2004. Интерлакен, Швейцария. ^{[ постоянная мертвая ссылка ]}

[7] Франк, Кристиан (2008). Новые направления для обедающих криптографов (PDF) (магистерская диссертация).

[CWF13-8] Перейти обратно: ^а ^б Генри Корриган-Гиббс; Дэвид Исаак Волински; Брайан Форд (14–16 августа 2013 г.). Проактивная подотчетность анонимных сообщений в приговоре . 22-й симпозиум USENIX по безопасности. Вашингтон, округ Колумбия, США.

[CF10-9] Перейти обратно: ^а ^б Генри Корриган-Гиббс; Брайан Форд (октябрь 2010 г.). Несогласие: Подотчетная групповая анонимность . 17-я конференция ACM по компьютерной и коммуникационной безопасности (CCS). Чикаго, Иллинойс, США. Архивировано из оригинала 29 ноября 2012 г. Проверено 9 сентября 2012 г.

[SGRE04-10] Эмин Гюн Сирер; Шарад Гоэль; Марк Робсон; Доган Энгин (19–22 сентября 2004 г.). Ускользая от хищников: обмен файлами со строгой анонимностью (PDF) . Европейский семинар ACM SIGOPS. Левен, Бельгия.

[BDMT07-11] Никита Борисов; Джордж Данезис; Пратик Миттал; Париса Тебриз (октябрь 2007 г.). Отказ в обслуживании или отказ в безопасности? Как атаки на надежность могут поставить под угрозу анонимность (PDF) . Конференция ACM по компьютерной и коммуникационной безопасности (CCS). Александрия, Вирджиния, США.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]