Elementary matrices for O.
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.
- public-key cryptography
- MOR cryptosystem
- Chevalley groups
- Gaussian elimination
- 2010 Mathematics Subject Classification: 94A60
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. . We further recommend the work of Grogoriev et al.  and Roman’kov .
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  and cryptanalyzed by Monico . It became clear that working with matrix groups of size d over and 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 or (, 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 . The reason that we undertook this study is to see if the security in other classical Chevalley groups is or .
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 . 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  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 SLto denote what we will denote by SLor SL. We have used to denote the transpose of the matrix X. This was necessary to avoid any confusion that might arise when using and simultaneously. In this chapter, we use and interchangeably, while each of them is a finite field of odd characteristic. However, in the appendix the field k is unrestricted. The matrix is used to denote the matrix unit with t in the place and zero everywhere else. We will often use as generators, a notation used in the theory of Chevalley groups. Here r is a short hand for and are defined in Tables A1,A3,A5, and A7. We often refer to the orthogonal group as , specifically, the split orthogonal group as or and the twisted orthogonal group as . 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. . 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 but is not secure in any cyclic group.
Definition 2.1 (The discrete logarithm problem). The discrete logarithm problem in, 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,, and, find.
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 . It is defined as follows:
2.1 The ElGamal cryptosystem
A cyclic group is public.
Public-key: Let and be public.
Private-key: The integer be private.
To encrypt a plaintext , get an arbitrary integer and compute and . The ciphertext is .
After receiving the ciphertext , the user uses the private-key . So she computes from and then computes .
It is well known that the hardness of the ElGamal cryptosystem is equivalent to the Diffie-Hellman problem (, 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 be a finite group. Let be a non-identity automorphism.
Public-key: Let and be public.
Private-key: The integer is private.
To encrypt a plaintext , get an arbitrary integer and compute and . The ciphertext is .
After receiving the ciphertext , the user knows the private-key m. So she computes from and then computes .
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 from in the public-key and in the ciphertext. This breaks the system.
On the other hand, observe that the plaintext is . Assume that there is an oracle that can break the MOR cryptosystem, i.e., given and a plaintext will deliver . Now we query the oracle s times with the public-key and the ciphertext for . From the output, one can easily find for . So we just witnessed that for and , one can compute using the oracle. This solves the Diffie-Hellman problem.
In a practical implementation of a MOR cryptosystem, there are two things that matter the most.
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.
b: Efficient algorithm to solve the word problem. This means that given and , is there an efficient algorithm to write as word in ? The reason of this importance is immediate—the automorphisms are presented as action on generators, and if one has to compute , 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 of odd characteristic. Let be 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 , where are column vectors. We will work with non-degenerate bilinear forms and that means . A symmetric or skew-symmetric bilinear form satisfies or , respectively.
Definition 3.1 (Orthogonal group). A square matrix X of size d is called orthogonal if, whereis 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 if, whereis skew-symmetric. And the set of symplectic matrices form a symplectic group.
We write the dimension of V as or for . We fix a basis and index it by in 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 and for split and twisted forms, respectively. We consider the non-degenerate bilinear forms on given by the following matrices:
a: The odd-orthogonal group. The form is symmetric with and .
b: The symplectic group. The form is skew-symmetric with and .
c: The split orthogonal group. The form is symmetric with and .
: The twisted orthogonal group. The form is symmetric with and ,
where Il is the identity matrix of size l over and for a fixed non-square , .
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
whereorandis of type a, c, or, respectively.
Definition 3.4 (Symplectic similitude group). The symplectic similitude group is defined as
whereis of type b.
Here depends on the matrix and is called the similitude factor. The similitude factor defines a group homomorphism from the similitude group to , and the kernel is the orthogonal group when is symmetric and symplectic group and when is skew-symmetric, respectively (, Section 12). Note that scalar matrices for belong to the center of similitude groups. The similitude groups are analog of what is for . 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 of, it is
and in the case of and , it is
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 .
Conjugation automorphisms: If N is a normal subgroup of a group G, then the conjugation maps for and are called conjugation automorphisms of G. In particular, both inner automorphisms and diagonal automorphisms are examples of conjugation automorphisms.
Central automorphisms: Let be a homomorphism to the center of the group. Then the map is an automorphism of G, known as the central automorphism. There are no nontrivial central automorphisms for perfect groups, for example, the Chevalley groups and , , and . In the case of orthogonal group, the center is of two elements , where I is the identity matrix. This implies that there are at most four central automorphisms in this case.
Field automorphisms: Let . 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 SLand and Oand . We also get an automorphisms of order 3 for O.
In the case of SL(d, q) for , the map , where
explicitly describes the graph automorphism.
In the case of O(2l, q) for , the graph automorphism is given by where B is a permutation matrix obtained from identity matrix of size by switching the row and row. This automorphism is a conjugating automorphism.
Theorem 3.1 (Dieudonne). Letbe a field of odd characteristic and.
1. For the group , any automorphism is of the form where is a conjugation automorphism defined by elements of and is a graph automorphism for the special linear group.
2. For the group , any automorphism is of the form where is a central automorphism and is a conjugation automorphism by elements of (this includes the graph automorphism of even-orthogonal groups).
3. For the group , any automorphism is of the form , where is a conjugation automorphism by elements of .
4. For the group , any automorphism is of the form where is a conjugation automorphism by elements of .
In all cases θ denotes a field automorphism.
For a proof of the above theorem, see , 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 and where is 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 Oand twisted orthogonal group by O. 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 : or . From Theorem 3.1, we know that where 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 . 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 (, Section 7) that if we can recover the conjugating matrix from the action on generators, the security is a discrete logarithm problem in , or else the security is a discrete logarithm problem in .
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 and usually constitute the bulk of automorphisms. If is an inner automorphism, say , we would like to determine the conjugating element g. For the special linear group, it was done in . We will follow the steps there for the present situation too. However, before we do that, let us digress briefly to observe that given by is a surjective group homomorphism. Thus if G is generated by , then is generated by . Let . If we can find generators, such that , then where . This implies that our problem is equivalent to solving the word problem in . 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 , where for the special linear group. For symplectic group . For the even-orthogonal group, . For the odd-orthogonal group . 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 . 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., , for some g, and we try to determine g.
Step 1: The automorphism is presented as action on generators .
Thus . This implies that we know for all possible . 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 , where Gi are column vectors of g. Then where Gi is at the jth place. Multiplying this with on the right, i.e., computing , determines Gi up to a scalar multiple di (say). Thus, we know where .
For the symplectic groups, we do the similar computation with the generators and . Write g in the column form as . Now,
where Gi is at −ith place. Multiplying this further with gives us scalar multiple of Gi, say .
where is at ith place. Multiplying this with gives us scalar multiple of , say .
Thus we get where D is a diagonal matrix .
Step 2: Compute which is equivalent to computing .
In the case of special linear groups, we have D a diagonal. Thus by computing , we determine for and form a matrix , and multiplying this to N, we get . Hence we can determine g up to a scalar matrix.
For symplectic groups, we can do similar computation as D is diagonal. First compute to get and for . Now compute to get . We form a matrix
and multiply it to to get . Thus we can determine g up to a scalar multiple say ag. Similarly we can determine gm up to a scalar multiple say . Now, compute and , and then we can recover m by solving the discrete logarithm in the matrices using Menezes and Wu’s idea . However, if we choose g such that , 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 using Menezes and Wu’s idea. We prove the following proposition.
Proposition 4.1Given anyup to scalar multiple ag,. If, we can determine the scalar a. Otherwise one can find the scalar a by solving a discrete logarithm problem in.
Proof. We can recover the scalar a as follows: Let be a set of eigenvalues of g, and then the eigenvalues of ag are . Set and thus as . Suppose , using extended Euclidean algorithm, we find u and such that . Next, computing , we get . Thus, if , then we have recovered the scalar a; otherwise we can recover the scalar by solving the discrete logarithm problem in .
Thus, if , then using the above proposition, we can recover the scalars a and b from and , respectively. Otherwise one needs to solve discrete logarithm problem in to recover the scalars. Now, we can recover and from and just by multiplying with scalar matrices and , respectively. Finally, we recover using Menezes and Wu’s idea. Thus, if we choose such that and , then to solve the discrete logarithm in , one needs to solve the discrete logarithm in and .
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.1Let. Consider the conjugation automorphism. Letbe a set of Chevalley generators of O(d,q) described in Appendix A. Suppose that the public-key is presented as an action ofon, 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, d even, and the theorem follows for other cases similarly. Let and we write g in columns form as . We compute which gives the following equations:
Note that , where Ci is at jth place and is at place. After multiplying by , we get a matrix whose all columns are linear combinations of columns and .
Note that , where is at place and is at place. After multiplying by , we get a matrix whose all columns are linear combinations of columns Ci and Cj.
Note that , where is at place and is at place. After multiplying by , we get a matrix whose all columns are linear combinations of columns and .
Suppose one can construct a matrix B from columns obtained above such that , where D is diagonal, then we can see that for some which is a contradiction as . Thus, it is not possible to construct a matrix B such that , 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 , 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; similar construction works for other cases as well. Computing gives the following equations:
, where is at jth place and is at place. This gives us a linear combination of the columns Gi and .
, where Gi is at place and Gj is at place. This will give us a linear combination of the columns Gi and Gj.
, where is at jth place and is at ith place. This will give us a linear combination of the columns and .
We construct a matrix N as follows: For each , compute whose each column is a linear combination of and . Choose one of its column say for each . Similarly compute and choose for each . Further, we compute to get and to get . We set . Now it is easy to note that , where , , and P are permutation matrix corresponding to the permutation of indexing set
Thus we get , 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 where and . Then the attack goes on smoothly as we saw earlier. However, when we look at generators of the form , where and , 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 and for . 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 (, 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 as 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 for some . We have loaded matrices in the memory in such a way that this formula takes as input t and put it in the (1, 2) position of the matrix and 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, for 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 , 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 .
5.1 Symplectic group Sp (2l, p)
Let p be an odd prime. It is known  that the group Sp(2l,p) is generated by two elements:
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 , where and .
Now and , so length of this SLP is . Hence we get all for . Number of SLP is l. Next observe the following:
So we generate all for and for . Now for and for , then we get and . Total number of SLPs is . 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 be a prime. It is known  that the group O+(2l,p) is generated by two elements:
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 , where and .
Now and , so length of this SLP is . Hence we get all for . The number of SLPs is l. Next observe the following:
So we generate all for . Now , and we get and the total number of SLPs is . It is shown by Ree  that elementary matrices generate , the commutator subgroup of O(2l, p). Hence we generate , using only two elements x and w. Since we generate and as a product of and , so we are able to generate . Here for and . Now we know , so we generate . Hence by induction, we generate for . Here , for . Hence we generate all the elementary matrices (Table A1) using only two generators x and w. So we generate a new subgroup of O(2l,p), which is a normal subgroup of O(2l, p). Our algorithm output matrix is . If , say , then , since . Then
Hence we generate using only two generators x and w.
5.3 Orthogonal group O(2l+1, p)
Let be a prime. It is known  that the group O(2l+1, p) is generated by these elements:
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, which is of length for . Now
and for , and length of this SLP is . So we get and for . Again we have and length of this SLP is . In what follows, we denote the length of SLPs by , where and .
As , so the length of this SLP is . Hence we generate all for and the number of SLPs is . Next observe the following:
So we generate all for . Now , and we have . The total number of SLPs is . It is shown in Ree  that elementary matrices generate , the commutator subgroup of Owhich is of index 4. So we generate , using only two generators x and w. Now we know , so we generate . Hence inductively we can generate for . Here for and for . 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 of the orthogonal group O, containing , which is indeed a normal subgroup of O. In our algorithm the output matrix is . If , say , here , since . Then
Hence we generate using and .
Remark 5.1Let, whereis non-square in. The groupis the orthogonal group.
5.4 Twisted orthogonal group O
We use the following generators which we refer as Steinberg generators.
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 , , , 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 . First, we compute which is of length for . Now we compute using the relation for , where and length of this SLP is . Thus, we get and , for . Similarly we compute and using the relations and for , and length of this SLP are and , respectively. Next, we compute using the commutator formula , and length of this SLP is . In what follows, we denote the length of SLPs by , where and .
As , so length of this SLP is . Hence, we get all for and the number of SLPs is . Next, we compute the remaining elementary matrices using the commutator formula and are listed in the table; let .
Thus, we have generated all for . Now, using the formula , we get and the total number of SLPs required is . Now we know , so we generate . Hence by induction we can generate , for . Here , for , and , for . Hence we generate all the elementary matrices defined in Table A7 using generators , , , , and and an extra element . In our algorithm the output matrix is . If , say , here , since .
Remark 5.2Let, whereis non-square in. Then as a consequence of our Gaussian elimination algorithm in Appendix A, we can see that,,,,andalong withgenerate the twisted orthogonal group.
This section is similar to (, 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 be a set of generators for the orthogonal or symplectic group as described before. As is the custom with a MOR cryptosystem, the automorphisms and are presented as action on generators, i.e., we have and as matrices for .
To encrypt a message in this MOR cryptosystem, we compute . 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 for . First thing that we do is write the matrix of as a word in generators. So essentially the map becomes a map where is a word in generators of some fixed length. Then multiplication becomes essentially a replacement, replace all instances of by . 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:
This can be implemented in parallel easily.
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 .
For parameters and complexity analysis of this cryptosystem, we refer to (, 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 . Now if we take , then the security is better than . Our key-size is about 8000 bits. Comparing with Monico (, 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.
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 and get to the identity matrix, thus writing g as a product of elementary matrices (, 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 . 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 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 O, O, and Oseparately.
A.1 Groups in which Gaussian elimination works
Symplectic groups: Since all non-degenerate skew-symmetric bilinear forms are equivalent (, Corollary 2.12), we have a Gaussian elimination algorithm for all symplectic groups over an arbitrary field.
Since non-degenerate symmetric bilinear forms over a finite field of odd characteristics are classified (, 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 (, p. 10) according to quadratic forms Q(x) defined in (, 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 Oand symplectic group
Recall that the bilinear forms are the following:
For symplectic group, Sp, , and .
For orthogonal group, O, , and .
Note that any isometry g satisfies . The main reason our algorithm works is the following: Recall that a matrix , where A, B, C, and D are matrices of size l, is orthogonal or symplectic if for the respective β. After some usual calculations, for orthogonal group it becomes
The above equation implies among other things, . 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 Oof even size
|Row operations||Column operations|
|wi||Interchange ith and row||Interchange ith and column|
Let us note the effect of multiplying g by elementary matrices. We write as , where , and are matrices.
A.2.2 Elementary matrices (Chevalley generators) for symplectic group
For , the elementary matrices are defined as follows (Table A3):
Let us note the effect of multiplying g by elementary matrices. We write as , where A, B, C, and D are matrices (Table A4).
|Row operations||Column operations|
|wi||Interchange ith and (−i)th rows||Interchange ith and (−i)th columns|
|with a sign change in the ith row||with a sign change in the ith column|
A.2.3 Gaussian elimination for and
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.
Step 2: There are two possibilities. One, the diagonal matrix A is of full rank, and two, the diagonal matrix A is of rank less than l. This is clearly identifiable by looking for zeros in the diagonal of A.
Step 3: Make rows of C, corresponding to the non-zero entries in the diagonal of A zero by using ER3. If , we have C as zero matrix. If not let us assume that ith row is zero in A. Then we interchange the row with the row 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 . 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 , where using ER1 (, Proposition 6.2). Once A is diagonal and C a zero matrix, the equation makes D a diagonal matrix of full rank.
Step 4: Use ER2 to make B a zero matrix. The matrix g becomes a diagonal matrix of the form
, where .
Step 5: (Only for symplectic groups) Reduce the to using Lemma A.1.
Lemma A.1For, the elementis a product of elementary matrices.
Proof. Observe that and denote it by , and then the diagonal element is .
Remark A.1As we saw in the above algorithm, we will have to interchangeandrows for. This can be done by pre-multiplying with a suitable matrix.
Let I be the identity matrix over k. To swap ith and −ith row in O, 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 Oand is of determinant −1. Pre-multiplying with wi does the row interchange we are looking for.
In the case of symplectic group Sp, 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 Oand Sp, respectively.
However there is one difference between orthogonal and symplectic groups. In symplectic group, wi can be generated by elementary matrices because . 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.
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 O. This group will be referred to as the odd-orthogonal group.
A.3.1 Elementary matrices (Chevalley generators) for
Following the theory of Lie algebra, we index rows by . These elementary matrices are listed in Table A5.
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 row as follows:
Otherwise, we can construct wi, which interchanges the ith row with row with a sign change in row in odd-orthogonal group as follows:
The Gaussian elimination algorithm for Ofollows 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 as , where , and are matrices, and are matrices, and are matrices, and . Then from the condition , we get the following relations:
Let us note the effect of multiplying g by elementary matrices (Table A6).
|Row operations||Column operations|
|Interchange and rows||Interchange and column|
|(odd)||with a sign change in rows||(odd)||with a sign change in columns|
|(even)||Interchange and row||(even)||Interchange and column|
A.3.2 Gaussian elimination for
Step 1: Use ER1 and EC1 to make A into a diagonal matrix, but in the process, it changes other matrices , and Y. For the sake of notational convenience, we keep calling these changed matrices as , and Y as well.
Step 2: Now there will be two cases depending on the rank of 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 rows of C zero.
If then C becomes zero matrix.
If then interchange all zero rows of A with corresponding rows of C using wi so that the new C becomes a zero matrix.
Once C becomes zero, note that Relation A.2 if char(k) is odd or Relation if 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 , where .
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.
Step 4: Use ER2 to make B a zero matrix. For char(k) even the relation guarantees 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 , where .
Remark A.4Let k be a perfect filed of characteristics 2. Note that we can write the diagonal matrixas a product of elementary matrices as follows:
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 from Section 3.
A.4.1 Elementary matrices (Chevalley generators) for twisted orthogonal groups O
In this section, we describe row-column operations for twisted Chevalley groups. These groups are also known as the Steinberg groups. An element is denoted as , where , and are matrices, and are matrices, and are matrices, and is a matrix. In the Gaussian elimination algorithm that we discuss, we reduce 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 block (also called A0) which will satisfy , where for odd characteristics and is a non-square. Then A0 is a orthogonal matrix given by the bilinear form . Now if we write , then we get the following equations:
Considering the fact that det, one more equation and this leads to two cases either and or and . Recall that, since is not a square, . Then if , then there are four choices for and these are .
To summarize, the output of the algorithm will have one of the following forms
and , , 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
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 in the list of generators with the condition that the determinant is 1.
The elementary matrices for Odepend on the characteristics of . We describe them separately in the following table. Let be an Arf-invariant, and and .
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.
|ER1 (both)||row and row|
|ER2 (both)||row and row|
|ER3 (both)||row and row|
|ER4 (odd)||row and row|
|ER5 (odd)||row and row|
|ER6 (odd)||row and row|
|ER7 (odd)||row and row|
|ER8 (even)||row and row|
|ER9 (even)||row and row|
|wi (both)||Interchange and row|
|EC1(both)||column and column|
|EC2 (both)||column and column|
|EC3 (both)||column and column|
|EC4 (odd)||column and column|
|EC5 (odd)||column and column|
|EC6 (odd)||column and column|
|EC7 (odd)||column and column|
|EC8 (even)||column and column|
|EC9 (even)||column and column|
|wi (both)||Interchange ith and (−i)th column|
Note that any isometry g satisfies . The main reason the following algorithm works is the closed condition which gives the following relations:
A.4.2 The Gaussian elimination algorithm for O
Step 1: Use ER1 and EC1 to make A into a diagonal matrix, but in the process, it changes other matrices , , and . For the sake of notational convenience, we keep calling these changed matrices as , , and as well.
Step 2: Now there will be two cases depending on the rank of the matrix . The rank of can be easily determined by the number of non-zero diagonal entries.
Step 3: Use ER3 and non-zero diagonal entries of to make corresponding rows of zero.
If then becomes zero matrix.
If then interchange all zero rows of with corresponding rows of using , so that the new becomes a zero matrix.
Once becomes zero one, can note that the relation if charis odd or the relation and the fact that is irreducible when charis even guarantees that becomes zero. Then the relation guarantees that has full rank which also makes a diagonal with full rank, and the relation shows that is zero. Now we diagonalize again to the form , where as in Step 1.
Step 4: Use EC4 and EC6 when charis odd or use EC8 and EC9 when charis even to make zero. Note that the relation shows that is invertible. Thus the relation guarantees that becomes zero.
Step 5: Use ER2 to make a zero matrix. Thus the matrix reduces to . Now if charis odd, then go to Step 6; otherwise go to Step 7.
Step 6: Using the relation , it is easy to check that has the form or . If the determinant of is , multiply by to get new of the above form such that has determinant 1. Now using the elementary matrix , we can reduce to .
Step 7: Using elementary matrix , we can reduce to .
Lemma A.2Let k be a field of characteristics 2 and let, where, be an element of Othen.
Proof. Let be the standard basis of the vector space . Recall that for a column vector , the action of the quadratic form is given by , where is irreducible over . By definition, for any , we have for all . Let be a matrix. Computing for all , we can see that . If then we can see that . Suppose for some , then we rewrite the equation by dividing it by as , which is a contradiction to the fact that is irreducible over . Thus, for all and hence . •
A.5 Time complexity of the above algorithms
We establish that the worst-case time complexity of the above algorithm is . We mostly count the number of field multiplications.
Step 1: We make a diagonal matrix by row-column operations that has complexity .
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 times and done many times. So the complexity is .
Step 3: In odd-orthogonal group and twisted orthogonal group, we clear , this clearly has complexity .
Step 4: This step has only a few operations that is independent of l.
Then clearly, the time complexity of our algorithm is .