Интерактивные доказательства: проверяющий задаёт тайный вопрос

Если различаешь полноту и защищённость от обмана - переходи к «Теперь сам».

Как думаешь: почему нельзя просто спросить «эти графы разные»?

Доказывающий уверяет, что две схемы соединений неизоморфны. У него неограниченное время; у проверяющего время полиномиально. Слова «я перебрал все перестановки» ничего не доказывают, а полный журнал перебора слишком велик. Но проверяющий может сам подготовить задачу с тайным ответом и посмотреть, умеет ли собеседник его узнавать.

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

На что это похоже

Представь два запечатанных вида деталей, различимых только экспертом. Проверяющий случайно берёт один вид, меняет упаковку и просит назвать источник. Если виды действительно различны, эксперт распознаёт их. Если внутри одно и то же, новая упаковка не сообщает тайный выбор. Успешная серия ответов становится свидетельством различимости. При этом проверяющий обязан скрыть источник; надпись на упаковке разрушит проверку.

Механизм: протокол неизоморфизма

Даны простые графы G₀ и G₁ на одном числе вершин. Проверяющий равновероятно выбирает бит b, равномерную перестановку вершин π и отправляет H = π(G_b). Доказывающий отвечает, из какого графа получен H. Проверяющий принимает раунд ровно при ответе b.

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

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

Повторяем с новыми независимыми битами и перестановками, требуя успеха во всех раундах. После r раундов вероятность обмана не больше 2⁻ʳ. Доказывающий видит предыдущие сообщения, но очередной тайный бит всё равно независим; условная вероятность очередного успеха не больше половины. Перемножение получается из условных вероятностей, а не из предположения, что стратегия противника не меняется.

Определение IP разрешает полиномиально много сообщений и полиномиальную суммарную работу проверяющего. Обычно используют постоянные разрывы вероятностей, например полноту не меньше 2/3 и ложное принятие не больше 1/3. Независимое повторение усиливает их. Теорема Шамира IP = PSPACE гораздо сильнее примера с графами. Идея сложного направления: логические утверждения превращают в утверждения о многочленах, а проверяющий сверяет их в случайных точках. Одна проверенная точка ещё не доказывает произвольную функцию; работают ограничения степени и конкретный протокол, как в проверке тождеств.

Правило

Честному доказывающему достаточно одной успешной стратегии; обманщик обязан быть ограничен при любой стратегии. Случайные биты проверяющего в протоколе неизоморфизма не раскрываются. Равенство IP = PSPACE относится к этой модели взаимодействия, а не к однократной проверке сертификата NP.

Разбор: одинаковое распределение выдаваемых графов

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

from itertools import permutations
from collections import Counter
from fractions import Fraction


def kod(rebra, p):
    return tuple(sorted(tuple(sorted((p[a], p[b])))
                        for a, b in rebra))


def raspredelenie(n, rebra):
    schetchik = Counter()
    for p in permutations(range(n)):
        schetchik[kod(rebra, p)] += 1
    return schetchik


def luchshee_ugadyvanie(a, b):
    # Оба источника равновероятны, число перестановок одинаково.
    vse = set(a) | set(b)
    uspeshno = sum(max(a[h], b[h]) for h in vse)
    return Fraction(uspeshno, sum(a.values()) + sum(b.values()))


put = [(0, 1), (1, 2)]
kopiya = [(0, 2), (2, 1)]
treugolnik = [(0, 1), (1, 2), (2, 0)]
a = raspredelenie(3, put)
b = raspredelenie(3, kopiya)
c = raspredelenie(3, treugolnik)
print('две копии: распределения равны', a == b)
print('лучшее угадывание:', luchshee_ugadyvanie(a, b))
print('разные графы: общих сообщений', len(set(a) & set(c)))
print('честный ответ:', luchshee_ugadyvanie(a, c))
for r in [1, 4, 10]:
    print('раундов', r, 'обман не больше', Fraction(1, 2 ** r))

две копии: распределения равны True
лучшее угадывание: 1/2
разные графы: общих сообщений 0
честный ответ: 1
раундов 1 обман не больше 1/2
раундов 4 обман не больше 1/16
раундов 10 обман не больше 1/1024

Функция угадывания выбирает для каждого наблюдаемого сообщения более вероятный источник. Это даже разрешает обманщику заранее знать все распределения. При одинаковых графах такая информация не помогает: у каждого сообщения частоты источников равны. При разных графах сообщение встречается только у одного источника.

Разбор: раскрыли перестановку - разрушили эксперимент

Если вместе с H отправить b, любой доказывающий повторит ответ. Если вместо b отправить перестановку π, проверяющий тоже может выдать лишнюю информацию: доказывающий обратит её и увидит точную исходную маркировку. Для двух изоморфных, но по-разному подписанных входов источники тогда могут различаться. Секретность - часть математического протокола, а не необязательная настройка транспорта.

Что ломается без этого

Пример удачного диалога не доказывает защищённость: надо ограничить лучшую стратегию обманщика. Повторение с одной и той же случайностью не снижает ошибку. Нельзя приписывать этому протоколу автоматически нулевое разглашение или защиту от квантового противника: это отдельные определения и доказательства. Здесь установлена принадлежность языка классу IP.

Зачем это в работе

Удалённые вычисления и криптографические протоколы ставят вопрос о проверке работы более мощного участника. Модель IP объясняет, почему взаимодействие и случайность расширяют возможности проверяющего. Для практической системы дополнительно нужны вычислимая стратегия честной стороны, размеры сообщений, конкретные вероятности и модель противника; неограниченный доказывающий из определения сам по себе не готовая реализация.

Теперь сам

Какова верхняя граница ложного принятия после 12 независимых раундов протокола неизоморфизма, если принимаются только 12 правильных ответов подряд?