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

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

Проблема

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

• Алиса посылает вызов двум гроссмейстерам: Гарри Каспарову и Анатолию Карпову
• Игра происходит в одно и то же время, в одном и том же месте, но в разных комнатах
• Пусть Карпов делает ход, Алиса его записывает, затем идет в комнату к Каспарову и делает такой же ход на доске Каспарова. Аналогично Алиса записывает ответный ход Каспарова и повторяет его на доске Карпова и.т.д.

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

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

Возможное решение этой проблемы было предложено Томасом Бетом (T. Beth) и Иво Десмедтом (Y. Desmedt). Для исключения возможности обмана, они предложили следующий алгоритм.

• Шаг 1. До того, как оба гроссмейстера начнут играть, они договариваются об определенном значении t, где t — промежуток времени в секундах. Также они договариваются, кто первый ходит, первого обозначим F , а второго S. У каждого игрока есть секундомер.

• Шаг 2. F делает первый ход и устанавливает на своем секундомере время $z:=0$.

• Шаг 3. S запускает секундомер и точно за время t он должен обдумать и совершить ход. После этого у него на секундомере будет время $y:=t$.

• Шаг 4. F считывает со своего секундомера время e.

       If $e-z \ne t$
       then F прекращает играть, поскольку понимает, что его обманули. Протокол завершается.
        else if S выиграл
              then F прекращает играть и протокол завершается.
              else F точно за время t обдумывает и совершает ход, к 
                     этому   моменту с начала протокола пройдет ровно $e+t$ секунд,
                     следовательно на секундомере у F будет время $z:=e+t.$

• Шаг 5. S считывает со своего секундомера время f.

       If $f-y \ne t$
       then S прекращает играть, поскольку понимает, что его обманули. Протокол завершается.
        else if F выиграл
              then S прекращает играть и протокол завершается.
              else S точно за время t обдумывает и совершает ход, к 
                     этому   моменту с начала протокола пройдет ровно $f+t$ секунд,
                     следовательно на секундомере у S будет время $y:=f+t.$

• Шаг 6. перейти к шагу 4.

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

См. также

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

Литература

• Шнайер Б. Глава 5. Часть 2. Идентификация с помощью доказательств с нулевым разглашением. Проблема гроссмейстера // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 133—134. — 816 с. — 3000 экз. — ISBN 5-89392-055-4
• T. Beth, Y. Desmedt Identification Tokens - or: Solving the Chess Grandmaster Problem (англ.) // Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology. — London, UK: Springer-Verlag, 1990. — С. 169—177. — ISBN 3-540-54508-5.

Для улучшения этой статьи желательно?: Проставить интервики в рамках проекта Интервики. Викифицировать статью.