What I am looking for is a function that meets the following criteria:
For each possible input (assume integers from [0, 255]), there must be trillions of possible outputs so as to prevent preimage attacks and is hence probabilistic.
The function must be a one-way hash, so given an output the input cannot be deduced.
The outputs must exhibit additive homomorphism such that some operation on f(a) and f(b) will equal f(a+b).
Is such a scheme possible? I've read many papers that have developed methods close to this, but none that I understand fully meet my criteria.
Paillier exhibits these properties, except it's an encryption scheme as opposed to a hash, meaning it requires public and private keys. In this scheme, there should be no feasible way to "decrypt" an output.
I've found several homomorphic hashing schemes, but each one seems to fall short in some way:
- LtHash is interesting, but not probabilistic, as an input maps to only one output and a small input set should be easy to preimage.
- The cryptosystem proposed in this paper seems like it could be a good fit, but I don't entirely understand how the global vs per-publisher hashing would work.
- This blog post outlines a similar mechanism, but I'm not sure if it's still vulnerable to pre-imaging and always maintains it's homomorphic properties.
I've read through StackExchange, and I've only seen a few posts in the last few years relevant to the question, including this one, but I don't see how Merkle or Hash trees could be used as a solution to these criteria.
The purpose of this function is to obfuscate values in a distributed ledger, while still allowing arithmetic operations to be conducted on them. Paillier would work perfectly if only a public key was distributed, but the potential existence of a private key doesn't work for this scenario, as it would allow one party to read all of the data.
If one of these solutions does, in fact, meet the criteria outlined, a quick explanation as to how would be greatly appreciated. Thanks.