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.



Your Answer

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