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

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

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

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

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

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

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

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

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

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

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

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

If the little girt G needs at least Q time ${\displaystyle l>0}$ to communicate the moves between "game 1" and "game 2" and F and S follow the protocol, and the number of moves ${\displaystyle m}$ in the game is more than 2 (so ${\displaystyle 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 договариваются о времени ${\displaystyle t_{1}}$, а в «партии 2» G и S договариваются о времени ${\displaystyle t_{2}}$ (${\displaystyle t_{1}}$ и ${\displaystyle t_{2}}$ не обязательно равны).
F делает первый ход в момент времени 0 в «партии 1» и выставляет на секундомере время ${\displaystyle z:=0.}$ Для копирования и переноса этого хода в «партию 2», G нужно время ${\displaystyle l_{1}\geq l>0.}$ Она совершает ход в момент времени ${\displaystyle l_{1}}$ и одновременно S обнуляет свой секундомер. Затем S делает свой ход в момент времени ${\displaystyle t_{2}+l_{1}}$ и выставляет на часах ${\displaystyle y:=t_{2}.}$ Для переноса этого хода в «партию 1», G нужно время ${\displaystyle l_{2}\geq l>0.}$ Она совершает ход в «партии 1» в момент времени ${\displaystyle l_{1}+t_{2}+l_{2}.}$ F проверяет часы и убеждается, что ${\displaystyle e-z\neq t_{1}.}$ Теперь ${\displaystyle e=l_{1}+t_{2}+l_{2}}$ и ${\displaystyle z=0.}$
F, в случае ${\displaystyle t_{1}=l_{1}+t_{2}+l_{2}}$, не обнаружит обман. Если же F обнаружил, то теорема доказана. Предположим, что:

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

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

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

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

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

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

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

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

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

• Обман с несколькими личностями
• Обман, выполненный мафией

• Шнайер Б. Глава 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