Get your bingo out,'cause we 'll be rollin' hard for this one.

Hash inversion is a hard problem. At first it seems very dissimilar to what AI is good for.

It's a mapping between two spaces. But whereas AI is also building an associative table between two space in the most smooth manner, a good hash algorithm, tries to make this table as scrambled as possible.

For bad hash algorithm like differentiable perceptual hash, they can be reverted, using optimization technique like in AI (aka gradient descent), where we use the differentiability property to get a hint for the direction to modify the input so that the output hash is closer to the target hash.

But when the hash function is not differentiable, all seems lost, as the technique can't be applied. So you use the, familiar to Haskell's monad enthusiasts, trick : Lifting !

In order to use the specificity of your hash function, you go back to its definition. You write it as a boolean formula as specified by the program : You now have a SAT problem, where you can apply your SAT-solver, which will use heuristics to partition and explore the solution space more efficiently.

Well you could stop here, but why stop here when you can apply the same trick once : Lift again.

This time we go from boolean formula to continuous space. We replace each bit 0 or 1 by a real number x € [0,1] which is the probability of the bit being 1. And we also have to lift the binary operation to this continuous space. This is equivalent to measuring the voltage in an electrical circuit with transistors and gates that go smoothly from 0 to 1 : We have soften the hard boundaries of a digital circuit, so we can now attack the problem from the inside and we are looking for a continuous vector x € R^n on the boundary of the [0,1]^n hypercube.

So we are now attacking the hash inversion problem using some interior point method, but we have to progressively enforce the hard constraint again so that the softened gates behave like hard digital gates at the end of the optimization process.

I'm guessing you're guessing what we'll be doing next : Lifting.

So up to now our gates are softened, and we are using a cooling adiabatic process to get to the solution. But we have not yet talked about the avalanche characteristic of the hash function. For cryptographic hash function are designed so that one bit of difference in the input result in all the outputs bits being possibly different. Which viewed through the lenses of the transformations we have just made make our problem very badly behaved and chaotic, where numerical precision become an issue.

The other aspect that the hash that we haven't yet talked about is how they map from a big space to a small space. Which is not so different from neural networks that maps pictures to text. And then you can run stable diffusion to get a picture back from your text. Although this one-way ness aspect seem frightening, you just have to hallucinate the information you don't have.

In the context of hash inversion this hallucination means replacing your irreversible soft gates like (Or, And, Maj,...) by reversible soft gates and adding an unknown variable as input, so that now your hash computation is reversible provided this unknown variables that will be degrees of freedom that your optimizer could use.

Now that the gates are reversible, this is not very different than a quantum adiabatic process. Gates themselves are not hardly defined but are parametrized such that they behave at the border like the gates they are representing, but each variation of the gate will allow some freedom to escape from local minimas : aka quantum tunneling : We can now use algorithm like Toshiba's "Simulated Bifurcation Algorithm" which model this chaotic process with differential equations.

But you can lift once more : instead of learning to solve for a single hash function, you can learn to invert all hash function at the same time. By learning an embedding of hash functions into R^n such that hash function that can be inverted using similar heuristics, because they are similar in the computational sense.

And that's how you plant backdoors into hash function.

But you can lift once more : ...