Обман, выполненный мафией

Обман, выполненный мафией (The mafia fraud) — один из способов злоупотребления доказательством с нулевым разглашением. Такое название способ получил благодаря высказыванию Ади Шамира:

Я могу ходить в принадлежащий мафии магазин хоть миллион раз подряд, а они все ещё не смогут выдать себя за меня.

Оригинальный текст  (англ.)  

I can go to a Mafia-owned store a million successive times and they still will not be able to misrepresent themselves as me.

Но на самом деле подобное мошенничество возможно.

Описание

Пусть имеется 4 участника: A, B, C, D. Причем B и С сотрудничают между собой («принадлежат одной мафии»). А доказывает свою личность B, а С хочет выдать себя за A перед D. Обычно, мошенничество описывают следующей ситуацией: B владеет рестораном, принадлежащим мафии, С — также представитель мафии, D — ювелир. A и D не знают о предстоящем мошенничестве. В момент, когда A готов заплатить за обед и идентифицировать себя перед B, B извещает С о начале мошенничества. Это возможно, благодаря наличию радио-канала между ними. В это время, С выбирает бриллиант, который хочет купить, и D начинает идентифицировать личность С(а на самом деле A). С передает вопрос по протоколу B, а тот, в свою очередь, задает его А. Ответ передается в обратном порядке. Таким образом, А заплатит не только за обед, но и за дорогой бриллиант.

Как видно из вышеописанного, существуют определенные требования для подобного мошенничества. Например, моменты, когда А начинает доказывать свою личность перед B, а С — перед D должны быть точно синхронизированы.

Способы предотвращения

• Идентификация должна проходить в клетке Фарадея. Если в магазине ювелира будет клетка Фарадея, то мафиози не смогут обмениваться сообщениями.
• Иво Десмедт (Yvo Desmedt) и Томас Бет(Thomas Beth) предложили использовать точные часы. Если каждый этап протокола будет проходить за точный период времени, то Мафиози просто не успеют передавать сообщения друг другу. Стоит также учитывать, что сообщения между доказывающей и подтверждающей стороной передаются не мгновенно, а с некоторой задержкой. Эта задержка связана с тем, что скорость света не бесконечна, поэтому на передачу сообщений тратится время, равное $l/c$, где l-расстояние между сторонами, а с-скорость света.

См. также

• Проблема гроссмейстера
• Обман с несколькими личностями

Литература

• Y.Desmedt, C.Goutier, S.Bengio, «Special Uses and Abuses of the Fiat-Shamir Passport Protocol», Advances in Cryptology CRYPTO’87 Proceeding, Springer-Verlag, 1988, pp.21-39.
• T.Beth and Y.Desmedt, «Identification Tokens-or: Solving the Chess Grandmaster Problem», Advances in Cryptology CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 169—176.
• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4