In the OpenFHE paper, the following statement is made:
“If the goal is to minimize the ciphertext modulus Q for the same precision, then the FLEXIBLEAUTOEXT mode is the best option. In some scenarios, the decrease in Q may also result in reduced ring dimension for the same security level, yielding better performance for FLEXIBLEAUTOEXT as compared to all other modes.”
My question is how exactly this works, or how one can determine when this is the case, is there a resource for this, and if so, in which section is it to be found? Thank you.
1 Like
OpenFHE uses the collection of parameter sets defined at openfhe-development/src/core/lib/lattice/stdlatticeparms.cpp at v1.1.4 · openfheorg/openfhe-development · GitHub. These tables are updated versions of the tables 1 and 2 in https://homomorphicencryption.org/wp-content/uploads/2018/11/HomomorphicEncryptionStandardv1.1.pdf The high-level idea is that you if you are close to the \log Q threshold for a given ring dimension (slightly above it), you can go to a twice smaller ring dimension by decreasing slightly \log Q (if the updated \log Q is now below the threshold for the reduced ring dimension).
Note that in the case of hybrid key switching, we work with \log QP rather than \log Q. In the case of BV key switching, we use \log Q to find the smallest secure ring dimension for the desired security level.
If I interpret your response correctly, I understand the table in such a way that by using
StdLatticeParm(HEStd_error, 65536, HEStd_192_classic, 1230),
I achieve a security level of 192 bits with a ring dimension of 65k and a maximum log(Q) value of 1230. If this is the case, how do I specifically reach this maxLog(Q)?
I achieve a security level of 192 bits with a ring dimension of 65k and a maximum log(Q) value of 1230.
Correct.
If this is the case, how do I specifically reach this maxLog(Q)?
The logic is quite tricky:
In the case of BV key switching, \log Q \approx [first mod size] + depth*[scale mod size] + (only for FLEXIBLEAUTOEXT) 20. This estimate may be off by 1-2 bits.
In the case of hybrid key switching, \log QP \approx \log Q (as above) + \lceil \frac{\log Q}{d_{num} \log p_i} \rceil \times \log p_i. Here, \log p_i = 60 (for NATIVE_SIZE=64) and 119 (for NATIVE_SIZE=128). d_{num} is by default set to 3.
For more details on key switching, please see Appendix B of Revisiting Homomorphic Encryption Schemes for Finite Fields
I have just recalculated it based on the formula for hybrid key switching the following values:
FirstModsize = 60, ScaleModsize = 59, Mult Depth = 14, FLEXIBLEAUTOEXT = 20, and dnum = 3, log_P_i = 60.
60 + (14 * 59) + 20 + (60 + (14 * 59) + 20) / (3 * 60)) * 60 = 1208.
This still does not correspond to any value within the table link. For example, I want to achieve 256-bit security for Uniform Ternary. What do I need to adjust for this? Do I need to change some parameters, and if so, which ones? Many thanks in advance.
You need to take the ceiling function of (60 + (14 * 59) + 20) / (3 * 60)), not compute it directly (see my expression). I think at this point we are getting into basic math questions, which is beyond the scope of this forum. You should be able to figure it out on your own.
If you need to find alternative parameters, you can always reduce the scaling mod size or increase d_{num} to make \log QP smaller than a given threshold.
You’re right, that’s the Ceil function. Where can I configure the d_num in the source code?