search

microsoft / SEAL

Microsoft SEAL is an easy-to-use and powerful homomorphic encryption library.
https://www.microsoft.com/en-us/research/group/cryptography-research/
MIT License
3.55k stars 706 forks source link

Confused by the rounding operation in multiply_add_plain_with_scaling_variant #664

Closed halfmanli closed 11 months ago

halfmanli commented 1 year ago

The comment of multiply_add_plain_with_scaling_variant in native/src/seal/util/scalingvariant.cpp says "Coefficients of plain m multiplied by coeff_modulus q, divided by plain_modulus t, and rounded to the nearest integer (rounded up in case of a tie). Equivalent to floor((q m + floor((t+1) / 2)) / t)". Why is the rounding operation used here? According to the paper, which says: image Thus, we just need to calculate $\Delta m_p = \lfloor q / t \rfloor m_p$, where $m_p$ is the plaintext added to the ciphertext. It seems that we don't need to round to the nearest integer.

fionser commented 11 months ago

Old BFV paper describes $\Delta = \lfloor q/t\rfloor $. However, current SEAL uses another formula to achieve a smaller nosie growth ${\sf round}(q/t\cdot m_p)$ Some follow up papers also use this formula e.g., Revisiting Homomorphic Encryption Schemes for Finite Fields

halfmanli commented 11 months ago

This makes sense. Thank you!