Research On The Signature Scheme And Minimal Logarithmic Signatures Of MST Cryptosystems

The development of quantum algorithms breaks some typical crypto-graphic assumptions based on commutative algebraic structures. With the pur-pose to resist known quantum algorithmic attacks, non-commutative algebraic structures come on the stage of modern cryptography. With the rapid devel-opment of non-commutative cryptography, MST cryptosystems based on the hardness of group factorization problem(GFP) have gradually become the typ-ical representative of this field and made great progress in the recent thirty years. But until now, there are no plenty schemes based on MST cryptosys-tems, most schemes pay more attention on design of encryption scheme rather than on other cryptographic primitives such as signature, signcryption, key ex-change, etc. In this sense, it’s meaningful to devise new schemes based on new cryptographic primitives. Meanwhile, as a special type of factorization of finite groups, logarithmic signature (LS) is used as the main component of cryptographic keys that operate in MST cryptosystems. An LS with the short-est length is called a minimal logarithmic signature (MLS) that constitutes of the smallest sized blocks and offers the lowest complexity, and is therefore de-sirable for cryptographic constructions. However, the existence of MLSs for finite simple groups should be firstly taken into an account. The MLS conjec-ture states that every finite simple group has an MLS. If it holds, then by the consequence of Jordan - Holder Theorem, every finite group would have an MLS. In fact, many cryptographers and mathematicians are keen for solving this problem. Some effective work has already been done in search of MLSs for finite groups. But until now, it’s still an open problem. So in this sense, it’s challenging work to prove the conjecture.In this thesis, we mainly discuss two key problems in MST cryptosystems which is the typical representative in non-commutative cryptography and yield some positive results:(1) We devise a new encryption scheme based on MST cryptosystems, the hardness hypothesis of our scheme is based on Group Factorization Prob-lem(GFP). Compared with the original scheme, our scheme is more ef-ficient. Then,we make further efforts to design the first digital signature scheme based on MST cryptosystems. Our scheme has very strong secu-rity and high efficiency.(2) According to the classification of finite simple groups, we employ many mathematical methods such as finite group theory, algebraic group theory and projective geometry to provide MLSs for the remaining simple group-s. Consequently, we have contributed to prove MLS conjecture complete-ly. Our results are as follows:(a) We use the relationship between stabilizers of one-dimensional isotropic subspace of the orthogonal group On(q) (the special orthog-onal group SOn(q)) and its parabolic subgroups and combine the ba-sic theory of spread to give the construction of MLSs for projective commutator subgroup PΩn(q).(b) We take advantage of the relationship between stabilizers of one-dimensional isotropic subspace of the unitary group Un(q) (the spe-cial unitary group SUn(q)) and its parabolic subgroups and com-bine the basic theory of spread to present the construction of MLSs for projective unitary group PUn(q) (projective special unitary group PSUn(q))-(c) We employ stabilizers of isotopic 1-subspaces and linear transforma-tions in corresponding algebraic systems(Octonion algebras, Albert algebras, Lie algebras) to construct MLSs for all ten families of ex-ceptional groups of Lie types.(d) We utilize Sylow Theorem and stabilizers of the corresponding spo-radic groups to construct MLSs for thirteen types of sporadic groups.