Русская Википедия:Проблема гроссмейстера
Проблема гроссмейстера (Шаблон:Lang-en) — один из способов злоупотребления доказательством с нулевым разглашением. Также является одной из задач теории игр.Шаблон:Sfn Результатом данной проблемы является обман, выполненный мафией. Проблема заключается в том, что злоумышленник может доказать владение секретом, не обладая им на самом деле, или, другими словами, может имитировать то лицо, которому на самом деле принадлежит секрет.
Проблема
Примером данной проблемы является история девочки, которая продемонстрировалаШаблон:Sfn одновременную игру против двух гроссмейстеров. Её методика заключалась в следующем:
- Алиса играет против двух гроссмейстеров, которые находятся в разных комнатах и не знают о присутствии друг друга.
- Алиса записывает ходы одного гроссмейстера и дублирует их в игре с другим, затем записывает ходы второго и повторяет с первым, и так далее.
Таким образом это продолжается до того момента, пока она не проиграет одну партию, выигрывая вторую, или пока обе партии не закончатся вничью. Использование этого обмана позволяет обмануть любого шахматиста и выиграть благодаря не своим знаниям.
Данная методика обмана может использоваться против доказательства личности с нулевым разглашением.Шаблон:Source-ref
Возможное решение
Возможное решение этой проблемы было предложено Томасом Бетом (англ. Thomas Beth) (1949—2005) и Шаблон:Iw. Для исключения возможности обмана, они предложили следующий алгоритм.Шаблон:Sfn
Гроссмейстеры хотят быть уверены в том, что подобного рода обман не произойдёт и противники будут играть используя только свои знания, без чужой помощи. Для этого все шахматисты будут следовать следующему протоколу:
- Перед началом игры шахматисты договариваются о каком-то конкретном значении времени <math>t</math>, выраженном в секундах. Также они договариваются кто играет белыми, а кто — черными. Для удобства обозначим начинающего F (от слова first (первый)), а второго S (от слова second (второй)). Каждый игрок имеет свой секундомер.
- F начинает игру и устанавливает на своем секундомере время <math>z:=0</math>.
- S запускает секундомер и точно за время <math>t</math> обдумывает и совершает ход. После хода он должен мгновенно установить на секундомере время <math>y:=t</math>.
- F отсчитывает на секундомере время <math>e</math>. Если <math>e-z \ne t</math>, то F прекращает игру и считает себя обманутым. Протокол завершается. Иначе, в случае победного хода от S, F признает себя поражённым и протокол завершается. Если же ход не победный, то F точно за время <math>t</math> обдумывает и совершает ход. К этому моменту времени у F на секундомере будет время <math>z:=e+t.</math>
- S отсчитывает на секундомере время <math>f</math>. Если <math>f-y \ne t</math>, то S прекращает играть, поскольку считает себя обманутым и протокол завершается. Иначе, в случае победного хода от F, S признает своё поражение и протокол завершается. Если же ход не победный, то S точно за время <math>t</math> обдумывает и совершает ход. К этому моменту времени у S на часах будет время <math>y:=f+t.</math>
- Перейти к пункту 4.
Теорема
ФормулировкаШаблон:Sfn Шаблон:Начало цитаты Если маленькой девочке G нужно по крайней мере время <math>l>0</math> на совершение перехода между «партией 1» и «партией 2», и F и S следуют протоколу, и количество ходов <math>m</math> в игре больше двух (<math>m\ge3</math>), тогда мошенничество девочки будет обнаружено F или S. Шаблон:Oq Шаблон:Конец цитаты
ДоказательствоШаблон:Sfn
Обозначения F и S берём из предложенного решения. Маленькую девочку обозначим буквой G — от слова girl (девочка).
В случае присутствия девочки G, «партия 1» играется между F и G, а «партия 2» играется между G и S. Девочка копирует ходы как было описано ранее. Предположим, что в пункте 1 нашего протокола, в «партии 1», F и G договариваются о времени <math>t_1</math>, а в «партии 2» G и S договариваются о времени <math>t_2</math> (<math>t_1</math> и <math>t_2</math> не обязательно равны).
F делает первый ход в момент времени 0 в «партии 1» и выставляет на секундомере время <math>z:=0.</math> Для копирования и переноса этого хода в «партию 2», G нужно время <math>l_1\ge l>0.</math> Она совершает ход в момент времени <math>l_1</math> и одновременно S обнуляет свой секундомер. Затем S делает свой ход в момент времени <math>t_2+l_1</math> и выставляет на часах <math>y:=t_2.</math> Для переноса этого хода в «партию 1», G нужно время <math>l_2\ge l>0.</math> Она совершает ход в «партии 1» в момент времени <math>l_1+t_2+l_2.</math> F проверяет часы и убеждается, что <math>e-z\ne t_1.</math> Теперь <math>e=l_1+t_2+l_2</math> и <math>z=0.</math>
F, в случае <math>t_1=l_1+t_2+l_2</math>, не обнаружит обман. Если же F обнаружил, то теорема доказана. Предположим, что:
<math>t_1=l_1+t_2+l_2 \quad (1)</math>
F сделает ход в момент времени <math>t_1+l_1+t_2+l_2.</math> Для переноса этого хода в «партию 2», G нужно время <math>l_3\ge l>0.</math> Она совершает ход в момент времени <math>l_1+t_2+l_2+t_1+l_3.</math> S смотрит на часы и получает, что <math>f=t_2+l_2+t_1+l_3</math> и <math>y:=t_2.</math> То есть <math>f-y=l_2+t_1+l_3.</math> S проверяет, что <math>f-y\ne t_2.</math> В случае, что он не заметит обмана, должно выполняться равенство:
<math>t_2=l_2+t_1+l_3 \quad (2)</math>
Однако комбинируя <math>(1)</math> и <math>(2)</math> мы получаем, что:
<math>l_1+2l_2+l_3=0</math>
Но так как <math>l_1,l_2,l_3>0</math> — это невозможно. Следовательно S обнаружит обман. Теорема доказана.
Замечания
- Подчеркнем, что согласно данной теореме, F или S обнаруживает обман. Это означает, что один из них может остаться в неведении о происходящих махинациях.Шаблон:Sfn
- Данное математическое решение использует идеальную точность, которая невозможна с точки зрения физики. Учитывая неточность скорости компьютерных вычислений, данное решение становится непрактичным для многих приложений.Шаблон:Source-ref
Применение решения
Вероятностный канал перестроения (The Probabilistic Channel Hopping)
Проблема гроссмейстера и проблема обмана мафией лежат в основе работы Аммара Алкассара (Ammar Alkassar), Кристиана Стюбле (Christian Stuble) и Ахмада-Реза Садеги (Ahmad-Reza Sadeghi). Они представили вероятностный канал перестроения. Он основан на предположении, что злоумышленник не может эффективно ретранслировать все коммуникации параллельно. Основной идеей является использование системы перестраиваемых каналов (channel hopping system), благодаря которой злоумышленник не может прослушивать связь между участвующими сторонами. Данный подход также использует семантически безопасный ключ, разделенный между первой (проверяющей) и второй (доказывающей) сторонами. Это позволяет использование в беспроводных самоорганизующихся сетяхШаблон:УточнитьШаблон:Source-ref.
Другие решения
- Идентификация в клетке Фарадея, предложенное Сэми Бенгио (Samy Bengio)Шаблон:Source-ref.
- Система точного измерения, предложенная Иво Десмедтом и Томасом БетомШаблон:Sfn.
- Дистанционно-ограниченный протокол, предложенное Стефаном Бэндсом (Stefan Bands) и Дэвидом Чаумом (David Chaum)Шаблон:Source-ref.
См. также
Примечания
Литература
