- Jean-Jacques Quisquater: Is...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in March 2016

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

**Speaker:**
Jean-Jacques Quisquater
, UCL Crypto Group

**Date:**
Friday, March 18, 2016

**Time:**
10:30 AM to 12:00 PM
** Note: all times are in the Eastern Time Zone**

**Public:**
Yes

**Location:**
G882, Hewlett

**Event Type:**

**Room Description:**

**Host:**
Vinod Vaikuntanathan

**Contact:**
Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

**Speaker URL:**
None

**Speaker Photo:**

None

**Reminders to:**
seminars@csail.mit.edu, cis-seminars@csail.mit.edu

**Reminder Subject:**
TALK: 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).

**Research Areas:**

**Impact Areas:**

Created by Deborah Goodwin at Monday, February 08, 2016 at 8:17 AM.