- using a regular hash or AES_k, which should work in the same way, but salt/AES key needs to have sufficient security and only known by trusted parties (e.g., the user who is computing the sum). aka, the hash sum would be the user's own bookkeeper, and other people should not trust that result.

> AdHash initially received the most attention by several works which aimed to implement the construction [SY98, CL99, GSC01], each using a 128-bit or 256-bit modulus. However, Wagner [Wag02] later showed an attack on the generalized birthday problem which could be used to find collisions for AdHash on an n-bit modulus in time O(2^{2\sqrt{n})), and that the AdHash modulus needs to be greater than 1600 bits long to provide 80-bit security. Lyubashevsky [Lyu05] and Shallue [Sha08] showed how to solve the Random Modular Subset Sum problem (essentially equivalent to finding collisions in AdHash) in time O(2^{n^\epsilon}) for any \epsilon < 1, which indicates that AdHash requires several more orders of magnitude larger of a modulus just to provide 80-bit security.

On Saturday, May 3, 2025 at 8:07:54 PM UTC+8 Greg Maxwell wrote:

On Saturday, May 3, 2025 at 11:55:28 AM UTC Sanket Kanjalkar wrote:
> hash(UTXO_A||salt) + hash(UTXO_B||salt) - hash(UTXO_C||salt) - hash(UTXO_D||salt) == 0 (proving (A==C && B==D) || (A==D && B==C))

What if instead of hash we encrypt with AES and modular add/subs? I cannot prove it; but I also don't see a clear way this is broken.

1. Sample random symmetric key `k`
2. Instead of above; AES_k(UTXO_A) + AES_k(UTXO_B) - AES_k(UTXO_C) - AES(UTXO_D) == 0 => (proving (A==C && B==D) || (A==D && B==C))?

AES in CTR mode is, I'm not sure about other modes? Obviously CTR mode would be unsuitable! (I mean sure modular add/sub and xor are different operations but they are quite close). I think that in many modes the collision resistance would have to at least be restricted by the birthday bound with the small block size. I think CMC might be needed to avoid that sort of issue.