# Research topics related to cryptography and Hamiltonian cycles

I am very interested in pursuing a research where I can show an application of Hamiltonian cycles in Cayley graphs of some group such as reflection groups to the field of cryptography.

But currently I can't figure out where the existence of such a cycle will become important in cryptography and how to develop any useful finding as research output.

Can anyone suggest me an idea to start? An approach?

Cycles (not necessarily Hamiltonian) in the Cayley graph correspond to relations among generators of the group. The RSA assumption can be written as "It is computationally difficult to find a non-trivial relation in the RSA group $$(\mathbb{Z}/pq\mathbb{Z})^*$$", which is a property of $$(\mathbb{Z}/pq\mathbb{Z})^*$$ known as being "pseudo-free" (see The RSA Group is Pseudo-Free), so the computational complexity of finding cycles in the cayley graph can be connected to more standard cryptographic assumptions via this notion.
If one wants to force this point of view, you can see the sieving step of index calculus attacks (on both factoring and discrete log) as finding relations in between group generators (this is the standard notion), so finding cycles in the cayley graph of certain groups. While the discrete log problem is defined over a cyclic group (who's cayley graph is simply a $$n$$-gon), it's not clear to me what particular cayley graph one would be finding cycles in. In particular, for the discrete log problem you fix a "factor base" of various different generators of the group, and then find relations between their discrete logarithms (with respect to a fixed generator), so the cayley graph does not appear to be just that of a cyclic group (which only has a single generator).
• Thank you very much, @Mark when we talk about finding a cycle, I would like to clarify a certain point. Suppose the generators of a particular Cayley graph is s and t and a cycle is $sttstt$. Then $st^2st^2=e$, right? But how can finding a cycle be related to the basis of a cryptosystem? It is not very clear to me.... Commented Apr 11, 2020 at 16:00
• As one can write the RSA assumption in these terms the answer is trivially "yes". I haven't tried working out the details of translating an RSA-based cryptosystem in terms of computations on the Cayley graph of $(\mathbb{Z}/pq\mathbb{Z})^*$, but doing such seems like a fairly straightforward exercise. I'd encourage you to do exactly this, and submit a new question if you run into issues. Commented Apr 11, 2020 at 21:05