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

CC BY-SA 4.0
2023-07-29T04:53:54.403Z
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.
D.W.
CC BY-SA 4.0
2023-07-29T17:18:00.450Z
@D.W. I've included a brief discussion of the computational model.
Mark Schultz-Wu
<ds.algorithms><fourier-analysis>
Compute Fourier coefficients from Single Fourier coefficient and initial vector?
Mark Schultz-Wu
# Compute Fourier coefficients from Single Fourier coefficient and initial vector?

(Asked by: username_0 on 2023-07-28)

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.

**Tags:** ds.algorithms, fourier-analysis
> **Comments:**
> **username_1**: 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.  
> **username_0**: @D.W. I've included a brief discussion of the computational model.  

---

## 0 answers

