I want to distinguish different concepts: Bootstrapping, Modular Switching, and Key Switching. I am also sometimes confused about Evaluation & Relinearization.

My understanding of these concepts are:

  1. Bootstrapping is a method to shrink errors in ciphertext.

  2. Modular switching is just an arithmetic technique to transfer, for example, ring elements in $\mathcal{R}_{t}$ into $\mathcal{R}_{q}$.

  3. Key switching is involving an evaluation key (or relinearization key) that basically encrypts secret key to achieve evaluation on homomorphic mult & rotation.

  4. My understanding of evaluation is calculating homomorphic add/mult/rotate/... and relinearization is applying key switching technique to make these evaluation happen. So basically, eval key & relin key are pretty much the same thing with different naming methods?

Am I misunderstanding something here?

Also, is there any state-of-art survey/comparison on these techniques?

Many thanks!


2 Answers 2

  1. Sort of, not really. "Shrink" makes it sound like some process you can repeat until there are "no errors" (which is insecure). I would instead suggest thinking about it as "resetting" the error level. It's a small difference, but makes it clear there is a "lower limit" to how much error one can remove.

  2. Yeah roughly. It might make a bit more sense if you view ciphertexts as secretly being elements of $\mathcal{R}$, rather than $\mathcal{R}_q$ or $\mathcal{R}_t$. The ciphertexts are encoded as $\mathcal{R}$-elements in a particular way, for example as $(a(x), a(x)s(x) + e(x) + \Delta m(x))$ for some scaling factor $\Delta$. Modulus switching is really just a technique for changing this scaling factor $\Delta$. This has the consequence (when $\Delta\mid q$) of "changing plaintext arithmetic" from being mod $q/\Delta$ to $q/\Delta'$, but you could change to some scaling factor $\Delta'\nmid q$ that doesn't really have a "plaintext modulus" that is coherently defined.

  3. Key switching is really a way to change ciphertexts of the form $\mathsf{Enc}_s(m)$ to $\mathsf{Enc}_{s'}(m)$, i.e. to switch the particular key one is encrypting under. You're right it typically involves an evaluation key (often called the key-switching key), but this isn't entirely fundamental to the idea --- if someone had a way to do key-switching without a circular security assumption/a key-switching key, we might all switch to it and still call it "keyswitching". I say not entirely fundamental as a cryptosystem that supports taking any ciphertext $\mathsf{Enc}_s(m)$ and switching it to an arbitrary (potentially attacker-controlled) key is obviously insecure.

  4. Not really. You need to relinearize when you do "tensor-based multiplications". There are other ways to do multiplications though ("gadget based") that don't need to relinearize. You're right that you could call all keys that are not a private/public key an "evaluation key" generically, but not every evaluation key is a relinearization key.

  • $\begingroup$ Thanks for your answer! Clear and helpful. About 2), I actually have a more detailed question. In BGV scheme, what's the relationship between modular switching and encryption levels? I'm confused about this "level" thing and I sometimes mixed it up with RNS representation. I understand it is used to enc/dec ciphertext in specific level. For example, for all L levels, we have Q = Q_0 * ... * Q_L, and if we want to enc/dec a specific level, say level i, we should use Q_i = Q_0 * ... * Q_i as ciphertext moduli, and apply modular switching between Q_i/Q or something? Am I understanding it correct? $\endgroup$
    – Daisy Ding
    Oct 24, 2022 at 8:16

Welcome to Crypto SE : - )

These concepts operate on different levels, so I would first advice you to make a mental diagram of the layers here. On top you have homomorphic encryption in general, which I assume you are already familiar with. It turns out that in all (fully) homomorphic constructions we know of, each ciphertext has some associated noise, and there can be many equivalent ciphertexts that decrypt to the same thing, but have different noises. Typically, when operating on ciphertexts the noise of the result is strictly larger than the noise of operands, and it keeps increasing to the point that ciphertexts become unusable. Bootstrapping prevents this to happen; this technique cleans the ciphertext so that it can further be used in homomorphic operations.

(You might be confused as to why it is called bootstrapping. This is because the technique's ground idea is to homomorphically evaluate the decryption algorithm, e.g., the encryption scheme uses its own decryption circuit to obtain a cleaner ciphertext.)

The rest of the concepts are specific to one particular construction of a homomorphic encryption scheme; please refer to @Mark's answer.

  • $\begingroup$ Thanks for your answer! Can I also ask how in details, for example, mathematically, that Bootstrapping cleans the ciphertext so that the noise level can be low? Or which paper should I look at? $\endgroup$
    – Daisy Ding
    Oct 24, 2022 at 7:55
  • $\begingroup$ This is explained in many papers and presentations, even in Gentry's initial papers. I dare explain how it works but very informally, I won't even define notation. An FHE scheme can evaluate any function given that it can be written as a circuit. As it turns out, this includes the decryption function of itself $d: (k, y) \mapsto DEC(k, y)$. So IF I have $k' = ENC(k, k)$ and $y' = ENC(k, x)$, we can evaluate $d(k', y')$ homomorphically and obtain another ciphertext $y''$ also encrypting $x$. It turns out that $y''$ has less noise than $y'$. Please look for proper expositions. $\endgroup$
    – zugzwang
    Oct 24, 2022 at 11:14
  • $\begingroup$ Thanks! That's very clear. $\endgroup$
    – Daisy Ding
    Oct 25, 2022 at 1:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.