Good read!
Does this new proof have an effect on cryptography given that it's often desirable to have highly sensitive cryptographic functions (you flip one bit in the input and get a very different output)?
Take all possible input strings
Given any input string, the sensitivity of that string is how many bits you could flip that cause the output to flip.
Now take the /maximum/ of all input string sensitivities.
For e.g. a hash function, you'd want either a minimum or something like a 1st percentile.
As far as I know, all cryptographic hash functions are sensitive to single bit-flips by design.
Finding those inputs is essentially impossible, but for a true 'random oracle ' they are likely to exist.
And I thought they had ways to construct hash functions so that all the inputs of the same length have a different output?
That's trivially impossible for fixed-size hashes, by the pigeon hole principle.
The point being, for at least that case you can guarantee a sensitivity of one bit.
The sensitivity of that string is the minimum number of bits that need to be changed in order to change the output?
Not being snarky - just want to see if I understand. The phrase "how many bits you could flip" is ambiguous.
From the article: "If, say, there are seven different lies you could have told that would have each separately flipped the outcome, then for your loan profile, the sensitivity of the Boolean function is seven."
With all the leaks lately from inside those places, it would be nice if some basic math results could make it outside.