oa Public-Key Cryptosystem Based on Invariants of Groups

The presented work falls within one of Qatar's Research Grand Challenges, namely the area of Cyber Security. We have designed a new public-key cryptosystem that can improve the security of communication networks. This new cryptosystem combines two important ideas. The first idea is the difficulty of finding an invariant of infinite diagonalizable group. More specifically, for the coding purposes, we build an infinite diagonalizable group that has a given polynomial invariant of high degree. One possible attack on this cryptosystem is to find an invariant of this group. However, during the design of the system we guarantee that the minimal degree of invariants of this group is very high which makes the direct attempt to find any invariant using linear algebra techniques computationally expensive. The second idea is based on our discovery that when working over the ring Z of integers, another attack to break the cryptosystem is possible. This attack is based on replacing the prime factorization of integers by finding a factorization of “atoms” and can be implemented using the Euclidean algorithm. Similar algorithm works for rings that are unique factorization domains. To prevent this type of attack, we work over number fields that are not unique factorization domains (there are many such suitable number fields of small degrees). By doing so we invoke the well-known problem of prime factorization (used in commercial cryptosystems like RSA) which becomes principally more complicated over number fields that are not unique factorization domains. We have also showed that similar system based on finite diagonalizable groups are not secure against attack because such a system can be broken in polynomial time using an algorithm that finds a root of every polynomial p(x) with complex coefficients such that all of its roots are roots of unity. All invariants considered for diagonalizable groups are linear combinations of monomial invariants. The situation is more complicated for diagonalizable supergroups. Since it could improve the safety of the cryptosystem, we also investigated the case of supergroups and derived theoretical results about the minimal degrees of invariants. Since the diagonalizable supergroups enjoy more complicated structural properties, a cryptosystem based on them would be even more secured. In order to move to the supergroups, a better understanding of general linear supergroups was desired. We have established theoretical results describing and proving the linkage principle for these supergroups and we gained an understanding how are the composition factors of highest weight modules related. For the future work, we plan to implement the algorithm for the public-key cryptosystem that we have designed and test the speed of coding and test the security of the system by determining the time and space complexities of known attacks of the system.