Design And Application Of Some Cryptographic Mechanisms Using Non-commutative Structures

Shor proposed a famous quantum algorithm for factorization large numbers using quantum entanglement and superposition——hor algorithm in1994. Large numbers decomposition problem and some discrete logarithm problems on finite abelian groups (such as the multiplicative group of a finite field, elliptic curve over point group) can be done in polynomial time using the algorithm with the aid of a quantum computer, so potential threats and challenges are posed to the existing public key cryptosystems (such as RSA, DH, ElGamal, ECC).In order to resist the attack of the known quantum algorithms, two major aspects of progress have been achieved:one is non-commutative structure cryptography, the most representative is braid group; the other is post quantum cryptography whose scope is much broader since21st Century(Code-based cryptography, one kind of the post quantum cryptography, also belongs to the category of non-commutative structure cryptography). It is a significant practice in cryptography to seek new and alternative realizations of primitives in cryptography.Related research works are as follows:(1) Comprehend the conjugacy search problem and root extraction problem on braid group into a compound problem, whose difficulty is harder than the single conjugacy search problem and the root extraction problem.Proposed a new two side key agreement protocol of Diffie-Hellman type, one-way function, public-key encryption, authentication scheme, most of all are the designing of1-out-of-2oblivious transfer protocol and1-out-of-N oblivious transfer protocol; the advantages and disadvantages of various oblivious transfer protocols based on the assumptions of different hard problems are compared; in this thesis, expounded the fundamental difference of cryptography based on the difficult computational problems assumption of the abelian group and non-abelian group in the face of the attack of the known quantum algorithms.(2) As a promising candidate who are against attackers equipped with a quantum computational power, code-based cryptography has attracted an increasing attention in recent years. Demonstrated the reasons and significance of the code-based cryptography is still secure in the face of quantum adversaries. Reviewed oblivious transfer protocols based on McEliece assumptions; M-out-of-N string oblivious transfer protocol based on McEliece assumptions is proposed for the first time, meanwhile its communication complexity is lower, and achieves unconditional security for the sender, computational secure for receiver, points out that not only the public key cryptosystems with homomorphic properties can be used toconstructed1-out-of-N or M-out-of-N oblivious transfer protocol directly; comparing with the informed scheme, our1-out-of-N string oblivious transfer protocol has a better security; we adopts a variant of McEliece--Wild McEliece, and makes the public key’s size much smaller under the same security level.(3) Resolved the question of not satisfy verified and receipt-free simultaneously in electronic voting scheme by using1-out-of-2OT thought skillfully, further broadened the application of oblivious transfer, and this idea can also be used to solve other cases need to be satisfy verified and receipt-free at the same time; the electronic voting scheme will has better fairness by controlling polling center structure with secret sharing scheme, and significantly reduce the calculate amount of election management centre in the stage of distributing votes, meanwhile it meets the basic features of secure electronic voting, and more efficient for large scale elections; finally, the comparison of performance between our sheme with typical electronic voting schemes is given in detail.