google
BGV: Symbolic Noise Analysis for Dependency Tracking
Status
This PR is intended for the symbolic part Symbolic.h/Symbolic.cpp, as this part is big enough.
Also it should be rebased after #1816 is in.
The BGV adoption of it is not comprehensive as it only supports addition/multiplication but it is enough to demonstrate along with (#1782, which would be another PR). Its complete version supporting modulus switching/key switching needs another PR regarding SelectVariableNames. Its extension to BFV is already in a branch (also need SelectVariableNames). CKKS noise analysis could also benefit from it but lets wait until all the TODOs in #1685.
Backgrounds
Recent attacks like GNSJ24, CCP+24, CSBB24 demonstrated that the ability for noise analysis to handle dependent ciphertext is crucial for security.
These attacks exploited the fact that dependency among ciphertext will lead to faster noise growth, and former average-case analysis is not so able to handle them (strong independency assumption).
This approach could handle it but there are some issues. One obvious issue is that is could not scale-up as the number of symbolic terms grows exponentially with the number of multiplication (though there are some optimizations).
HEIR formerly has a pass called openfhe-count-add-and-key-switch in #1254 that could in spirit handle those attacks but it is standalone and not connected to the NoiseAnalysis inside HEIR.
Some experiments
Multiplication of Independent ciphertext
func.func @mul(%arg0 : i16 {secret.secret}, %arg1 : i16 {secret.secret}) -> i16 {
%1 = arith.muli %arg0, %arg1 : i16
return %1 : i16
}
MP24 model
Propagating 28.05 to <block argument> of type 'i16' at index: 0
Propagating 28.05 to <block argument> of type 'i16' at index: 1
Propagating 58.94 to %1 = arith.muli %input0, %input1
Propagating 58.94 to %2 = mgmt.relinearize %1
Propagating 24.08 to %3 = mgmt.modreduce %2
Symbol model: able to handle common dependency like secret key and error in public key (namely #1782)
Propagating 28.05 ... block arg
Propagating 28.05 ... block arg
Propagating 59.23 ... muli
Multiplication of same ciphertext
func.func @mul(%arg0 : i16 {secret.secret}) -> i16 {
%1 = arith.muli %arg0, %arg0 : i16
return %1 : i16
}
MP24: the same as above
Symbol: even higher noise
Propagating 59.73 ... muli
Addition of 4 indep ciphertext
func.func @mul(
%arg0 : i16 {secret.secret},
%arg1 : i16 {secret.secret},
%arg2 : i16 {secret.secret},
%arg3 : i16 {secret.secret}
) -> i16 {
%1 = arith.addi %arg0, %arg1 : i16
%2 = arith.addi %1, %arg2 : i16
%3 = arith.addi %2, %arg3 : i16
return %3 : i16
}
MP24
Propagating 28.05 to <block argument> of type 'i16' at index: 0
Propagating 28.55 to %1 = arith.addi %input0, %input1
Propagating 28.55 to %2 = arith.addi %input2, %input3
Propagating 29.05 to %3 = arith.addi %1, %2
Symbol (should align with MP24)
Propagating 28.05 <block argument>
Propagating 28.55 ... to %1 = arith.addi %input0, %input1
Propagating 28.55 ... to %2 = arith.addi %input2, %input3
Propagating 29.05 ... to %3 = arith.addi %1, %2
Addition of same ciphertext 4 times
func.func @mul(%arg0 : i16 {secret.secret}) -> i16 {
%1 = arith.addi %arg0, %arg0 : i16
%2 = arith.addi %1, %1 : i16
return %2 : i16
}
MP24 (unable to handle faster growth)
Propagating 28.05 to <block argument>
Propagating 28.55 to %1 = arith.addi %input0, %input0
Propagating 29.05 to %2 = arith.addi %1, %1
Symbol
Propagating 28.05 block arg
Propagating 29.05 addi
Propagating 30.05 addi
It looks like you may have spotted it already, but there is this ArithmeticDag framework now with an option to use "SymbolicValue" (https://github.com/google/heir/blob/e44747cff3ed1cdf1209dd730b5cbe2f96649c4d/lib/Kernel/AbstractValue.h#L110) for leaf nodes.
While it doesn't quite meet your needs I imagine, it should be extended/adapted.
