1
$\begingroup$

There seems to be a quantity, often denoted $\gamma$, such that the $l_2$ norm of a product of two polynomials can be written as the product of the norms, up to multiplication by $\gamma$.

For instance if $f$ and $g$ are two polynomials, we have $\|fg\|\leq\gamma\cdot\|f\|\|g\|$. For example, see Section 2 of this paper. I can find information for the factor in terms of vectors, but I don't understand it in terms of polynomials.

Where does this quantity come from? What results do we know about it? How is computed for different rings, or maybe even modules?

$\endgroup$

1 Answer 1

4
$\begingroup$

I encourage you to read section 3.1 of Generalized Compact Knapsacks are Collision Resistant, where it is first defined. The answers to your questions are:

I can find information for the factor in terms of vectors, but I don't understand it in terms of polynomials.

The idea behind the "Expansion Factor" way of defining a norm on $R = \mathbb{Z}[x]/(f(x))$ is to use what is called the "coefficient embedding" $\sigma : R \to\mathbb{R}^{\deg f}$, and then simply take the (standard) norm of vectors within $\mathbb{R}^{\deg f}$. The coefficient embedding takes some input $r(x)$, reduces it mod $f(x)$ to obtain a unique representative of $r(x)$ within $\mathbb{Z}[x] + \langle f(x)\rangle$ (it is the unique representative of degree $< \deg f$), and then reads off the coefficients of this unique representative as a vector. This is to say that the norm you are working with is defined such the destinction between "$r(x)$ the polynomial" and "$\vec r$ the vector" is intentionally very small.

Where does this quantity come from?

It is essentially defined because the desired relationship $\lVert g(x)h(x)\rVert \not\leq \lVert g(x)\rVert\lVert h(x)\rVert$ does not hold, where $\lVert\cdot\rVert$ is the norm induced on $R$ by the coefficient embedding. One can define the expansion factor such that an approximate version of this inequality holds, i.e. $\lVert g(x)h(x)\rVert \leq \gamma \lVert g(x)\rVert\lVert h(x)\rVert$. If you view this as being the goal of defining it, it should be relatively clear to see why the expansion factor takes that precise definition that it does.

As for why we want an expression like this to hold, you should view it as being similar to a "multiplicative" version of the triangle inequality. Essentially, when working with a norm on some algebraic structure, things work much better if your norm "respects" your algebraic structure. For rings, this means that the norm is sub-additive (also known as satisfying the triangle inequality) and sub-multiplicative (meaning satisfies $\lVert g(x)h(x)\rVert \leq \lVert g(x)\rVert \lVert h(x)\rVert$), or even only "approximately" so (say up to a "fudge factor" of $\gamma$).

What results do we know about it?

There are some general results bounding it (that are discussed in the linked paper), but many authors do not work with it much anymore because there is a "better" way to define a norm on $\mathbb{Z}[x]/(f(x))$ that directly leads to sub-multiplicative constructions without needing to introduce a "fudge factor" (which is essentially what the expansion factor is doing). See section 4.3.3 of Piekert's survey A Decade of Lattice Cryptography for details. The norm defined using the expansion factor is often called the coefficient embedding, the norm that is by default sub-multiplicative is often called the Minkowski or Canonical embedding.

Note that the Canonical embedding has other advantages besides that of analyzing expressions --- it corresponds to evaluating a polynomial on a number of points, i.e. to a "Fourier Transform" type of operation. While computing this representation is less efficient than just reading the coefficients off of some polynomial, once you have computed it you get certain computational benefits (faster multiplication algorithms).

How is computed for different rings, or maybe even modules?

It is computed for a few examples in that paper, but for the most part I think the answer is "it isn't". It has been computed for a number of "common" rings if you want to use it (including some general results --- see the paper), but many authors just use the Minkowski embedding, which circumvents the issue of forcing a certain norm to be sub-multiplicative.

Note that things like the expansion factor can show up in other "lattice crypto adjacent" areas. For example, in this recent paper the authors need to define/analyze similar quantities for a "Big Integer" version of lattice cryptography (see this paper for the motivation for calling it that). Of course, it is possible that this is an indication that the "wrong norm" is being used for analysis, and if people could just find the "right norm", they would not need to define the expansion factor (arguably this is what happened for norms on $\mathbb{Z}[x]/(f(x))$). Time will tell.

$\endgroup$
2
  • 1
    $\begingroup$ Excellent answer! $\endgroup$ Commented Mar 31, 2021 at 0:26
  • $\begingroup$ Thanks so much! $\endgroup$
    – a196884
    Commented Mar 31, 2021 at 15:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.