WikiSort.ru - Не сортированное

Теорема

Формулировка^[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_{1}+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]

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

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

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

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