Why the multiply of BGV/BFV is much slower than CKKS?

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.53k stars 703 forks source link

Why the multiply of BGV/BFV is much slower than CKKS? #522

Closed yzhou79 closed 2 years ago

yzhou79 commented 2 years ago

When I run the performance test, the multiply of BGV/BFV is much slower than CKKS while relinearize's time are almost the same. Is this expected? If yes, is there any math explanation behind this?

/ | Encryption parameters : | scheme: CKKS | poly_modulus_degree: 16384 | coeff_modulus size: 438 (48 + 48 + 48 + 49 + 49 + 49 + 49 + 49 + 49) bits \ Average multiply: 1655 microseconds Average relinearize: 21415 microseconds

/ | Encryption parameters : | scheme: BGV | poly_modulus_degree: 16384 | coeff_modulus size: 438 (48 + 48 + 48 + 49 + 49 + 49 + 49 + 49 + 49) bits \ Average multiply: 15114 microseconds Average relinearize: 22472 microseconds

WeiDaiWD commented 2 years ago

Yes, that is expected. Ciphertext multiplications in the BFV scheme are different from those in BGV or CKKS. Here is an explanation: section 8.2.

Ciphertext multiplications in BGV is slower than those in CKKS because they are stored in different forms. In a future release, ciphertext multiplications in BGV and CKKS will have the same performance.

yzhou79 commented 2 years ago

Thanks Wei. It looks like the divide and rounding operation is not compatible with RNS, so has to work on the base convention way just like the key-switching did. This maybe a reason why need to stay at the non-NTT form to handle the divide and rounding operation, but the dyadic multiplication needs to work in the NTT-form. RNS convention and NTT/INTT are not trivial.

CKKS also has a scale factor just like the BFV, but CKKS uses an approximate way ($q{l-1}/q{l}$) to rescale down the message and the noise. In my opinion, It is fair to include this operation effort when comparing the multiplication with other schemes even this operation is fast as it is an approximate way.

Related to the BGV scheme, you mentioned that BGV will have the same performance with CKKS in the future release. I guess you may put the INTT operation into the key switching and stay at the NTT-form when performing multiplication just like the CKKS did?

Please correct me if I misunderstood. Thanks.

WeiDaiWD commented 2 years ago

stay at the NTT-form when performing multiplication just like the CKKS did

Yes, exactly like that.

jrylost commented 1 year ago

Yes, that is expected. Ciphertext multiplications in the BFV scheme are different from those in BGV or CKKS. Here is an explanation: section 8.2.

Ciphertext multiplications in BGV is slower than those in CKKS because they are stored in different forms. In a future release, ciphertext multiplications in BGV and CKKS will have the same performance.

Since BFV multiplication is much slower than BGV multiplication, is there any advantanges of BFV in Integer computation?