Bilinear cryptography using groups of nilpotency
class 2⋆

arXiv:1711.07647v1 [cs.CR] 21 Nov 2017

Ayan Mahalanobis and Pralhad Shinde
Indian Institute of Science Education and Research Pune
Dr. Homi Bhabha Road, Pashan, Pune, INDIA
ayan.mahalanobis@gmail.com

Abstract. In this paper, we develop a novel idea of a bilinear cryptosystem using the discrete logarithm problem in matrices. These matrices
come from a linear representation of a group of nilpotency class 2. We
discuss an example at the end.

1

Introduction

Simply stated, this paper is an application of nilpotency class 2 groups in bilinear
public-key cryptography to build a secure bilinear cryptosystem. Bilinear or
pairing based cryptosystems are used in many practical situations such as the
following:
– Identity based encryption: In this case the user’s public-key is based on his
own identity, like his email address or phone number, see [4].
– Short signatures: Signature schemes where the signature is short, about half
the size of the original signatures, see [3].
– Key exchange: Tripartite Diffie-Hellman key exchange [8,2].
– And others.
We are not going to survey all of pairing-based cryptographic protocols but
will refer the reader to [6]. However, we briefly talk about the tripartite DiffieHellman key exchange protocol purely as a motivation to our paper.

2

A brief introduction to bilinear public-key
cryptography

The origin of pairing based cryptosystems is in the MOV attack [10] on the
elliptic curve discrete logarithm problem. The attack was first envisioned by
Gerhard Frey. The idea was to use the bilinear properties of the Weil pairing to
reduce a discrete logarithm problem in an elliptic curve over a finite field Fq to
a discrete logarithm problem in Fqk . It is known [1] that most of the time for
non super-singular curves, this k, the embedding degree is very large.
⋆

This research was supported by a NBHM and a SERB research grant.

The Weil or the Tate pairing is a bilinear map
B : G × G → Fq k .
Where G is the (abelian) group of the elliptic curve written additively. Then the
discrete logarithm problem in G to the base g ∈ G is given g and αg find α.
It was Joux [8] who first noticed that one can manipulate the bilinear map to
deliver a one-round tripartite Diffie-Hellman key exchange protocol. The idea of
using a bilinear map can also be traced back to the work of Dan Boneh on the
decisional Diffie-Hellman problem. Let A, B and C be three users who want to
set up a common secret key among themselves. Then choose three integers α,
β and γ respectively and keep it a secret. They then compute αg, βg and γg
respectively from the public information G = hgi and broadcast this information
over the public channel. The user A on receiving βg, γg can compute B(βg, γg)α
using his private key α. The same thing can be computed by B and C by using
the public information of the other two users and his private information. The
common key becomes B(g, g)αβγ . All is well and nice in what we just said,
except that B being a alternate(skew-symmetric) map, B(g, g) = 1. There are
many approaches to solve that problem, one was proposed by Joux [8] and the
other using a distortion map. In the interest of brevity of this paper we won’t
go into further details of pairing based cryptosystems using elliptic curve. We
will just have to comment on a few things. There are lots of issues with elliptic
curve pairing. The most important of those are, how to find curves with right
embedding degree and what is the right embedding degree?

3

A brief introduction to nilpotency class 2 groups and
commutator identities

For any group G we can define the lower-central series as follows:
G := γ0 (G) D γ1 (G) D · · · D γk (G) · · ·
Where γi (G) = [γi−1 (G), G] , i > 1. Let x, y be elements of a group G, we follow
the usual definition of a commutator as [x, y] = x−1 y −1 xy . For two subgroups,
H and K of G we define [H, K] = h[h, k] | h ∈ H, k ∈ Ki. If the central series
stops at identity, then we call that group a nilpotent group. If the length of the
series is c, i.e., γc+1 (G) = 1, then we call it a nilpotent group of class c. This c
is also often referred to as the nilpotency class of a group or simply the class. In
this paper we refer the nilpotent class simply as the class. It is not hard to show
that if G is a group of class c, then any commutator [x1 , x2 , ..., xc+1 ] of weight
c + 1 is the identity.
Nilpotent groups of class 2 have many properties similar to that of abelian
groups. We state without proof a well known lemma about groups of class 2.
Lemma 1. Let x, y ∈ G and assume that both x and y commute with [x, y] then:
a) [x, y]n = [xn , y] = [x, y n ] for all integer n

b) (xy)n = xn y n [y, x]

n(n−1)
2

for all n ≥ 0

For a proof see Rotman [12, Lemma 5.42]. The above lemma is a restatement
of the fact, that in a nilpotent group of class 2, the map x 7→ [a, x] for a fixed
a is a linear map. This gives rise to the fact that (x, y) 7→ [x, y] is a bilinear
map from G × G → G. This is the central idea that we are going to use next.
However, at this point we are obliged to report that in the case of groups of
class 2, the bilinear map is from the group to the same group. Unlike the case of
elliptic curves, where the bilinear map is from the group of an elliptic curve to
a finite field. This change can have a profound effect on bilinear cryptography,
especially in designing protocols.

4

The central idea

Let G be a group of nilpotency class 2. As discussed earlier, there are three users
– A, B and C with private exponent α, β and γ respectively. The main formula
on which this key-exchange protocol is based an identity in a nilpotent group of
class 2.
[x, y]n = [xn , y] = [x, y n ]
(1)
As with the tripartite Diffie-Hellman key exchange, the users A and B and
C transmits in public xα , y α ; xβ , y β and xγ , y γ respectively in public.
Key Exchange. The tripartite key-exchange is as follows: On receiving xβ ,
y γ through the public channel, the user A can compute [xβ , y γ ]α = [x, y]αβγ . On
receiving xα , y γ through the public channel, the user B can compute [xα , y γ ]β =
[x, y]αβγ . On receiving xα , y β through the public channel, the user C can compute
[xα , y β ]γ = [x, y]αβγ . The common key is [x, y]αβγ .
4.1

The primary security concerns

The primary security concerns are as follows:
– Given x and xα find α. The same can be said for y. This is the classic discrete
logarithm problem.
– From the information xα and y, one can compute [xα , y] = [x, y]α . Then it
turns out to be the discrete logarithm problem in [x, y].
– Note that [xα , y β ] = [x, y]αβ . Clearly [x, y]αβ can be easily computed and so
is [x, y]γ from [x, y γ ]. The key-exchange is also broken, if we can compute
[x, y]αβγ from [x, y]αβ and [x, y]γ . This is the classic Diffie-Hellman problem,
also known as the computational Diffie-Hellman problem.
Bilinear cryptography described in previous section works in any nilpotent
group of class 2. It is well known that every finite p-group is nilpotent. There are
plenty of finite p-groups. So, it is a natural choice to investigate p-groups of class
2 for the purpose of bilinear cryptography. From now on we shall be concerned
with finite p-groups of class 2. In order to build an effective and secure bilinear
cryptosystem using finite p-groups of class 2, users needs to choose the private
exponents cleverly. Here we shed some light on the choices of private exponents.

Exponent Semigroup Let G be a group, define E(G) = {n ∈ Z | (xy)n =
xn y n for all x, y ∈ G}. The semigroup E(G) is called the exponent semigroup
and is of independent interest in group theory, see [9,11]. We state without proof
a proposition which describes the structure of E(G).
Proposition 1. [11, Proposition 3.2] Let G be a finite p-group, |G| = pm and
exp(G/Z(G))=pe . Then there exist a nonnegative integer r such that E(G) =
pe+r Z ∪ (pe+r Z + 1).
Let G be a finite p-group of class 2 and |G| = pm . Let x, y ∈ G such that
ord(x)=pi , ord(y)=pj where 1 < i, j ≤ m. The private exponents α, β, γ used in
tripartite key-exchange protocol are independent of each other. In order to have
a successful key-agreement it is necessary to have [x, y]αβγ 6= 1. Thus, α, β, γ
must be choosen relatively prime to p, otherwise we could have [x, y]αβγ = 1.
Henceforth, we can assume that the private exponents α, β, γ < pm and are
n(n−1)
relatively prime to p. Recall that (xy)n = xn y n [y, x] 2
for all n ≥ 0. If
n(n−1)
= 1 for all x, y ∈ G, implies n ∈ E(G). Thus, by above proposition
[y, x] 2
n = ape+r or n = ape+r + 1, where 1 ≤ a < pm−e−r . Therefore, we must avoid
choosing private exponents α, β or γ in E(G) = pe+r Z ∪ (pe+r Z + 1). If all α, β, γ
is in E(G), then αβγ belongs to E(G) and by computing integers of the form
ape+r or ape+r + 1 where 1 ≤ a < pm−e−r recover the private key αβγ. However,
this attack is not of much concern because α, β and γ are chosen independent of
one another and is a secret, so it is not likely that all three of these will belong
to E(G). When there is no prior information on whether α, β and γ belongs to
E(G) is available, there is no guarantee that αβγ will belong to E(G) and the
attack then is just a mere exhaustive search.
We now hope that there is a convincing argument that our central idea runs
parallel to the pairing based cryptosystems currently being studied. There is
a lot that can be said about protocols using the above idea. A lot can be said
about ”provable” or semantic security of those cryptosystems. It can be an active
field of study to design proper protocols using the above idea in an appropriate
security model. However, this paper is not about ”provable” or semantic security.
It is about finding the right group in which the above mentioned scheme works
nicely and securely. As we know the security of the discrete logarithm problem
depends on the presentation of the group. There are three most commonly used
presentations of finite groups.
– Permutation presentation.
– Polycyclic presentation.
– Matrix presentation.

5

Finding a right group

From the above discussion it is clear that the stepping stone to bring this idea to
light is to look at 2-generator p-groups of nilpotency class 2. Fortunately there
is a lot known about 2-generator p-groups of class 2, these groups have even

been classified. The automorphism group of these groups are somewhat known
but there is no mention in the literature on the linear representations of these
groups. Our idea simply is to find suitable representations of these 2-generator
p-groups of class 2 and then use it in the ideas described above. In particular,
for the purpose of an exposition, we are interested in the extra-special p groups.
5.1

Extra-special p-groups

Let G be a finite p-group. Then G is defined to be special if either G is elementary
abelian or G is of class 2 and G′ = Φ(G) = Z(G) is elementary abelian. If G is
a non-abelian special group with |Z(G)| = p, then G is said to be extraspecial.
For example, dihedral group D8 and quaternion group Q8 are extraspecial. An
example of our interest is the following: For α ≥ β ≥ γ ≥ 1,
α

β

γ

G = ha, b|ap = bp = [a, b]p = 1, [a, b, a] = [a, b, b] = 1i.
It is clear that G is a two-generator p-group of nilpotency class 2. It is not hard
to see that the derived subgroup G′ is cyclic and of order pγ . Furthermore G/G′
is isomorphic to Cpγ ⊕ Cpβ . Here Cn is the cyclic group of order n.
Here our main goal is to find suitable linear representations for the above
mentioned group. The following theorem will be very useful for our study.
Theorem 1. Every extraspecial p-group G is the central product of extraspecial
groups of order p3 . Irreducible representations of G are all obtained as tensor
product of irreducible representations of the individual factors of G.
We now give some examples of p-groups that we will use for our study. The
modular p-group M odn (p) is given by the generators and relations
n−1

M odn (p) = ha, b|ap

n−2

= bp = 1, ab = a1+p

i.

(2)

And the group
M (p) = ha, b|ap = bp = [a, b]p = 1, [a, b, a] = [a, b, b] = 1i.

(3)

In light of the above theorem we will study the linear representations of extraspecial p-groups of order p3 . The following theorem characterize the non-abelian
groups of order p3 .
Theorem 2. A non-abelian p-group G of order p3 is extraspecial and is isomorphic to one of the groups M od3 (p), M (p), D8 or Q8 .
For the purpose of bilinear cryptography we will look for the irreducible faithful
linear representations of M od3 (p) over a finite field. As we know that [7, Theorem 5.5], if G be an extraspecial p-group of order p2r+1 and F be a field of
characteristic 0 or prime to p which contains a primitive p2 -root of unity. Then
the faithful representation of G over F are all of degree pr . Throughout we will
assume that p and s are odd primes and q = sr . Let ζ be a primitive mth root
of unity in Fs and let k be a positive integer with |k|m = n. Where |k|m is the
order of k in the multiplicative groups of units mod m.

Lemma 1. [5, Lemma 2.2] The Frobenius automorphism τ on Fs defined by
n−1
τ (x) = xq permutes the elements of {ζ, ζ k , · · · , ζ q } iff q ≡ k i (mod m) for
some 0 ≤ i ≤ n − 1.
Theorem 3. [5, Theorem 2.5] Let G = ha, b|am = 1 = bn , b−1 ab = ak i where
|k|m = n. Let ρ be the representation of hai defined by ρ(a) = ζ where ζ is a
primitive mth root of unity in Fs , (s, m) = 1. Then the induced representation
ρG is realizable over Fq iff q ≡ k i (mod m) for some 0 ≤ i ≤ n − 1.
Observe that if we choose m = p2 , n = p, and k = p+1 in the above theorem then
G = M od3 (p) as (p + 1)p ≡ 1 (mod p2 ). Now as we know that by [5, Proposition
2.1] ρG is irreducible over Fs iff |k|m is equal to the order of b. Observe that
n−1
n
ζ, ζ q , · · · , ζ q
are distinct and ζ q = ζ whence |q|p2 = p. By [5, Lemma 2.2],
q ≡ (p + 1)i (mod p2 ) for some i. As |q|p2 = |p + 1|p2 implies that i and p are
co-prime. Hence, letting c = bi we have G = ha, c|am = 1 = cn , c−1 ac = aq i. The
induced representation ρG using coset representatives 1, c, c2 , · · · , cp−1 is given
by


0 0 ··· 0 1
1 0 · · · 0 0 




G
ρ (c) = 0 1 · · · 0 0
 .. ..
.. .. 
. . · · · . .
0 0 ··· 1 0


ζ

0




 ζq


ρ (a) = 

..


.
p−1
q
0
ζ
G

Again by [5, Lemma 2.2] we can see that V −1 ρG (a)V = X

and V −1 ρG (c)V =
p−1
Y
i
(x − ζ q )) are
Y ∈ Mp (Fq ) where V and X(the companion matrix of f (x) =
i=1

as follows:

1 ζ0
1 ζ1

V = . .
 .. ..
1 ζp−1


· · · ζ0p−1
p−1 
· · · ζ1 
. ,
· · · .. 
p−1
· · · ζp−1

0 0 ···
1 0 · · ·


X = 0 1 · · ·
 .. ..
. . · · ·



0 −a0
0 −a1 

0 −a2 
,
.. .. 
. . 

0 0 · · · 1 ζq

p−1





1

 ζp

Y =
..

.

ζ (p−1)p






i

where ζi = ζ q , 0 ≤ i ≤ n − 1. Here we have f (x) = xp − ζ p , hence we get the
equivalent representation σ of ρG which is given by:


0 0 ···
1 0 · · ·


σ(a) = 0 1 · · ·
 .. ..
. . · · ·


0 ζp
0 0

0 0
,
.. .. 
. .

0 0 ··· 1 0



 ζp


ζ 2p
σ(c) = 

..

.




1

ζ (p−1)p









1
0

0

.. 
···
.
(p−2)p
0 0 ··· ζ
0
The characteristic polynomial of σ(a) and σ(ac) is same which is xp − ζ p .
Now consider the tensor product of representation σ with itself. If the characterism
n
Y
Y
(x−µj ),
(x−λi ) and PB (x) =
tic polynomials of A and B factor as PA (x) =
0 0
1 0
 p

Note that σ(ac) = 0 ζ
 .. ..
. .

···
···
···

0
0
0
..
.

i=1

then the characteristic polynomial of A⊗B is PA⊗B (x) =

n Y
m
Y

i=1

(x−λi µj ). Thus

i=1 i=1

characteristic polynomial of σ(a), σ(ac) is (xp − ζ p )p . Observe that the polynomial (xp − ζ p ) is irreducible over F where F is a subfield of Fq with ζ p ∈ F .

6

Conclusion

In this short note, we introduced a novel idea of pairing based cryptosystem
using matrices. The idea is simple, use linear representation of groups of class
2. As a test case we looked at the extraspecial p-group of exponent p2 . For this
particular group, the set of parameters is not encouraging. From [5], it follows
that the only possible matrices that we can come up with is matrices of size

p over Zp . The most security this can provide is the security in the finite field
Fpp . However, since the size of the field and the size of the matrix must be
the same, this is of little practical value. The size of the matrix is too large.
However, we hope, that there are other groups of class 2 for which we can get
better parameters.

References
1. Balasubramanian, R., Koblitz, N.: The improbability than an elliptic curve has
subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm. Journal of Cryptology 11(2), 141–145 (1998)
2. Barua, R., Dutta, R., Sarkar, P.: Extending Joux’s protocol to multi party key
agreement. In: Indocrypt2003. pp. 205–217 (2003)
3. Boneh, D., Shacham, H., Lynn, B.: Short signatures from the Weil pairing. Journal
of Cryptology 17(4), 297–319 (2004)
4. Chatterjee, S., Sarkar, P.: Identity-Based Encryption. Springer (2011)
5. Chebolu, S., Minác̆, J., Reis, C.: Reciprocity laws for represetations of finite groups.
Annales mathématiques du Québec 34(1), 37–61 (2010)
6. Dutta, R., Barua, R., Sarkar, P.: Pairing based cryptographic protocols: A survey,
http://eprint.iacr.org/2004/064
7. Gorenstein, D.: Finite Groups. AMS Chelsea Publishing (1980)
8. Joux, A.: A one round protocol for Diffie-Hellman. In: Proceedings of the 4th
International Symposium on Algorithmic Number Theory. pp. 385–394 (2000)
9. Kobayashi, Y.: On the structure of exponent semigroups. Journal of Algebra 78,
1–19 (1982)
10. Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to
logarithms in a finite field. IEEE transactions on information theory 39(5), 1639 –
1646 (1993)
11. Moravec, P.: Schur multipliers and power endomorphisms of groups. Journal of
Algebra 308(1), 12–25 (2007)
12. Rotman, J.J.: An Introduction to the Theory of Groups. Springer-Velag, 4 edn.
(1994)

