Do any probabilistic hashing algorithms have additive homomorphism?
The outputs must exhibit additive homomorphism such that some operation on $f(a)$ and $f(b)$ will equal $f(a+b)$.


Because $f$ is mandated to be nondeterministic, I assume that the requirement be that $f(a) \odot f(b)$ be some possible output $f(a+b)$ (for some computable operation $\odot$).

If so, there must be some further requirement; here's one $f$ function that meets the above requirements in a spectacularly unuseful way:

$f(x)$ is a nondetermanistic function that ignores the input $x$ and generates a random bit string of length $n$ (for a suitably large value of $n$).

Then:


For any input, there are $2^n$ possible outputs; if $n$ is large enough, this easily meets the 'trillions of possible outputs'
Examining the output does not allow the input to be deduced - obviously true.
There must be an operation on $f(a)$ and $f(b)$ that yields a possible output of $f(a+b)$ - for this, we can pick any arbitrary operation $\odot$ that maps two $n$ bit inputs to an $n$ bit output, and then we have $f(a) \odot f(b)$ is a possible output of $f(a+b)$.


Obviously, this function $f$ is unlikely to solve the specific problem you have in mind - what additional requirements are there?