# An encryption scheme using properties of non-abelian groups

I had a discussion about various encryption schemes with a colleague yesterday, and the following thought came to my mind: is it possible to devise an encryption scheme exploiting the phenomenon that in general it takes many more "moves" to return a generic element $g$ ins some non-abelian group $G$ to the identity element of $G$?

The most well-known example of what I am trying to get at is the Rubik's cube. It is known that the diameter of the Cayley graph of the Rubik's cube group is 20, but if you follow the procedure posted on youtube 6 years ago (https://www.youtube.com/watch?v=HsQIoPyfQzM) then the average number of moves to solve the Rubik's cube using that algorithm is much larger (on average, twice as many moves are necessary).

So here is an encryption scheme: given a large, obscure group $G$ with generators $g_1, \cdots, g_k$. The 'key' would be a path $a_1 \cdots a_m$, where $a_i = g_j$ for some generator $g_j$, $1 \leq i \leq m$. Then we code the information to be sent as $a_m^{-1} \cdots a_1^{-1} = g$, and to decode it one would need to find $g^{-1}$.

The question would then be how efficient can one search for $g^{-1}$ in an unknown non-abelian group.

So my questions are:

1) Does this encryption scheme work in theory? That is, in general is it very hard to find short paths on the Cayley graph of a generic group?

2) What are the difficulties in implementing such a scheme if it is worthwhile in theory?

Thanks for any insight and I apologize in advance if I have posed a trivial question, I am not really familiar with the subject.

-
I don’t get it. As you wrote it, the encoded message depends only on the encryption key, not on the plaintext message. – Emil Jeřábek Jan 28 '14 at 20:12
Search for "SL_2 hashing" for an example where such ideas are proposed. – Edgardo Jan 28 '14 at 20:31