Проблема гроссмейстера (HjkQlybg ijkvvbywvmyjg)

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

Проблема

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

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

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

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

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

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

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

Перед началом игры шахматисты договариваются о каком-то конкретном значении времени $t$ , выраженном в секундах. Также они договариваются кто играет белыми, а кто — черными. Для удобства обозначим начинающего F (от слова first (первый)), а второго S (от слова second (второй)). Каждый игрок имеет свой секундомер.
F начинает игру и устанавливает на своем секундомере время $z:=0$ .
S запускает секундомер и точно за время $t$ обдумывает и совершает ход. После хода он должен мгновенно установить на секундомере время $y:=t$ .
F отсчитывает на секундомере время $e$ . Если $e-z\neq t$ , то F прекращает игру и считает себя обманутым. Протокол завершается. Иначе, в случае победного хода от S, F признает себя поражённым и протокол завершается. Если же ход не победный, то F точно за время $t$ обдумывает и совершает ход. К этому моменту времени у F на секундомере будет время $z:=e+t.$
S отсчитывает на секундомере время $f$ . Если $f-y\neq t$ , то S прекращает играть, поскольку считает себя обманутым и протокол завершается. Иначе, в случае победного хода от F, S признает своё поражение и протокол завершается. Если же ход не победный, то S точно за время $t$ обдумывает и совершает ход. К этому моменту времени у S на часах будет время $y:=f+t.$
Перейти к пункту 4.

Теорема

Формулировка:^[4]

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

Оригинальный текст (англ.)
If the little girt G needs at least Q time $l>0$ to communicate the moves between "game 1" and "game 2" and F and S follow the protocol, and the number of moves $m$ in the game is more than 2 (so $m\geq 3$ ), then the little girl's fraud is detected by F or S.

Доказательство^[4]
Обозначения F и S берём из предложенного решения. Маленькую девочку обозначим буквой G — от слова girl (девочка). В случае присутствия девочки G, «партия 1» играется между F и G, а «партия 2» играется между G и S. Девочка копирует ходы как было описано ранее. Предположим, что в пункте 1 нашего протокола, в «партии 1», F и G договариваются о времени $t_{1}$ , а в «партии 2» G и S договариваются о времени $t_{2}$ ( $t_{1}$ и $t_{2}$ не обязательно равны).
F делает первый ход в момент времени 0 в «партии 1» и выставляет на секундомере время $z:=0.$ Для копирования и переноса этого хода в «партию 2», G нужно время $l_{1}\geq l>0.$ Она совершает ход в момент времени $l_{1}$ и одновременно S обнуляет свой секундомер. Затем S делает свой ход в момент времени $t_{2}+l_{1}$ и выставляет на часах $y:=t_{2}.$ Для переноса этого хода в «партию 1», G нужно время $l_{2}\geq l>0.$ Она совершает ход в «партии 1» в момент времени $l_{1}+t_{2}+l_{2}.$ F проверяет часы и убеждается, что $e-z\neq t_{1}.$ Теперь $e=l_{1}+t_{2}+l_{2}$ и $z=0.$
F, в случае $t_{1}=l_{1}+t_{2}+l_{2}$ , не обнаружит обман. Если же F обнаружил, то теорема доказана. Предположим, что:

$t_{1}=l_{1}+t_{2}+l_{2}\quad (1)$

F сделает ход в момент времени $t_{1}+l_{1}+t_{2}+l_{2}.$ Для переноса этого хода в «партию 2», G нужно время $l_{3}\geq l>0.$ Она совершает ход в момент времени $l_{1}+t_{2}+l_{2}+t_{1}+l_{3}.$ S смотрит на часы и получает, что $f=t_{2}+l_{2}+t_{1}+l_{3}$ и $y:=t_{2}.$ То есть $f-y=l_{2}+t_{1}+l_{3}.$ S проверяет, что $f-y\neq t_{2}.$ В случае, что он не заметит обмана, должно выполняться равенство:

$t_{2}=l_{2}+t_{1}+l_{3}\quad (2)$

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

$l_{1}+2l_{2}+l_{3}=0$

Но так как $l_{1},l_{2},l_{3}>0$ — это невозможно. Следовательно S обнаружит обман. Теорема доказана.

Замечания

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

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

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

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

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

Идентификация в клетке Фарадея, предложенное Сэми Бенгио (Samy Bengio)^[8].
Система точного измерения, предложенная Иво Десмедтом и Томасом Бетом^[9].
Дистанционно-ограниченный протокол, предложенное Стефаном Бэндсом (Stefan Bands) и Дэвидом Чаумом (David Chaum)^[10].

См. также

Примечания

↑ ¹ ² Conway, 1976, pp. 75.
↑ Desmedt Y. G., Goutier C., Bengio S. Special Uses and Abuses of the Fiat-Shamir Passport Protocol (extended abstract) (англ.) // Advances in Cryptology — CRYPTO ’87: A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings / C. Pomerance — Berlin: Springer Berlin Heidelberg, 1987. — P. 21—39. — (Lecture Notes in Computer Science; Vol. 293) — ISBN 978-3-540-18796-7 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-48184-2_3
↑ Beth, Desmedt, 1991, с. 172.
↑ ¹ ² Beth, Desmedt, 1991, с. 172—173.
↑ Beth, Desmedt, 1991, с. 173.
↑ Alkassar A., Stüble C., Sadeghi A. Secure object identification: or: solving the Chess Grandmaster Problem (англ.) // NSPW'03: Proceedings of the 2003 workshop on New security paradigms / C. F. Hempelmann, V. Raskin — New York City: ACM, 2003. — P. 77—85. — ISBN 978-1-58113-880-1 — doi:10.1145/986655.986668
↑ Arbaugh W. A., Farber D. J., Smith J. M. A secure and reliable bootstrap architecture (англ.) // SP'97: 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 1081-6011; 2375-1207 — doi:10.1109/SECPRI.1997.601317
↑ Bengio S., Brassard G., Desmedt Y. G., Goutier C., Quisquater J. Secure implementation of identification systems (англ.) // Journal of Cryptology / I. Damgård — Springer Science+Business Media, International Association for Cryptologic Research, 1991. — Vol. 4, Iss. 3. — P. 175—183. — ISSN 0933-2790; 1432-1378 — doi:10.1007/BF00196726
↑ Beth, Desmedt, 1991, с. 174.
↑ Brands S. A., Chaum D. Distance-Bounding Protocols (англ.): Extended abstract // Advances in Cryptology — EUROCRYPT ’93: Workshop on the Theory and Application of Cryptographic Techniques Lofthus, Norway, May 23–27, 1993 Proceedings / T. Helleseth — 1 — Berlin: Springer Berlin Heidelberg, 1994. — P. 344—359. — 465 p. — ISBN 978-3-540-57600-6 — doi:10.1007/3-540-48285-7_30

Литература

Шнайер Б. Глава 5. Часть 2. Идентификация с помощью доказательств с нулевым разглашением. Проблема гроссмейстера // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 133—134. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
Conway J. H. On Numbers and Games (англ.) — New York City: 1976.
Beth T., Desmedt Y. G. Identification Tokens — or: Solving The Chess Grandmaster Problem (англ.) // Advances in Cryptology — CRYPTO ’90: 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: Springer Berlin Heidelberg, 1991. — P. 169—176. — (Lecture Notes in Computer Science; Vol. 537) — ISBN 978-3-540-54508-8 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-38424-3_12

[_cea76e4babd8cb7b-1] ¹ ² Conway, 1976, pp. 75.

[_59dd14f90f61a936-2] Desmedt Y. G., Goutier C., Bengio S. Special Uses and Abuses of the Fiat-Shamir Passport Protocol (extended abstract) (англ.) // Advances in Cryptology — CRYPTO ’87: A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings / C. Pomerance — Berlin: Springer Berlin Heidelberg, 1987. — P. 21—39. — (Lecture Notes in Computer Science; Vol. 293) — ISBN 978-3-540-18796-7 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-48184-2_3

[_a6a1aebc161fc804-3] Beth, Desmedt, 1991, с. 172.

[_4c2b08cb6ebdfa0d-4] ¹ ² Beth, Desmedt, 1991, с. 172—173.

[_a6a1aebc161fc805-5] Beth, Desmedt, 1991, с. 173.

[_ad345eb1b2904f1c-6] Alkassar A., Stüble C., Sadeghi A. Secure object identification: or: solving the Chess Grandmaster Problem (англ.) // NSPW'03: Proceedings of the 2003 workshop on New security paradigms / C. F. Hempelmann, V. Raskin — New York City: ACM, 2003. — P. 77—85. — ISBN 978-1-58113-880-1 — doi:10.1145/986655.986668

[_332793a4a741f93b-7] Arbaugh W. A., Farber D. J., Smith J. M. A secure and reliable bootstrap architecture (англ.) // SP'97: 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 1081-6011; 2375-1207 — doi:10.1109/SECPRI.1997.601317

[_21a4b165531ad036-8] Bengio S., Brassard G., Desmedt Y. G., Goutier C., Quisquater J. Secure implementation of identification systems (англ.) // Journal of Cryptology / I. Damgård — Springer Science+Business Media, International Association for Cryptologic Research, 1991. — Vol. 4, Iss. 3. — P. 175—183. — ISSN 0933-2790; 1432-1378 — doi:10.1007/BF00196726

[_a6a1aebc161fc802-9] Beth, Desmedt, 1991, с. 174.

[_73fe00419515e5a7-10] Brands S. A., Chaum D. Distance-Bounding Protocols (англ.): Extended abstract // Advances in Cryptology — EUROCRYPT ’93: Workshop on the Theory and Application of Cryptographic Techniques Lofthus, Norway, May 23–27, 1993 Proceedings / T. Helleseth — 1 — Berlin: Springer Berlin Heidelberg, 1994. — P. 344—359. — 465 p. — ISBN 978-3-540-57600-6 — doi:10.1007/3-540-48285-7_30

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]