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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:34, 6 ноября 2015.
Short Pairing-Based Non-interactive Zero-Knowledge Arguments
Short Pairing-Based Non-interactive Zero-Knowledge Arguments.png
Авторы Jens Groth[@: 1].
Опубликован 2010 г.
Сайт Homepage of Jens Groth
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал


__NUMBEREDHEADINGS__

Аннотация. Мы строим не интерактивные доказательства с нулевым разглашением информации для схемы завершенной выполнимости, характеризующейся совершенным нулевым разглашением и вычислительной надежностью. Не интерактивные доказательства с нулевым разглашением имеют сублинейный размер и эффективную проверку открытого ключа. Размер доказательств с нулевым разглашением может быть приведен к группе с постоянным количеством элементов, если мы допускаем, что общая строка ссылки велика. Наши построения опираются на группы сопряжения, а безопасность основывается на двух криптографических предположениях; мы не пользуемся эвристическими или случайными оракулами Фиата – Шамира.
Ключевые слова: доказательства с нулевым знанием сублинейного размера, криптография сопряженных основ, знание показателя предположения, предположения Диффи – Хелмана, вычислительные возможности.

Введение

Доказательства с нулевым разглашением, введенные Голдвассером, Микали и Ракоффом [1], являются фундаментальными блоками в криптографии, которые используются в многочисленных протоколах. Доказательства с нулевым разглашением обеспечивают доказывающую сторону возможностью убедить проверяющую сторону в верности утверждения без утечки другой информации. Основные свойства заключаются в понятиях полноты, надежности и нулевого разглашения.

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

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

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

Первые доказательства с нулевым разглашением основывались на интерактивном взаимодействии доказывающей и проверяющей сторон, хотя многие криптографические задачи решаются автономно: на пример, постановка подписи или шифрующие сообщения. Для таких задач желательно иметь не интерактивные подтверждения с нулевым разглашением (NIZK), для которых не предусмотрено взаимодействие, а подтверждение представляет собой единичное сообщение от доказывающей стороны проверяющей. К сожалению, только языки ВРР имеют подтверждения с нулевым разглашением NIZK в простых моделях без какой либо установки [2],[3]. Однако, Блум, Фельдман и Микали [4] ввели NIZK в модель общей строки ссылки, когда и доказывающая и проверяющая стороны имеют доступ к общей строке, созданный достоверным способом. Такие NIZK подтверждения имеют многие приложения, начиная от защиты криптосистем с открытым ключом от атак на основе подобранного ранее шифрованного сообщения [5],[6], заканчивая недавно разработанными схемами подписи [7],[8]. Поэтому, в последнее время проводились многочисленные исследования принципиальных утверждений [9],[10],[11], эффективности [12],[13],[14],[15], и гарантий безопасности, которую предлагают NIZK доказательства [16],[6],[17].

NIZK доказательства, основанные на стандартных криптографических предположениях, считались когда-то неэффективными и бесполезными на практике. Чтобы преодолеть эту неэффективность, криптографы, работающие в прикладной области, до недавнего времени полагались на так называемую эвристику Фиат-Шамира для криптографических преобразований интерактивных подтверждений с нулевым разглашением и открытым ключом в NIZK доказательства, используя криптографическую хэш-функцию для вычисления запросов подтверждающей стороны. Эвристика Фиат – Шамира может дать весьма эффективные NIZK доказательства, которые защищены в модели случайных оракулов [18], где криптографическая хэш-функция моделируется как случайная. На пример, возможно использовать эвристику Фиат-Шамира для преобразования интерактивных доказательств с нулевым разглашением и открытым ключом сублинейного размера [19] в не интерактивные доказательства с нулевым разглашением сублинейного размера [20]. К сожалению, существует несколько примеров протоколов, которые имеют защиту в модели случайных оракулов, но незащищены в стандартной модели конкретизации понятий, независимо от того, какая хэш-функция применяется [21],[22],[23],[24],[25]. Особенно уместна здесь демонстрация схемы подписи, выведенная на основе схемы идентификации открытого ключа Голдвассером и Калаи [26], которая оказывается защищенной в модели случайных оракулов и незащищенной в реальной жизни.

Недавние разработки в области не интерактивных доказательств с нулевым разглашением использовали билинейные группы для повышения их эффективности. Грот, Островский и Сахали [27],[28] предоставили не интерактивные доказательства с нулевым разглашением NIZK для схемы выполнимости, когда доказательство представлены группой элементов , где есть число входов в схему. Эти доказательства NIZK имеют свойство, которое заключается в том, что они могут быть установлены для того, чтобы обеспечить полную надежность и вычисление нулевого разглашения или преобразовывать первоначальную надежность и нулевое разглашение. В работах Боуена, Грота и Сахали ,[8],[29],[30],[31] проведены исследования возможности построения эффективных доказательств NIZK, которые могут быть непосредственно применены к билинейным группам вместо прохождения по схеме выполнимости. В отдельных случаях, на пример в строке подписи Чандрана, Грота и Сахали [7], эти методики приводят к доказательствам суб-линейного размера NIZK, но, в общем, число элементов группы в доказательствах NIZK возрастает прямолинейно в зависимости от размера утверждения. Эйб и Фейр [32] предоставили конструкцию, основанную на фиксации вместо кодирования, но, поскольку имеется фиксация для каждой цепи, они получили линейное увеличение размера схемы.

Рассматривая полную задачу NP выполнимости схемы, можно определить, что причина, по которой доказательства NIZK возрастают линейно размеру схемы, состоит в том, что они кодируют каждую цепь схемы. Новая полностью одноморфная система Джентри [33] может свести NIZK доказательства к линейным размерам свидетельствующей стороны: доказывающий шифрует входы в сеть и использует одноморфные свойства криптосистемы, которая может вычислять выходы из сети. Доказывающая сторона, затем, предоставляет NIZK доказательства того, что входы в шифрованные сообщения достоверны, а выходы шифртекстов содержат 1. Однако, полное одноморфное шифрование оказывается полезным тогда, когда схема имеет малое свидетельство: если схема содержит линейное число цепей входов, то конечные размеры NIZK доказательств будут линейными в соответствии с размерами схемы.

Наш вклад

Доказательства вычислительной надежности Микали [20] показали возможность сублинейного размера NIZK доказательств, но, несмотря на десятилетние исследования в этой области, эвристика Фиат – Шамира является единственной известной стратегией для построения NIZK доказательств сублинейного размера. Наша цель – ввести новый тип NIZK доказательств сублинейного размера, где стойкость системы не зависит от модели случайных оракулов.

Мы строим NIZK доказательства для схемы завершенной выполнимости, вычислительной надежности и совершенного нулевого разглашения (см. определения в разделе 2). NIZK доказательства являются краткими и очень эффективными для подтверждения, но доказывающая сторона должна использовать сверх линейное число групповых операций. Мы сначала даем доказательство NIZK, состоящее из постоянного числа элементов группы и длинной общей строкой ссылки. Затем, мы показываем возможно уменьшить размер общей строки ссылки за счет увеличения размера NIZK доказательства, делая их одновременно сублинейными в размере схемы.

Надежность нашего NIZK доказательства основывается на q вычислительной возможности Диффи – Хеллмана и q вычислительной возможности показателя предположений (см. Раздел 3). Предположение q-CPDH есть предположение о нормальном вычислительном диалоговом взаимодействии, где q-PKE представляет собой так называемое разглашение предположения о показателе. Разглашение предположения о показателе подверглось критике из-за своей невозможности быть нефальсифицированными [34], а использование нестандартного предположения может оказаться неизбежным, поскольку Эйб и Фейр [32] показали, что NIZK доказательства со статистическим нулевым разглашением для NP-полного языка имеет преобразование «стандартного черного ящика» в стандартное криптографическое предположение, если . [прим. 1],[прим. 2]

Таблица 1. Сравнение NIZK доказательств и аргументов
CRS размер Размер Доказывающий Проверяющий Предположение
Groth [15]
Переест. с потайным входом
Groth [15]
бит
бит
Naccache-Stern
Gentry [33]
Решетчатый
G-Ostrovsky-Sahai [27][28]




Сопряженный
Abe-Fehr [32]
Разглашение эксп.
Groth [35]
Случайный оракул
Настоящая работа
PKE и CDHP
Настоящая работа
PKE и CDHP

Таблица 1 дает возможность сравнительного анализа NIZK доказательств и аргументов для схемы выполнимости, где есть параметр стойкости системы, обозначает размер группы элементов, и представляют затраты на умножение и возведение в степень, а – стоимость сопряжения билинейных групп. (см. раздел3).

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

Совершенное нулевое предположение ZAP. Модель общей строки ссылки предполагает наличие достоверной установки для создания общей строки ссылки и ее доступность как для доказывающей стороны, так и для проверяющей. Если, по каким либо причинам, такая установка невозможна [прим. 3], мы можем свести сублинейный размер 2 к свидетельству с открытой проверкой неразличимого аргумента, при котором первое сообщение проверяющего может использоваться неоднократно, так называемые ZAP [36], следующим образом: Проверяющий образует строку ссылки. Доказывающий подтверждает, что строка ссылки сформирована должным образом (наша строка ссылки не является случайной, но содержит некоторые структуры, которые делают возможным проверку сформированности) и может теперь сделать посредниками многие ZAP, используя начальные сообщения подтверждения в качестве общей строки ссылки. Так как наши NIZK доказательства являются полным нулевым разглашением, то ZAP будет полностью неразличимым свидетельством.

Основные принципы наших NIZK доказательств

Мы будем строить NIZK доказательства для существующего ввода в бинарную схему , делая ее выход 1. При потере постоянного фактора, можно предположить, что состоит из И-НЕ схем. Далее, если обозначить выходную цепь как , можно добавить цикл самоконтроля к схеме, состоящей из И-НЕ схем, где , принуждая а быть 1. Эту упрощает сложную задачу доказать, что имеется распределение истинных величин по цепям относительно всех И-НЕ схем в системе.

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

Входное произведение: хранения содержат величины и , что удовлетворяет для всех .

Перестановка: хранения содержат величины и , что удовлетворяет условию для всех , при которых есть открытая перестановка элементов.

Рассмотрим вкратце каким образом хранения совместно с двумя видами не интерактивного доказательства дают постоянный размер NIZK доказательств для схемы выполнимости, для которой . Доказывающая сторона получает свидетельство выполнимости схемы и , где есть вводы в схему и все величины совместимы с цепями и соотнесены со И-НЕ схемами. Мы пользуемся положением, согласно которому -1 соответствует ложному утверждению, а +1 истинному, следовательно, если выход схемы , мы имеем

Доказывающая сторона привязывается к кортежу.

Доказывающая сторона предоставляет доказательство входного произведения на основании , показывая, что и для всех . Это показывает, что являются соответствующими истинными величинами.

Выход одной И-НЕ схем может быть входом другой И-НЕ схемы, что означает, что соответствующие величины вынуждены иметь одинаковое распределение. Доказывающая сторона выбирает перестановку р, которая содержит циклы для всех наборов величин, которые должны совпадать и давать доказательство перестановки на основании . Это показывает, что каждому набору величин, соответствующему тому же выходу цепи, где Так, что величины совпадают с цепями схемы. Доказывающая сторона использует дополнительные хранения, входное произведение и доказательства перестановки, что бы показать, что другие связанные величины и согласуются со схемой и величинами , которые мы рассмотрим подробно в разделе 8.

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

Этот принцип показывает как построить доказательство NIZK постоянного размера для схемы выполнимости, но для получения возможности доказательств входного произведения и доказательств перестановки общая строка ссылки имеет размер групп элементов. В разделе 9 мы уменьшаем общую строку ссылки, используя соглашение для элементов, где .

При меньшем чем нам необходимо привести доказательства перестановки, которые проходят через множество хранений. Используя метод сетевой перестановки [37] нам удастся построить большие перестановки из многих малых.

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

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

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

Для того, чтобы доказать, что наши NIZK доказательства надежны, нам необходимо продумать коэффициенты этих многочленов. Однако, обманывающая доказывающая сторона может создать хранение, не зная как его открыть. Здесь на помощь приходит предположение qPKE :доказывающая сторона приводит не интерактивные доказательства, показывая, что ей «известны» возможности открытия хранений. Под этим мы понимаем существование некоего экстрактора, которому дан тот же вход, так как доказывающий может перестроить хранения вместе с открытиями хранений.

Определения

Пусть будет эффективно вычисляемым бинарным отношением. Для пар будем называть утверждением, а свидетельством. Пусть является NP языком, состоящим из утверждений со свидетельством . Мы ограничиваемся размером и будем писать соответственно и .

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

СОВЕРШЕННАЯ ПОЛНОТА. Понятие полноты подразумевает, что честный доказывающий должен быть в состоянии убедить честного проверяющего, что утверждение верно. Для и всех противников выходящие :

ВЫЧИСЛИТЕЛЬНАЯ НАДЕЖНОСТЬ. Понятие надежности подразумевает неосуществимость для противника появиться с приемлемым доказательством ложного утверждения. Для и всех противников неоднородного полиномиального времени :

СОВЕРШЕННАЯ РАЗЛИЧИМОСТЬ СВИДЕТЕЛЬСТВА. Мы говорим, что не интерактивное доказательство является совершенно различимым доказательством. Для и всех явных интерактивных противников выходящие :

СОВЕРШЕННОЕ НУЛЕВОЕ РАЗГЛАШЕНИЕ. Доказательство является нулевым разглашением, если нет утечки информации помимо верного утверждения. Мы говорим, что не интерактивное доказательство является совершенным нулевым разглашением, если существует моделирующая программа полиномиального времени со свойством последующего нулевого разглашения. дает моделированную ссылку общей строки и модели потайного ключа. принимает общую строку ссылки, формирование потайного ключа и утверждения как вход и создает моделирующее доказательство. Для и явных интерактивных противников выходящие :

Билинейные Группы

ПОНЯТИЕ. Если даны две функции , мы пишем , когда для каждой постоянной . Мы говорим, что функция пренебрежимо мала, когда и безгранична, когда .

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

БИЛИНЕЙНЫЕ ГРУППЫ. Пусть принимает параметр стойкости , записанный в унарной системе как вход и выход, тогда описание билинейной группы будет выглядеть как , где

  1. eсть основной бит.
  2. eсть циклические группы порядка.
  3. eсть билинейная карта (сопряжение) такая как .
  4. Если образует , тогда образует .
  5. Вхождение в может быть эффективно решено, групповые операции и сопряжение эффективно вычисляются, генераторы эффективно вычисляемы и опимание групп и групповых элементов каждый из которых имеет объем бит.

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

Степень разглашения экспоненциального предположения . Знание экспоненты (КЕА) предположения показывает, что, при условии, что даны , неосуществимо создание как без знания а как и . Беллари и Палачио [38] распространили это на КЕА3 предположение, которое говорит, что при заданных неосуществимо создание как без знания так и и .

Степень разглашения экспоненциального предположения является генерацией КЕА и КЕА3. Говорится, что при заданных невыполнимо создание без знания так, что без знания как и

Дадим формальное определение степени разглашения экспоненциального предположения . Вслед за Эйбом и Фейром [32] мы запишем , где на входе дает на выходе и на одном и том же входе (включая ленту случайных вводов ) дает .

TemplateDifinitionIcon.svg Определение «Определение 1.(q-PKE)»
Предположение степени разглашение экспоненциальное сохраняет для , если для всех неоднородных вероятностных противников полиномиального времени существует неоднородный вероятностный экстрактор полиномиального времени , так, что

Вычислительная степень предположения Диффи-Хеллмана (CDH) утверждает, что при заданных неосуществимо вычисление . Вычислительная степень Диффи-Хеллмана предположения является образующей предположения (CDH), которое говорит, что при заданных , за исключением отсутствующих элементов , трудно вычислить отсутствующие элементы.

TemplateDifinitionIcon.svg Определение «Определение 2. (q-CPDH)»
Вычислительная степень предположения Диффи-Хеллмана сохраняет для , если для всех если для всех неоднородных вероятностных противников полиномиального времени , мы имеем

В полной статье мы приводим эвристические доказательства достоверности утверждений q –PKE и q-CPDH, доказывая, что они хранятся в настраиваемой групповой модели.

Хранение сведений

Мы будем использовать вариант схемы хранения Педерсена для наших NIZK доказательств, где мы привязываем к . В доказательство стойкости наших аргументов для 3SAT нам надо удалить сохраненные значения ; сама схема совершенна по части сокрытия сведений и не предъявляет их. По этой причине, мы потребуем у доказывающего создания связанного хранения и будем рассчитывать на предположение q-PKE для удаления сохраняемых величин. Мы называем хранением разглашения, так как доказывающий не может создать надежного хранения без «знания» хранящихся величин.

Образующий ключ: Выберем . Ключ хранения , а ключ потайного входа .

Хранение: Для хранения выберем и рассчитаем хранение сведений как

При заданном мы можем подтвердить его хорошую сформированность, проверяя .

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

Открытие потайного входа: Алгоритм открытия потайного входа по сообщению возвращает рандомизатору . Открытие потайного входа удовлетворяет условию и .

Схема хранения имеет свойства сопоставимые со стандартными схемами хранения Педерсена как показывает теорема, данная ниже. В полной статье мы приводим доказательства ее справедливости.

TemplateTheoremIcon.svg Теорема Теорема 1.
Схема хранения является совершенным потайным входом и привязкой родственных по структуре вычислений. Если предположение q-PKE удерживается, то существует для всех неоднородных вероятностных хранителей полиномиального времени неоднородный вероятностный экстрактор полиномиального времени , который рассчитывает содержание хранения, если задан вход (включая любые случайности).
Доказательство


Доказательство ограничений

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

Установка: .

Общая строка ссылки: Если задан как вход, выбираем случайно и вычисляем общую строку ссылки как .

Утверждение: Достоверное хранение разглашения .

Свидетельство доказывающего: Открытия и и

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

Подтверждение: Выход 1, если только .

TemplateTheoremIcon.svg Теорема Теорема2.
Аргумент ограничения есть совершенно полное, полностью неразличимое свидетельство. Если q-CPDH предположение удерживается, то все вероятностные неоднородные противники полиномиального времени имеют пренебрежимо малую вероятность выходов так, что для некоторых и есть приемлемое доказательство ограничений для хранений соответствующих открытиям.
Доказательство
В полной работе мы приводим доказательство этого. Мы обозначаем надежность доказательства ограничений как невозможность обнаружить открытия хранений так, как это нарушает ограничения. Поскольку схема хранения является полностью скрывающей (Теорема 1), мы не можем исключить существование открытий, которые нарушают ограничения.


Общая строка ссылки

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

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

Образование общей строки ссылки:

На входе и :

  1. Образуйте и
  2. Выберите и вычислите
  3. Образуйте где
  4. Образуйте где
  5. Образуйте где

Общая строка ссылки есть , а возбуждение потайного входа .

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

TemplateLemmaIcon.svg Лемма «Лемма1.»
Если предположение q-CPDH удерживается для с , то противник вероятностный неоднородный полиномиальный имеет пренебрежимо малый шанс обнаружения не тривиальной линейной комбинации , такой как , при заданной случайной общей строке ссылки .


Доказательство произведения

Рассмотрим три хранения

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

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

В конечной сумме левый член уравнения содержит коэффициенты , которые предположительно равны 0, однако, правый член уравнения усложняет. Доказательство будет построено таким образом, что его можно использовать для отмены последнего члена.

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

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

Учтем, так, что аргумент не будет содержать каких-либо коэффициентов формы , то есть коэффициентов или . Если есть некое при котором , тогда мы имеем нетривиальное полиномиальное уравнение с . Исходя из леммы 1, мы имеем возможность открыть и нарушить предположение q-PKE.

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

Утверждение: Хранения .

Свидетельство доказывающей стороны: Открытия и и таковы, что

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

Проверка: выход 1 если и только если

TemplateTheoremIcon.svg Теорема Теорема3.
Доказательство произведения имеет совершенную полноту и полную неразличимость свидетельства. Если удерживается предположение q-CDPH, тогда неоднородный вероятностный противник имеет пренебрежимо малый шанс вывода хранений и принимая доказательство с соответствующими открытиями и таким аргументом , для которого некое получим .
Доказательство
Доказательство можно найти в полной работе.

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

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


Доказательство перестановки.

Рассмотрим два хранения и перестановку

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

По лемме 1 накладываем условия для всех

Для получения желаемой линейной комбинации вычислим и Они имеют дискретные логарифмы

Получаем желаемую сумму и , но из-за дополнительных членов, это не является случаем, когда

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

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

Утверждение: Хранения и перестановки .

Свидетельство доказывающего: Открытия и таковы, что

Доказательство: Вычисляем доказательство как

Проверка: Выход 1, если и только если и

TemplateTheoremIcon.svg Теорема Теорема 4.
Доказательство перестановки имеет совершенную полноту и полную неразличимость свидетельства. Если q-CPDH предположение удерживается, то неоднородный вероятностный противник полиномиального времени имеет пренебрежимо малый шанс открыть перестановку , хранения и допустимый аргумент , который соответствует открытиям хранений и доказательствам таким, для которых некоторые имеют
Доказательство
Доказательство теоремы приводится в полной работе.


NIZK доказательства постоянного размера для схемы выполнимости

Приведем NIZK доказательства для выполнимости И-НЕ схем , которые состоят из постоянного числа групп элементов, но имеет большую общую строку ссылки. Пусть будет выходом цепи схемы. Добавим дополнительные циклы И-НЕ схем для того, чтобы было верным. Это сводит проблему выполнимости к демонстрации того, что существует доказательство истинной величины такое, что оказывается внешне совместимо со всеми И-НЕ схемами. Далее, пусть величина -1 соответствует ложному утверждению, а +1 верному. Теперь мы получаем полное NIZK доказательство, о которм говорилось во вступлении.

CRS: образование общей строки ссылки с .

Утверждение: Схема с И-НЕ схемами, для которой мы доказываем, что цепи могут быть распределенными величинами внутренне совместимыми.

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

Доказательство:

  1. Создать ограниченное хранение к
  2. Создать ограниченное хранение к
  3. Создать ограниченное хранение к
  4. Создать ограниченное хранение к
  5. Создать ограниченное хранение к
  6. Создать ограниченное хранение к
  7. Показать, что и содержат одни и те же величины, приводя доказательство произведения для , которое содержит входное произведение величин (хранение и
  8. Показать, что приводя доказательство произведения для (хранение ), содержащие произведение входных цепей в и
  9. Показать, что величины внутренне совместимы с цепями. Величины могут соответствовать одной цепи. Выберете перестановку так, что она содержит цикл формы для всех последовательностей соответствующей одной и той же цепи. При ведите локазательство перестановки для содержащей перестановку величин в . Для каждой последовательности соответствующей одной цепи, это дает , так что величины должны быть одинаковыми.
  10. Приведите доказательство перестановки для и , показывая, что выходные величины совместимы с входными .(Величины сохраняются. величины соответствуют копиям выходной цепи схемы.
  11. Приведите доказательство произведения для , содержащего обмен величин в .
  12. Приведите доказательство перестановки для , содержащей входное произведение величин в и ( содержит )
  13. Приведите доказательство произведения для , содержащего входное произведение величин в и (содержит )
  14. Покажите, что И-НЕ схемы соблюдаются, приводя доказательство произведения для , содержащего входное произведение величин в и

Доказательство состоит из 6 хранений разглашений с соответствующими доказательствами, 5 доказательствами произведения и 3 доказательств перестановки, которые даны выше. Общий размер составляет 42 групп элементов.

Проверка: Принимаем доказательство, если и только если 6 хранений разглашений хорошо сформированы, их соответствующие доказательства ограничений приемлемы, 5 доказательств произведений приемлемы и 3 доказательства перестановки приемлемы.

TemplateTheoremIcon.svg Теорема Теорема 5.
NIZK доказательства для схемы выполнимости являются совершенно полными и полностью нулевым разглашением. Если q-PKE и q-CPDH предположения удерживаются с , то тогда NIZK доказательство надежно.
Доказательство
Доказательство можно найти в полной работе.


Арифметические схемы. Возможна регулировка NIZK доказательств в соответствии с арифметическими схемами, состоящими из сложения и умножения схем по . Схема хранения является одноморфной, поэтому, если мы умножаем два хранения, мы получаем сумму величин, которые можно использовать для управления схемами сложения. Схемы умножения могут управляться доказательством произведения.

Сокращение общей строки ссылки

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

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

Доказательство перестановки по всему диапазону множества хранений

Рассмотрим две последовательности со значениями и . Будем пользоваться сетью Клоса [37] для приведения доказательства для двух последовательностей хранящихся величин, являющимися перестановками друг друга в открытой перестановке . Идея сети Клоса состоит в создании больших перестановок для малых. Рассмотрим перестановку . Первое, разделим элементы на блоки элементов и переставим элементы в пределах одного блока. Второе, распределим элементы каждого блока равномерно по другим блокам, что даст нам новую последовательность блоков, каждый из которых содержит по одному элементу из предшествующего блока. Снова переставим элементы в каждом блоке. Снова распределим элементы каждого блока равномерно по новым блокам. И, наконец, переставим элементы внутри последнего блока для того, чтобы получить элементы переставленные в желаемом порядке. Перестановки в сети Клоса варьируются в зависимости от , в то время как распределение между блоками фиксируется и от не зависит.

Для того, чтобы привести доказательство перестановки для содержащих те же величины, которые переставлены согласно , доказывающая сторона строит сеть Клоса для перестановки . Создается 4 последовательности промежуточных хранений совместно с доказательством разглашения и доказательством ограничений. Каждое хранение содержит блок величин на средних этапах сети Клоса. Используется доказательство перестановки, рассмотренное в разделе 7, чтобы показать, что для всех пары хранений и содержат одни и те же элементы в порядке перестановки, что продиктовано . Остается проблема приведения доказательств наличия рассредоточенных величин между и , так, что для каждого значения величины распределены по отличных от и приведение доказательств распределения при распределении величин по , так, что для каждого элемента из хранящихся величин они распределяются по . Представляем доказательство дисперсности в разделе 9.2, где используются существующие CRS, состоящие из групп элементов и имеющие размер доказательств группы элементов. Вычисляя стоимость хранений, доказательств перестановок и доказательств дисперсии, мы приходим к размеру групп элементов для доказательства того, что две последовательности хранений величин связываются открытой перестановкой .

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

Доказательство дисперсии

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

У нас есть предположение для конструкции, рассматривая в начале простой случай, где рандомайзеры равны 0. Тогда мы имеем

Применяя дискретный логарифм для обеих сторон уравнения, получаем

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

Утверждение: хранения

Свидетельство доказывающего: открытия

Доказательства: Выберем произвольно и вычислим доказательство как


Подтверждение: выход 1 если и только если



TemplateTheoremIcon.svg Теорема Теорема 6.
Доказательство дисперсии есть совершенно полное и полностью неразличимо свидетельством. Если q-CPDH предположение удерживается, неоднородный вероятностный противник полиномиального времени имеет пренебрежимо малый шанс производить хранения и принимать доказательства с соответствующими открытиями хранений и доказательством, так что и являются хранениями двух различных матриц.
Доказательство
За доказательством обратимся к полной работе.


Контакты авторов материала

  1. University College London, E-mail: j.groth@ucl.ac.uk

Примечание

  1. Эйб и Фейр не исключили возможность существования статистических доказательств NIZK с неадаптивной статистической надежностью, при которой противник очевидно выбирает утверждения общей строки ссылки. Поскольку общая строка ссылки находится в свободном доступе, более естественно было бы определить надежность адаптивно; на самом деле нам неизвестны практические приложения NIZK доказательств с неадаптивной надежностью.
  2. Само предположение о том, что NIZK доказательства являются надежными, кажется нефальсифицированным, а также, если даже противник выдает ложное утверждение с убедительными NIZK доказательствами, может оказаться затруднительным подтвердить его ложность. Грот, Островский и Сахали [30] обходят эту проблему, определяя взаимонадежность языков для , которое является фальсифицированным, так как противник может предъявить свидетельство проверки coNP, удостоверяющее ложность утверждения.
  3. We remark that even if the common reference string is adversarially chosen the sub- linearity of our NIZK arguments impose an information theoretic upper bound on how much information can be leaked. (Перевод google: Отметим, что, даже если общая строка ссылка adversarially выбрали суб-линейность наши аргументы NIZK навязывать информацию теоретико верхнюю границу от того, сколько информации может быть утечка.)

Литература

  1. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proofs. SIAM Journal of Computing 18(1), 186–208 (1989)
  2. Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof sys- tems. Journal of Cryptology 7(1), 1–32 (1994)
  3. Goldreich, O., Krawczyk, H.: On the composition of zero-knowledge proof systems. SIAM Journal of Computing 25(1), 169–192 (1996)
  4. Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its appli- cations. In: STOC, pp. 103–112 (1988)
  5. Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. SIAM Journal of Computing 30(2), 391–437 (2000)
  6. 6,0 6,1 Sahai, A.: Non-malleable non-interactive zero-knowledge and adaptive chosen- ciphertext security. In: FOCS, pp. 543–553 (2001)
  7. 7,0 7,1 Chandran, N., Groth, J., Sahai, A.: Ring signatures of sub-linear size without random oracles. In: Arge, L., Cachin, C., Jurdzin ́ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 423–434. Springer, Heidelberg (2007)
  8. 8,0 8,1 Boyen, X., Waters, B.: Compact group signatures without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 427–444. Springer, Heidelberg (2006)
  9. Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs under general assumptions. SIAM Journal of Computing 29(1), 1–28 (1999)
  10. Barak, B., Canetti, R., Nielsen, J.B., Pass, R.: Universally composable protocols with relaxed set-up assumptions. In: FOCS, pp. 186–195 (2004)
  11. Groth, J., Ostrovsky, R.: Cryptography in the multi-string model. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 323–341. Springer, Heidelberg (2007)
  12. Damg ̊ard, I.: Non-interactive circuit based proofs and non-interactive perfect zero- knowledge with preprocessing. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 341–355. Springer, Heidelberg (1993)
  13. De Santis, A., Di Crescenzo, G., Persiano, G.: Randomness-optimal characteriza- tion of two NP proof systems. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol. 2483, pp. 179–193. Springer, Heidelberg (2002)
  14. Kilian, J., Petrank, E.: An efficient noninteractive zero-knowledge proof system for NP with general assumptions. Journal of Cryptology 11(1), 1–27 (1998)
  15. 15,0 15,1 15,2 Groth, J.: Short non-interactive zero-knowledge proofs. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 321–340. Springer, Heidelberg (2010)
  16. De Santis, A., Persiano, G.: Zero-knowledge proofs of knowledge without interac- tion. In: FOCS, pp. 427–436 (1992)
  17. De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust non- interactive zero knowledge. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 566–598. Springer, Heidelberg (2001)
  18. Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM CCS, pp. 62–73 (1993)
  19. Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC, pp. 723–732 (1992)
  20. 20,0 20,1 Micali, S.: Computationally sound proofs. SIAM Journal of Computing 30(4), 1253–1298 (2000)
  21. Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. In: STOC, pp. 209–218 (1998)
  22. Canetti, R., Goldreich, O., Halevi, S.: On the random-oracle methodology as ap- plied to length-restricted signature schemes. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 40–57. Springer, Heidelberg (2004)
  23. Maurer, U.M., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004)
  24. Bellare, M., Boldyreva, A., Palacio, A.: An uninstantiable random-oracle-model scheme for a hybrid encryption problem. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 171–188. Springer, Heidelberg (2004)
  25. Nielsen, J.B.: Separating random oracle proofs from complexity theoretic proofs: The non-committing encryption case. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 111–126. Springer, Heidelberg (2002)
  26. Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: FOCS, pp. 102–113 (2003)
  27. 27,0 27,1 Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero-knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339–358. Springer, Heidelberg (2006)
  28. 28,0 28,1 Groth, J., Ostrovsky, R., Sahai, A.: Non-interactive zaps and new techniques for NIZK. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 97–111. Springer, Heidelberg (2006)
  29. Boyen, X., Waters, B.: Full-domain subgroup hiding and constant-size group sig- natures. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 1–15. Springer, Heidelberg (2007)
  30. Groth, J.: Simulation-sound NIZK proofs for a practical language and constant size group signatures. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 444–459. Springer, Heidelberg (2006)
  31. Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008)
  32. 32,0 32,1 32,2 32,3 Abe, M., Fehr, S.: Perfect NIZK with adaptive soundness. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 118–136. Springer, Heidelberg (2007)
  33. 33,0 33,1 Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169– 178 (2009)
  34. Naor, M.: On cryptographic assumptions and challenges. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 96–109. Springer, Heidelberg (2003)
  35. Groth, J.: Linear algebra with sub-linear zero-knowledge arguments. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 192–208. Springer, Heidelberg (2009)
  36. Dwork, C., Naor, M.: Zaps and their applications. In: FOCS, pp. 283–293 (2000)
  37. 37,0 37,1 Clos, C.: A study of non-blocking switching networks. Bell System Technical Jour- nal 32(2), 406–424 (1953)
  38. Bellare, M., Palacio, A.: Towards plaintext-aware public-key encryption without random oracles. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 48–62. Springer, Heidelberg (2004)