Using High Level Probability Theory (eg Markov Chain Mixing) in Cryptography/Cryptanalysis [closed]

Question

I'm currently doing a PhD in probability theory, specifically (discrete space) Markov chains and their mixing properties. As well as my current main project, I'm looking to have a side project, eg to work on if I want a (temporary) change from my main project. What I'm doing is fairly applied in the sense that we have certain graphs and we're looking at mixing on them; it's fully rigorous though.

While it's not hugely related to Markov mixing, I'm also very interested in cryptography/cryptanalysis. I expect cryptanalysis is more related to my kind of probability theory, but I could be wrong. I'd like to be able to apply similar principles of my main project (Markov chains, in particular mixing) to this.

I'm interested in using high level probability theory. By this, I don't mean only having to know about discrete distrubutions and conditional probabilities, but more -- for example, material in the Aldous/Fill book. By this I mean that it would be a probability project on (/applied to) cryptography/cryptanalysis.

In a related field, I'd also be interested in similar applications to coding theory, eg codes that error-correct with high probability. I know coding theory is based on basic probability, but again I'd be looking for more than just having to know some basic rules.

After some searching it doesn't appear that anything like this has been done. It might be a nice opportunity to do develop some new tools. After all, Tim Gowers got his field medal for combining combinatorics and functional analysis. Not suggesting I'm on Tim Gowers' level, of course! Bollobas successfully used probabilistic methods to show lots of stuff about graphs (again, no claim to be on his level!). This could include things such as developing algorithms via Markov chains and proving fast (polynomial) mixing. I'd be happy to learn new things -- maybe some machine learning techniques would be helpful? -- in order to do this. But I would like it to be probability at heart.

Now, it might be that there isn't literature on this topic because the tools I want to use just aren't applicable in this situation, or it might just be that people haven't done it it. People have different interests, and maybe this is a less common crossover. Let's hope for the latter!

So I'm wondering if anyone has experience of, or knows about, any such questions or areas of research? I've looked at various literature, but maybe someone of a more cryptographical/cryptanalytical background would know of some such problems.

I'd certainly appreciate any comments. This is a cross-post from Maths Overflow (see here).

---

Note the highly related question "Current mathematics theory used in cryptography/coding theory". In this, however, there is no mention of probabilistic tools being used there; it's mostly number theoretic or algebraic. Note that there is the tag "probabilistic encryption".

Answer 1

I think you're being too dismissive and thinking of this as a "side project".

The challenge is representing the action of the cryptographic mappings such as the key schedule and the round functions which result in a pseudorandom permutation that can only sample a vanishingly small subset (a fraction $$\frac{2^k}{(2^n)!}$$ for keylength $k$ block length $n$, which are usually the same, but not necessarily) of all permutations in $S_{2^n}$.

The key is random, but the subkeys are not, they are directly derived from the key, so you have $k$ bit maximum key entropy used typically for $kr$ total subkeys bits.

More importantly, you need a worst-case approach while to my understanding the mixing time convergence to uniform is more of an average case criterion.

Are you aware of work by Lai-Massey-Murphy, Luby Rackoff. You can start by tracking the references to those.

And poly time mixing may tell you hundreds of rounds are enough on average but you'll want to use sublinear number of rounds.

This answer focused on block ciphers alone.