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

From CryptoWiki
Jump to: navigation, search

Доказательства с нулевым разглашением на основе спариваний (Pairing-based Zero-Knowledge arguments, PBZK) - доказательства с нулевым разглашением, построения которых опираются на группы билинейных спариваний.

Contents

Основные определения

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

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

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

  • Полнота (Completeness): Доказывающий может убедить Проверяющего, если утверждение действительно верно.
  • Корректность (Soundness): Любой, даже нечестный доказывающий, не может убедить проверяющего, в верности ложного утверждения.

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

  • Нулевое разглашение (Zero-knoeledge): Любой, даже нечестный проверяющий, ничего не узнает, кроме того факта, что утверждение верно.

Необходимо различать понятия вычислительного нулевого разглашения (computational zero-knowledge) - Проверяющий не сможет ничего узнать о доказательстве за полиномиальное время, и идеального нулевого разглашения (perfect zero-knowledge) - Проверяющий, даже с неограниченными вычислительными возможностями, ничего не сможет узнать о доказательстве.

Спаривание (pairing)

Пусть (G1, +) - циклическая аддитивная группа порядка p, (G2, *) - мультипликативная группа порядка p, где p - большое простое число.

Билинейным отображением (спариванием) называется отображение:

e: G1 × G1 → G2,

которое обладает следующими свойствами:

  • Аддитивность:

∀ R, S, T ∈ G1: e(R + S, T) = e(R, T)e(S, T);

  • Невырожденность:

∀ R, S, T ∈ G1: e(R, S + T) = e(R, S)e(R, T);

Следствия из определения:

  • e(R,0) = e(0,R) = 1;
  • e(-R,S) = e(R, -S) = e(R, S)^(-1);
  • Билинейность: e(R, S) = e(aP, bP) = e(P, P)^(ab) = e(S, R).

История

Доказательства с нулевым разглашением, введенные Голдвассером, Микали и Ракоффом [1], являются фундаментальными блоками в криптографии, которые используются в многочисленных протоколах. Первые доказательства с нулевым разглашением основывались на интерактивном взаимодействии доказывающего с проверяющим, несмотря на то, что многие криптографические задачи решаются автономно: например, подпись или шифрование. Для таких задач желательно иметь неинтерактивные доказательства с нулевым разглашением (non-interactive zero-knowledge - NIZK), для которых не предусмотрено взаимодействие между сторонами, а подтверждение представляет собой единичное сообщение от Доказывающего Проверяющему. Блум, Фельдман и Микали [2] ввели NIZK-доказательства в модель общей строки, когда и доказывающая и проверяющая стороны имеют доступ к общей строке, созданной доверенным способом. Такие NIZK-доказательства широко применимы, начиная от защиты криптосистем с открытым ключом от атак на основе подобранного ранее шифрованного сообщения [3],[4], заканчивая недавно разработанными схемами подписи [5],[6].

Повышение эффективности NIZK-доказательств

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

Эвристический метод Фиата-Шамира

С помощью эвристического метода Фиата-Шамира можно получить весьма эффективные NIZK-доказательства, которые защищены в модели со случайным оракулом. Например, доказательство с нулевым разглашением на основе интерактивного доказательства с общедоступной монетой (interactive public-coin proof) сублинейного размера [7] можно перевести в NIZK-доказательство сублинейного размера [8]. Однако, существуют протоколы, обеспечивающие защиту в модели со случайным оракулом, но не обеспечивающие ее в обычной модели, независимо от того, какая хэш-функция применяется. Таким примером является схема подписи, основанная Голдвассером и Калаи [9] на идентификационной схеме интерактивного доказательства с общедоступной монетой.

Доказательства с предназначенным Проверяющим

Другим способом обхода неэффективности стандартных NIZK-доказательства является использование неинтерактивных доказательств с предназначенным Проверяющим. В доказательствах с предназначенным Проверяющим доказательство не подлежит общедоступной проверке, оно может быть проверено только определенным Проверяющим. Дамгард, Фазио и Николоси [10] разработали эффективное, работающее за линейное время, неинтерактивное доказательство с предназначенным Проверяющим для решения задачи об истинности булевой схемы (CircuitSAT), основой которому послужила криптосистема Пэйе.

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

Так же для повышения эффективности NIZK-доказательств используются билинейные группы. Грот, Островский и Сахали [11],[12] предоставили NIZK-доказательства для задачи об истинности булевой схемы (CircuitSAT), состоящее из O(n) элементов группы, где n это количество входных переменных в схеме. Такие NIZK-доказательства обладают следующим свойством: они обеспечивают либо идеальную корректность и вычислительное нулевое разглашение, либо вычислительную корректность и идеальное нулевое разглашение. В работах Боуена, Грота и Сахали [13],[14],[15],[16] проведены исследования о возможности построения эффективных NIZK-доказательств, которые могут быть непосредственно применены к билинейным группам вместо задачи об истинности булевой схемы (CircuitSAT). В отдельных случаях, например, в кольцевой подписи Чандрана, Грота и Сахали [5], эти методики приводят к NIZK-доказательствам сублинейного размера, но, в общем, число элементов группы в NIZK-доказательствах зависит линейно от размера утверждения. Эйб и Фейр [17] предложили схему, основанную на схеме обязательств вместо шифрования, при этом размер схемы увеличивался линейно, так как фиксация значения необходима для каждой передачи.

Размер NIZK-доказательств

Доказательства вычислительной корректности (Computational Soundness proof) Микали [18] показали возможность привести NIZK-доказательства к сублинейному размеру, но, несмотря на десятилетние исследования в этой области, эвристический метод Фиата-Шамира является единственным известным методом для построения NIZK-доказательств сублинейного размера. Однако, был введен новый тип NIZK-доказательств сублинейного размера, в которых стойкость системы не зависит от модели случайных оракулов[19]. NIZK-доказательства для задачи об истинности булевой схемы (CircuitSAT) обладают свойствами: идеальной полноты (perfect completeness), вычислительной корректностью (computational soundness) и идеальным нулевым разглашением (perfect zero-knowledge) (определения понятий см. в след. разделе). NIZK-доказательства являются краткими и очень эффективными для проверки, но Доказывающий должен использовать сверхлинейное число групповых операций. За основу берется NIZK-доказательство, состоящее из группы с конечным числом элементов, равному длинне общей строки. Затем, размер общей строки уменьшается за счет увеличения размера NIZK-доказательства, делая их одновременно сублинейного размера в схеме.

Pairing-based ZK-доказательства

Математический аппарат

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

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

Пусть R - эффективно вычисляемое бинарное отношение. Для пар (C, w) ∈ R, будем считать C утверждением, а w докадками (witness). Пусть L является NP-языком, состоящим из утверждений с догадками в R. При ограничении утверждения до размера N будут приняты обозначения LN и RN соответственно.

Неинтерактивное доказательство для отношения R состоит из алгоритма, генерирующего общую строку, K , алгоритма Доказывающего P и алгоритма Проверяющего V. Генератор общей строки принимает на вход секретный параметр k размера N (возможны добавочные входы) и создает общую строку σ. Доказывающий принимает на вход (σ, C, w) и создает доказательство π. Проверяющий принимает на вход (σ, C, π) и выдает на выходе 1, если доказательство принято, или 0, если доказательство отклонено.

(K,P,V) - доказательство для R, если оно обладает свойствами полноты и корректности, которые описаны ниже.

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

Pr[σ ← K(1^k, N); (C, w) ← A(σ); π ← P(σ, C, w): V(σ, C, π) = 1 if (C, w) ∈ R] = 1.

Вычислительная корректность. Понятие корректности подразумевает невозможность предоставления приемлемого доказательства ложного утверждения противником (нечестным Доказывающим). Для NkO1.png и всех противников неоднородного полиномиального времени A:

Pr[σ ← K(1^k, N); (C, π) ← A(σ): C ∉ L and V(σ, C, π) = 1] ≈ 0.

Идеальная неразличимость догадок (Perfect witness-indistinguishable). Неинтерактивное доказательство (K, P, V) является доказательством с идеально неразличимыми догадками, если среди множества догадок нельзя предсказать какая из них принадлежит Доказывающему. Для NkO1.png и всех явных интерактивных противников A:

Pr[σ ← K(1^k, N); (C, w0, w1) ← A(σ); π ← P(σ, C, w0): (C, w0),(C, w1) ∈ RN and A(π) = 1] =

= Pr[σ ← K(1^k, N); (C, w0, w1) ← A(σ); π ← P(σ, C, w1): (C, w0),(C, w1) ∈ RN and A(π) = 1].

Идеальное нулевое разглашение. Доказательство обладает свойством нулевого разглашения, если не раскрывается информация об утверждении, помимо того факта, что оно истинно. Неинтерактивное доказательство (K, P, V) обладает свойством идеального нулевого разглашения, если существует модель полиномиального времени S = (S1, S2) со следующим свойством нулевого разглашения. Выход S1 моделируют общую строку и секрет (trapdoor). S2 принимает на вход общую строку, смоделированный секрет и утверждение, и создает моделирующее доказательство. Для NkO1.png и явных интерактивных противников A:

Pr[σ ← K(1^k, N);(C, w) ← A(σ); π ← P(σ, C, w): (C, w) ∈ RN and A(π) = 1]= =Pr[(σ, τ) ← S1(1^k, N);(C, w0, w1) ← A(σ); π ← S2(σ, τ, C): (C, w) ∈ RN and A(π) = 1].

Предположения q-PKE и q-CPDH

Пусть даны две функции f, g: ℕ → [0,1]. Обозначение f(k) ≈ g(k) означает, что |f(k) − g(k)| = O(k^(−c)) для любой константы c > 0. Функция f пренебрежимо мала, если f(k) ≈ 0 и максимальна, если f(k) ≈ 1.

Запись y = A(x; r) означает, что алгоритм A принимает на вход x и случайную величину r, и получает на выходе y. Запись y ← A(x) означает, что случайной величине r присваивается некоторое значение и устанавливается значение y = A(x; r). Запись y ← S выбор y случайным образом из S. [n] обозначает набор значений {1, 2, …, n}.

Билинейные группы. Пусть G-biliniar.png принимает на вход секретный параметр k, записанный в унарной системе, и получает на выходе описание билинейной группы (p, G, GT, e) ← G-biliniar.png(1^k), где

  1. p - k-разрядное простое число.
  2. G, GT - циклические группы порядка p.
  3. e: G × G - билинейное отображение (спаривание) такое, что ∀a, b: e(g^a,g^b) = e(g,g)^(ab).
  4. Если g образует G, тогда e(g, g) образует GT.
  5. Отношение G, GT может быть эффективно решено, эффективно вычисляются групповые операции и спаривание e , эффективно вычисляемые генераторы и описания групп и их элементов имеют объем O(k) бит.

Стойкость NIZK-доказательств основана на двух предположениях: q-PKE (q-power knowledge of exponent assumption) предположение о знании показателя степени мощности q и q-CPDH (computational power Diffie-Hellman assumption) предположение о вычислительной проблеме Диффи-Хеллмана мощности q.

Предположение q-PKE. Предположение о знании показателя степени (КЕА) показывает следующее. При известных g, g^α, невозможно вычислить c, c' такие, что c' = c^α, не зная а такого, что c = g^a и c' = (g^α)^a. Существует и КЕА3 предположение, которое говорит следующее. При известных g, g^x, g^α, g^(αx) невозможно вычислить c, c' такие, что c' = c^α, не зная a0, a1 таких, что QPKEc1.png и QPKEc2.png.

Предположение q-PKE является обобщением КЕА и КЕА3. При известных QPKEg.png невозможно вычислить c, c' такие, что c' = c^α, не зная a0, …, aq таких, что QPKEc3.png и QPKEc4.png.

Обозначение (y; z) ← (A || χA)(x), где A принимает на вход x на выходе получает y и χA принимает на вход то же, что и A (включая ленту случайных вводов A), и получает на выходе z.

Формальное определение предположения q-PKE. Предположение q-PKE сохраняется для G-biliniar.png, если для любого неоднородно вероятностного противника полиномиального времени A существует неоднородно вероятностный экстрактор полиномиального времени χAтакое, что

QPKE.png

Предположение q-CPDH. Предположение о вычислительной проблеме Диффи-Хеллмана (CDH) говорит, что при известных g, g^β, g^x невозможно вычислить g^(βx). Предположение q-CPDH является обобщением предположения о вычислительной проблеме Диффи-Хеллмана (CDH): при известных QCPDH1.png, за исключением отсутствующих элементов QCPDH2.png, трудно вычислить эти отсутствующие элементы.

Формальное определение предположения q-CPDH. Предположение q-CPDH сохраняется для G-biliniar.png, если для всех j ∈ {0, …, q} и для всех неоднородно вероятностных противников полиномиального времени A выполняется следующее:

QCPDH.png

Принцип построения

В данном разделе приведен принцип построения NIZK-доказательства постоянного размера для задачи об истинности булевой схемы (CircuitSAT).

Условия

Для NIZK-доказательств для булевой схемы C существуют входные данные, которые дают на выходе 1. Если убрать постоянный фактор, то можно предположить, что C полностью состоит из НЕ-И(NAND = Not AND)-элементов. Если обозначить промежуточные выходные значения как a, то к схеме можно добавить самоконтролирующийся цикл (self-loop), состоящий из НЕ-И-элемента, где a = ¬(a ∧ b), тем самым гарантируя а принмать значение 1. Это упрощает сложную задачу доказательства того, что имеется распределение истинных значений последовательностей, которые отвечают всем N = |C| НЕ-И-элементам в схеме.

NIZK-доказательства основываются на схемах обязательств, снижающих длину, при этом можно зафиксировать n величин в конечном поле Zp , используя только группу с конечным числом элементов. Схема обязательств должна быть гомоморфной, то есть при комбинировании двух фиксаций (commitments) получается новая, равная образу от суммы соответствующих входных значениий. Для доказательства свойств фиксированых величин (committed values) также используются неинтерактивные доказательства, состоящие из групп с конечным числом элементов:

Входное произведение (Entry-wise product): Фиксированные величины (commitments) c, d, v представляют собой наборы a1, …, an, b1, …, bn и u1, …, un соответственно, которые удовлетворяют условию: ui = ai * bi для всех i.

Перестановка (Permutation): Фиксированные величины c, d, состоящие из a1,…,an и b1,…,bn, удовлетворяют условию: bi = aρ(i) для всех i, при которых ρ - открытая перестановка n элементов.

Принцип работы

Гомоморфные фиксации (commitments) совместно с представленными выше двумя видами неинтерактивных доказательств дают постоянный размер NIZK-доказательства задачи об истинности булевой схемы (CircuitSAT), в которой n = 2N. Доказывающий получает догадки (witness) задачи об истинности булевой схемы (CircuitSAT) a1 … aN и b1 … bN, где ai, bi - входные значения соответствующие элементу i схемы и все величины совместимы с выходными последовательностями и соотнесены с НЕ-И-элементами.

Значение 0 соответствует ложному утверждению, а 1 истинному, следовательно, если ui выход i-го элемента схемы, то 1 - ui = ai * bi.

Доказывающий создает фиксации к 2N-кортежам.

(a1…aN,b1…bN) (b1…bN, 0…0) (u1…uN, 0…0)

Доказывающий предоставляет доказательство входного произведения для c, d, v фиксаций (a1…aN,b1…bN), показывая, что ai=ai^2 и bi=bi^2 для всех i. Это показывает, что a1…aN, b1…bN ∈ {0,1} являются соответствующими истинными величинами.

Выход одного НЕ-И-элемента может быть входом другого НЕ-И-элемента, следовательно соответствующие величины Index1.png должны иметь одинаковое распределение. Доказывающий выбирает перестановку ρ, которая содержит циклы i1 → i2→ … → il → j1+N → j2+N → ⋯ → jm+N → i1 для всех наборов величин, которые должны быть согласованы и отвечать доказательству перестановки (permutation argument) для фиксации (a1…aN,b1…bN). Таким образом, для каждого набора величин, соответствующих одному и тому же выходу, где Index2.png значения (a1…aN,b1…bN) согласованы с данной схемой. Доказывающий использует дополнительные фиксации и доказательства произведения входов (entry-wise product) и перестановки (permutation), чтобы показать, что другие фиксированные величины (b1…bN, 0…0) и (u1…,uN, 0,…0) согласованы со схемой и величинами (a1…aN,b1…bN).

Доказывающий использует доказательство входного произведения (entry-wise product argument), чтобы показать, что произведением (a1…aN,b1…bN) и (b1…bN,0…0) является (1-u1…,1-uN,0,…0). Последняя фиксация для (1-u1…,1-uN,0,…0) может быть получена из фиксации к (u1…,uN, 0,…0) при помощи гомоморфных свойств схемы обязательств.

Применение предположений

Схема обязательств является вариантом схемы обязательств Педерсена (Pedersen commitment scheme), в которой ключ фиксации (commitment key) определяется в виде: Index3.png. Фиксацией a1,…,aq является элемент группы, который может быть вычислен по формуле: Index4.png.

Плюсом схемы обязательств является то, что дискретный логарифм является полиномом Index5.png. При вычислении спаривания от двух фиксаций будет получено произведение двух полиномов, возведенных в некоторую степень. Применяя линейные комбаниции над произведением двух полиномов, можно представить входные произведения (entry-wise products) и перестановки (permutations) в виде уравнений над коэффициентами этих полиномов. Предположение q-CPDH позволяет сделать вывод об идентичности этих коэффициентов и о том, что фиксированные значения являются произведением (entry-wise multiplication) друг друга или перестановкой (permutation). При вычислении спариваний от фиксаций (это эквивалентно умножению многочленов в степени), появится много перекрестных условий. Роль неинтерактивных доказательств будет состоять в отмене этих условий. Обычно, вычисление спаривания элемента группы с g, оказывается достаточным для отмены всех перекрестных условий, поэтому неинтерактивные доказательства для входных произведений и перестановок сами по себе высокоэффективны.

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

Глоссарий

Библиографический указатель

Перейти к списку использованных источников.

Ларина Т., 2016