Relinearization
? ? ? ? 重线性化主要是针对密文乘法后密文尺寸膨胀的问题。
? ? ? ? 先来看加解密过程。生成公私钥过程：
????????????????
????????????????
????????????????
? ? ? ? 加解密过程：
????????????????
????????????????
????????????????
? ? ? ? 同态加法及解密正确性：
????????????????
????????????????
? ? ? ? 同态乘法：
????????如果同态乘法是正确的，则有???????：
???????????????????????
? ? ? ? 已知，则可以推出，同态乘法正确计算并解密后的结果为：
???????????????????????
????????其中。
? ? ? ? 可以观察到，密文经过一次乘法后膨胀了，原始密文只有两项，而同态乘法后变为了三项。如果不经处理，一直这样乘下去，那么两次乘法后就会变为五项，三次乘法后就会变为七项......
? ? ? ? 所以需要在每次乘法后进行重线性化，来防止密文尺寸的增加。
重现性化
???????????????我们可以知道，重线性化后的结果应该是：。对重线性化后的结果解密可以得到：
???????????????????????
，观察上式可以看到：。如果存在一组多项式P，满足
，则
，即：
???????????????????????
? ? ? ? 那么现在问题就是如何确定P了。解密过程最多只乘进来一个s，而期待的中s为二次，那么P中一定是包含s的。问题来了：sk是要我们自己偷偷保管的啊，不可以给别人，那么又该怎样把s传到P中呢？用到的就是evaluation key。
evaluation key
????????令，则
。同时可以看到，evk中添加了两个随机化参数，可以保证s不泄露。
? ? ? ? 所以可以设置，
???????。但是问题又来了：
，
较大。
? ? ? ? 解决办法就是更改下evk的形式，设置，其中
。
????????故而，
。
Rescaling
????????为了保证计算精度，在编码过程中预先乘入了缩放因子。两次乘法后缩放因子就又膨胀了，变为
。
????????设置，
。
代表整数部分精度，
代表小数部分精度。则有重缩放过程：
???????????????????????