Desilo / liberate-fhe

A Fully Homomorphic Encryption (FHE) library for bridging the gap between theory and practice with a focus on performance and accuracy.
https://docs.desilo.ai/
BSD 3-Clause Clear License
104 stars 9 forks source link

The recovered message breaks when the values are > 2^60. #4

Open juwhan-k opened 7 months ago

juwhan-k commented 7 months ago

Albeit decrypt and decode uses the by-the-book approach in recovering the message by using only the base channel, the fused version decrode does bias-guarding when an extra channel is available. However, the bias-guard only fixes the overflow of the first (DC) overflow. The bias guard consumes one level. That results in confinement of the recovered message into $-2^{60} < . < 2^{60}$ range. However, in the presence of yet another level (consuming one more level) after all the homomorphic operations, we can use 2 channels to recover the message and overcome the range limit.

If the base channel was denoted as b, and the extra channel e, we can convert the RNS representation $(e, b)$ to a Mixed Radix System (MRS) $(e', b)$, and then apply decrypt/decode (also may apply bias-guard) to each channel. Then sum them by $m = m_e * qb +m b$, where me is the recovered message from $e'$, $m{b}$ is from $b$, and $q_{b}$ is the base channel prime.

Additional computational cost will be minimal, since the MRS conversion is for only 2 channels. Also, it should be selectively performed according to the number of channels remaining after evaluating the homomorphic circuit, whatever that is.