Question on definition of EvalAddCount and KeySwitchCount

Library Questions
1

For longer context, check BGV: Count Add/Keyswitch in one level for OpenFHE by ZenithalHourlyRate · Pull Request #1254 · google/heir · GitHub.

We are trying to provide EvalAddCount and KeySwitchCount parameter from compiler, and we encounter the question what is the exact definition of them. Is it the number of add/keyswitch operations (then we would simply count the number of operations), or is it the number of addition/keyswitch op when the circuit is flattened. My own understanding is the second one.

They are initially defined in “Revisiting Homomorphic Encryption Schemes for Finite Fields, Section 4”, yet later attacks revealed that correctly setting them is crucial, see “Application-Aware Approximate Homomorphic Encryption: Configuring FHE for Practical Use, Introduction, Attacks by Guo et al”, which said that when the circuit is repeated addition of one ciphertext then the EvalAddCount should be set higher, yet neither of these papers gives exact way to calculate EvalAddCount.

We ask for clarification and detailed step to calculate these quantities in the documentation of these APIs in OpenFHE.

Cc @j2kun

1 Like
2

+1, I think the main question here is, when our program iteratively adds the same ciphertexts together (x1 = x+x; x2 = x1+x1; ...), does that imply we should provide a higher EvalAddCount than if the additions are independent? If we should provide a higher count, what is the precise relationship between the circuit and the required value of EvalAddCount?

3

@zenithal @j2kun We are currently revising the Application-Aware FHE paper to include a formal application specification language that would allow a granular description of any circuit. We will share it here once it is ready.

You are right that in order to support the doubling circuit, the EvalAddCount should be set larger, essentially to capture all additions done on the (single) input x. However, this is error-prone and not sufficiently descriptive, which is why we are planning a change.