Молчание — золото: доказательство существования Гамильтонова цикла в графе

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

Заменив такую сложную конструкцию плоским графом, изоморфным исходному, получим задачу, которую далее рассмотрим в системе протоколов с нулевым разглашением.

Доказательство с нулевым разглашением

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

Очень убедительное (но не абсолютно определенное) свидетельство, что теорема верна, и что доказывающий знает это самое доказательство, дает интерактивный вероятностный протокол, называющийся доказательством с нулевым разглашением.

Интерактивность в данном определении говорит о том, что стороны общаются в течение нескольких раундов. В стандартных математических доказательствах имеет место только один вид взаимодействия: доказывающий дает проверяющему доказательство "на проверку", и на этом все заканчивается. В нашем же случае процесс доказательства утверждения превращается в разговор, который заканчивается убеждением проверяющего (если все идет хорошо).

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

Как убедить кого-то в существовании Гамильтонова цикла, не раскрывая сам цикл

Пусть обеим сторонам известен некоторый граф G = (E, V) , вершины которого пронумерованы от 1 до V. Необходимо доказать проверяющему существование цикла в G, который посещает каждую вершину ровно один раз.

На вход системе с нулевым разглашением мы подаем(G, k), где k- положительное целое число, которое играет роль параметра безопасности и является количеством последовательных взаимодействий между сторонами: чем больше k, тем больше уверенность проверяющего в доказательстве.

Дальнейшие шаги будут выполнятьсяk раз.

Доказывающая сторона выбирает случайную перестановку чисел \{1,...,|V|\}и рисует матрицу смежности для графа, помечая строки и столбцы в соответствии с этой перестановкой. Получается новый граф, изоморфный исходному, построенный по данной матрице, если бы нумерация строк и столбцов у нее шла в естественном порядке.

Проще говоря, мы заменяем исходный граф на его изоморфную копию.

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

Проверяющая сторона получает скрытую матрицу и делает выбор:

  • Попросить доказывающую сторону открыть2|V|сетки, соответствующих ребрам цикла Гамильтона. Процесс раскрытия симметричен: если показана запись \{i, j\} в матрице, доказывающая сторона должна также показать запись\{j, i\}.

  • C другой стороны, можно попросить доказывающую сторону открыть граф целиком.

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

Наличие 1 во всех открытых квадратах говорит о существовании ребер между соответствующими вершинами графа. Так как мы открывали по условию те квадраты, которые отвечают ребрам цикла Гамильтона, получаем доказательство существования такого цикла в графе.

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

Выбор того, что проверяющий будет просить у доказывающего, на каждом шаге определяется "подбрасыванием монетки".

Если все в порядке, проверяющая сторона принимает доказательство. 

Если же первом случае проверяющая сторона увидит в открытых квадратах 0, она поймет, что доказывающая сторона не владеет знанием о цикле Гамильтона. Аналогично, по описанной выше причине, проверяющая сторона во втором случае тоже может понять, что доказывающий пытается ее обмануть, и в итоге она отклонит доказательство.

Почему это - нулевое знание?

Докажем, что проверяющая сторона, благодаря разговору, не может получить никакой "лишней" информации.

Может показаться, что в первом случае проверяющему предоставляется знание, благодаря которому он способен самостоятельно полностью узнать доказательство. 

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

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

Что и требовалось доказать.

Заключение

Рассмотрим задачу аутентификации субъекта. Она состоит в проверке подлинности одной стороны другой, например, при входе в операционную систему пользователь может доказывать свою лигитимность вводом пароля.

Если решать ее таким простым способом, то гарантия того, что он не попадет в руки злоумышленников, не очень велика.

Конечно, при таком условии нельзя быть абсолютно уверенным в том, что аутентификация субъекта будет стопроцентной. Но проверяющий каждый раз может запросить любую часть информации, причём несколько раз. К тому же, можно использовать при этом Гамильтоновы циклы, получая относительно надёжную систему доступа, ведь вероятность в каждом раунде  успешно обманывать проверяющую сторону равна 1/2^k, где k – число взаимодействий сторон.

Материал подготовлен при использовании литературы:

Manuel Blum "How to Prove a Theorem So No One Else Can Claim It"

Шнайер Б. Прикладная криптография, 2-е издание: протоколы, алгоритмы, исходные тексты на языке Си //Под редакцией ПВ Семьянова. М., Триумф. – 2002.

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 13

    0

    Интересно, можно ли разработать алгоритм для случая, когда у "доказывающего" есть не сам граф, а доказательство его существования (не конструктивное).
    Или для Гамильтонова цикла такое доказательство трудно придумать?

      +1
      Спасибо за интересный вопрос!
        0
        Как я понимаю, существование Гамильтонова цикла можно строго доказать в графах специального вида (теорема Оре), но в таких графах и сам цикл ищется за полиномиальное время. По-видимому, задача доказательства существования цикла в произвольном графе равносильна задаче нахождения самого цикла (которая, естественно, NP-полная).
      0
      соответствующих краям цикла Гамильтона

      Это вы «edge» так перевели?
      И почему тогда нет указания, что это перевод?
        +2
        Спасибо за замечание! Исправила неточность.
          0
          Это «неточность» из разряда «с прямым углом перепутал».
          Поясню, что мне кажется подозрительным. Если бы это была ваша статья, то вряд ли бы вы оставили в стороне очевидный выход для доказывающей стороны:
          при ответе на первый вопрос показывать единички для произвольной перестановки вершин, а при ответе на второй — произвольный изоморфизм.
          Ведь оба вопроса одновременно задавать нельзя.
          Это решаемая проблема, но ваше изложение уж слишком упрощённое.
            0

            Например, можно заранее передавать матрицу, шифруя каждую ячейку уникальным публичным ключом, а "вскрытие карточек" осуществлять путем передачи соответствующих приватных ключей. Тогда принимающая сторона узнает только часть информации, но будет уверена, что доказывающий знает всю матрицу.

              –2
              Кажется, этого мало.
              Пусть доказывающий, не зная истинного цикла, при ответе на первый вопрос выбирает произвольную перестановку вершин и открывает соответствующие карточки. Как проверяющий поймёт, что его пытаются обмануть?
                +1

                Но ведь, если эти карточки все состоят из единиц, то доказывающий случайно нашел гамильтонов цикл и ни капельки не соврал. Если же там нули где-то, то проверяющий видит попытку обмана.

                  0
                  Да, точно. Что-то запутался.
                  Спасибо!
        0

        Что-то непонятно.
        Доказывающий (жулик) создаёт две матрицы: одна для исходного графа (его перестановка), другая — для заведомо закольцованного (тупо с V вершинами и V рёбрами, например).
        Проверяющий просит: "открой мне цикл" — доказывающий открывает цикл во второй матрице.
        Просит: "открой мне граф" — открывает первую.


        Если проверяющий просит: "открой мне весь граф и покажи на нём цикл" — это, извините, отнюдь не нулевое знание.
        Потому что задача нахождения изоморфизма графов — хоть и NP-полная, но решаемая. А в некоторых случаях решаемая довольно легко.
        Больше того: проверяющий даже без "покажи на нём цикл" должен выполнить эту сверку.
        А то мало ли, жулик ему не тот граф всучил.


        Чтобы жулик не жульничал с двумя матрицами, но и не давал проверяльщику халяву, — нужен какой-то нотариус, который получает ровно одну матрицу с нарисованным на ней циклом, но при этом сам не заинтересованный в доказательстве.
        С другой стороны, если такой нотариус есть, то зачем нужен проверяльщик? Нотариус убедится, что доказательство верное, и скажет: "да, жулик не ворует, мамой клянусь (а теперь заплатите госпошлину)".

          0

          В статье главное не указано — доказыватель сначала передает все данные так, что каждый элемент зашифрован своим ключем. Потом, или выдает проверяющему все ключи, или только ключи от цикла.

        Only users with full accounts can post comments. Log in, please.