Cryptographic Applications Of Semigroup Action Problem

All kinds of semigroup action problems such as discrete logarithm problem and conjugacy problem play very significant role in modern cryptography. The decisional Diffie-Hellman assumption from discrete logarithm is the base of security of many modern cryptosystems. Recently, many scholars have designed some simple cryptosystems based on conjugacy problem on several non-abelian groups. However, DDH assumption does not hold in bilinear groups and most cryptosystems based on conjuacy problem are not secure. So it is a very important research direction to find other appropriate semigroup action problem. This paper dissertation investigates the several semigroup action problems exploringly and analyzes logarithm problem, matrix semigroup action problem, multiple conjugacy search problem on Clifford semigroup and their related problems. The main results are as follows:(1) The algebraic theory of semigroup action is discussed. Split integral Dubreil-Jacotin semigroup is defined and studied and the structure of a class of split Dubreil-Jacotin semigroup is described by some ordered group action on ordered monoid.(2) An extended computational Diffie-Hellman problem and an extended decisional Diffie-Hellman problem based on a class of vector space of finite field with respect to matrix semigroup action are proposed. The relationship of n -ECDH assumption, n -EDDH assumption, DL assumption, CDH assumption and DDH assumption is analyzed. It is proved that the n -EDDH problem satisfies the random self-reducibility property and 2-EDDH assumption is weaker than the classic DDH assumption in the generic bilinear groups in the generic group model.(3) A new extended ElGamal public key encryption scheme is proposed. The new encryption scheme is one-way if and only if ECDH assumption holds and it is semantically secure in the standard model if and only if the EDDH assumption holds.(4) Several new extended Cramer-Shoup public key encryption schemes is proposed and analyzed. These schemes are proved secure against adaptive chosen ciphertext attack under EDDH assumption.(5) Two new constructions of pseudo-random functions are presented. The proof of security on them is proposed under the EDDH assumption and GECDH assumption.(6) Two algebraic key establishment protocol models are presented. The new key establishment protocol models are based on the multiple conjugacy (idempotent) search problem on Clifford semigroup. Some finite presented Clifford semigroup maybe implement these protocol models and resist the length attack.(7) Two amended multiplicative noisy polynomial interpolation algorithms presented by von zur Gathen and Shparlinski are proposed and analyzed. The amended algorithms reduce respectively the lower bound of the order of finite field and the initial query value inputted to multiplicatively approximate multiplicative black box.