Автор: Уланов А.
Источник: https://docplayer.ru/32670062-Protokoly-s-nulevym-razglasheniem-i-ih-primeneniya.html
Во многих криптографических системах возникает задача одной стороне A (доказывающая сторона) доказать знание секрета другой стороне B (проверяющая сторона), причем сделать это необходимо таким образом чтобы сторона B после этого не знала сам секрет. То есть A демонстрирует знание какой-то информации без разглашая какой-либо части этой информации. Впервые понятие протоколов с нулевым разглашением было введено в работе Гольдвассера, Микали и Ракоффа в 1985 г.[1]. Такие протоколы позволяют решить проблемы которыми обладают все методы авторизации по паролю: необходимость хранить пароль на сервере либо простота отслеживания пароля третьей стороной, подслушивающей процесс авторизации.
Как правило все протоколы с нулевым разглашением носят вероятностный характер. Это означает что проверяющая сторона никогда не может быть полостью уверена в знании стороной A секрета, но может убедиться в этом с точностью до любой, наперед заданной, вероятностью за конечное время.
Итак протоколом доказательства с нулевым разглашением называется протокол доказательства, обладающий следующими свойствами:
Необходимо заметить что многие протоколы призванные обеспечивать аутентификацию пользователя проверяя знание им пароля (или секретного ключа в системах с открытым ключом) не передавая в открытом виде сам пароль (или закрытый ключ) не являются с математическом точки зрения алгоритмами с абсолютно нулевым разглашением по той причине что не удовлетворяют последнему свойству. Такие алгоритмы называют иногда доказательством с вычислительно нулевым разглашением.
Классическим примером протокола доказательства с нулевым разглашением является протокол доказательства знания пароля к двери внутри круговой пещеры. Пусть Алиса (Alice) знает этот пароль и хочет доказать его знание Бобу (Bob) без разглашения самого пароля. Используется следующий протокол:
После каждой итерации уверенность Боба в том что Алиса знает секрет увеличивается вдвое. Таким образом после k успешно выполненных операций вероятность того что Алиса на самом деле обманывает Боба равна 1/(2^k) .
Следующий пример так же как и предыдущий носит чисто гипотетический характер. Пусть Алиса знает как решить Кубик Рубика из какой-то позиции (назовем ее исходной) и хочет доказать это Бобу, при этом она не хочет чтобы Боб также научился складывать кубик из данной позиции. Для решения этой задачи может использоваться протокол состоящий из нескольких последовательных выполнений следующих действий:
Очевидно Алиса всегда сможет доказать Бобу умение решать исходную позицию если она действительно таким умением обладает. В противном же случае она не всегда сможет выполнить последний пункт. Так же любое количество итераций никаким образом не поможет Бобу выяснить как решается исходная позиция.
Пусть дана пара графов G1 = (U,E1) и G2 = (U,E2) , здесь U – множество вершин графа, а E1 и E2 – множества ребер. Графы G1 и G2 называют изоморфными если существует перестановка q вершин графа которая переводит один граф в другой. Задача нахождения такой перестановки и поиск ответа на вопрос о её существовании есть сложная математическая задача не решаемая за полиномиальное время. Итак рассмотрим следующий протокол. Пусть q – изоморфизм графов G1 и G2 знанием которого обладает Алиса. Она доказывает это знание Бобу:
Следующий протокол основывается на сложности вычисления квадратного корня числа по модулю большого числа с неизвестным разложением на простые множители.
В протоколе предполагает что обе стороны заранее снабжены каким-то числом n = pq . При этом разложение n на простые множители считается неизвестным для всех участников протокола. Доказывающая сторона (Алиса) выбирает секретное число s , взаимно простое с n , далее вычисляет значение v = s 2 mod n и публикует значение v объявляя его своим открытым ключом.
Как и все предыдущие, протокол Фейга-Фиата-Шамира состоит в последовательном выполнении следующих итераций:
Как было отмечено выше многие другие криптографические протоколы идентификации не являются в точном математическом смысле протоколами с абсолютно нулевым разглашением. Однако совсем не этот фактор имеет в данном случает решающее значение.
Многие протоколы в том числе протоколы на основе систем с открытым ключом требуют огромного количества вычислений с обоих сторон. В то же время они обладают тем существенным преимуществом что для полной проверки доказываемого знания достаточно одной итерации. В случае же с протоколами с нулевым разглашением вычисления как правило более просты. Но в тоже время они требуют большого количества итераций прежде чем проверяющая сторона сможет убедиться в идентичности доказывающей стороны с достаточной степенью вероятности.
Описанные свойства и определили в основном возможные применения протоколов с нулевым разглашением. Очевидно в силу требования к большому количеству итераций их применение в компьютерных сетях связано с трудностями. С другой стороны использование протоколов со сложными вычислениями невозможно на сравнительно простых устройствах с малым количеством памяти таких как смарт-карты. Последние и приводятся чаще всего в качестве основного примера где возможно использование протоколов с нулевым разглашением.