# Using High Level Probability Theory (eg Markov Chain Mixing) in Cryptography/Cryptanalysis

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. I've also cross-posted this on the cryptography SE site (see here).

• Put "on hold" as off-topic at Crypto.SE because Requests for literature, software or similar recommendations are off-topic here. For details, see: Do we want “literature recommendations” and similar “list/subjective questions”?" – e-sushi Feb 16 '17 at 17:06
• I tagged it as a "soft question", for which the tag states "Questions that are about research in mathematics, or about the job of a research mathematician, without being mathematical problems or statements in the strictest sense. In other words, questions that can be answered without making computations or applying theorems and axioms"; this seems on topic here. I'm asking for a very specific scenario, that (appears to be) very understudied. Hopefully this is ok! :) – Sam T Feb 16 '17 at 19:00

## 1 Answer

Dr. Ben Morris from UC Davis has a research program on mixing times of Markov chains applied to cryptography, in particular the Thorp shuffle (a method of card shuffling based on "local swaps" that can be used to encipher small messages such as social security numbers). See An Enciphering Scheme Based on a Card Shuffle and Deterministic Encryption and the Thorp Shuffle

• Ooh, very interesting, thank you. I assume this is the same Morris who developed Evolving Sets with Yuval Peres? (His homepage isn't that helpful... math.ucdavis.edu/~morris) The work on mixing that I'm doing uses this process (along with the related Diaconis/Fill coupling) fundamentally! – Sam T Feb 15 '17 at 13:49
• yep, same Morris; you may find this NSF page helpful: nsf.gov/awardsearch/showAward?AWD_ID=1007739 – Carlo Beenakker Feb 15 '17 at 14:21
• Thank you again for these links. I found them very interesting. I looked at them at the time, but it now turns out that my research may have an implication similar to in these papers, so I looked in more details. I wasn't able to fully understand some of the motivation and statements, though. I was wondering if you are knowledgeable in this field, or if it just happened that you knew these papers? – Sam T Oct 4 '18 at 8:28
• If the former, if you are willing and have time, I'd be grateful if you had a look at my related post (on crypto.SE), and give any insight that you might have? Of course, if you're too busy or any other reason, no problem! (If you feel the post should be here, not on crypto, then let me know and I'll move it here.) I would appreciate any insights you may have to offers. Thanks crypto.stackexchange.com/questions/62816/… – Sam T Oct 4 '18 at 8:29