Я недавно читал газету Подход без PCP к краткому квантово-безопасному нулевому знанию.
Среди прочего, в нем обсуждается адаптация метода «складывания» (из Bulletproofs) к доказательствам на основе SIS.
Бумага измеряет расстояния в $\ell_\infty$ норма (а не $\ell_2$), и неясно, какой выбор встраивания он использует (хотя я предполагаю, что это вложение коэффициентов).
Такой выбор означает, что они получают дополнительные факторы $n$ при ограничении нормы умножения, в частности.
Например, в какой-то момент (на странице 20) они хотят установить границу
$$\lVert 8\lambda_i\rVert_\infty \leq 2n^2$$
куда $\лямбда_i$ имеет форму
$$\lambda_i = \pm\frac{f}{(X^u-X^v)(X^v-X^w)(X^w-X^u)},$$
$\lVert f\rVert_1 \leq 2$, и известно, что $2/(X^i-X^j)$ имеет коэффициенты в $\{-1,0,1\}$ за $i\neq j$.
Я могу установить желаемую границу следующим образом
Написать $$8\lambda_i = \pm f \frac{2}{X^u-X^v}\frac{2}{X^v-X^w}\frac{2}{X^w-X^u}$$
Для каждого умножения используйте результат вида, который $\lVert rs\rVert_\infty \leq \lVert r\rVert_\infty\lVert s\rVert_\infty \min(\lVert r\rVert_0,\lVert s\rVert_0)$. В частности, для продуктов-и $р, с$ неразреженный, у нас есть это $\min(\lVert r\rVert_0,\lVert s\rVert_0) \leq n$, теряя нам фактор $n$ на каждое из умножений (не включая $f$), и коэффициент 2 на умножение с участием $f$.
Неравенство $\lVert rs\rVert_\infty \leq \lVert r\rVert_\infty \lVert s\rVert_\infty \min(\lVert r\rVert_0,\lVert s\rVert_0)$ (или что-то очень близкое к этому --- возможно, отсутствует постоянный коэффициент 2) должен выполняться, поскольку каждый коэффициент в произведении $rs$ является сверткой коэффициентов $г$ и $s$.
Эта свертка имеет $\min(\lVert r\rVert_0, \lVert s\rVert_0)$ много ненулевых членов, и каждое из этих ненулевых слагаемых имеет размер не более $\lVert r\rVert_\infty \lVert s\rVert_\infty$.
В частности, это означает, что при анализе $\lVert rs\rVert_\infty$, они часто (неявно) связывали это как $\lVert rs\rVert_\infty \leq n\lVert r\rVert_\infty\lVert s\rVert_\infty$, получая дополнительный множитель $n$ для каждого умножения (кроме умножения на $f$, что мало).
Это противопоставляется анализу в каноническом вложении (и $\ell_2$-норма), где субмультипликативность получила бы ту, которая
$$\lVert 8\lambda_i\rVert_2^{can} \leq \lVert f\rVert_2^{can}(\lVert 2/(X^i-X^j)\rVert_2^{can})^3$$
не набирая дополнительных множителей $n$ по пути (хотя я верю $\lVert r\rVert_2^{can} = \sqrt{n}\lVert r\rVert_2$, поэтому могут быть некоторые неявные факторы $n$ подобрал).
Я думаю, мой общий вопрос
Есть ли какая-то концептуальная причина, по которой каноническое вложение кажется менее популярным в работе над системами доказательств на основе решеток?
У меня сложилось впечатление, что когда кто-то хочет оптимизировать границы (особенно границы, связанные с умножениями!), то каноническое вложение обычно предпочтительнее из-за субмультипликативности.
Но при беглом чтении мне кажется, что вложение коэффициентов более популярно в работах по системам доказательств, и мне интересно знать, почему.
