Open access peer-reviewed chapter - ONLINE FIRST

The MOR Cryptosystem in Classical Groups with a Gaussian Elimination Algorithm for Symplectic and Orthogonal Groups

By Sushil Bhunia, Ayan Mahalanobis, Pralhad Shinde and Anupam Singh

Submitted: October 25th 2018Reviewed: January 23rd 2019Published: March 9th 2019

DOI: 10.5772/intechopen.84663

Downloaded: 88

Abstract

In this chapter, we study the MOR cryptosystem with symplectic and orthogonal groups over finite fields of odd characteristics. There are four infinite families of finite classical Chevalley groups. These are special linear groups SL(d, q), orthogonal groups O(d, q), and symplectic groups Sp(d, q). The family O(d, q) splits into two different families of Chevalley groups depending on the parity of d. The MOR cryptosystem over SL(d, q) was studied by the second author. In that case, the hardness of the MOR cryptosystem was found to be equivalent to the discrete logarithm problem in Fqd. In this chapter, we show that the MOR cryptosystem over Sp(d, q) has the security of the discrete logarithm problem in Fqd. However, it seems likely that the security of the MOR cryptosystem for the family of orthogonal groups is Fqd2. We also develop an analog of row-column operations in symplectic and orthogonal groups which is of independent interest as an appendix.

Keywords

  • public-key cryptography
  • MOR cryptosystem
  • Chevalley groups
  • Gaussian elimination
  • 2010 Mathematics Subject Classification: 94A60
  • 20H30

1. Introduction

Public-key cryptography is the backbone of this modern society. However with recent advances in quantum computers and its possible implication to factoring integers and solving the discrete logarithm problems, it seems that we are left with no secure cryptographic primitive. So it seems prudent that we set out in search for new cryptographic primitives and subsequently new cryptosystems. The obvious question is: how to search and where to look? One can look into several well-known hard problems in Mathematics and hope to create a trap-door function, or one can try to generalize the known, trusted cryptosystems.

This chapter is in the direction of generalizing a known cryptosystem with the hope that something practical and useful will come out of this generalization. A new but arbitrary cryptosystem might not be considered by the community as a secure cryptosystem for decades. So our approach is conservative but practical. Several such approaches were earlier made by many eminent mathematicians. To name a few, Maze et al. [1, 2] developed SAP and Shpilrain and Zapata developed CAKE, both work in non-abelian structures. There is an interesting cryptosystem in the work of Climent et al. [3]. We further recommend the work of Grogoriev et al. [4] and Roman’kov [5].

The cryptosystem that we have in mind is the MOR cryptosystem [6, 7, 8, 9]. In Section 2, we describe the MOR cryptosystem in details. It is a simple but powerful generalization of the well-known and classic ElGamal cryptosystem. In this cryptosystem, the discrete logarithm problem works in the automorphism group of a group instead of the group. As a matter of fact, it can work in the automorphism group of most algebraic structures. However, we will limit ourselves to finite groups. One way to look at the MOR cryptosystem is that it generalizes the discrete logarithm problem from a cyclic (sub)group to an arbitrary group.

The MOR cryptosystem over SL(d, q) was studied earlier [6] and cryptanalyzed by Monico [10]. It became clear that working with matrix groups of size d over Fqand with automorphisms that act by conjugation, like the inner automorphisms, there are two possible reductions of the security to finite fields. It is the security of the discrete logarithm problem in Fqdor Fqd2([6], Section 7). This reduction is similar to the embedding of the discrete logarithm problem in the group of rational points of an elliptic curve to a finite field; the degree of the extension of that field over the field of definition of the elliptic curve is called the embedding degree. In the case of SL(d, q), it became the security of Fqd. The reason that we undertook this study is to see if the security in other classical Chevalley groups is Fqdor Fqd2.

In cryptography, it is often hard to come up with theorems about security of a cryptosystem. However, at this moment it seems likely that the security of the MOR cryptosystem in orthogonal groups O(d, q) is Fqd2. The way we implement this cryptosystem is by solving the word problem in generators. It presents no advantage to small characteristic. In the light of Joux’s [11] improvement of the index-calculus attack in small characteristic, this contribution of the MOR cryptosystem is remarkable.

In summary, the proposed MOR cryptosystem is totally different from the known ElGamal cryptosystems from a functional point of view. Its implementation depends on Gaussian elimination and substitutions (substituting a matrix for a word in generators). However, we do have a concrete and tangible understanding of its security. It is clear from this work that the MOR cryptosystem over classical groups is not quantum-secure. However, for other groups like solvable groups, the answer is not known and could be a topic of further research.

1.1 Structure of the chapter

This chapter is an interplay between computational group theory and public-key cryptography, in particular the MOR cryptosystem, and is thus interdisciplinary in nature. In this chapter, we study the MOR cryptosystem using the orthogonal and symplectic groups over finite fields of odd characteristic.

In Section 2, we describe the MOR cryptosystem in some details. We emphasize that the MOR cryptosystem is a natural generalization of the classic ElGamal cryptosystem. In Section 3, we describe the orthogonal and symplectic groups and their automorphisms. In Appendix A, we describe few new algorithms. These algorithms use row-column operations to write an element in classical groups as a word in generators. This is very similar to the Gaussian elimination algorithm for special linear groups. These algorithms are vital to the implementation of the MOR cryptosystem. These algorithms are also of independent interest in computational group theory.

1.2 Notations and terminology

It was bit hard for us to pick notations for this chapter. The notations used by a Lie group theorist is somewhat different from that of a computational group theorist. We tried to preserve the essence of notations as much as possible. For example, a Lie group theorist will use SLl+1qto denote what we will denote by SLl+1qor SLdq. We have used TXto denote the transpose of the matrix X. This was necessary to avoid any confusion that might arise when using X1and TXsimultaneously. In this chapter, we use Kand Fqinterchangeably, while each of them is a finite field of odd characteristic. However, in the appendix the field k is unrestricted. The matrix teijis used to denote the matrix unit with t in the ijthplace and zero everywhere else. We will often use xrtas generators, a notation used in the theory of Chevalley groups. Here r is a short hand for ijand xrtare defined in Tables A1,A3,A5, and A7. We often refer to the orthogonal group as Odq, specifically, the split orthogonal group as O+2lqor O+2l+1qand the twisted orthogonal group as O2lq. All other notations used are standard.

2. The MOR cryptosystem

The MOR cryptosystem is a natural generalization of the classic ElGamal cryptosystem. It was first proposed by Paeng et al. [9]. To elaborate the idea behind a MOR cryptosystem, we take a slightly expository route. For the purpose of this exposition, we define the discrete logarithm problem. It is one of the most common cryptographic primitive in use. It works in any cyclic (sub)group G=gbut is not secure in any cyclic group.

Definition 2.1 (The discrete logarithm problem). The discrete logarithm problem inG=g, given g and gm, find m.

The word “find” in the above definition is bit vague, in this chapter we mean compute m. The hardness to solve the discrete logarithm problem depends on the presentation of the group and is not an invariant under isomorphism. It is believed that the discrete logarithm problem is secure in the multiplicative group of a finite field and the group of rational points of an elliptic curve.

A more important cryptographic primitive, related to the discrete logarithm problem, is the Diffie-Hellman problem, also known as the computational Diffie-Hellman problem.

Definition 2.2 (Diffie-Hellman problem). Given g,gm1, andgm2, findgm1m2.

It is clear; if one solves the discrete logarithm problem, then the Diffie-Hellman problem is solved as well. The other direction is not known.

The most prolific cryptosystem in use today is the ElGamal cryptosystem. It uses the cyclic group G=g. It is defined as follows:

2.1 The ElGamal cryptosystem

A cyclic group G=gis public.

  • Public-key: Let gand gmbe public.

  • Private-key: The integer mbe private.

Encryption:

To encrypt a plaintext MG, get an arbitrary integer r1Gand compute grand grm. The ciphertext is grMgrm.

Decryption:

After receiving the ciphertext grMgrm, the user uses the private-key m. So she computes gmrfrom grand then computes M.

It is well known that the hardness of the ElGamal cryptosystem is equivalent to the Diffie-Hellman problem ([12], Proposition 2.10).

2.2 The MOR cryptosystem

In the case of the MOR cryptosystem, one works with the automorphism group of a group. An automorphism group can be defined on any algebraic structure, and subsequently a MOR cryptosystem can also be defined on that automorphism group; however, in this chapter we restrict ourselves to finite groups. Furthermore, we look at classical groups defined by generators and automorphisms that are defined as actions on those generators.

Let G=g1g2gsbe a finite group. Let ϕbe a non-identity automorphism.

  • Public-key: Let ϕgii=1sand ϕmgii=1sbe public.

  • Private-key: The integer mis private.

Encryption:

To encrypt a plaintext MG, get an arbitrary integer r1ϕand compute ϕrand ϕrm. The ciphertext is ϕrϕrmM.

Decryption:

After receiving the ciphertext ϕrϕrmM, the user knows the private-key m. So she computes ϕmrfrom ϕrand then computes M.

Theorem 2.1The hardness to break the above MOR cryptosystem is equivalent to the Diffie-Hellman problem in the groupϕ.

Proof. It is easy to see that if one can break the Diffie-Hellman problem, then one can compute ϕmrfrom ϕmin the public-key and ϕrin the ciphertext. This breaks the system.

On the other hand, observe that the plaintext is ϕmrϕmrM. Assume that there is an oracle that can break the MOR cryptosystem, i.e., given ϕ,ϕmand a plaintext ϕrgwill deliver ϕmrg. Now we query the oracle s times with the public-key and the ciphertext ϕrgifor i=1,2,,s. From the output, one can easily find ϕmrgifor i=1,2,,s. So we just witnessed that for ϕmand ϕr, one can compute ϕmrusing the oracle. This solves the Diffie-Hellman problem.

In a practical implementation of a MOR cryptosystem, there are two things that matter the most.

  1. a: The number of generators. As we saw that the automorphism ϕis presented as action on generators. Larger the number of generators, bigger is the size of the public key.

  2. b: Efficient algorithm to solve the word problem. This means that given G=g1g2gsand gG, is there an efficient algorithm to write gas word in g1,g2,,gs? The reason of this importance is immediate—the automorphisms are presented as action on generators, and if one has to compute ϕg, then the word problem must be solved.

The obvious question is: what are the right groups for the MOR cryptosystem? In this chapter, we pursue a study of the MOR cryptosystem using finite Chevalley groups of classical type, in particular, orthogonal and symplectic groups.

3. Description of automorphisms of classical groups

This chapter studies the MOR cryptosystem for orthogonal and symplectic groups over a field of odd characteristics. As we discussed before, MOR cryptosystem is presented as action on generators of the group. Then to use an automorphism on an arbitrary element, one has to solve the word problem in that group with respect to that set of generators.

The generators and the Gaussian elimination algorithm to solve the word problem are described in Appendix A. We will be very brief here.

Let V be a vector space of dimension d over a field Kof odd characteristic. Let β:V×VKbe a bilinear form. By fixing a basis of V, we can associate a matrix to β. We shall abuse the notation slightly and denote the matrix of the bilinear form by βitself. Thus βxy=Txβy, where x,yare column vectors. We will work with non-degenerate bilinear forms and that means detβ0. A symmetric or skew-symmetric bilinear form βsatisfies β=Tβor β=Tβ, respectively.

Definition 3.1 (Orthogonal group). A square matrix X of size d is called orthogonal ifTXβX=β, whereβis symmetric. It is well known that the orthogonal matrices form a group known as the orthogonal group.

Definition 3.2 (Symplectic group). A square matrix X of size d is called symplectic ifTXβX=β, whereβis skew-symmetric. And the set of symplectic matrices form a symplectic group.

We write the dimension of V as d=2l+1or d=2lfor l1. We fix a basis and index it by 0,1,,l,1,,lin the odd dimension, and in the case of even dimension where there are two non-degenerate symmetric bilinear forms up to equivalence, we index the bases by 1,2,,l,1,2,,land 1,1,2,,l,2,,lfor split and twisted forms, respectively. We consider the non-degenerate bilinear forms βon Vgiven by the following matrices:

  1. a: The odd-orthogonal group. The form βis symmetric with d=2l+1and β=20000Il0Il0.

  2. b: The symplectic group. The form βis skew-symmetric with d=2land β=0IlIl0.

  3. c: The split orthogonal group. The form βis symmetric with d=2land β=0IlIl0.

  4. c: The twisted orthogonal group. The form βis symmetric with d=2land β=β00000Il10Il10,

where Il is the identity matrix of size l over Kand for a fixed non-square ϵK, β0=100ϵ.

We now describe the automorphism group of the orthogonal and symplectic groups. This helps us in picking the right set of automorphisms for the MOR cryptosystem.

Definition 3.3 (Orthogonal similitude group). The orthogonal similitude group is defined as the set of matrices X of size d as

GOdq=XGLdqTXβX=μβμFq×,

whered=2l+1or2landβis of type a, c, orc, respectively.

Definition 3.4 (Symplectic similitude group). The symplectic similitude group is defined as

GSp2lq=XGL2lqTXβX=μβμFq×,

whereβis of type b.

Here μdepends on the matrix Xand is called the similitude factor. The similitude factor μdefines a group homomorphism from the similitude group to Fq×, and the kernel is the orthogonal group Odqwhen βis symmetric and symplectic group Sp2lqand when βis skew-symmetric, respectively ([13], Section 12). Note that scalar matrices λIfor λFq×belong to the center of similitude groups. The similitude groups are analog of what GLdqis for SLdq. For a discussion of the diagonal automorphisms of Chevalley groups, we need the diagonal subgroups of the similitude groups.

Definition 3.5 (Diagonal group). The diagonal groups are defined to be the group of non-singular diagonal matrices in the corresponding similitude group and are as follows: in the case ofGO2l+1q, it is

diagαλ1λlμλ11μλl1λ1λlα2=μFq×,

and in the case of GO2lqand GSp2lq, it is

diagλ1λlμλ11μλl1λ1λlμFq×.

Conjugation by these diagonal elements produces diagonal automorphisms in the respective Chevalley groups. To build a MOR cryptosystem, we need to work with the automorphism group of Chevalley groups. In this section we describe the automorphism group of classical groups following Dieudonne [14].

Conjugation automorphisms: If N is a normal subgroup of a group G, then the conjugation maps ngng1for nNand gGare called conjugation automorphisms of G. In particular, both inner automorphisms and diagonal automorphisms are examples of conjugation automorphisms.

Central automorphisms: Let χ:GZGbe a homomorphism to the center of the group. Then the map gχggis an automorphism of G, known as the central automorphism. There are no nontrivial central automorphisms for perfect groups, for example, the Chevalley groups SLl+1Kand Sp2lK, K4, and l2. In the case of orthogonal group, the center is of two elements II, where I is the identity matrix. This implies that there are at most four central automorphisms in this case.

Field automorphisms: Let fAutK. In terms of matrices, field automorphisms amount to replacing each term of the matrix by its image under f.

Graph automorphisms: A symmetry of Dynkin diagram induces such automorphisms. This way we get automorphisms of order 2 for SLl+1Kand l2and O+2lKand l4. We also get an automorphisms of order 3 for O+4K.

In the case of SL(d, q) for d3, the map xA1Tx1A, where

A=000010001000100010001l10000

explicitly describes the graph automorphism.

In the case of O(2l, q) for l5, the graph automorphism is given by xB1xBwhere B is a permutation matrix obtained from identity matrix of size 2l×2lby switching the lthrow and lthrow. This automorphism is a conjugating automorphism.

Theorem 3.1 (Dieudonne). LetKbe a field of odd characteristic andl2.

1. For the group SLl+1K, any automorphism is of the form ιγθwhere ιis a conjugation automorphism defined by elements of GLl+1Kand γis a graph automorphism for the special linear group.

2. For the group O+dK, any automorphism is of the form cχιθwhere cχis a central automorphism and ιis a conjugation automorphism by elements of GO+dK(this includes the graph automorphism of even-orthogonal groups).

3. For the group OdK, any automorphism is of the form ιθ, where ιis a conjugation automorphism by elements of GOdK.

4. For the group Sp2lK, any automorphism is of the form ιθwhere ιis a conjugation automorphism by elements of GSp2lK.

In all cases θ denotes a field automorphism.

For a proof of the above theorem, see [26], Theorems 30 and 36. In the above theorem, conjugation automorphisms are given by conjugation by elements of a larger group, and it includes the group of inner automorphisms. We introduce diagonal automorphisms to make it more precise. The conjugation automorphisms ιcan be written as a product of ιgand ηwhere ιgis an inner automorphism and ηis a diagonal automorphism.

Diagonal automorphisms: In the definition of the conjugating automorphism, when the conjugating element is from the similitude group but not in the group we get a diagonal automorphism. In the case of special linear groups, diagonal automorphisms are given by conjugation by diagonal elements of PGL(l + 1, q) on PGL(l + 1, q). In the case of symplectic and orthogonal groups, diagonal automorphisms are given by conjugation by corresponding diagonal group elements defined in Definition 3.5.

4. Security of the proposed MOR cryptosystem

The purpose of this section is to show that for a secure MOR cryptosystem over the classical Chevalley and twisted orthogonal groups, we have to look at automorphisms that act by conjugation like the inner automorphisms. There are other automorphisms that also act by conjugation, like the diagonal automorphism and the graph automorphism for odd-order orthogonal groups. Then we argue what is the hardness of our security assumptions. We denote the split orthogonal group by O+2lqand twisted orthogonal group by O2lq. Now onwards O(2l,q) means either split or twisted orthogonal group and we will specify whenever required.

Let ϕbe an automorphism of one of the classical Chevalley groups G: SLl+1q,O2l+1q,Sp2lq,or O2lq. From Theorem 3.1, we know that ϕ=cχιηγθwhere cχis a central automorphism, ιis an inner automorphism, ηis a diagonal automorphism, γis a graph automorphism, and θis a field automorphism.

The group of central automorphisms are too small and the field automorphisms reduce to a discrete logarithm in the field Fq. So there is no benefit of using these in a MOR cryptosystem. Also there are not many graph automorphisms in classical Chevalley and twisted orthogonal groups other than special linear groups and odd-order orthogonal groups. In the odd-order orthogonal groups, these automorphisms act by conjugation. Recall here that our automorphisms are presented as action on generators. It is clear ([6], Section 7) that if we can recover the conjugating matrix from the action on generators, the security is a discrete logarithm problem in Fqd, or else the security is a discrete logarithm problem in Fqd2.

So from these we conclude that for a secure MOR cryptosystem, we must look at automorphisms that act by conjugation, like the inner automorphisms. Inner automorphisms form a normal subgroup of AutGand usually constitute the bulk of automorphisms. If ϕis an inner automorphism, say ιg:xgxg1, we would like to determine the conjugating element g. For the special linear group, it was done in [6]. We will follow the steps there for the present situation too. However, before we do that, let us digress briefly to observe that GInnGgiven by gιgis a surjective group homomorphism. Thus if G is generated by g1,g2,,gs, then InnGis generated by ιg1,,ιgs. Let ϕInnG. If we can find gj,j12sgenerators, such that ϕ=jιgj, then ϕ=ιgwhere g=jgj. This implies that our problem is equivalent to solving the word problem in InnG. Note that solving word problem depends on how the group is presented and it is not invariant under group homomorphisms. Thus the algorithm described earlier to solve the word problem in the classical Chevalley and twisted orthogonal groups does not help us in the present case.

In what follows, we will use generators xrt, where r=ij;ij,1i,jdfor the special linear group. For symplectic group r=ij;i,j±1±2±l. For the even-orthogonal group, r=ij;i,j±1±2±l;±i±j. For the odd-orthogonal group r=ij;lil  and  j±1±2±l;±i±j. These are the Chevalley generators for the Chevalley groups we are dealing with and are described in details in Tables A1,A5,A3, andA7 in the Appendix.

4.1 Reduction of security

In this subsection, we show that for special linear and symplectic groups, the security of the MOR cryptosystem is the hardness of the discrete logarithm problem in Fqd. This is the same as saying that we can find the conjugating matrix up to a scalar multiple. We further show that the method that works for special linear and symplectic groups does not work for orthogonal groups.

Let ϕbe an automorphism that works by conjugation, i.e., ϕ=ιg, for some g, and we try to determine g.

Step 1: The automorphism ϕis presented as action on generators xrt.

Thus ϕxrt=gI+terg1=I+tgerg1. This implies that we know gerg1for all possible r. We first claim that we can determine N = gD where D is sparse, in fact, diagonal in the case of special linear and symplectic groups.

In the case of special linear groups, write g=G1GiGd, where Gi are column vectors of g. Then gei,j=G1Gdei,j=00Gi00where Gi is at the jth place. Multiplying this with g1on the right, i.e., computing gei,jg1, determines Gi up to a scalar multiple di (say). Thus, we know N=gDwhere D=diagd1dl+1.

For the symplectic groups, we do the similar computation with the generators I+tei,iand I+tei,i. Write g in the column form as G1GlG1Gl. Now,

  1. G1GlG1Glei,i=00Gi00where Gi is at −ith place. Multiplying this further with g1gives us scalar multiple of Gi, say diGi.

  2. G1GlG1Glei,i=00Gi00where Giis at ith place. Multiplying this with g1gives us scalar multiple of Gi, say diGi.

Thus we get N=gDwhere D is a diagonal matrix diagd1dld1dl.

Step 2: Compute N1ϕxrtN=D1g1gxrtg1gD=I+D1erDwhich is equivalent to computing D1erD.

In the case of special linear groups, we have D a diagonal. Thus by computing D1ei,jD, we determine di1djfor ijand form a matrix diag1d21d1dl1d1, and multiplying this to N, we get d1g. Hence we can determine g up to a scalar matrix.

For symplectic groups, we can do similar computation as D is diagonal. First compute D1ei,jej,iDto get di1djand di1djfor ij. Now compute D1ei,iD,D1ei,iDto get didi1,didi1. We form a matrix

diag1d21d1dl1d1d11d2.d21d2.d21d1dl1d1.d11d1

and multiply it to N=gDto get d1g. Thus we can determine g up to a scalar multiple say ag. Similarly we can determine gm up to a scalar multiple say bgm. Now, compute agq1=gq1and bgmq1=gmq1, and then we can recover m by solving the discrete logarithm in the matrices using Menezes and Wu’s idea [15]. However, if we choose g such that gq1=1, then it seems that we might avoid this line of attack. We can bypass this argument by recovering the scalars a and b, and then to determine m, we compute the discrete logarithm in gusing Menezes and Wu’s idea. We prove the following proposition.

Proposition 4.1Given anygSpdqup to scalar multiple ag,aFq. Ifgcddq1=1, we can determine the scalar a. Otherwise one can find the scalar a by solving a discrete logarithm problem inFq.

Proof. We can recover the scalar a as follows: Let λ1λdbe a set of eigenvalues of g, and then the eigenvalues of ag are aλ1aλd. Set α=aλ1aλdand thus α=adas λ1λd=detg=1. Suppose gcddq1=ζ, using extended Euclidean algorithm, we find u and vsuch that ud+vq1=ζ. Next, computing αu, we get aud=aζvq1=aζ. Thus, if gcddq1=1, then we have recovered the scalar a; otherwise we can recover the scalar by solving the discrete logarithm problem in Fq.

Thus, if gcddq1=1, then using the above proposition, we can recover the scalars a and b from agand bgm, respectively. Otherwise one needs to solve discrete logarithm problem in Fqto recover the scalars. Now, we can recover gand gmfrom agand bgmjust by multiplying with scalar matrices a1Iand b1I, respectively. Finally, we recover musing Menezes and Wu’s idea. Thus, if we choose gsuch that gq1=1and gcddq11, then to solve the discrete logarithm in ϕ, one needs to solve the discrete logarithm in Fqand Fqd.

However, in the case of orthogonal groups, we show that one cannot recover g up to a diagonal matrix using the above approach, and hence the above reduction attack does not work.

Theorem 4.1LetgGOdq. Consider the conjugation automorphismϕ:OdqOdq. Letxrbe a set of Chevalley generators of O(d,q) described in Appendix A. Suppose that the public-key is presented as an action ofϕonxr, then it is impossible to recover a matrix gD, where D is a diagonal matrix using the above reduction.

Proof. We prove the theorem for O+dq, d even, and the theorem follows for other cases similarly. Let d=2land we write g in columns form as g=C1ClC1Cl. We compute gerg1which gives the following equations:

  1. Note that gei,jej,ig1=00Ci00Cj00g1, where Ci is at jth place and Cjis at ithplace. After multiplying by g1, we get a matrix whose all columns are linear combinations of columns Ciand Cj.

  2. Note that gei,jej,ig1=00Ci00Cj00g1, where Ciis at jthplace and Cjis at ithplace. After multiplying by g1, we get a matrix whose all columns are linear combinations of columns Ci and Cj.

  3. Note that gei,jej,ig1=00Ci00Cj00g1, where Ciis at jthplace and Cjis at ithplace. After multiplying by g1, we get a matrix whose all columns are linear combinations of columns Ciand Cj.

Suppose one can construct a matrix B from columns obtained above such that B=gD, where D is diagonal, then we can see that diCi=aiCj+bjCkfor some i,j,kwhich is a contradiction as detg0. Thus, it is not possible to construct a matrix B such that B=gD, where D is diagonal.

This conclusively proves that the attack on the special linear groups and symplectic groups will not work for most orthogonal groups.

For orthogonal groups, the best we can do is the following: We can construct N such that N=gD1+PD2, where D1 and D2 are diagonal and P is a permutation matrix. We demonstrate the construction of N in the case of a split orthogonal group O+2lq; similar construction works for other cases as well. Computing gerg1gives the following equations:

  1. G1GlG1Glei,jej,ig1=00Gi00Gj00g1, where Giis at jth place and Gjis at ithplace. This gives us a linear combination of the columns Gi and Gj.

  2. G1GlG1Glei,jej,ig1=00Gi00Gj00g1, where Gi is at jthplace and Gj is at ithplace. This will give us a linear combination of the columns Gi and Gj.

  3. G1GlG1Glei,jej,ig1=00Gi00Gj00g1, where Giis at jth place and Gjis at ith place. This will give us a linear combination of the columns Giand Gj.

We construct a matrix N as follows: For each i=1,,l1, compute gI+ei,i+1ei+1,ig1Iwhose each column is a linear combination of Ciand Ci+1. Choose one of its column say riCi+siCi+1for each i=1,,l1. Similarly compute gI+ei+1,iei,i+1g1Iand choose riCi+siCi+1for each i=1,,l1. Further, we compute gI+e1,lel,1g1Ito get rlCl+slC1and gI+e1,lel,1g1Ito get rlCl+slC1. We set N=r1C1+s1C2rl1Cl1+sl1ClrlCl+slC1r1C1+s1C2rl1Cl1+sl1ClrlCl+slC1. Now it is easy to note that N=gD1+PD2, where D1=diagr1rlr1rl, D2=diags1sls1sl, and P are permutation matrix corresponding to the permutation of indexing set 1234l1l1234l1l1.

Thus we get N=gD1+PD2, where D1 and D2 are diagonal and P is a permutation matrix. This is not a diagonal matrix. One can do a similar computation for the odd-orthogonal group and twisted orthogonal group as well.

Remark 4.1An observant reader would ask the question: why does this attack works for the special linear and symplectic groups but not for orthogonal groups? The answer lies in a closer look at the generators (elementary matrices) for these groups.

In the special linear groups, the generators are the elementary transvections of the form I+tei,jwhere ijand tFq. Then the attack goes on smoothly as we saw earlier. However, when we look at generators of the form I+tei,jtej,i, where tFqand ij, conjugating by them, it gets us a linear sum of the ith and jth column, not scalar multiple of one particular column. This stops the attack from going forward. However in the symplectic groups, there are generators of the form I+ei,iand I+ei,ifor 1il. These generators make the attack possible for the symplectic groups. However there are no such generators for orthogonal groups, and so this attack turns out to be impossible for orthogonal groups.

5. The case for two-generators and prime fields

One serious objection against a MOR cryptosystem is the size of the key ([10], Section 7). The reason is that in a MOR cryptosystem, the automorphisms are presented as action on generators. Now the bigger the number of generators, the larger the key-size.

On the other hand, many of the finite simple groups can be generated by two elements. However, a set of generators is not enough. We must be able to compute the image of an arbitrary element. When the automorphism is presented as action on generators, we need an efficient solution to the word problem in order to do that. We have demonstrated in Appendix A that there is one set of generators, the elementary matrices, for which the word problem is easy.

The theme of this section is that for symplectic and even-order split orthogonal groups, there are two generators and for the odd-orthogonal group there are three generators. Over the prime field of odd characteristic, one can easily compute the word corresponding to the elementary matrices for these generators.

So one can present the automorphisms ϕand ϕmas action on these few generators and then compute the action of these automorphisms on the elementary matrices later. This substantially reduces the key-size. To do this we use the technique of straight line programs, which is popular in computational group theory. These are programs, but in practice are actually easy to use formulas. Say, for example, we want to compute xi,jtfor some tFq. We have loaded matrices wi1x1,2wi1in the memory in such a way that this formula takes as input t and put it in the (1, 2) position of the matrix x1,2and do the matrix multiplication. This is one straight line program. Since these programs are loaded in the memory, computation is much faster. This is somewhat similar to a time-memory trade-off. We have built a series of these straight line programs, where one straight line program can use other straight line programs and have written down the length of these programs. The length is nothing but the number of matrices in the formula.

Using the symplectic group in the MOR cryptosystem is straightforward. However, using orthogonal groups is little tricky because of the presence of λ in the output of the Gaussian elimination algorithm (see Section A.2.3). It is well known that the elementary matrices, without wi—the row interchanges matrices and generates Ω, the commutator subgroup of a orthogonal group. However in between the commutator and the whole group, there is another important subgroup, WΩ=Ωwifor some i. From the algorithmic point of view, it is the subgroup of all the matrices for which the λ is a square. Now once the λ is a square and we can efficiently compute the square root, we can write this matrix down as product of elementary matrices, and it is easy to implement in the MOR cryptosystem. It is well known that if p3mod4, then it is easy to compute the square root. Only for this reason, in the latter part of this section and for orthogonal groups, we concentrate on p3mod4.

5.1 Symplectic group Sp (2l, p)

Let p be an odd prime. It is known [16] that the group Sp(2l,p) is generated by two elements:

x=x1,21E1
w=01I2l10E2

We will refer these two elements as Steinberg generators. However in the context of the MOR cryptosystem, we need to know how to go back and forth between these two generating sets—Steinberg generators and elementary matrices (see Table A3). To write w as a product of elementary matrices is easy, just put this generator through our Gaussian elimination algorithm. Here we demonstrate the other way round, that is, how to write elementary matrices as a product of x and w. In what follows, we denote the length of SLPs by Lδi, where δ=jiand 1i<jl.

δ=1,xi,jt=wi1x1,2twi1,δ=2,xi,jt=xi,j1txj1,j1,δ=3,xi,jt=xi,j1txj1,j1,δ=l1,xi,jt=xi,j1txj1,j1.

Here

Lδi=2i1forδ=1,2Lδ1+4i+δ6forδ=2,3,,l1.

Now wl=1l10IlIl0and xj,it=wlxi,jtwl, so length of this SLP is Lδi+2l. Hence we get all xi,jtfor 1ijl. Number of SLP is l. Next observe the following:

ElementsIndicesEquationLength
x1,ltwxl1,ltw12l1
x1,it2il1xi,ltx1,l12Llii+2l1
xi,jt2il1i+1jlxi,1tx1,j12Li11+4l12Li11+2Lljj+6l2j=ljl
xi,iti=1,2,,l1xi,i+1t2xi,i+1122Ll21+10l52(L1i+2Li11+4Lli+1i+1+12l4)i=l1il1
xl,ltxl,l1t2xl1,l122Ll21+12l5

So we generate all xi,jtfor 1i<jland xi,itfor 1il. Now wlxi,jtwl=xi,jtfor 1i<jland wlxi,itwl=xi,itfor 1il, then we get xi,jtand xi,it. Total number of SLPs is l+3+1+2+1=l+7. Hence we generate all the elementary matrices (Table A3) using only two generators x and w. Hence Sp(2l, p) is generated by only two generators x and w.

5.2 Split orthogonal group O+(2l, p)

Let p3mod4be a prime. It is known [16] that the group O+(2l,p) is generated by two elements:

x=x1,21,E3
E4

We will refer these two elements as Steinberg generators. As we discussed earlier, in context of the MOR cryptosystem, we need to know how to go back and forth between these two generating sets—Steinberg generators and elementary matrices (Table A1). To write w as a product of elementary matrices is easy, just put this generator through our Gaussian elimination algorithm. Here we demonstrate the other way round, that is, how to write elementary matrices as a product of x and w. In what follows, we denote the length of SLPs by Lδi, where δ=jiand 1i<jl.

δ=1,xi,jt=wi1x1,2twi1,δ=2,xi,jt=xi,j1txj1,j1,δ=3,xi,jt=xi,j1txj1,j1,δ=l1,xi,jt=xi,j1txj1,j1.

Here

Lδi=2i1forδ=1,2Lδ1+4i+δ6forδ=2,3,,l1.

Now wl=1l0IlIl0and xj,it=wlxi,jtwl, so length of this SLP is Lδi+2l. Hence we get all xi,jtfor 1ijl. The number of SLPs is l. Next observe the following:

ElementsIndicesEquationLength
x1,ltwxl1,ltw12l1
x1,it2il1xi,ltx1,l12Llii+2l1
xi,jt2il1i+1jlxi,1tx1,j12Li11+2Lljj+6l22Li11+4l1jlj=l

So we generate all xi,jtfor i>j. Now wlxi,jtwl=xi,jt, and we get xi,jtand the total number of SLPs is l+4. It is shown by Ree [17] that elementary matrices xi,jtgenerate Ω2lp, the commutator subgroup of O(2l, p). Hence we generate Ω2lp, using only two elements x and w. Since we generate xi,jtand wi,jas a product of xi,jtand w=w1,21w2,31wl1,l1wl, so we are able to generate wl. Here wi,jt=xi,jtxj,it1xi,jtfor ijand wl=Iel,lel,l+el,l+el,l. Now we know wl1=wlwl,l11wl1,l1, so we generate wl1. Hence by induction, we generate wi=wi+1wi+1,i1wi,i+11for i=l1,,1. Here wi,jt=xi,jt1xi,jt1xi,jt, for i<j. Hence we generate all the elementary matrices (Table A1) using only two generators x and w. So we generate a new subgroup WΩ2lpof O(2l,p), which is a normal subgroup of O(2l, p). Our algorithm output matrix is dλ=diag11λ11λ1. If λFp×2, say λt2mod p, then tλp+14mod p, since p3mod 4. Then

dλ=diag1t21t2=wl1,l1diag1t211t21wl1,l1=wl1,l1wl1,ltwl1,l1wl1,ltwl1,l1wl1,l1.

Hence we generate WΩ2lpusing only two generators x and w.

5.3 Orthogonal group O(2l+1, p)

Let p3mod4be a prime. It is known [16] that the group O(2l+1, p) is generated by these elements:

x=x0,11,E5
w=1000010I2l10,E6
wl=Iel,lel,l+el,l+el,l.E7

We will refer these three elements as Steinberg generators. However in context of the MOR cryptosystem, we need to know how to go back and forth between these two generating sets—Steinberg generators and elementary matrices (Table A5). To write w as a product of elementary matrices is easy, just put this generator through our Gaussian elimination algorithm. Here we demonstrate the other way round, that is, how to write elementary matrices as a product of w and x. First we compute, x0,it=wi1x0,11wi1which is of length 2i1for 1il. Now

wl=1l10000Il0Il0

and xi,0t=wlx0,itwlfor 1il, and length of this SLP is 2l+2i1. So we get xi,0tand x0,itfor i=1,2,,l. Again we have x1,2t=x1,0t2x0,21and length of this SLP is 4l+8. In what follows, we denote the length of SLPs by Lδi, where δ=jiand 1i<jl.

δ=1,xi,jt=wi1x1,2twi1,δ=2,xi,jt=xi,j1txj1,j1,δ=3,xi,jt=xi,j1txj1,j1,δ=l1,xi,jt=xi,j1txj1,j1.

Here

Lδi=2i+4l+6forδ=1,2Lδ1i+4i+δ+2l+2forδ=2,3,,l1.

As xj,it=wlxi,jtwl, so the length of this SLP is Lδi+2l. Hence we generate all xi,jtfor 1ijland the number of SLPs is 3+l1+1=l+3. Next observe the following:

ElementsIndicesEquation (SLP)Length
x1,ltwxl1,ltw16l+6
x1,it2il1xi,ltx1,l124l+202Llii+12l+1i=l1il1
xi,jt2il1i+1jlxi,1tx1,j12Li11+4Lljδjδ+47l+62Li11+47l+52Li11+10l+6j<l1j=l1j=l

So we generate all xi,jtfor i<j. Now wlxi,jtwl=xi,jt, and we have xi,jt. The total number of SLPs is l+7. It is shown in Ree [17] that elementary matrices xi,jtgenerate Ω2l+1p, the commutator subgroup of O2l+1pwhich is of index 4. So we generate Ω2l+1p, using only two generators x and w. Now we know wl1=wlwl,l11wl1,l1, so we generate wl1. Hence inductively we can generate wi=wi+1wi+1,i1wi,i+11for i=l1,,1. Here wi,jt=xi,jtxj,it1xi,jtfor ijand wi,jt=xi,jtxi,jt1xi,jtfor i<j. Hence we generate all the elementary matrices (Table A5) using only two generators x and w and an extra element wl. Hence we generate a new subgroup WΩ2l+1pof the orthogonal group O2l+1p, containing Ω, which is indeed a normal subgroup of O2l+1p. In our algorithm the output matrix is dλ=diag11λ1λ1. If λFp×2, say λt2modp, here tλp+14modp, since p3mod4. Then

dλ=diag11t21t2=wl1,l1diag11t211t21wl1,l1=wl1,l1wl1,ltwl1,l1wl1,ltwl1,l1wl1,l1.

Hence we generate WΩ2l+1pusing x,wand wl.

Remark 5.1Letdζ=diag11ζ1ζ1, whereζis non-square inFp×. The groupWΩdζis the orthogonal group.

5.4 Twisted orthogonal group O2lp

We use the following generators which we refer as Steinberg generators.

x=x1,21,
x=x1,21,
w=I2000010I2l30,
wl=Iel,lel,lel,lel,l,
x1ts,wheretFp×,sFpandx2.

In the context of MOR cryptosystem, we need to know how to go back and forth between these generators and elementary matrices (Table A7). The procedure is almost similar to the case of O+(2l,p). Again, note that x=x1,2, x=x1,2, x1ts, and x2 are elementary matrices. Thus, we just need to write w as a product of elementary matrices. However, computing w is fairly easy, just put this generator through our Gaussian elimination algorithm in Appendix A. Here we demonstrate the other way round, that is, how to write elementary matrices as a product of w, x, and x. First, we compute x1,it=wi1x1,21wi1which is of length 2i1for 2il. Now we compute xi,1tusing the relation xi,1t=wl1x1,itwl1for 2il, where wl1=1l1I20000Il10Il10and length of this SLP is 2l1+2i1. Thus, we get xi,1tand x1,it, for i=2,,l. Similarly we compute xi,1tand x1,itusing the relations x1,it=wi1x1,21wi1and xi,1t=wl1x1,itwl1for 2il, and length of this SLP are 2i1and 2l1+2i1, respectively. Next, we compute x2,3tusing the commutator formula x2,3t=x2,1t2x1,31, and length of this SLP is 4l1+8. In what follows, we denote the length of SLPs by Lδi, where δ=jiand 2i<jl.

δ=1,xi,jt=wi1x2,3twi1,δ=2,xi,jt=xi,j1txj1,j1,δ=3,xi,jt=xi,j1txj1,j1,δ=l1,xi,jt=xi,j1txj1,j1.

Here

Lδi=2i+4l1+6forδ=1,2Lδ1i+4i+δ+2l1+2forδ=2,3,,l2.

As xj,it=wl1xi,jtwl1, so length of this SLP is Lδi+2l1. Hence, we get all xi,jtfor 2ijland the number of SLPs is l+2. Next, we compute the remaining elementary matrices using the commutator formula and are listed in the table; let r=l1.

ElementsIndicesEquation (SLP)Length
x1,ltwxl1,ltw16l1+6
x1,it2il1xi,ltx1,l124l1+202Lrii+12r+1i=l1il1
xi,jt2ir1i+1jlxi,1tx1,j12Li11+47r+6+4Lrjδjδ2Li11+47r+52Li11+10r+6j<l1j=l1j=l

Thus, we have generated all xi,jtfor i<j. Now, using the formula wlxi,jtwl=xi,jt, we get xi,jtand the total number of SLPs required is l+6. Now we know wl1=wlwl,l11wl1,l1, so we generate wl1. Hence by induction we can generate wi=wi+1wi+1,i1wi,i+11, for i=l1,,2. Here wi,jt=xi,jtxj,it1xi,jt, for ij, and wi,jt=xi,jtxi,jt1xi,jt, for i<j. Hence we generate all the elementary matrices defined in Table A7 using generators x, x, x1ts, x2, and wand an extra element wl. In our algorithm the output matrix is dλ=diag1,1,1λ1λ1. If λFp×2, say λt2mod p, here tλp+14mod p, since p3mod 4.

Then dλ=diag1,1,1t21t2=wl1,l1diag1,1,1t211t21wl1,l1=wl1,l1wl1,ltwl1,l1wl1,ltwl1,l1wl1,l1.

Remark 5.2Letdζ=diag1,1,1ζ1ζ1, whereζis non-square inFp×. Then as a consequence of our Gaussian elimination algorithm in Appendix A, we can see thatx,x,x1ts,x2,wandwlalong withdζgenerate the twisted orthogonal group.

6. Conclusion

This section is similar to ([6], Section 8). A useful public-key cryptosystem is a delicate dance between speed and the security. So one must talk about speed along with security.

The implementation of the MOR cryptosystem that we have in mind uses the row-column operations. Let g1g2gsbe a set of generators for the orthogonal or symplectic group as described before. As is the custom with a MOR cryptosystem, the automorphisms ϕand ϕmare presented as action on generators, i.e., we have ϕgiand ϕmgias matrices for i=1,2,,s.

To encrypt a message in this MOR cryptosystem, we compute ϕr. We do that by square-and-multiply algorithm. For this implementation, squaring and multiplying is almost the same. So we will refer to both squaring and multiplication as multiplication. Note that multiplication is composed of automorphisms.

The implementation that we describe in this chapter can work in parallel. Each instance computes ϕrgifor i=1,2,,s. First thing that we do is write the matrix of ϕgias a word in generators. So essentially the map ϕbecomes a map giwiwhere wiis a word in generators of some fixed length. Then multiplication becomes essentially a replacement, replace all instances of giby wi. This can be done very fast. However, the length of the replaced word can become very large. The obvious question is how soon are we going to write this word as a matrix. This is a difficult question to answer at this stage and depends on available computational resources.

Once we decide how often we change back to matrices, how are we going to change back to matrices? There can be a fairly easy time-memory trade-offs. Write all words up to a fixed length and the corresponding matrix as a pre-computed table and use this table to compute the matrices. Once we have matrices, we can multiply them together to generate the final output. There are also many obvious relations among the generators of these groups. One can just store and use them. The best strategy for an efficient implementation is yet to be determined. It is clear now that there are many interesting and novel choices.

The benefits of this MOR cryptosystem are:

  1. This can be implemented in parallel easily.

  2. This implementation does not depend on the size of the characteristic of the field. This is an important property in light of Joux’s recent improvement of the index-calculus attacks [11].

For parameters and complexity analysis of this cryptosystem, we refer to ([6], Section 8). Assume that we take a prime of size 2160 and we are using two generators presentation of ϕfor the even-orthogonal group. Then the security is the discrete logarithm problem in Fpd2. Now if we take d=4, then the security is better than F22560. Our key-size is about 8000 bits. Comparing with Monico ([10], Section 7), where he says an ElGamal will have about 6080 bits, our system is quite comparable. Moreover, the MOR cryptosystem is better suited to handle large primes and can be easily parallelized.

Acknowledgments

We are thankful to the editor and referees for their valuable comments which has improved the paper substantially. This work was supported by a SERB research grant. This chapter contains part of the PhD thesis of the first and the third author, directed by the second and the fourth author at IISER Pune.

In computational group theory, one is always looking for algorithms that solve the word problem. When G is a special linear group, one has a well-known algorithm to solve the word problem—the Gaussian elimination algorithm. One observes that the effect of multiplying an element of the special linear group by an elementary matrix (also known as elementary transvection) from left or right is either a row or a column operation, respectively. Using this algorithm one can start with any matrix gSLl+1kand get to the identity matrix, thus writing g as a product of elementary matrices ([18], Proposition 6.2). One of the objective of this appendix is to discuss a similar algorithm for orthogonal and symplectic groups, with a set of generators that we will call elementary matrices in their respective groups. Similar algorithms can be found in the works of Brooksbank [19, 20] and Costi [21]. However, we have no restrictions on the cardinality or characteristic of the field k.

We first describe the elementary matrices and the row-column operations for the respective groups. These row-column operations are nothing but multiplication by elementary matrices from left and right, respectively. Here elementary matrices used are nothing but Chevalley generators which follows from the theory of Chevalley groups.

The basic idea of the algorithm is to use the fact that multiplying any orthogonal matrix by any one of the generators enables us to perform row or column operations. The relation Tgβg=βgives us some compact relations among the blocks of g which can be used to make the algorithm faster. To make the algorithm simple, we will write the algorithm for O2l+1k, O+2lk, and O2lkseparately.

A.1 Groups in which Gaussian elimination works

  • Symplectic groups: Since all non-degenerate skew-symmetric bilinear forms are equivalent ([22], Corollary 2.12), we have a Gaussian elimination algorithm for all symplectic groups over an arbitrary field.

  • Orthogonal groups:

    • Since non-degenerate symmetric bilinear forms over a finite field of odd characteristics are classified ([22], p. 79) according to the β (see Section 3), we have a Gaussian elimination algorithm for all orthogonal groups over a finite field of odd characteristics.

    • Since non-degenerate quadratic forms over a perfect field of even characteristics can be classified ([23], p. 10) according to quadratic forms Q(x) defined in ([24], Section 4.2), we have a Gaussian elimination algorithm for all orthogonal groups over a perfect field of even characteristics.

    • Furthermore, we have Gaussian elimination algorithm for orthogonal groups that are given by the above bilinear forms or quadratic forms over arbitrary fields. This algorithm also works for bilinear or quadratic forms that are equivalent to the above forms.

A.2 Gaussian elimination for matrices of even size—orthogonal group O+dkand symplectic group

Recall that the bilinear forms βare the following:

  • For symplectic group, Spdk, d=2l, and β=0IlIl0.

  • For orthogonal group, O+dk, d=2l, and β=0IlIl0.

Note that any isometry g satisfies Tgβg=β. The main reason our algorithm works is the following: Recall that a matrix g=ABCD, where A, B, C, and D are matrices of size l, is orthogonal or symplectic if Tgβg=βfor the respective β. After some usual calculations, for orthogonal group it becomes

TCA+TACTCB+TADTDA+TBCTDB+TBD=0IlIl0EA.1

The above equation implies among other things, TCA+TAC=0. This implies that TAC is skew-symmetric. In an almost identical way, one can show, if g is symplectic, TAC is symmetric. The working principle of our algorithm is simple—use the symmetry of TAC. The problem is, for arbitrary A and C, it is not easy to use this symmetry. In our case we were able to reduce A to a diagonal matrix, and then it is relatively straightforward to use this symmetry. We will explain the algorithm in details later. First of all, let us describe the elementary matrices and the row-column operations for orthogonal and symplectic groups. The genesis of these elementary matrices lies in the Chevalley basis of simple Lie algebras. We will not go into details of Chevalley’s theory in this appendix. Furthermore, we do not need to, the algorithm that we produce will show that these elementary matrices are generators for the respective groups.

Next we present the elementary matrices for the respective groups and then the row-column operations in a tabular form.

A.2.1 Elementary matrices (Chevalley generators) for orthogonal group O+dkof even size

Following the theory of root system in a simple Lie algebra, we index rows by 1,2,,l,1,2,,l. For tk, the elementary matrices are defined as follows (Tables A1 and A2):

Char(k)Elementary matrices
xi,jtI+tei,jej,iij
Bothxi,jtI+tei,jej,ii<j
xi,jtI+tei,jej,ii<j
wiIei,iei,i+ei,i+ei,i1il

Table A1.

Elementary matrices for O+2lk.

Row operationsColumn operations
ER1ithith+tjthrowEC1jthjth+tithcolumn
jthjthtithrowithithtjthcolumn
ER2ithith+tjthrowEC2ithithtjthcolumn
jthjthtithrowjthjth+tithcolumn
ER3ithithtjthrowEC3jthjth+tithcolumn
jthjth+tithrowithithtjthcolumn
wiInterchange ith and ithrowInterchange ith and ithcolumn

Table A2.

The row-column operations for O+2lk.

Let us note the effect of multiplying g by elementary matrices. We write gO+2lkas g=ABCD, where A,B,C, and Dare l×lmatrices.

A.2.2 Elementary matrices (Chevalley generators) for symplectic group

For tk, the elementary matrices are defined as follows (Table A3):

Char(k)Elementary matrices
xi,jtI+tei,jej,iij
Bothxi,jtI+tei,j+ej,ii<j
xi,jtI+tei,j+ej,ii<j
xi,itI+tei,i1il
xi,itI+tei,i1il

Table A3.

Elementary matrices for Sp2lk.

Let us note the effect of multiplying g by elementary matrices. We write gSp2lkas g=ABCD, where A, B, C, and D are l×lmatrices (Table A4).

Row operationsColumn operations
ER1ithith+tjthrowEC1jthjth+tithcolumn
jthjth+tithrowithith+tjthcolumn
ER2ithith+tjthrowEC2ithith+tjthcolumn
jthjth+tithrowjthjth+tithcolumn
ER3ithith+tjthrowEC3jthjth+tithcolumn
jthjth+tithrowithith+tjthcolumn
ER1aithith+tithrowEC1aithith+tithcolumn
ER2aithith+tithrowEC2aithith+tithcolumn
wiInterchange ith and (−i)th rowsInterchange ith and (−i)th columns
with a sign change in the ith rowwith a sign change in the ith column

Table A4.

The row-column operations for symplectic groups.

A.2.3 Gaussian elimination for Sp2lkand O+2lk

  1. Step 1: Use ER1 and EC1 to make A into a diagonal matrix. This makes A into a diagonal matrix and changes other matrices A, B, C, and D. For the sake of notational convenience, we keep calling these changed matrices as A, B, C, and D as well.

  2. Step 2: There are two possibilities. One, the diagonal matrix A is of full rank, and two, the diagonal matrix A is of rank rless than l. This is clearly identifiable by looking for zeros in the diagonal of A.

  3. Step 3: Make rrows of C, corresponding to the non-zero entries in the diagonal of A zero by using ER3. If r=l, we have C as zero matrix. If not let us assume that ith row is zero in A. Then we interchange the ithrow with the ithrow in g. We do this for all zero rows in A. The new C is a zero matrix. We claim that the new A must have a full rank. This follows from Equation A.1; in particular TCB+TAD=Il. If C is zero matrix, then A is invertible. Now make A a diagonal matrix by using Step 1. Then one can make A a matrix of the form diag11λ, where λk×using ER1 ([18], Proposition 6.2). Once A is diagonal and C a zero matrix, the equation TCB+TAD=Ilmakes D a diagonal matrix of full rank.

  4. Step 4: Use ER2 to make B a zero matrix. The matrix g becomes a diagonal matrix of the form

  5. diag11λ11λ1, where λk×.

  6. Step 5: (Only for symplectic groups) Reduce the λto 1using Lemma A.1.

Lemma A.1ForSp2lk, the elementdiag11λ11λ1is a product of elementary matrices.

Proof. Observe that I+λel,lIλ1el,lI+λel,l=Iel,lel,l+λel,lλ1el,land denote it by wlλ, and then the diagonal element is wlλwl1.

Remark A.1As we saw in the above algorithm, we will have to interchangeithandithrows fori=1,2,,l. This can be done by pre-multiplying with a suitable matrix.

Let I be the 2l×2lidentity matrix over k. To swap ith and −ith row in O+2lk, swap ith and −ith rows in the matrix I. We will call this matrix wi. It is easy to see that this matrix wi is in O+2lkand is of determinant −1. Pre-multiplying with wi does the row interchange we are looking for.

In the case of symplectic group Sp2lk, we again swap two rows ith and −ith in I. However we do a sign change in the ith row and call it wi. Simple computation with our chosen βshows that the above matrices are in O+2lkand Sp2lk, respectively.

However there is one difference between orthogonal and symplectic groups. In symplectic group, wi can be generated by elementary matrices because wi=xi,i1xi,i1xi,i1. In the case of orthogonal groups, that is not the case. This is clear that the elementary matrices come from the Chevalley generators and those generates Ω, the commutator of the orthogonal group. All matrices in Ωhave determinant 1. However wi has determinant −1. So we must add wi as an elementary matrix for O+2lk.

Remark A.2This algorithm proves every element in the symplectic group is of determinant 1. Note the elementary matrices for the symplectic group are of determinant 1, and we have an algorithm to write any element as product of elementary matrices. So this proves that the determinant is 1.

Remark A.3This algorithm proves if X is an element of a symplectic group then so is TX. The argument is similar to the above; here we note that the transpose of an elementary matrix in symplectic groups is an elementary matrix.

A.3 Gaussian elimination for matrices of odd size—the odd-orthogonal group

In this case, matrices are of odd size and there is only one family of group to consider; it is the odd-orthogonal group O2l+1k. This group will be referred to as the odd-orthogonal group.

A.3.1 Elementary matrices (Chevalley generators) for O2l+1k

Following the theory of Lie algebra, we index rows by 0,1,,l,1,,l. These elementary matrices are listed in Table A5.

Char(k)Elementary matrices
Bothxi,jtI+tei,jej,iij
xi,jtI+tei,jej,ii<j
xi,jtI+tei,jej,ii<j
Oddxi,0tI+t2ei,0e0,it2ei,i1il
x0,itI+t2ei,0+e0,it2ei,i1il
Evenxi,0tI+te0,i+t2ei,i1il
x0,itI+te0,i+t2ei,i1il

Table A5.

Elementary matrices for O2l+1k.

Elementary matrices for the odd-orthogonal group in even characteristics differ from that of odd characteristics. In above table we made that distinction and listed them separately in different rows according to the characteristics of k. If char(k) is even, we can construct the elements wi, which interchanges the ith row with ithrow as follows:

wi=I+e0,i+ei,iI+e0,i+ei,iI+e0,i+ei,i=I+ei,i+ei,i+ei,i+ei,i.

Otherwise, we can construct wi, which interchanges the ith row with ithrow with a sign change in ith,ithand0throw in odd-orthogonal group as follows:

wi=x0,i1xi,01x0,i1=I2e0,0ei,iei,iei,iei,i.

The Gaussian elimination algorithm for O2l+1kfollows the earlier algorithm for symplectic and even-orthogonal group closely, except that we need to take care of the zero row and the zero column. We write an element gO2l+1kas g=αXYEABFCD, where A,B,C, and Dare l×lmatrices, Xand Yare 1×lmatrices, Eand Fare l×1matrices, αkand β=20000Il0Il0. Then from the condition Tgβg=β, we get the following relations:

2TXX+TAC+TCA=0EA.2
2αTX+TAF+TCE=0EA.3
2αY+TED+TFB=0EA.4
2TXY+TAD+TCB=IlEA.5

Let us note the effect of multiplying g by elementary matrices (Table A6).

Row operationsColumn operations
ER1ithith+tjthrowEC1jthjth+tithcolumn
(both)jthjthtithrow(both)ithithtjthcolumn
ER2ithith+tjthrowEC2ithithtjthcolumn
(both)jthjthtithrow(both)jthjth+tithcolumn
ER3ithithtjthrowEC3jthjth+tithcolumn
(both)jthjth+tithrow(both)ithithtjthcolumn
ER40th0thtithrowEC40th0th+2tithcolumn
(odd)ithith+2t0tht2ithrow(odd)ithitht0tht2ithcolumn
ER50th0th+tithrowEC50th0th2tithcolumn
(odd)ithith2t0tht2ithrow(odd)ithith+t0tht2ithcolumn
ER60th0th+tithrowEC6ithith+t0th+t2ithcolumn
(even)ithith+t2ithrow(even)
ER70th0th+tithrowEC7ithith+t0th+t2ithcolumn
(even)ithith+t2ithrow(even)
wiInterchange ithand ithrowswiInterchange ithand ithcolumn
(odd)with a sign change in ith,ithand0throws(odd)with a sign change in ith,ithand0thcolumns
wi(even)Interchange ithand ithrowwi(even)Interchange ithand ithcolumn

Table A6.

The row-column operations for O2l+1k.

A.3.2 Gaussian elimination for O2l+1k

  1. Step 1: Use ER1 and EC1 to make A into a diagonal matrix, but in the process, it changes other matrices A,B,C,D,E,F,X, and Y. For the sake of notational convenience, we keep calling these changed matrices as A,B,C,D,E,F,X, and Y as well.

  2. Step 2: Now there will be two cases depending on the rank rof matrix A. The rank of A can be easily determined using the number of non-zero diagonal entries. Use ER3 and non-zero diagonal entries of A to make corresponding rrows of C zero.

    1. If r=lthen C becomes zero matrix.

    2. If r<lthen interchange all zero rows of A with corresponding rows of C using wi so that the new C becomes a zero matrix.

  3. Once C becomes zero, note that Relation A.2 if char(k) is odd or Relation Qgv=Qvif char(k) is even guarantees that X becomes zero. Relation A.5 guarantees that A has full rank l which also makes D a diagonal with full rank l. Thus Relation A.3 shows that F becomes zero as well. Then use Step 1 to reduce A=diag11λ, where λk×.

  4. Step 3: Now if char(k) is even, then Relation A.4 guarantees that E becomes zero as well. If char(k) is odd, then use ER4 to make E a zero matrix.

  5. Step 4: Use ER2 to make B a zero matrix. For char(k) even the relation Qgv=Qvguarantees that Y is a zero matrix, and for char(k) odd Relation A.4 implies that Y becomes zero.

Thus the matrix g reduces to diag±11λ1λ, where λk×.

Remark A.4Let k be a perfect filed of characteristics 2. Note that we can write the diagonal matrixdiag11λ11λ1as a product of elementary matrices as follows:

diag11λ11λ1=xl,ltxl,lt1xl,lt,wheret2=λ,

and hence we can reduce the matrix g to identity.

A.4 Gaussian elimination in twisted orthogonal groups

In this section we present a Gaussian elimination algorithm for twisted orthogonal groups. The size of the matrix is even; the bilinear form used is cfrom Section 3.

A.4.1 Elementary matrices (Chevalley generators) for twisted orthogonal groups O2lk

In this section, we describe row-column operations for twisted Chevalley groups. These groups are also known as the Steinberg groups. An element gO2lkis denoted as g=A0XYEABFCD, where A,B,C, and Dare l1×l1matrices, Xand Yare 2×l1matrices, Eand Fare l1×2matrices, and A0is a 2×2matrix. In the Gaussian elimination algorithm that we discuss, we reduce X,Y,E,F,B, and C to zero and A and D to diagonal matrices. However, unlike the previous cases, we were unable to reduce A0 to an identity matrix. However, for odd characteristics we were able to reduce A0 to a two-parameter subgroup.

We now talk about the output of the algorithm. In the output we will have a 2×2block (also called A0) which will satisfy TA0β0A0=β0, where β0=100ϵfor odd characteristics and εis a non-square. Then A0 is a orthogonal matrix given by the bilinear form β0. Now if we write A0=abcd, then we get the following equations:

a2+c2ϵ=1,ab+cdϵ=0,b2+d2ϵ=ϵ.

Considering the fact that detA0=±1, one more equation adbc=±1and this leads to two cases either a=dand b=cϵor a=dand b=cϵ. Recall that, since ϵis not a square, d0. Then if c=0, then there are four choices for A0and these are A0=±100±1.

To summarize, the output of the algorithm A0will have one of the following forms

tsϵstortsϵst,wheret2+s2ϵ=1,EA.6

and tk×, sk, and ϵare non-square. There are now two ways to describe the algorithm: one is to leave A0 as it is in the output of the algorithm, and the other is to include these matrices as generators. For the purpose of uniform exposition, we chose the latter and included the following two generators

x1ts=I+t1e1,1t+1e1,1+se1,1+ϵe1,1;t2+ϵs2=1,x2=I2e1,1,

in the list of elementary matrices in Table A7. In the case of even characteristics, no such reduction is possible, and we included the matrix tprsin the list of generators with the condition that the determinant is 1.

Char(k)Elementary matrices
xi,jtI+tei,jej,iij
Bothxi,jtI+tei,jej,ii<j
xi,jtI+tei,jej,ii<j
wiIei,iei,i+ei,i+ei,i2il
xi,1tI+te1,i2ei,1t2ei,i2il
x1,itI+te1,i+2ei,1t2ei,i2il
xi,1tI+te1,i2εei,1εt2ei,i2il
Oddx1,itI+te1,i+2εei,1εt2ei,i2il
x1tsI+t1e1,1t+1e1,1+se1,1+εe1,1t2+εs2=1
x2I2e1,1
x1,itI+te1,i+tei,1+αt2ei,i2il
Evenx1,itI+te1,i+tei,1+αt2ei,i2il
xA0I+t1e1,1+s1e1,1+pe1,1+re1,1ts+pr=1

Table A7.

Elementary matrices for O2lk.

The elementary matrices for O2lkdepend on the characteristics of k. We describe them separately in the following table. Let αbe an Arf-invariant, 2i,jland tKand ξk×.

Let us note the effect of multiplying g by elementary matrices. Elementary matrices for the twisted orthogonal group in even characteristics differ from that of odd characteristics, so in the following tables (Tables A8 and A9), we made that distinction and listed them separately in different rows according to the characteristics of k.

Row operations
ER1 (both)ithith+tjthrow and jthjthtithrow
ER2 (both)ithith+tjthrow and jthjthtithrow
ER3 (both)ithithtjthrow and jthjth+tithrow
ER4 (odd)1st1sttithrow and ithith+2t1stt2ithrow
ER5 (odd)1st1st+tithrow and ithith2t1stt2ithrow
ER6 (odd)1th1thtithrow and ithith+2εt1thεt2ithrow
ER7 (odd)1th1th+tithrow and ithith2εt1thεt2ithrow
ER8 (even)1st1st+tithrow and ithith+t1th+αt2ithrow
ER9 (even)1th1th+tithrow and ithith+t1st+αt2ithrow
wi (both)Interchange ithand ithrow

Table A8.

The row operations for O2lk.

Column operations
EC1(both)jthjth+tithcolumn and ithithtjthcolumn
EC2 (both)ithithtjthcolumn and jthjth+tithcolumn
EC3 (both)jthjth+tithcolumn and ithithtjthcolumn
EC4 (odd)1st1st+2tithcolumn and ithitht1stt2ithcolumn
EC5 (odd)1st1st2tithcolumn and ithith+t1stt2ithcolumn
EC6 (odd)1th1th+2εtithcolumn and ithitht1thεt2ithcolumn
EC7 (odd)1th1th2εtithcolumn and ithith+t1thεt2ithcolumn
EC8 (even)1th1th+tithcolumn and ithith+t1st+αt2ithcolumn
EC9 (even)1st1st+tithcolumn and ithith+t1th+αt2ithcolumn
wi (both)Interchange ith and (−i)th column

Table A9.

The column operations for O2lk.

Note that any isometry g satisfies Tgβg=β. The main reason the following algorithm works is the closed condition Tgβg=βwhich gives the following relations:

TA0β0A0+TFE+TEF=β0,EA.7
TA0β0X+TFA+TEC=0,EA.8
TA0β0Y+TFB+TED=0,EA.9
TXβ0X+TCA+TAC=0,EA.10
TXβ0Y+TCB+TAD=Il1.EA.11

A.4.2 The Gaussian elimination algorithm for O2lk

  1. Step 1: Use ER1 and EC1 to make A into a diagonal matrix, but in the process, it changes other matrices A0, A,B,C,D,E,F,X, and Y. For the sake of notational convenience, we keep calling these changed matrices as A0, A,B,C,D,E,F,X, and Yas well.

  2. Step 2: Now there will be two cases depending on the rank rof the matrix A. The rank of Acan be easily determined by the number of non-zero diagonal entries.

  3. Step 3: Use ER3 and non-zero diagonal entries of Ato make corresponding rrows of Czero.

    • If r=l1then Cbecomes zero matrix.

    • If r<l1then interchange all zero rows of Awith corresponding rows of Cusing wi, so that the new Cbecomes a zero matrix.

    • Once Cbecomes zero one, can note that the relation TXβ0X+TCA+TAC=0if charkis odd or the relation Qgv=Qvand the fact that αt2+t+αis irreducible when charkis even guarantees that Xbecomes zero. Then the relation TXβ0Y+TCB+TAD=Il1guarantees that Ahas full rank l1which also makes Da diagonal with full rank, and the relation TA0β0X+TFA+TEC=0shows that Fis zero. Now we diagonalize Aagain to the form diag11λ, where λk×as in Step 1.

  4. Step 4: Use EC4 and EC6 when charkis odd or use EC8 and EC9 when charkis even to make Ezero. Note that the relation TA0β0A0+TFE+TEF=β0shows that A0is invertible. Thus the relation TA0β0Y+TFB+TED=0guarantees that Ybecomes zero.

  5. Step 5: Use ER2 to make Ba zero matrix. Thus the matrix greduces to g=diagA01λ1λ1. Now if charkis odd, then go to Step 6; otherwise go to Step 7.

  6. Step 6: Using the relation TA0β0A0=β0, it is easy to check that A0has the form tϵsstor tϵsst. If the determinant of A0is 1, multiply gby x2to get new gof the above form such that A0has determinant 1. Now using the elementary matrix x1ts, we can reduce gto diagI21λ1λ1.

  7. Step 7: Using elementary matrix xA0, we can reduce gto diagI21λ1λ1.

Lemma A.2Let k be a field of characteristics 2 and letg=A0XYEABF0D, whereA=diag111λ, be an element of O2lkthenX=0.

Proof. Let e1e1e2ele2elbe the standard basis of the vector space V. Recall that for a column vector x=x1x1x2xlx2xlt, the action of the quadratic form Qis given by Qx=αx12+x12+x1x1++xlxl, where αt2+t+αis irreducible over kt. By definition, for any gO2lk, we have Qgx=Qxfor all xV. Let X=x11x1l1x21x2l1be a 2×l1matrix. Computing Qgei=Qeifor all 2il, we can see that αx1i2+x2i2+x1ix2i=0. If x2i=0then we can see that x1i=0. Suppose x2i0for some i, then we rewrite the equation by dividing it by x2ias αx1ix2i2+x1ix2i+α=0, which is a contradiction to the fact that αt2+t+αis irreducible over kt. Thus, x2i=0for all 2iland hence X=0. •

A.5 Time complexity of the above algorithms

We establish that the worst-case time complexity of the above algorithm is Ol3. We mostly count the number of field multiplications.

  1. Step 1: We make Aa diagonal matrix by row-column operations that has complexity Ol3.

  2. Step 2: In making both C and B zero matrix, we multiply two rows by a field element and additions. In the worst case, it has to be done Oltimes and done Ol2many times. So the complexity is Ol3.

  3. Step 3: In odd-orthogonal group and twisted orthogonal group, we clear X,Y,E,F, this clearly has complexity Ol2.

  4. Step 4: This step has only a few operations that is independent of l.

Then clearly, the time complexity of our algorithm is Ol3.

We have implemented the above algorithms in Magma [25]. For details of that implementation along with performance analysis of our algorithm, we refer to Bhunia et al. ([24], Section 8).

Download

chapter PDF

© 2019 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Sushil Bhunia, Ayan Mahalanobis, Pralhad Shinde and Anupam Singh (March 9th 2019). The MOR Cryptosystem in Classical Groups with a Gaussian Elimination Algorithm for Symplectic and Orthogonal Groups [Online First], IntechOpen, DOI: 10.5772/intechopen.84663. Available from:

chapter statistics

88total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More about us