Page 1 of 12
European Journal of Business &
Social Sciences
Available at https://ejbss.org/
ISSN: 2235-767X
Volume 06 Issue 12
December 2018
Available online: https://ejbss.org/ P a g e | 357
Some Aspects of Group-Based Cryptography
PREETI RANI
Extension Lecturer, Faculty of Mathematics,
SMGCW, Safidon (Jind)
ABSTRACT
In the last few years, many papers have proposed cryptosystems based on group theoretic
concepts. Group-based cryptosystems have not yet led to practical schemes to rival RSA and
Diffie–Hellman, but the ideas are interesting and the different perspective leads to some
worthwhile group theory. The cryptographic literature is vast and diverse, and it is difficult
for a newcomer to the area to find the right sources to learn from. How group theory can be
used in cryptography is described through this paper. The main purpose in cryptography is
that the system developed for communication must be secure. The security of the system
depends on the method on which the algorithm is based. In this paper we discuss the methods
based on group theory.
Key Words: Non-abelian Group; Cryptosystem; Public Key; Private Key.
INTRODUCTION
In recent times numerous cryptographic protocols have emerged based on group theoretic
concepts. Such protocols have not yet led to practical schemes to rival the likes of RSA and
Diffie–Hellman, but the ideas are interesting and have led to some rewarding group theory.
With the realisation that quantum computers can efficiently solve both the Integer
Factorisation Problem and standard variants of the Discrete Logarithm Problem, the search for
alternative cryptosystems has become more important. Cryptosystems, including group-based
examples that are not necessarily vulnerable to quantum adversaries have become known as
post-quantum cryptosystems. A well-known example is the McEliece cryptosystem based on
the difficulty of decoding error-correcting codes. Other examples include lattice-based
Page 2 of 12
European Journal of Business &
Social Sciences
Available at https://ejbss.org/
ISSN: 2235-767X
Volume 06 Issue 12
December 2018
Available online: https://ejbss.org/ P a g e | 358
cryptosystems and cryptosystems based on large systems of multivariate polynomial
equations.
This paper is concerned with group-based cryptography: the design and analysis of
cryptographic schemes based on nonabelian groups. More specifically, we explore the role of
matrix groups as a platform for group-based cryptosystems. If one is to implement a group- based cryptosystem, one needs an efficient method of representing, storing and manipulating
group elements. For these reasons matrix groups are an attractive source of nonabelian
groups: matrices are easy to store and represent on a computer, and linear algebra provides an
efficient tool to manipulate elements. But linear algebra is also a powerful tool for the
cryptanalyst. Indeed, the focus of this thesis is on cryptanalysis. We demonstrate the
insecurity of several group-based cryptosystems that employ matrix groups as a platform,
rendering them unfit for use in the real world. We treat several key establishment protocols, a
public key cryptosystem, and a group-based hash function. With the exception of the hash
function (where we will be concerned with collision resistance) we work in the passive
adversary model. Thus we assume that an adversary has the power only of an eavesdropper
who knows everything about the system being used except for secret keys and random
choices made by individual parties.
CRYPTOGRAPHY USING GROUPS
The first proposal to use nonabelian groups in public key cryptography is due to Wagner and
Magyarik in 1985. The cryptosystem is based on the hardness of the Word Problem (or more
accurately the Word Choice Problem) for finitely presented groups. However, the scheme is
rather theoretical with several unresolved issues: critiques are given by Gonzalez Vasco and
Steinwandt [39] and Levy-dit- ́ Vehel and Perret. The importance of Wagner and Magyarik’s
scheme lies in its novelty, which commenced interplay between cryptography and
combinatorial group theory. Let G be a group given by a finite presentation. In 1911, Max
Dehn posed the following problems:
The Word Problem: given a word w on the generators of G, decide if w = 1 in G.
The Conjugacy Problem: given words u, v on the generators of G, decide if u and v
represent conjugate elements in G.
Page 3 of 12
European Journal of Business &
Social Sciences
Available at https://ejbss.org/
ISSN: 2235-767X
Volume 06 Issue 12
December 2018
Available online: https://ejbss.org/ P a g e | 359
The Isomorphism Problem: given two finite presentations, decide if they present
isomorphic groups.
KEY AGREEMENT PROTOCOL BY DIFFIE–HELLMAN
Assuming that G be a cyclic group, and g a generator of G, where both g and its order d are
publicly known. If A and B wishes to create a shared key, they can proceed as follows:
1. On uniform basis A chooses at random an integer a ε [2, d − 1], computes ga, and transfer it
to B.
2. Again, on uniform basis B chooses at random an integer b ε [2, d − 1], computes
b
g
and
transfer it to A.
3. A computes ka = (
)
b a
g
while B computes kb =
( ) a b
g
4. The shared key is thus k = ka = kb ∈ G.
In this Scheme security depends on the assumption that, knowing g ∈ G and having observed
both ga and g
b
it is computationally infeasible for an outsider to obtain the shared key. This is
known as the Diffie–Hellman Problem (DHP). The Diffie–Hellman problem is related to a
better known problem, the Discrete Logarithm Problem:
DISCRETE LOGARITHM PROBLEM (DLP)
To describe the Discrete Logarithm Problem (DLP) let G be a cyclic group, and g a generator
of G. Given h ε G, find an integer t such that
t
g
= h. It is clear that if DLP is easy then DHP
is also easy. Hence, the Diffie–Hellman key agreement protocol is insecure. So if we are
using DLP, we have to take care for use of difficult instances of it to make the system more
secure. It is clear that difficulty level of the DLP depends heavily on the way the group G is
represented, not just on the isomorphism class of G. The security of the system depends on
the keys. So it is useful to choose groups of larger order. For example, the DLP is trivial if G
= Z/dZ is the additive group generated by g = 1. Turning from the Diffie–Hellman scheme to
the more general model, Here the main two points which are required to be emphasized are
as follows:
1. A AND B ARE COMPUTERS
