zkSnark Intro от Максима Петкуса: Многочлен определен над $Z$ или над $Z_n$?

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

Здесь у него многочлен $p(x) = x^3 ≈ 3x^2 + 2x$

и гомоморфное шифрование, определяемое как $E(c) = g^c \bmod 7$

Немного неясно, где определяется полином над $Z$ или это определено более $Z_7$ - в тексте осталось немного двусмысленности.

Это имеет значение на этапе, когда верификатор оценивает $E(h.t) = E(h)^t$. Я могу лучше объяснить свой вопрос с помощью $Z_{11}$ вместо $Z_7$, поэтому я использую $Z_{11}$ ниже.

Предположим $E(c) = g^c \bmod 11$

Образцы верификатора при s = 14

$E(s^0)= 5, E(s^1)= 9, E(s^2) = 5, E(s^3) = 9$

Доказательство вычисляет $E(p(s)) = (9 * 5^{-3} * 9^2) \bmod 11 = 9$

вычисляет $Е(ч(с)) = 5$. Отправляет E(p)= 9 и E(h) = 9 верификатору

Верификатор вычисляет t(s=14) Рассмотрим два случая

Дело 1: Полином закончился $Z$ В этом случае t(s=14) = (13*12) = 156 Так $Е(ч)^т$ = $9^156 \bmod 11 = 9$

Итак, он проверяет -> $E(p) = E(h)^t$

Случай 2: Полином закончился $Z_{11}$ В этом случае t(s=14) = (13*12)%11 = 2 Так $Е(ч)^т$ = $9^2 \bmod 11 = 4$. Вот не проверяет.

Причина, по которой он не проверяет, заключается в том, что

$g^c \bmod м$ = $g^{c \bmod m-1} \bmod m$

т. е. t(s) необходимо уменьшить на 10, а не на 11. Однако, если многочлен превышает $Z_{11}$, то оно уменьшается на 11, а не на 10.

Итак, исходя из этого, я думаю, что полином определяется над $Z$ а не более $Z_7$.

Однако на странице 7 он пишет

в то время как теоретически полиномиальные коэффициенты $c_i$ может иметь широкий диапазон значений, в действительности он может быть весьма ограниченным (6 в предыдущем примере)

Откуда взялась 6? Если все кончено $Z$, то коэффициент может быть любым целым числом. Если он пишет, что количество ограничено 6, значит, должно быть больше. $Z_n$. Если бы это было кончено $Z_7$, то он будет ограничен 7, а не 6. Если бы он закончился $Z_6$, то она будет ограничена 6$.

Итак, полином определен или $Z$ или это определено более $Z_7$ или это определено более $Z_6$?

Что мы хотели бы для самых общих приложений, так это для $р(х)$ быть определено более $\mathbb Z$. Однако не существует общей конечной гомоморфной криптографической схемы, в которую мы можем инъективно отображать элементы $\mathbb Z$. Вместо этого мы должны отобразить в большое поле простых чисел (обратите внимание, что в разделе 3.2 не используется область целочисленности), чего должно быть достаточно для демонстрации знаний о $р(х)$ построенный из малых целых корней. Эта группа представлена ​​как подгруппа простого порядка любой криптографической группы, которую мы используем (мы можем работать в полной группе, но, как уже отмечалось, это приводит к проблеме, связанной с тем, что она не является целостной областью). В случае с группой $(\mathbb Z/7\mathbb Z)^\times$, группа имеет порядок 6, и мы должны думать, что для целей проверки $р(х)$ определяется над $\mathbb Z/6\mathbb Z$ если мы не заинтересованы в работе в целостной области. В вашем моде 11 пример поэтому $р(х)$ следует рассматривать как полином по модулю 10 (опять же игнорируя проблемы нецелочисленных областей). Как вы можете заметить, небольшие примеры, подобные этому, сталкиваются со всевозможными проблемами неоднозначности, которые становятся исчезающе маловероятными по мере того, как размер подгруппы растет относительно размера и количества корней.