How to understand these concepts in HE: Bootstrapping, Modular Switching, Key Switching, Evaluation, Relinearization?

DDD

10/24/23, 2:39 AM

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:

Bootstrapping is a method to shrink errors in ciphertext.
Modular switching is just an arithmetic technique to transfer, for example, ring elements in $\mathcal{R}_{t}$ into $\mathcal{R}_{q}$.
Key switching is involving an evaluation key (or relinearization key) that basically encrypts secret key to achieve evaluation on homomorphic mult & rotation.
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!

243

2 + 0

homomorphic-encryption

Score:1

Crypto

Mark

10/24/23, 3:08 AM

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

+ 1

DDD

10/24/23, 8:16 AM

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?

Score:1

Crypto

zugzwang

10/24/23, 6:06 AM

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.

+ 3

DDD

10/24/23, 7:55 AM

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?

zugzwang

10/24/23, 11:14 AM

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.

DDD

10/25/23, 1:27 AM

Thanks! That's very clear.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to understand these concepts in HE: Bootstrapping, Modular Switching, Key Switching, Evaluation, Relinearization?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.