FHE math chatgpt discussions

2025-07-17   blogpage sketch fhe

A ChatGPT discussion about relinearization and modulus switching:

• When is bootstrapping performed?
  

  • When noise grow too big
    

  • bootstrapping is the performance bottleneck of FHE, very expensive
    

• When is relinearization performed?
  

  • After each homomorphic multiplication
    

• When is modulus switching performed?
  

  • Very frequently, almost after each operation
    

  • computationally cheap
    

• As each modulus switching decreases the modulus, doesn't modulus become too small after a while?
  

  • Yes.
    

  • When modulus became too small, you do bootstrapping, which resets the modulus to a new number.
    

  • Leveled FHE schemes, which uses modulus switches, become having a low modulus after a while. At that point, they just stop working. For that reason, you can do limited number of multiplications with leveled FHE's (Recall that multiplications increase the noise multiplicatively).
    

Another ChatGPT discussion:

• Why does ciphertext have two components in FHE? e.g. (A, b) where b = A*s + m + e? Where A is random matrix, s is secret key, m is the message (plaintext), and e is noise.
  

  • It's a design for decryption. Decryption uses the random A matrix. The decryption equation is, b - A*s = m + e. Then m is recoverd by rounding the m+e to the nearest integer. As you can see, e is expected to be small, so that goes away by rounding. That's why FHE schemes strives to keep e (noise) small by bootstrapping and modulus switching and other tricks.
    

  • The reason CKKS uses a 'scaling factor' is to scale real numbers to integers, so that the noise is small enough to be rounded away. Lattice-based schemes assume working with integers.
    

    • CKKS rescales the integers by the scaling factor after each multiplication, as multiplications also multiplies the scaling factor.
      

• Why is matrix A chosen at random?
  

  • Because A is regenerated randomly for each encryption. So that each ciphertext is unique, even thought the plaintext and the secret key are the same. This is to avoid the attacker to learn the relationship between the plaintext and the ciphertext, which is called known-plaintext attack, or ciphertext distinguishability attack or chosen-plaintext attack (CPA). The protection against this attack is called semantic security, which is achieved by non-deterministically generating new ciphertext for each encryption.
    

• FHE schemes keep track of Ratio of noise size to modulus. So that they will decrease the noise after exceeding a certain threshold.