Введение
Система доказательств с нулевым разглашением информации получила большое общественное внимание, так как это является важной отраслью криптографии и теории сложности вычислений. Система неинтерактивных доказательств с нулевым разглашением содержит только одно сообщение, посланное доказывающей стороной проверяющей стороне. Данная система широко используется в построении различных типов криптографических протоколов и алгоритмов шифрования из-за хорошего уровня конфиденциальностиинформации, аутентификациии малой интерактивной сложности.
Определение
Первоначально, неинтерактивное доказательство с нулевым разглашением информации было определено только в качестве системы единой теоремы доказательства. В такой системе каждое доказательство требует своей собственной общей ссылочной строки. Общая ссылочная строка в общем случае не является случайной строкой. Она может, например, состоять из случайно выбранных элементов группы, которые используются всеми сторонами протокола. Хотя элементы группы являются случайными, ссылочная строка содержит определенную структуры, которая отличается хаотичностью.
История
В 1985 году, Голдвассер и другие впервые выдвинули концепцию интерактивной системы доказательств и проанализировали интерактивную систему доказательства с нулевым разглашением информации, что создало важную отрасль криптографии и теории сложности вычисленийдоказательства нулевого разглашения информации. Наиболее привлекательной особенностью нулевого разглашения информации является то, что доказывающий может доказать правильность утверждения проверяющему без утечки какой-либо дополнительной информации. Это позволяет обеспечить безопасность выполнения шагов протокола от недобросовестных участников. Таким образом, данная система имеет широкие перспективы применения. Проверяющий, получающий доказательство с нулевым разглашением информации, должен точно определить, является ли оно правдой. Основными характеристиками системы доказательства с нулевым разглашением информации является полнота, корректность и нулевое разглашение.
Полнота: если утверждение верно, то доказывающий сможет убедить в этом проверяющего с заданной точностью.
Корректность: если утверждение неверно, то любой, даже недобросовестный, доказывающий не сможет убедить в этом проверяющего (за исключением малой вероятности).
Нулевое разглашение: если утверждение верно, то любой, даже недобросовестный, проверяющий не узнает ничего, кроме самого факта, что утверждение верно.
Сначала Блюм и другие изучали систему неинтерактивных доказательств с нулевым разглашением информации (далее НДНР) и представили общую модель ссылочной строки, которая, как правило, применяется и в настоящее время. НДНР содержит только сообщение, отправленное от доказывающего к проверяющему, которое лучше используется при построении криптографических протоколов. Далее последовали исследования по теории и применения НДНР, в том числе НДНР с проблемами разрешимости, решение которых возможно проверить на машине Тьюринга(расширение конечного автомата и, согласно тезису Черча-Тьюринга, способна имитировать все исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен) за время, не превосходящее полинома от размера входных данных, при наличии некоторых дополнительных сведений, и статические (совершенные) НДНР, а также применимость НДНР для схем шифрования, анонимной проверки подлинности и строительства группы и кольца подписи.
В последние годы Грот и другие предлагают использовать исследования НДНР для решения конкретных проблем и построить НДНР, основанные на различных сценариях применения. Эта идея значительно повышает эффективность и практичность НДНР и создает новую линию исследований по применению НДНР.
Параметры инициализации
Как было показано, в простой модели только языки класса сложности BPP (класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью) НДНР, поэтому определение НДНР обычно содержит первоначальную настройку предположения. В настоящее время, как правило, исследователями признается построение НДНР в модели общей опорной строки.
Определение. Для пары вероятностных машин Тьюринга (P,V), в котором P - вероятностное полиномиальное время и V - детерминированное полиномиальное время, называется неинтерактивным доказательством с нулевым разглашением информации для языка L, если выполняются следующие условия:
Применяемые исследования НДНР
Присущие свойства обеспечения конфиденциальности и аутентификации НДНР способствуют в необходимости его широкого применения в строительстве криптографических протоколов. Интерактивные доказательства с нулевым разглашением информации (далее ИДНР), как правило, используются для построения многораундовых интерактивных протоколов в простой модели, например, общее двухпартийное и многопартийное безопасное вычисление, и в основном для разработки протоколов в абстрактной форме, в то время как НДНР обычно встроены в конструкцию специфических, практичных криптографическихалгоритмов и криптографических протоколов. В связи с этим возникают очень высокие требования к построению эффективных систем НДНР. Во-первых, Блюм и другие отмечают, что НДНР могут быть использованы для разработки открытых схем шифрования ключа против выбранной атаки шифртекстом. С тех пор, Наор и Юнг [18] выдвинули первую безопасную открытую схему шифрования ключа на основе вероятностного шифрования[20] и НДНР. Беллар и Голдвассер [19] представляют новый метод построения протокола проверки подлинности цифровой подписи и сообщения с помощью НДНР. А полученная схема безопасна против выбранной адаптивной атаки сообщением. В 1999 году Сахай [21] расширяет свойства криптографических протоколов НДНР, при которых злоумышленник не может перевести один шифртекст в другой в алгоритме шифрования, и предлагает способ преобразовать общую НДНР в НДНР с этим свойством.
С другой стороны, НДНР широко используются в групповых подписях, то есть подписях, функция генерации которых распределена между группой подписывающих и корректная подпись может быть получена только в том случае, если все члены группы приняли участие в выполнении протокола генерации этой подписи; кольцевой подписи, позволяющей подписать сообщение от имени группы и электронного голосования. НДНР сначала используется для построения доказуемой надежной схемы групповой подписи в стандартной модели Белла (модель контроля и управления доступом, основанная на мандатной модели управления доступом) и других моделях. [22]. Затем Грот использует НДНР для построения групповой подписи с фиксированным размером, а также полностью анонимными схемами групповой подписи [6] в стандартной модели.
Итоги и перспективы
За последние 20 лет исследования по НДНР и связанные с ними теории постепенно улучшились. Недавние исследования были в основном сосредоточены на эффективности применения и совершенствования НДНР, включая следующие аспекты:
1. В настоящее время исследования эффективности НДНР сосредоточены на вычислениях в билинейной группе, так что стоит тщательно изучать, как создать высокоэффективный протокол НДНР, применимый к остальным математическим конструкциям.
2. Другие криптографическиесредства, которые взаимодействуют с существующими системами доказательств: в последнее время, Абэ и другие предлагают структуру, сохраняющую обязательства и подписи, которые применяются к системе доказательств Грота-Сахая, так что она позволяет модульную конструкцию протоколов и в то же время обеспечивает эффективность. В настоящее время эти исследования только начинаются, и есть еще много проблем в эффективности и применение этих схем.
Система доказательства Грота-Сахая
Доказательство Система Грота-Сахая состоит из четырех алгоритмов: алгоритма генерации (установки) алгоритма генерации общей ссылочной строки К, доказывающего P и проверяющего V. Алгоритм установки участвует в параметрах безопасности и вывода (gk, sk), где gk является некоторой публичной информацией (в нашем случае описанием билинейной группы) и sk - это некоторые секретные данные (например, это может быть факторизация группы). Алгоритм генерации общей ссылочной строки K принимает на вход (gk, sk) а на выходе выдаст общую ссылочную строку σ. Доказывающий P принимает на вход (gk,σ,x,w) и на выходе дает доказательство π. В конце проверяющий принимает (gk,σ,x,π) и выдает 1, если принимает доказательство и 0 в противном случае.
Литература:
ПРОТОКОЛЫ АУТЕНТИФИКАЦИИ С НУЛЕВЫМ РАЗГЛАШЕНИЕМ СЕКРЕТА
ТИПЫ И ПРИЛОЖЕНИЯ ПРОТОКОЛОВ С НУЛЕВЫМ РАЗГЛАШЕНИЕМ СЕКРЕТА