В криптографии проблема обедающих криптографов изучает, как выполнить безопасное многостороннее вычисление логической функции ИЛИ. Дэвид Чаум впервые предложил эту проблему в начале 1980-х годов и использовал ее в качестве наглядного примера, чтобы показать, что можно отправлять анонимные сообщения с безусловным отсутствием отслеживания отправителя и получателя. Анонимные сети связи, основанные на этой проблеме, часто называют DC-сетями (где DC означает «обедающие криптографы»). [1]
Несмотря на слово обедать , проблема обедающих криптографов не связана с проблемой обедающих философов .
Описание
Три криптографа собираются за столом на обед. Официант сообщает им, что еда была оплачена кем-то, кто может быть одним из криптографов или Агентством национальной безопасности (АНБ). Криптографы уважают право друг друга на анонимный платеж, но хотят выяснить, заплатило ли АНБ. Поэтому они решили выполнить двухэтапный протокол.
На первом этапе каждые два криптографа устанавливают общий однобитовый секрет, например, бросая монету за меню, так что только два криптографа видят результат по очереди для каждых двух криптографов. Предположим, например, что после подбрасывания монеты криптограф A и B разделяют секретный бит, A и C делятся , а B и C делят .
На втором этапе каждый криптограф публично объявляет бит, а именно:
- если они не заплатили за еду, исключающее ИЛИ (XOR) двух общих битов, которые они хранят со своими двумя соседями,
- если они действительно заплатили за еду, противоположность тому XOR.
Предположим, что ни один из криптографов не заплатил, тогда А объявляет , B объявляет , а C объявляет . С другой стороны, если A заплатила, она объявляет.
Три публичных объявления вместе дают ответ на их вопрос. Просто вычисляется XOR трех объявленных битов. Если результат равен 0, это означает, что ни один из криптографов не заплатил (поэтому АНБ должно было оплатить счет). В противном случае один из криптографов заплатил, но их личность осталась неизвестной другим криптографам.
Дэвид Чаум придумал для этого протокола термин « сеть обедающих криптографов» или DC-net.
Ограничения
Протокол DC-net прост и элегантен. Однако он имеет несколько ограничений, некоторые решения которых были изучены в ходе последующих исследований (см. Раздел «Ссылки» ниже).
- Столкновение
- Если два криптографа заплатили за обед, их сообщения будут отменять друг друга, и окончательный результат XOR будет . Это называется коллизией и позволяет только одному участнику передавать одновременно по этому протоколу. В более общем случае коллизия происходит, пока любое четное количество участников отправляет сообщения.
- Нарушение
- Любой злонамеренный криптограф, который не хочет, чтобы группа успешно взаимодействовала, может заблокировать протокол, так что конечный результат XOR станет бесполезным, просто отправив случайные биты вместо правильного результата XOR. Эта проблема возникает из-за того, что исходный протокол был разработан без использования какой-либо технологии открытого ключа и не имеет надежных механизмов для проверки того, честно ли участники следуют протоколу. [2]
- Сложность
- Протокол требует попарно общих секретных ключей между участниками, что может быть проблематичным, если участников много. Кроме того, хотя протокол DC-net является «безусловно безопасным», на самом деле он зависит от предположения, что «безусловно безопасные» каналы уже существуют между парами участников, чего нелегко достичь на практике.
Связанный с этим алгоритм анонимной сети вето вычисляет логическое ИЛИ входных данных нескольких пользователей, а не логическое ИЛИ, как в сетях постоянного тока, что может быть полезно в приложениях, для которых естественно подходит операция объединения логического ИЛИ.
История
Дэвид Чаум впервые задумался об этой проблеме в начале 1980-х годов. Его первая публикация, в которой излагаются основные идеи. [3] Журнальная версия появилась в самом первом выпуске Journal of Cryptology. [4]
Обобщения
DC-сети легко обобщаются, чтобы обеспечить передачу более одного бита за раунд для групп, состоящих из более чем трех участников, и для произвольных «алфавитов», отличных от двоичных цифр 0 и 1, как описано ниже.
Передача более длинных сообщений
Чтобы анонимный отправитель мог передавать более одного бита информации за цикл DC-сетей, группа криптографов может просто повторять протокол столько раз, сколько требуется, чтобы создать желаемое количество битов в полосе пропускания передачи. Эти повторы не нужно выполнять последовательно. В практических системах DC-net обычно пары участников заранее согласовывают единый общий «главный» секрет, например, используя обмен ключами Диффи – Хеллмана . Затем каждый участник локально передает этот общий главный секрет в генератор псевдослучайных чисел , чтобы произвести столько общих «подбрасываний монеты», сколько необходимо, чтобы анонимный отправитель мог передавать несколько битов информации.
Большие группы
Протокол можно обобщить на группу участники, каждый из которых имеет общий секретный ключ, общий с другим участником. В каждом раунде протокола, если участник хочет передать группе не отслеживаемое сообщение, он инвертирует свой публично объявленный бит. Участники могут быть визуализированы как полностью связанный граф с вершинами, представляющими участников, и ребрами, представляющими их общие секретные ключи.
Редкие графики обмена секретами
Протокол может работать с неполностью подключенными графами совместного использования секрета, что может улучшить производительность и масштабируемость практических реализаций DC-сети с потенциальным риском снижения анонимности, если сговорившиеся участники могут разделить граф совместного использования секрета на отдельные подключенные компоненты. Например, интуитивно привлекательное, но менее безопасное обобщение научастники используют кольцевую топологию , где каждый криптограф, сидящий за столом, делится секретом только с криптографом слева и справа от них, а не со всеми остальными криптографами. Такая топология привлекательна, потому что каждому криптографу необходимо координировать два подбрасывания монеты за раунд, а не. Однако, если Адам и Чарли на самом деле агенты АНБ, сидящие сразу слева и справа от Боба, невинной жертвы, и если Адам и Чарли тайно вступают в сговор, чтобы раскрыть друг другу свои секреты, то они могут с уверенностью определить, был ли Боб отправитель 1 бита в цепочке DC-net, независимо от общего количества участников. Это связано с тем, что сговорившиеся участники Адам и Чарли эффективно «разделили» граф совместного использования секрета на два отдельных несвязанных компонента, один из которых содержит только Боба, а другой - всех остальных честных участников.
Другая компромиссная топология совместного использования секрета DC-net, используемая в системе Dissent для масштабируемости [5], может быть описана как топология клиент / сервер или пользователь / доверенное лицо . В этом варианте мы предполагаем, что есть два типа участников, играющих разные роли: потенциально большое количество n пользователей, желающих анонимности, и гораздо меньшее количество.из доверенных лиц , чья роль заключается в оказании помощи пользователям получить эту анонимность. В этой топологии каждый из пользователи делятся секретом с каждым из попечители - но пользователи не делятся секретами напрямую с другими пользователями, а опекуны не делятся секретами напрямую с другими опекунами, что приводит к матрица секретного обмена. Если количество попечителеймала, то каждому пользователю нужно управлять только несколькими общими секретами, повышая эффективность пользователей так же, как и кольцевая топология. Однако до тех пор, пока хотя бы один опекун ведет себя честно и не раскрывает свои секреты и не вступает в сговор с другими участниками, этот честный опекун формирует «хаб», объединяющий всех честных пользователей в единый полностью связанный компонент, независимо от того, какой и как многие другие пользователи и / или доверенные лица могут вступать в нечестный сговор. Пользователям не нужно знать или догадываться, какой доверительный управляющий честный; их безопасность зависит только от наличия хотя бы одного честного доверенного лица, не вступающего в сговор.
Альтернативные алфавиты и объединяющие операторы
Хотя простой протокол DC-nets использует двоичные цифры в качестве алфавита передачи и использует оператор XOR для комбинирования зашифрованных текстов, основной протокол обобщается для любого алфавита и комбинирующего оператора, подходящего для шифрования одноразового блокнота . Эта гибкость естественным образом проистекает из того факта, что секреты, разделяемые многими парами участников, по сути, представляют собой просто одноразовые планшеты, симметрично объединенные вместе в рамках одного раунда DC-сети.
Одним из полезных альтернативных вариантов выбора алфавита DC-сетей и оператора комбинирования является использование в качестве алфавита конечной группы, подходящей для криптографии с открытым ключом, такой как группа Шнорра или эллиптическая кривая, и использование связанного группового оператора в качестве комбинирующей DC-сети. оператор. Такой выбор алфавита и оператора позволяет клиентам использовать методы доказательства с нулевым разглашением , чтобы доказать свойства правильности генерируемых ими шифротекстов DC-сети, например, что участник не «заглушает» канал передачи, не ставя под угрозу анонимность, предлагаемая DC-net. Этот метод был впервые предложен Голлем и Джулсом [6], затем развит Франком [7] и позже реализован в Verdict , криптографически проверяемой реализации системы Dissent . [8]
Обработка или предотвращение столкновений
Мера, первоначально предложенная Дэвидом Чаумом для предотвращения коллизий, заключается в повторной передаче сообщения после обнаружения коллизии, но в документе не объясняется, как именно организовать повторную передачу.
Несогласие позволяет избежать возможности непреднамеренных конфликтов за счет использования проверяемого тасования для установления расписания передачи DC-сетей, так что каждый участник точно знает, какие биты в расписании соответствуют его собственному слоту передачи, но не знает, кто владеет другими слотами передачи. [9]
Противодействие разрушающим атакам
Herbivore разделяет большую анонимную сеть на более мелкие группы DC-net, позволяя участникам избегать попыток разрушения, покидая прерванную группу и присоединяясь к другой группе, до тех пор, пока участник не найдет группу, свободную от разрушителей. [10] Такой подход уклонения представляет риск того, что противник, владеющий множеством узлов, может выборочно разрушить только те группы, которые противник не полностью скомпрометировал, тем самым «загоняя» участников в группы, которые могут быть функциональными именно потому, что они полностью скомпрометированы. [11]
Несогласие реализует несколько схем противодействия сбоям. Исходный протокол [9] использовал проверяемое криптографическое перемешивание для формирования расписания передачи DC-сети и распределения «назначений передачи», позволяя проверять правильность последующих шифровальных текстов DC-сетей с помощью простой криптографической хеш- проверки. Однако этот метод требовал новой проверки перед каждым раундом DC-сетей, что приводило к большим задержкам. Более поздняя, более эффективная схема позволяет продолжить серию раундов DC-сети без прерывания перетасовки в отсутствие нарушения, но в ответ на событие нарушения используется перетасовка для распространения анонимных обвинений, позволяя жертве нарушения разоблачить и доказать личность преступник. [5] Наконец, более поздние версии поддерживают полностью проверяемые DC-сети - при значительных затратах на эффективность вычислений из-за использования криптографии с открытым ключом в DC-сети - а также гибридный режим, который использует эффективные DC-сети на основе XOR. сети в нормальном случае и проверяемые сети постоянного тока только при нарушении, чтобы распространять обвинения быстрее, чем это возможно при использовании проверяемых перетасовок. [8]
Рекомендации
- ^ Чаум DL (1988). «Проблема обедающих криптографов: безусловная неотслеживаемость отправителя и получателя». J Cryptol . 1 (1): 65–75.
- ↑ Knights and Knaves .
- ^ Дэвид Чаум (1985). «Безопасность без идентификации: системы транзакций, которые сделают старшего брата устаревшим» (PDF) . Коммуникации ACM . 28 (10): 1030–1044. CiteSeerX 10.1.1.319.3690 . DOI : 10.1145 / 4372.4373 . S2CID 15340054 .
- ^ Дэвид Чаум (1988). «Проблема обедающих криптографов: безусловная неотслеживаемость отправителя и получателя» . Журнал криптологии . 1 (1): 65–75. CiteSeerX 10.1.1.127.4293 . DOI : 10.1007 / BF00206326 . S2CID 2664614 .
- ^ а б Дэвид Исаак Волински; Генри Корриган-Гиббс; Брайан Форд; Аарон Джонсон (8–10 октября 2012 г.). Несогласие в цифрах: сильная шкала анонимности . 10-й симпозиум USENIX по проектированию и внедрению операционных систем (OSDI). Голливуд, Калифорния, США.
- ^ Филипп Голле; Ари Джуэлс (2–6 мая 2004 г.). Возвращение к ресторанным криптографам (PDF) . Eurocrypt 2004. Интерлакен, Швейцария.
- ^ Франк, Кристиан (2008). Новые направления для обедающих криптографов (PDF) (диплом магистра).
- ^ а б Генри Корриган-Гиббс; Дэвид Исаак Волински; Брайан Форд (14–16 августа 2013 г.). Упреждающий анонимный обмен сообщениями в Verdict . 22-й симпозиум по безопасности USENIX. Вашингтон, округ Колумбия, США.
- ^ а б Генри Корриган-Гиббс; Брайан Форд (октябрь 2010 г.). Несогласие: анонимность подотчетной группы . 17-я конференция ACM по компьютерной и коммуникационной безопасности (CCS). Чикаго, Иллинойс, США. Архивировано из оригинала на 2012-11-29 . Проверено 9 сентября 2012 .
- ^ Эмин Гюн Сирер; Шарад Гоэль; Марк Робсон; Доган Энгин (19–22 сентября 2004 г.). Ускользая от хищников: обмен файлами с полной анонимностью (PDF) . ACM SIGOPS Европейский семинар. Лёвен, Бельгия.
- ^ Никита Борисов; Джордж Данезис; Пратик Миттал; Париса Тебриз (октябрь 2007 г.). Отказ в обслуживании или отказ в безопасности? Как атаки на надежность могут нарушить анонимность (PDF) . Конференция ACM по компьютерной и коммуникационной безопасности (CCS). Александрия, Вирджиния, США.