0
$\begingroup$

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?

Thanks a lot in advance.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

Neither of these deal with Hamiltonian cycles though, and one doesn't need the cycles to be Hamiltonian for the problem to be difficult.

$\endgroup$
6
  • $\begingroup$ In the 2nd paragraph @Mark you have mentioned "as finding relations in between group generators (this is the standard notion". This is the standard notion means, is this idea used somewhere? $\endgroup$ Commented Apr 10, 2020 at 19:35
  • $\begingroup$ I mean the "standard definition" of pseudo-free groups is that it is computationally difficult to find non-trivial relations among the group generators. One can reinterpret this as it is computationally difficult to find "non-trivial" cycles in the Cayley graph of the group, but I don't believe this is how things are usually phrased. $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 10, 2020 at 20:29
  • $\begingroup$ Are there cryptosystems currently built on this idea, that you know of? I would like to go through some reference material to have a better idea, that's why I asked. Thanks a lot in advance @Mark $\endgroup$ Commented Apr 11, 2020 at 10:35
  • $\begingroup$ 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.... $\endgroup$ Commented Apr 11, 2020 at 16:00
  • $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 11, 2020 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.