In this paper, we examine the basic properties of n-th order linear feedback shift registers and show that n-th order shift registers based discrete logarithm problem is equivalent to discrete logarithm problem. This shows that the algebraic structure of n-th order linear feedback shift registers is useful in constructing cryptographic primitives.

In this paper, we examine the computational Diffie-Hellman problem and decisional Diffie-Hellman problem in 3-rd order linear feedback shift register and show that the shift register based Diffie-Hellman problems are equivalent to the Diffie-Hellman problems over prime subgroup of GF(p3e) respectively. This result will be useful in constructing new cryptographic primitives based on the hardness of the shift register based Diffie-Hellman problems.

In this paper, we propose a new digital signature scheme based on a third order linear feedback shift register for signing documents. This signature scheme is different from most of the signature schemes that are based on discrete logarithm problem, elliptic curves discrete logarithm problem, RSA or quadratic residues. An efficient algorithm for computing kth term of a sequence is also presented. The advantage of this scheme is that the computation is efficient than Schnorr scheme. We also show that the security of the proposed signature scheme is equivalent to that of Schnorr signature scheme.

In this paper, we construct a new signature scheme which is provably secure against adaptive chosen message attack in the standard model under the strong RSA assumption. The proposed scheme is different from Cramer-Shoup scheme and Camenisch-Lysyanskaya scheme and is more efficient than them. The tradeoff of the proposed scheme is a slight increase of the secret key.