3
$\begingroup$

How to determine the homomorphic encryption CKKS scheme's parameter bounds for correctness and 128-bit security using some specific floating-point numbers and specific computation metrics like summation or variance?

Any formal proof and theoretical process to decide the parameters like polynomial degree and so on?

$\endgroup$
4
  • 1
    $\begingroup$ "Correct" usually is equated to mathematical correctness within Cryptography. I'm wondering if "How to determine the parameter bounds for a given security level" would better fit the question. $\endgroup$
    – Maarten Bodewes
    Jul 26, 2023 at 15:51
  • 1
    $\begingroup$ @MaartenBodewes-onstrike CKKS is only approximately correct. Different choices of parameters will lead to homomorphic computations that are more/less correct. $\endgroup$
    – Mark Schultz-Wu
    Jul 26, 2023 at 18:54
  • $\begingroup$ @Mark I stand corrected :)_ $\endgroup$
    – Maarten Bodewes
    Jul 26, 2023 at 20:49
  • $\begingroup$ @Mark yep, CKKS is approximately correct. Here I mean we ignore approximation. The correctness here I mean is totally correctness where noise does not make decryption fail. $\endgroup$
    – macknight
    Jul 27, 2023 at 15:01

1 Answer 1

1
$\begingroup$

This question has no easy answer. There are already two things to be considered for setting the parameters: the security of the underlying RLWE sample and the noise budget you need.

  1. Security of the RLWE sample: this affects how you need to choose your ciphertext moduli with respect to the ring dimension and the standard deviation of the error you are adding. There are some great tools to determine these. First, many libraries have in-build functions for these purposes. Second, there is the HE Standard https://projects.csail.mit.edu/HEWorkshop/HomomorphicEncryptionStandard2018.pdf, and lastly there is the lattice estimator, that will tell you how many bits of security you get for your parameter sets against most known lattice attacks https://github.com/malb/lattice-estimator.

  2. The second part of setting CKKS parameters is to choose them such that your computation carries through without the noise obliterating your message. Decryption will never fail in CKKS in the sense that the algorithm aborts. Unless a library has implemented some safe guards, the decryption algorithm will always return you some result. However, the noise in CKKS is not stripped away during decryption, as for example in BGV or BFV. Therefore it accumulates in the lower bits and grows generally larger the more operations you perform on a ciphertext. It eventually will swallow the plaintext result and all you get is gibberish. So generally: the bigger your parameters are, the more computations you will be able to perform. How exactly the noise in CKKS grows, and how best to estimate it to set parameters has been the topic of some papers over recent years, for example https://eprint.iacr.org/2022/162. You then need to look at the circuit you want to evaluate, combine the noise estimates accordingly and that should give you a general idea of how big you need to choose your parameters at the start, to still have the precision in the end. But this can also be a lot of try and error, and there is no standard way to go about this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.