5
$\begingroup$

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).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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”?" $\endgroup$
    – e-sushi
    Commented Feb 16, 2017 at 17:06
  • $\begingroup$ 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! :) $\endgroup$
    – Sam OT
    Commented Feb 16, 2017 at 19:00

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ 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! $\endgroup$
    – Sam OT
    Commented Feb 15, 2017 at 13:49
  • 2
    $\begingroup$ yep, same Morris; you may find this NSF page helpful: nsf.gov/awardsearch/showAward?AWD_ID=1007739 $\endgroup$
    – Carlo Beenakker
    Commented Feb 15, 2017 at 14:21
  • $\begingroup$ 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? $\endgroup$
    – Sam OT
    Commented Oct 4, 2018 at 8:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .