6
$\begingroup$

I was recently reading the paper A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge. Among other things, it discusses an adaption of the "folding" technique (from Bulletproofs) to SIS-based proofs.

The paper measures distances in the $\ell_\infty$ norm (rather than $\ell_2$), and is vague on which choice of embedding it uses (although I imagine it is the coefficient embedding). These choices mean that they pick up extra factors of $n$ when bounding the norm of multiplications in particular.

For example, at one point (on page 20) they want to establish a bound

$$\lVert 8\lambda_i\rVert_\infty \leq 2n^2$$

where $\lambda_i$ is of the form $$\lambda_i = \pm\frac{f}{(X^u-X^v)(X^v-X^w)(X^w-X^u)},$$ $\lVert f\rVert_1 \leq 2$, and it is known that $2/(X^i-X^j)$ has coefficients in $\{-1,0,1\}$ for $i\neq j$. I can establish the desired bound as follows

  1. Write $$8\lambda_i = \pm f \frac{2}{X^u-X^v}\frac{2}{X^v-X^w}\frac{2}{X^w-X^u}$$

  2. For each multiplication, use a result of the form that $\lVert rs\rVert_\infty \leq \lVert r\rVert_\infty\lVert s\rVert_\infty \min(\lVert r\rVert_0,\lVert s\rVert_0)$. In particular, for product-ands $r, s$ non-sparse, we have that $\min(\lVert r\rVert_0,\lVert s\rVert_0) \leq n$, losing us a factor of $n$ on each of the multiplications (not involving $f$), and a factor of 2 on the multiplication involving $f$.

The inequality $\lVert rs\rVert_\infty \leq \lVert r\rVert_\infty \lVert s\rVert_\infty \min(\lVert r\rVert_0,\lVert s\rVert_0)$ (or something very close to it --- perhaps missing a constant factor of 2) should hold as each coefficient in the product $rs$ is the convolution of the coefficients of $r$ and $s$. This convolution has $\min(\lVert r\rVert_0, \lVert s\rVert_0)$ many non-zero terms, and each of these non-zero summands has size at most $\lVert r\rVert_\infty \lVert s\rVert_\infty$.

In particular, this means that when analyzing $\lVert rs\rVert_\infty$, they often (implicitly) bound this as $\lVert rs\rVert_\infty \leq n\lVert r\rVert_\infty\lVert s\rVert_\infty$, picking up an additional factor of $n$ for each multiplication (except for multiplication by $f$, which is sparse).

This is to be contrasted with analysis in the canonical embedding (and the $\ell_2$-norm), where sub-multiplicativity would get one that

$$\lVert 8\lambda_i\rVert_2^{can} \leq \lVert f\rVert_2^{can}(\lVert 2/(X^i-X^j)\rVert_2^{can})^3$$

picking up no extra factors of $n$ along the way (although I believe $\lVert r\rVert_2^{can} = \sqrt{n}\lVert r\rVert_2$, so there may be some implicit factors of $n$ picked up).

I guess my overall question is

Is there some conceptual reason why the canonical embedding seems less popular in work on lattice-based proof systems?

I had been under the impression that when one wants to optimize bounds (especially bounds involving multiplications!) that the canonical embedding is generally preferable due to sub-multiplicativity. But in my cursory reading, the coefficient embedding seems more popular in works on proof systems, and I am interested in knowing why.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.