# When is the number-theoretic transform of small vectors again small?

I am currently working on an idea in the context of lattice-based cryptography, but the problem that I am currently stuck on seems to have almost nothing to do with lattices anymore.

In particular, my problem refers to the "Number-theoretic Transform" (NTT), i.e. the discrete weighted Fourier Transform in the context of a finite field, when applied to small vectors. So let $$p$$ be a prime with $$p \equiv 1 \mod 2n$$ ($$n$$ a power of two), thus there is a primitive $$2n$$-th root of unity $$\zeta \in \mathbb{F}_p$$. Furthermore, we consider all "short" vectors $$y \in \mathbb{Z}^n \setminus \{0\}$$ (e.g. $$\|y\|_\infty \leq O(1)$$, $$\|y\|_2 \leq O(\sqrt{n})$$, etc. - I am not yet sure about what is the best notion here). Now we can consider the NTT of $$y$$, i.e. $$\hat{y}_k = \sum_{i = 0}^{n - 1} y_i \zeta^{ik} \in \mathbb{F}_p \quad \text{where k \in (\mathbb{Z}/2n\mathbb{Z})^*}$$ I don't think it makes much difference, but notice that this is not the standard DFT, but the evaluation at all primitive $$2n$$-th roots of unity.

The question is now: Can it happen that there is some short $$y$$ such that for "most"/all $$k$$, also $$\hat{y}_k$$ is small, e.g. bounded by $$p/4$$ (technically, we mean that the absolute value of the shortest lift of $$\hat{y}_k \in \mathbb{F}_p$$ is small)? If yes, can we say something about the primes $$p$$ where this happens? Do they have to be rare?

Any ideas/related problems/references are welcome, I am more asking for some directions to explore than for a proof or solution.

I am currently not sure which notions of small or most are best. I am interested in an asymptotic setting (as $$n, p \to \infty$$), and the example notions should give an idea of my idea of "small".

The context As I said, I do not think it is relevant here, but if you are interested - feel free to skip it: I want to prove a fact about a lattice whose dual depends on the "unit vectors" in the decomposition $$\mathbb{F}_p[X]/(X^n + 1) \cong \bigoplus_{i = 1}^n \mathbb{F}_p$$ via $$f \mapsto (f(\zeta^k))_k$$. This plays an important role in RLWE-based cryptography. The unit vectors are clearly $$n^{-1} \sum_i X^i \zeta^{ki}$$, and thus the above NTT of short $$y$$ appear naturally when taking the inner product of a short vector $$y \in \mathbb{Z}[X]/(X^n + 1)$$ with a shortest lift of of some "unit vector" (the used inner product is the one in the Minkowski space, but for $$n$$ power of two, it is equivalent to the coefficient-wise inner product).

While not being the angle that I approached this from, I think there is a much more fundamental reason why this problem appears: In RLWE, we consider "error vectors" $$e$$ that are short in the Minkowski-space norm (thus in the coefficient norm). The security of cryptosystems depends on the fact that the solution to linear equations over $$\mathbb{F}_p[X]/(X^n + 1)$$ is hard to find, if the equations are "perturbed" by such an error. If now a not-too-small amount of these errors were also small in the decomposition of $$\mathbb{F}_p[X]/(X^n + 1)$$ as $$\mathbb{F}_p^n$$ (or even just distinguishable from uniform), then one could find the error in each component separately, thus breaking RLWE.

My ideas so far I have tried to investigate a probabilistic approach. This gives a trivial bound in the case that we have an additional constant that is chosen at random - i.e. $$c\hat{y}_k$$ is not small for all $$y$$ and many $$k$$, assuming we pick specific $$c \in \mathbb{F}_p$$ and require that $$p$$ is absolutely huge compared to $$n$$. While the constant itself is not problem at all in my case, the "absolutely huge" is. In particular, my bound holds even when replacing the $$\zeta^{ik}$$ with almost arbitrary, fixed elements. I would really hope that we can better in the case of roots of unity.

However, using a probabilistic approach here seems very difficult, as the dependency between $$p$$ and $$\zeta$$ seems very intractable.

I am sorry for asking such a fuzzy question here. I am mainly working with cryptographers, and so I don't have the opportunity to discuss this kind of question with a pure mathematician at my institution.

• This seems like an interesting question, but I am not sure which terms are fixed and which are variable. Which regime are you working in? That is, are you fixing $n$ and considering $p$ as going to infinity, and then asking for whether a desirable $y$ exists, or are you considering both $n,p$ as fixed? Commented Mar 14 at 20:26
• Basically, I am considering the setting that $n$ is fixed and $p \to \infty$. Nevertheless, I am mainly interested what happens for large $n$. Commented Mar 15 at 9:09