Parallelizing blind rotation (proposed by Misheel)

Fix two parameters $q \approx 2^{64}$ and $N \approx 4096$; $N$ must be a power of $2$, but $q$ can be any integer. We will work in the cyclotomic ring mod $q$: $R = \mathbb{Z}[X] / (q, X^N + 1)$.

A plaintext will be any data you can store on your computer and work with. A ciphertext will be an encryption of an element of $R$; you do not need to worry about the encryption scheme. However, the encryption scheme gives you access to the following operations, with relative costs:

• (0): Any computation on plaintext.
• (0): “Encrypt” a plaintext element of $R$, turning it into a ciphertext.
• (0): Add two ciphertexts.
• (1): Multiply a ciphertext by a plaintext element of $R$.
• (12): Multiply a ciphertext by a special ciphertext.

(A “special ciphertext” is a special kind of ciphertext which very valuable, and correspondingly hard to produce. For the purposes of this problem, you cannot make your own special ciphertexts — you can only use ones that are given to you.)

Warmup: Single blind rotation

You are given a plaintext tuple of integers mod $2N$: $(a_1, a_2, ..., a_n)$. You are also given $n$ special ciphertexts (corresponding to a secret key): $s_1, s_2, ..., s_n$; each of them is either the constant polynomial $0$ or $1$. You want to produce a single ciphertext encrypting $X^m$, where $$m = a_1 s_1 + a_2 s_2 + \cdots + a_n s_n.$$

Hint to the warmup:

If $acc$ (an accumulator polynomial) is a ciphertext, you can compute $$\text{$acc'$ = ($acc$ if $s_i = 0$) or ($X^{a_i} * acc$ if $s_i = 1$)}.$$

The total cost is $13n$.

The real problem: Several blind rotations in parallel.

You have $k$ different $n$-tuples $(a_1^i, a_2^i, \ldots, a_n^i)$. Your goal is to get $k$ ciphertexts: for each $1 \leq i \leq k$, you want to get an encryption of $X^{m^i}$, where $m^i = \sum s_j a_j^i$.

Again, each $a_j^i$ is a number mod $2N$, and each $s_j$ is either $0$ or $1$.

You can assume you have special ciphertexts encrypting the $s_i$’s. If you like, you can also assume you have additional special ciphertexts, depending only on the $s_i$’s – these have been preprocessed for you.

If you repeat the naive procedure above, it will take time $13kn$. Can you do the calculation more efficiently?

One possible direction: Can you do something with a Fourier transform? (You are free to choose a suitable value of $q$.)

Motivation

This calculation would let us make fully homomorphic encryption (FHE) more efficient.

An FHE scheme allows you to encrypt messages (polynomials, say) in such a way that someone can operate on the messages without knowing the secret key. An FHE ciphertext has “error”, which grows as homomorphic operations are performed. If we want to perform many operations, we need a way to decrease the error; this is known as “bootstrapping”.

Most FHE schemes use an encryption algorithm like the following: a ciphertext has the form $(a_1, ..., a_n)$, and $a_1 s_1 + \cdots + a_n s_n = m + e$, where $m$ is the message, and $e$ is a small value (the “error”). The encryption scheme guarantees that $m$ is, say, a multiple of $2^{10}$ — so as long as $|e| < 2^{9}$, the message can be decrypted unambiguously.

The “blind rotation” trick is as follows. Let $f$ be the polynomial $\sum a_{i} X^i$, where $a_{i}$ is $-i$ rounded to the nearest $2^{10}$. Then the constant term of $X^{m + e} * f$ is precisely the rounding of $m + e$ to the nearest $2^{10}$ — that is, it is precisely $m$.

SO: Using the method above, you can convert an encryption of $m+e$ (with large error) to an encryption of $X^{m+e} * f = m$ (with much smaller error).