Jean-Jacques Quisquater: Is the Group Theory Fully Used for Cryptography

Abstract:  In "Rubik's for Cryptographers" Christophe Petit and Jean-Jacques Quisquater
(Notices of AMS, June/July  2013, Volume 60, Issue 06, pp. 733-739) gave 3 examples
of parallel research about cryptographic Cayley hash functions and Babai's conjecture on the
diameter of Cayley graphs. I here continue with another example of such a parallel research.
Again in finite group theory.

This talk is an answer to an interesting paper by Neil Sloane
(1982) about ``Encrypting by random rotations''. Sloane asked
many questions about finite groups G, especially the group S_n
(of all permutations on n elements): One question is the
possibility of the whole generation of G using a subset H of G
and combining these elements from H together in all possible ways
using the group composition.

An interesting problem is to see if there exists some (small) subset
H of G such that each element of G is presented efficiently
as the combination of few occurrences of elements from H. In this
talk we only examine the cases where G = S_n, the symmetric group or A_n, the alternate group.
Our answer is yes in a simple and constructive way.

The problem of efficient presentations of elements from S_n
by a small generating set of permutations was first motivated by Gluskov (1965),
for his automata theory. Golunkov (1968) gave interesting answers but his paper was never
cited in FOCS or STOC conferences for unknown reasons.

The main result of this talk is that it is possible to present
efficiently each finite symmetric (alternating) group using only two or three
well chosen generators. This result is a generalization of a result
by Golunkov (1971). Other similar results were independently
obtained by Babai, Kantor and others (1988, ...) but we improve it.
We'll also give related results for finite Cayley graphs with interesting properties.

(NB: we're very careful about vocabulary. In group theory there are the concepts of group
presentation (we here use) and group representation related to linear transformations and
homomorphims we don't use here. Some confusion appears in the literature).