Answer to Question #271526 in Discrete Mathematics for No one

Question

You are required to prepare a 15-minute presentation aimed towards new students engaged under a technology company’s graduate scheme.

Your presentation will include evidence of:

1. An explanation that adequately explains why group theory is taught to computing students.

2. The application of group theory within public key cryptography. All work should be appropriately and accurately referenced

Answer 1

1.

Computational group theory is the study of groups by means of computers. It is concerned with designing and analysing algorithms and data structures to compute information about groups. The subject has attracted interest because for many interesting groups it is impractical to perform calculations by hand.

Important algorithms in computational group theory include:

• the Schreier–Sims algorithm: algorithm can find the order of a finite permutation group, test membership (is a given permutation contained in a group?), and many other tasks in polynomial time
• the Todd–Coxeter algorithm: an algorithm for solving the coset enumeration problem. Given a presentation of a group G by generators and relations and a subgroup H of G, the algorithm enumerates the cosets of H on G and describes the permutation representation of G on the space of the cosets (given by the left multiplication action). If the order of a group G is relatively small and the subgroup H is known to be uncomplicated (for example, a cyclic group), then the algorithm can be carried out by hand and gives a reasonable description of the group G.
• Knuth–Bendix completion algorithm: is a semi-decision^[2][3] algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. When the algorithm succeeds, it effectively solves the word problem for the specified algebra.
• the product-replacement algorithm for finding random elements of a group.

2.

Group-based cryptography is a use of groups to construct cryptographic primitives. A group is a very general algebraic object and most cryptographic schemes use groups in some way. In particular Diffie–Hellman key exchange uses finite cyclic groups. So the term group-based cryptography refers mostly to cryptographic protocols that use infinite nonabelian groups such as a braid group.

Cryptographic primitives are well-established, low-level cryptographic algorithms that are frequently used to build cryptographic protocols for computer security systems.^[1] These routines include, but are not limited to, one-way hash functions and encryption functions.

Applications:

Diffie–Hellman key exchange. is a method of securely exchanging cryptographic keys over a public channel. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. This key can then be used to encrypt subsequent communications using a symmetric-key cipher.

Anshel–Anshel–Goldfeld protocol, also known as a commutator key exchange, is a key-exchange protocol using nonabelian groups. It was invented by Drs. Michael Anshel, Iris Anshel, and Dorian Goldfeld. Unlike other group-based protocols, it does not employ any commuting or commutative subgroups of a given platform group and can use any nonabelian group with efficiently computable normal forms. It is often discussed specifically in application of braid groups, which notably are infinite (and the group elements can take variable quantities of space to represent). The computed shared secret is an element of the group, so in practice this scheme must be accompanied with a sufficiently secure compressive hash function to normalize the group element to a usable bitstring.