2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I don’t get it. As you wrote it, the encoded message depends only on the encryption key, not on the plaintext message. $\endgroup$
    – Emil Jeřábek
    Commented Jan 28, 2014 at 20:12
  • $\begingroup$ Search for "SL_2 hashing" for an example where such ideas are proposed. $\endgroup$
    – Edgardo
    Commented Jan 28, 2014 at 20:31

1 Answer 1

Reset to default
2
$\begingroup$

There has been some work done using calculations in nonabelian groups as a basis for cryptography and this work seems to be ongoing. The wikipedia site

http://en.wikipedia.org/wiki/Group-based_cryptography

would be a first link to some of the work that has been done.

The authors referenced there can probably direct you to more recent work. Or you might just look to see later work by these authors and who they reference in later work.

Some of the obstacles here are that one wants rapid encoding and (with possession of the key) rapid decoding.

Improve this answer
$\endgroup$

You must log in to answer this question.

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