Приветствуем! Впервые на сайте Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with monthly highlights on ecosystem growth, network development and how to get started with Zcash!

Язык

Разбираем SNARK, часть 1: Гомоморфная схема шифрования

Ariel Gabizon | Feb 28, 2017

Конструкция zk-SNARKs включает в себя точную комбинацию нескольких составляющих; полное понимание механизма взаимодействия этих составляющих требует некоторого времени.

Если бы мне пришлось выбрать одну составляющую, выполняющую самую важную роль, то это было бы то, что мы называем гомоморфным схемой шифрования (Homomorphic Hiding или HH) [1]. В этой статье мы объясним, что это такое и на примере покажем, в чем его эффективность и как оно устроено.

Гомоморфное шифрование \(E(x)\) числа \(x\) представляет из себя функцию, удовлетворяющую следующие условия:

Вот простенький пример эффективности гомоморфного шифрования в работе доказательств с нулевым разглашением: Допустим, Алиса хочет доказать Бобу, что ей известны значения \(x,y\) через их сумму \(x+y=7\) (конечно, не самая интригующая задачка, но на примере с такими значениями \(x,y\) удобно объяснить суть концепции).

  1. Алиса отправляет \(E(x)\) и \(E(y)\) Бобу.
  2. Боб вычисляет \(E(x+y)\) с помощью присланных ему значений (что возможно, поскольку \(E\) является гомоморфным шифром).
  3. Боб также вычисляет \(E(7)\) и проверяет верно ли утверждение \(E(x+y)=E(7).\) Он принимает доказательство Алисы, только если оба вычисления равны.

Потому как разные входные данные преобразуются \(E\) в разные шифры, Боб примет доказательство, только если Алиса отправит ему зашифрованные \(x,y\) при которых \(x+y=7.\) С другой стороны, Боб не узнает самих значений \(x\) и \(y,\) потому что располагает только шифрами, образованными от них [2].

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

Пусть \(n\) является некоторым целым числом. Когда мы записываем \(A\;\mathrm{mod}\;n\) для \(A,\) то это значит, что мы берем возвращающий остаток от целочисленного деления \(A\) на \(n.\) Например, \(9\;\mathrm{mod}\; 7 = 2\) и \(13\; \mathrm{mod}\;12 = 1.\) Мы можем использовать \(\mathrm{mod}\; n\) чтобы задать дополнительное условия для \(\{0,\ldots,n-1\}:\) мы производим повторяющееся сложение, а затем применяем \((\mathrm{mod}\; n)\) к результату, чтобы вернуть число в ряд \(\{0,\ldots,n-1\}.\) Иногда мы добавляем \((\mathrm{mod}\; n)\) к правой части, чтобы показать, что мы используем данный тип вычисления. Например, \(2+3 = 1\; (\mathrm{mod} \;4).\) Мы называем множество чисел \(\{0,\ldots,n-1\}\) с этим дополнительным вычислением группой \(\mathbb{Z}_n\).

Для простого числа \(p\) мы можем использовать вычисление \(\mathrm{mod}\;p\), чтобы задать операцию умножнния для ряда \(\{1,\ldots,p-1\}\) так, чтобы его результат также принадлежал к ряду \(\{1,\ldots,p-1\}\). Для этого мы проделаем операцию умножения, а затем \(\mathrm{mod}\; p.\) [3] Например \(2\cdot 4=1\; (\mathrm{mod}\; 7).\)

Это множество элементов вместе с вычислением по модулю p называется группой \(\mathbb{Z}_p^*\). \(\mathbb{Z}_p^*\) обладает следующими полезными свойствами:

  1. Эта группа циклична, что значит, что существует элемент \(g\) группы \(\mathbb{Z}_p^*\), который называется порождающий, и все элементы группы \(\mathbb{Z}_p^*\) можно записать как \(g^a\) для некоторого \(a\) в группе \(\{0,..,p-2\}\), где \(g^0=1.\)
  2. Задача вычисления дискретного логарифма считается трудноразрешимой для \(\mathbb{Z}_p^*\). Это значит, что если p является большим числом, а \(h\) является элементом \(\mathbb{Z}_p^*\), довольно сложно найти целое число \(a\) в \(\{0,..,p-2\}\), так чтобы \(g^a=h\;(\mathrm{mod}\;p).\)
  3. Т.к. "экспоненты добавляются когда элементы перемножаются", то для \(a,b\) в \(\{0,..,p-2\}\) \(g^a\cdot g^b = g^{a+b\;(\mathrm{mod}\;p-1)}.\)

Используя эти свойства мы можем построить схему гомоморфного шифрования, которая "поддерживает сложение" - в смысле такую, где \(E(x+y)\) можно вычислить из \(E(x)\) и \(E(y).\) Предположим, что \(x\) от \(E\) входит в множество \(\mathbb{Z}_{p-1}\) и таким образом принадлежит \(\{0,\ldots,p-2\}.\) Задаем условие, что \(E(x)=g^x\) для каждого такого \(x\), а \(E\) является гомоморфным шифром: первое свойство говорит нам о том, что разные исходные значения \(x\) в \(\mathbb{Z}_{p-1}\) преобразуются в разные конечные результаты. Второе свойство, что для \(E(x)=g^x\) довольно сложно найти \(x\). И согласно последнему свойству, имея \(E(x)\) и \(E(y)\), мы можем вычислить \(E(x+y)\) через \(E(x+y) = g^{x+y\;\mathrm{mod}\; p-1} = g^x\cdot g^y = E(x)\cdot E(y).\)

[1]Строго говоря, гомоморфная схема не совсем то, что используется в криптографии, и этот термин приведен здесь скорее в дидактических целях. Это нечто похожее на довольно известную схему обязательства скрытого вычисления, только менее эффективную. Разница между ними в том, что гомоморфная схема является определяющей функцией исходных данных, в то время как схема обязательств дополнительно использует рандомность. Как следствие, гомоморфная схема "скрывает большинство x", а схема обязательств - "все возможные x".
[2]Боб узнает некоторую информацию об x и y. Например, он может задать x' рандомное значение и проверить, будет ли x=x' через E(x'). По этой причине данный протокол не является протоколом с нулевым разглашением и используется здесь только в образовательных целях. В сущности, гомоморфная схема используется в snarks чтобы скрыть задачи проверяющей стороны, нежели секреты доказывающей.
[3]Когда p не является простым числом, становится проблематично составить вычисление подобным образом. Одной из причин является то, что результатом вычисления может стать 0, даже когда обе независимые переменные не равны 0. Например, при p=4 мы можем получить 2*2=0 (mod 4).