Research On Public Key Cryptosystems Based On Typical Non-Commutative Algebric Structures

Since the inception of public key cryptography, many excellent publickey cryptosystems (PKCs) have been proposed and improved. At present, most of unbroken PKCs are based on difficult problems from commutative algebraic structures, such as integer factoring problem, discrete logarithm problem, etc. However, since recent development of quantum computation, many intractability assumptions based on commutative algebraic structures are no longer difficult. Therefore, in order to resist currently known quantum algorithm attacks, reseachers pay attention to new difficult problems from non-commutative algebraic structures and building secure PKCs based thereon.Up to date, many PKCs based on non-commutative algebraic structures have been proposed. In particular, cryptosystems based on braid groups attracted a great deal of research. Unfortunately, almost all published braid-based cryptographic schemes have been shown to be insecure. Thus, people have made lots of effort on developing PKCs based on other non-commutative algebraic structures. Moreover, it is a challenge to find suitable non-commutative algebraic structures and relevant cryptographic assumptions, and then to construct non-commutative variants of mature PKCs based on commutative algebraic structures. Under this background, this dissertation focus on studying PKCs based on several kinds of typical non-commutative algebraic structures.The main originalities and results of this dissertation are summarized as follows:1. Propose two new conjugation-related cryptography assumptions, CSP-based hash Diffie-Hellman problem (CSP-HDH) and CSP-based oracle Diffie-Hellman problem (CSP-ODH), based on a special monoid of matrices of truncated multi-variable polynomials over the ring Z12, where the conjugacy search problem is assumed to be intractable. Moreover, based onthe above assumptions, a new public-key cryptosystem, CSP-based Diffie-Hellman integrated encryption scheme (CSP-DHIES), is proposed. The construction can be viewed as the first non-communicativevariant of the well-known DHIES cryptosystem. Under the intractability assumptions of CSP-HDH and CSP-ODH, the scheme is both indistinguishable against chosen-plaintext attacks and self-adaptively chosen-ciphertext attacks in the standard model, respectively.2. Propose a family of chameleon hash functions and strongly unforgeable one-time signature schemes based on the intractability assumption of the discrete logarithm problem over inner automorphism groups. Since the sizes of the working parameters used in the constructions can be shorter significantly, this leads to remarkable gains for both in running time and in storage space. As far as we know, this is the first time to build a family of chameleon hash functions and one-time signature schemes based on non-commutative groups.3. Propose three signature schemes based on the intractability assumption of the discrete logarithm problem over inner automorphism groups. These schemes can be viewed as non-communicative variants of Schnorr signature scheme, DSA signature scheme and mNyberg-Rueppel signature scheme.4. Propose three blind signature schemes based on the intractability assumption of the discrete logarithm problem over inner automorphism groups. The proposed schemes are proved to be blind and one-more unforgery against adaptively chosen-message attacks. These schemes can be seen as non-communicative variants of Schnorr blind signature scheme, DSA blind signature scheme and mNyberg-Rueppel blind signature scheme, respectively.5. Propose a non-interactive verifiable secret sharing scheme based on the intractability assumption of the discrete logarithm problem over inner automorphism groups. The secret sharing scheme protects the privacy of the secret unconditionally, but the correctness of the shares depends on DLP-IAG assumption. As far as we know, this is the first time to build a non-interactive verifiable secret sharing scheme based on non-commutative groups.