Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Описание [ править ]

Обеденные криптографы проблема иллюстрации

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

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

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

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

Предположим, что ни один из криптографов не заплатил, тогда A объявляет , B объявляет , а C объявляет . С другой стороны, если A заплатила, она объявляет .

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

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

Ограничения [ править ]

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

Столкновение
Если два криптографа заплатили за обед, их сообщения будут отменять друг друга, и окончательный результат XOR будет . Это называется коллизией и позволяет только одному участнику передавать одновременно по этому протоколу. В более общем случае коллизия происходит, пока любое четное количество участников отправляет сообщения.
Нарушение
Любой злонамеренный криптограф, который не хочет, чтобы группа успешно взаимодействовала, может заблокировать протокол, так что конечный результат XOR станет бесполезным, просто отправив случайные биты вместо правильного результата XOR. Эта проблема возникает из-за того, что исходный протокол был разработан без использования какой-либо технологии открытого ключа и не имеет надежных механизмов для проверки того, честно ли участники следуют протоколу. [2]
Сложность
Протокол требует попарно общих секретных ключей между участниками, что может быть проблематичным, если участников много. Кроме того, хотя протокол DC-net является «безусловно безопасным», на самом деле он зависит от предположения, что «безусловно безопасные» каналы уже существуют между парами участников, чего нелегко достичь на практике.

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

История [ править ]

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

Обобщения [ править ]

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

Передача более длинных сообщений [ править ]

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

Группы большего размера [ править ]

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

Редкие графики обмена секретами [ править ]

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

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

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

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

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

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

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

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

Противодействие подрывным атакам [ править ]

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

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

Ссылки [ править ]

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