While using binary gates. Why ciphertext should be independent
If you are referring to the check inside EvalBinGate, there are two reasons for the ciphertexts to not be equal, and implicitly, for their associated errors to be independent.
The parameters for correctness and security are estimated under the assumption that the input ciphertexts to a circuit are independent https://eprint.iacr.org/2020/086.pdf. This allows for a smaller error expansion and smaller parameters. Furthermore, when you know that (two of) the inputs to a gate are identical, then you already know the result of that gate if it is a binary gate and therefore you do not need to compute it homomorphically (AND and OR return the same value, XOR returns 0, XNOR returns 1), or you can instead compute a gate with fewer inputs if it is a multi-input gate.
Hi, for homomorphic addition of an array I am using ripple carry adder which is designed with the help of binary gates. So for some inputs I am getting this error. so can you tell me how to fix this?
Can you replace the binary gates which have the same input ciphertext for both input wires with the corresponding result the way I mentioned above? x AND x = x, x NAND x = neg(x), x OR x = x, x NOR x = neg(x), x XOR x = 0, x XNOR x = 1.
@andreea.alexandru the first is always true, in the second case, in the real world you cannot know if it is the same ciphertext arriving at both inputs of a gate. Think about building an adder, multiplier etc, for an nbit integer. Then at the application layer what if the integer is operated on with itself (happens all the time, y = x*x etc).
@sam what I have found to work is take one input of your adder, and
NOT(NOT(x)) each input bit.
Additionally, it is not expedient to manually simplify gates for standard combinatorial circuits as they are often complex (for example I just built a 32b Baugh Wooley Multiplier see here).
We will be releasing a basic C++ integer math library based on binfhe in a couple months. It is not complete, but it has very fast add/sub/compare.
To clarify: from a performance perspective, if it is possible in your circuit, it is always better to rewrite gates which have the same inputs. You can also always test before a gate whether the inputs ciphertexts are equal and then replace the gate functionality; but that can become burdensome.
When this is not possible and simply creating a fresh encryption of the same plaintext is also not possible, the solution is to re-randomize one of the input ciphertexts, in order to refresh the noise and uncorrelate it from the noise of the other input. Performing NOT(NOT(ct)) bypasses the equality check, but does not actually refresh the noise because EvalNOT does not perform bootstrapping. So you do not want to apply this solution too often, because the noise estimate would not be valid anymore. The safe solution (more expensive, since it involves bootstrapping) which uncorrelates the ciphertext from its original version is to perform AND between your ciphertext and a fresh encryption of 1. Finally, for completeness and going technical, the noise can be uncorrelated also by doing ct’ = ct + Enc(0). However, not doing bootstrapping on ct’ immediately after (this would be equivalent to performing the AND gate above), but rather evaluating another gate on ct and ct’ would be similar to evaluating a gate with three inputs, whose noise estimate differs from a gate with two inputs.
Bottomline, to use the library as intended, i.e., to have guarantees on the correctness and security of the parameters, the same input ciphertext should not be supplied to a gate. If there are no ways of avoiding this, then you need to refresh one of the inputs, e.g., by doing ct AND Enc(1). Efficient solutions such as NOT(NOT(ct)) and ct + Enc(0) can be used (infrequently) in practice, but they do not come with formal guarantees. There have been proposed attacks tweaking the evaluated circuits to cause error overflows, so such safeguards are important. Interested readers can check https://eprint.iacr.org/2024/203.pdf.