Рейтинг:2

zkSnark: ограничение полинома

флаг et

Я читаю это объяснение zkSnark, написанное Максимом Петкусом - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

Я все понял на первых 15 страницах.

В 3.4 Ограничение многочлена (стр. 16)

Мы уже ограничиваем доказывающего в выборе зашифрованных степеней s, но такое ограничение не применяется, например, можно было бы использовать любые возможные способы найти некоторые произвольные значения $z_p$ и $z_h$ которые удовлетворяют уравнению $z_p = (z_h)^{t(s)}$ и предоставить их верификатору вместо $г^р$ и $г^ч$. Например, для некоторого случайного r $z_h = г^г$ и $z_p = (г^{т(с)})^{г}$, куда $ г ^ {т (с)} $ может быть вычислено из предоставленных зашифрованных мощностей $s$. Вот почему верификатору нужно доказательство того, что он только предоставил шифровки полномочий $s$ были использованы для расчета $г^р$ и $г^ч$ и ничего больше.

Я не могу понять, как доказывающий может найти некоторые произвольные значения $z_p$ и $z_h$ которые удовлетворяют $z_p = (z_h)^{t(s)}$? Например, для некоторого случайного r $z_h = г^г$ и $z_p = (г^{т(с)})^{г}$

Доказывающий не знает $s$ и он тоже не знает $г$, так как он это сделает?

Короче говоря, я не могу понять, что это за атака (от которой нужно защититься), для которой нужно «ограничение полинома».

Рейтинг:3
флаг ru

На странице 15 статьи прувер снабжен $E(s^0)=E(1)=g$ (Я буду называть это $E_0$). Так же они снабжены $$E_1:=E(s), E_1:=E(s^2),\cdots, E_d:=E(s^d).$$ Позволять $t(s)=\sum_{0\le i\le d}c_is^i$$c_i$ известно доказывающему), то $g^{t(s)}=E(t(s))=\prod_{0\le i\le d}E_i^{c_i}$.

Таким образом, доказывающий знает оба $г$ и $ г ^ {т (с)} $ и, как и в газете, они могут выбрать случайный $г$ строить $z_h$ и $z_p$ возведя эти значения в степень $г$.

Смысл атаки в том, что приведенные выше расчеты не требуют знания $р(х)$ это то, о чем доказывающий должен доказывать знание. Проверяющий, достаточно глупый, чтобы поверить, что случайное значение $z_h$ равно $ г ^ {ч (с)} $ и что $z_p$ равно $ г ^ {р (с)} $ не будет ничего, что могло бы противоречить их вере.

флаг et
Я знаю, что уже принял ответ. Тем не менее, я попробовал пример, и это не сработало.
флаг et
E(c) = g^c mod 23. Проверяющая выборка при s = 14 и выдает $E(s^0) = 5$, $E(s^1) = 13$, $E(s^2) = 12 $, $E(s^3) = 3$ Два известных корня: 3 и 4, т. е. $t(s) = (x-3)(x-4)$. Доказывающий выбирает случайное r = 6. t(6) = 3 * 2 = 6. Доказывающий вычисляет $z_h = 5^6 \pmod {23} = 8$ & $z_p = (5^6)^6 \pmod {23 } = 13$ Отправляет $z_p$ и $z_h$ верификатору Верификатор вычисляет t(14) = 11 * 10 = 110. Верификатор вычисляет $E(h)^t = 8^{110} \pmod {23} = 1$. Итак, $E(p) \ne E(h)^t$ Что я делаю не так? Я неправильно понял ваш ответ?
Daniel S avatar
флаг ru
Доказательство не вычисляет $t(r)$, а затем $g^{t(r)}$. Вместо этого они вычисляют $g^{t(s)}=g^{s^2·7s+12}=12·13^{·7}·5^{12}$ и возводят это значение в мощность $r$. Запустив sagemath, мы видим, что $g^{t(s)}\equiv 1\pmod{23}$, поэтому программа проверки устанавливает $z_p=1^r\equiv 1\pmod{23}$ и $z_h=8$ . Затем они вычисляют $z_h^{110}=8^{110}\equiv 1\pmod{23}$, что является тем же самым значением.
флаг et
Хорошо, это проверено!!
флаг et
Я обнаружил еще одну проблему с протоколом, описанным в 3.3. Пусть фактическим истинным 3-м корнем будет 0, т.е. истинный многочлен равен (x)(x-3)(x-4). Даже если доказывающий не знал истинный многочлен и истинный корень, и он предположил, что третий корень равен 2 вместо 0, и что многочлен был (x-2)(x-3)(x-4) и сделать все шаги - шаги все еще проверяются, и проверяющий не будет знать, что доказывающий не знает правильного полинома. Мне было интересно, является ли это отдельной ошибкой с протоколом, описанным в 3.3, или это разновидность того же, что и в 3.4. Я думаю, что это ошибка дифа
Daniel S avatar
флаг ru
Да, проблема в том, что выбранное значение выборки $s=14$ является корнем $t(x)$ по модулю 22, что является порядком группы по модулю 23. Это приводит к $z_p=1$, что вызывает вырождение как Вы нашли. Верификатор должен проверить перед отправкой, что $t(s)\not\equiv 1\pmod{q}$ для большого простого числа $q$, делящего $p-1$. Это очень вероятно, если мы используем большое и сильное простое число.
флаг et
Вы говорите, что обе проблемы (одна описанная в 3.4 и та, которую я указал в моем последнем комментарии) связаны с тем, что $s=14$ является корнем $t(x) \pmod {22}$ или является только одной из них? из-за этого?
флаг et
Итак, я пробовал обе проблемы с s = 16, который не является корнем. И обе проблемы все еще остаются. Таким образом, наличие s в качестве корня t(s) mod (p-1) действительно приводит к тому, что E(p) всегда равно 1, но в противном случае, как это вызывает какие-либо проблемы с протоколом?
Daniel S avatar
флаг ru
У меня нет проблем с $s=16$. Для многочлена $t(x)=x(x-3)(x-4)$ $t(s)=2496$. Для полинома $(x-2)(x-3)(x-4)=x^3-9x^2+26x-24$ доказывающий вычислит $E(s^3)E(s^2)^ {-9}E(s)^{26}E(1)^{-24}=8$. Случайный выбор доказывающего $r=6$ отправляет $z_h=8$ и $z_p=13$. Затем верификатор имеет $z_h^{2496}=3$, что не совпадает с $z_p$.
флаг et
p(x) = x(x-3)(x-4), t(x) = (x-3)(x-4) - так что t(16) = 156, а не 2496. $13^{156} \ pmod {23} \equiv 8$ - значит соответствует

Ответить или комментировать

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