I have some vector $\vec v\in\mathbb{Z}_q^n$, and would like to obtain $n$ vectors $\vec f_0,\dots, \vec f_{n-1}$ where $\vec f_i = (\mathcal{F}(\vec v)_i,0,\dots,0)$, i.e. each vector is a single fourier coefficient $\mathcal{F}(\vec v)_i$ (note that my Fourier transform $\mathcal{F}$ is actually a number-theoretic transform. I doubt this matters). One could do this by
- computing the fourier transform $\mathcal{F}(\vec v) := (\mathcal{F}(\vec v)_0,\dots, \mathcal{F}(\vec v)_{n-1})$
- Rotating and projecting this vector appropriately
In my particular computational paradigm (related to Fully Homomorphic Encryption), rotations and projections are extremely expensive though. Ideally, I could
- compute $\mathcal{F}(\vec v)$,
- project it once to get $\vec f_0$
- "update this in-place" to get $\vec f_1, \vec f_2$, etc.
Here "update in-place" doesn't mean anything too formal. Ideally, there would some efficient way to write $\vec f_1$ as a small modification of $\vec f_0$, i.e. compute $\vec f_1$ from $\vec f_0$ and $\vec v$ in $o(n)$ $\mathbb{Z}_q$ operations.
Does such a way of quickly computing $\vec f_1$ from $\vec f_0$ and $\vec v$ exist?
Condensed Description of the Computational Model
Vectors are actually polynomials in $R_q:=\mathbb{Z}_q[x]/(x^{n}+1)$ for $n = 2^k$ where $k\in\mathbb{N}$. They are actually plaintexts of ciphertexts, which are roughly pairs of polynomials $(a,b)\in R_q^2$ such that there exists a third polynomial (the secret key) such that
$$b(x)-a(x)s(x) = (q/p)v(x)+e(x),$$
where $v(x)$ is a polynomial encoding the message we want to compute. The $(q/p)$ is included so you can (eventually) round the noisely-encoded message $(q/p)v(x)+e(x)$ to remove the "error polynomial" (required for security) to obtain $v(x)$.
This computational model supports efficient additions of two ciphertexts encrypted under the same key (it is pair-wise addition of the polynomials). Multiplication by publicly-known polynomials is also fine (there is some nuance to make sure, when multiplying by $c(x)$, that the new error $c(x)e(x)$ does not get too large. It can be handled). Homomorphic multiplication of two encrypted polynomials can be done, but is much more complex.
To efficiently compute an encryption of $\mathcal{F}(\vec v)$, I can compute $\mathcal{F}(\vec v)$ using standard techniques, and then encrypt this (this is sort of cheating, but works in my target application). To compute rotations, one generally applies a Galois automorphism to the pair $(a(x), b(x))$, i.e. maps them to $(a(x^i), b(x^i))$. This now decrypts to $(q/p)m(x^i)+e(x^i)$ under the modified secret key $s(x^i)$. To obtain an encryption with respect to the initial secret key $s(x)$, one must
include an encryption of $s(x^i)$ with respect to $s(x)$, i.e. an overhead of $O(n^2 \log q)$ space to include all $O(n)$ such automorphisms
compute multiplication of this encryption with our initial encryption (that we applied the galois automorphism to), i.e. a comparitively-hard operation.
For projections, there is a similar story. Roughly speaking, projecting a polynomial to its constant coefficient is equivalent to taking what is known as a "Field trace" over the cyclotomic field $\mathbb{Q}[x]/(x^n+1)$. There are semi-efficient ways to do this (which require $O(k)$ Galois automorphisms rather than $O(n)$), but it is still more expensive than other operations.
