| This paper deals with three applications of group theory to cryptography. Two involve methods of public-key encryption with a private key for decryption. The first, proposed in [Wag84], uses the Word Problem, while the second method, proposed in [Ansh93], makes use of the conjugacy problem. In both cases, the methods assume that the underlying group is infinite.; We consider the possibility of applying these methods using finite groups. While we obtain some results applicable to all finite groups, we focus specifically on the Shuffle Group. This group, which originated in an investigation of popular magic tricks using certain types of “perfect shuffles”, has been thoroughly investigated in a classical paper [Dia83]. In brief, it was found that the underlying group structure breaks down into five categories, depending on the number of cards in the underlying deck. In our results, we found that four of the five types, where 2n ≠ 2 k, could be analyzed using the same methods, while the fifth case, where the deck is of size 2n = 2k, required a different approach.; We found that the Word Problem could be solved in the first case with an order of magnitude that is linear in the size of the input, and of much smaller magnitude than the order of the group. While the method presented could apply equally to the second case, it would not be as efficient. Instead, we offer a second method, using a canonical representation for the group elements.; The Conjugacy Problem, in both cases, uses the solution to the Word Problem. An analysis of the cycle structures of permutations in the Shuffle Group yields an efficient method for solving the Conjugacy Problem when 2n ≠ 2k. This method cannot be applied in the case where 2n = 2k, but again an alternative efficient method using the canonical representation is presented.; The third application of group theory is to a protocol for a secret-key exchange. This application seems most likely to be effective with finite groups. However, several pitfalls must be avoided in this case. We make several observations about the avoidance of these pitfalls, specifically with regard to the Shuffle Group. |
