Interested Article - Проблема гроссмейстера

Проблема гроссмейстера ( англ. chess grandmaster problem ) — один из способов злоупотребления доказательством с нулевым разглашением . Также является одной из задач теории игр . Результатом данной проблемы является обман, выполненный мафией . Проблема заключается в том, что злоумышленник может доказать владение секретом, не обладая им на самом деле, или, другими словами, может имитировать то лицо, которому на самом деле принадлежит секрет.

Проблема

Примером данной проблемы является история девочки, которая продемонстрировала одновременную игру против двух гроссмейстеров. Её методика заключалась в следующем:

  • Алиса играет против двух гроссмейстеров, которые находятся в разных комнатах и не знают о присутствии друг друга.
  • Алиса записывает ходы одного гроссмейстера и дублирует их в игре с другим, затем записывает ходы второго и повторяет с первым, и так далее.

Таким образом это продолжается до того момента, пока она не проиграет одну партию, выигрывая вторую, или пока обе партии не закончатся вничью. Использование этого обмана позволяет обмануть любого шахматиста и выиграть благодаря не своим знаниям.

Данная методика обмана может использоваться против доказательства личности с нулевым разглашением .

Возможное решение

Возможное решение этой проблемы было предложено (англ. Thomas Beth ) ( 1949 2005 ) и . Для исключения возможности обмана, они предложили следующий алгоритм .

Гроссмейстеры хотят быть уверены в том, что подобного рода обман не произойдёт и противники будут играть используя только свои знания, без чужой помощи. Для этого все шахматисты будут следовать следующему протоколу:

  1. Перед началом игры шахматисты договариваются о каком-то конкретном значении времени , выраженном в секундах. Также они договариваются кто играет белыми, а кто — черными. Для удобства обозначим начинающего F (от слова first (первый)), а второго S (от слова second (второй)). Каждый игрок имеет свой секундомер.
  2. F начинает игру и устанавливает на своем секундомере время .
  3. S запускает секундомер и точно за время обдумывает и совершает ход. После хода он должен мгновенно установить на секундомере время .
  4. F отсчитывает на секундомере время . Если , то F прекращает игру и считает себя обманутым. Протокол завершается. Иначе, в случае победного хода от S , F признает себя поражённым и протокол завершается. Если же ход не победный, то F точно за время обдумывает и совершает ход. К этому моменту времени у F на секундомере будет время
  5. S отсчитывает на секундомере время . Если , то S прекращает играть, поскольку считает себя обманутым и протокол завершается. Иначе, в случае победного хода от F , S признает своё поражение и протокол завершается. Если же ход не победный, то S точно за время обдумывает и совершает ход. К этому моменту времени у S на часах будет время
  6. Перейти к пункту 4.

Теорема

Формулировка

Если маленькой девочке G нужно по крайней мере время на совершение перехода между «партией 1» и «партией 2», и F и S следуют протоколу, и количество ходов в игре больше двух ( ), тогда мошенничество девочки будет обнаружено F или S.

Иллюстрация к теореме

Доказательство
Обозначения F и S берём из предложенного решения. Маленькую девочку обозначим буквой G — от слова girl (девочка).

В случае присутствия девочки G, «партия 1» играется между F и G, а «партия 2» играется между G и S. Девочка копирует ходы как было описано ранее. Предположим, что в пункте 1 нашего протокола, в «партии 1», F и G договариваются о времени , а в «партии 2» G и S договариваются о времени ( и не обязательно равны).
F делает первый ход в момент времени 0 в «партии 1» и выставляет на секундомере время Для копирования и переноса этого хода в «партию 2», G нужно время Она совершает ход в момент времени и одновременно S обнуляет свой секундомер. Затем S делает свой ход в момент времени и выставляет на часах Для переноса этого хода в «партию 1», G нужно время Она совершает ход в «партии 1» в момент времени F проверяет часы и убеждается, что Теперь и
F, в случае , не обнаружит обман. Если же F обнаружил, то теорема доказана. Предположим, что:

F сделает ход в момент времени Для переноса этого хода в «партию 2», G нужно время Она совершает ход в момент времени S смотрит на часы и получает, что и То есть S проверяет, что В случае, что он не заметит обмана, должно выполняться равенство:

Однако комбинируя и мы получаем, что:

Но так как — это невозможно. Следовательно S обнаружит обман. Теорема доказана.

Замечания

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

Применение решения

Вероятностный канал перестроения (The Probabilistic Channel Hopping)

Проблема гроссмейстера и проблема обмана мафией лежат в основе работы Аммара Алкассара ( Ammar Alkassar ), Кристиана Стюбле ( Christian Stuble ) и Ахмада-Реза Садеги ( Ahmad-Reza Sadeghi ). Они представили вероятностный канал перестроения. Он основан на предположении, что злоумышленник не может эффективно ретранслировать все коммуникации параллельно. Основной идеей является использование системы перестраиваемых каналов (channel hopping system), благодаря которой злоумышленник не может прослушивать связь между участвующими сторонами. Данный подход также использует семантически безопасный ключ, разделенный между первой (проверяющей) и второй (доказывающей) сторонами. Это позволяет использование в беспроводных самоорганизующихся сетях [ уточнить ] .

Другие решения

См. также

Примечания

  1. , pp. 75.
  2. , , (англ.) // : A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings / C. Pomerance — Berlin: , 1987. — P. 21—39. — ( ; Vol. 293) — ISBN 978-3-540-18796-7 — ISSN ; —
  3. , с. 172.
  4. , с. 172—173.
  5. , с. 173.
  6. , , (англ.) // : Proceedings of the 2003 workshop on New security paradigms / , — New York City: ACM , 2003. — P. 77—85. — ISBN 978-1-58113-880-1
  7. , , (англ.) // : Proceedings of the 1997 IEEE Symposium on Security and Privacy — Washington, D.C.: IEEE Computer Society , 1997. — P. 65—71. — ISBN 978-0-8186-7828-8 — ISSN ; —
  8. , Brassard G. , , , (англ.) // / — Springer Science+Business Media , International Association for Cryptologic Research , 1991. — Vol. 4, Iss. 3. — P. 175—183. — ISSN ; —
  9. , с. 174.
  10. , Chaum D. (англ.) : Extended abstract // : Workshop on the Theory and Application of Cryptographic Techniques Lofthus, Norway, May 23–27, 1993 Proceedings / — 1 — Berlin: , 1994. — P. 344—359. — 465 p. — ISBN 978-3-540-57600-6

Литература

  • Шнайер Б. Глава 5. Часть 2. Идентификация с помощью доказательств с нулевым разглашением. Проблема гроссмейстера // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М. : Триумф, 2002. — С. 133—134. — 816 с. — 3000 экз. ISBN 5-89392-055-4 .
  • Conway J. H. (англ.) — New York City: 1976.
  • , (англ.) // : 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings / A. J. Menezes , S. A. Vanstone — Berlin, Heidelberg, New York City, London: , 1991. — P. 169—176. — ( ; Vol. 537) — ISBN 978-3-540-54508-8 — ISSN ; —


Источник —

Same as Проблема гроссмейстера