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

  1. computing the fourier transform $\mathcal{F}(\vec v) := (\mathcal{F}(\vec v)_0,\dots, \mathcal{F}(\vec v)_{n-1})$
  2. 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

  1. compute $\mathcal{F}(\vec v)$,
  2. project it once to get $\vec f_0$
  3. "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

  1. 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

  2. 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.

  • $\begingroup$ I doubt this is possible to answer unless you edit your question to specify the computational model and which operations are expensive and which are inexpensive. It's hard for me to guess how the Fourier transform can be inexpensive to compute by a rotation or projection would be expensive, so I think you need to explain that. $\endgroup$
    – D.W.
    Jul 29, 2023 at 4:53
  • $\begingroup$ @D.W. I've included a brief discussion of the computational model. $\endgroup$
    – Mark
    Jul 29, 2023 at 17:18


Your Answer

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

Browse other questions tagged or ask your own question.