Public Key Cryptosystem based on Number Theoretic Transforms

In this paper a Public Key Cryptosystem is proposed using the number theoretic transforms (NTT) over a ring of integer modulo a composite number. The key agreement is similar to ElGamal public key algorithm. The security of the system is based on solution of multivariate linear congruence equations and discrete logarithm problem. In the proposed cryptosystem only fixed numbers of multiplications are carried out (constant complexity) and hence the encryption and decryption can be done easily. At the same time, it is very difficult to attack the cryptosystem, since the cipher text is a sequence of integers which are interrelated. The system provides authentication also. Using Mathematica version 5.0 the proposed algorithm is justified with a numerical example.

Authors:

• C. Porkodi
• R. Arumuganathan

Keywords:

• Cryptography
• decryption
• discrete logarithm problem encryption
• Integer Factorization problem
• Key agreement
• Number Theoretic Transform.

References:

[1] Alfred Menezes J, Paul Van Oorchot C, Scott A Vanstone, "Hand book
of Applied Cryptography", CRC Press, 1997.
[2] S. Cabay and T.P.L. Lam, "Congruence Techniques for the Exact
Solution of Integer Systems of Linear Equations, ACM Transactions on
Mathematical Software,Vol.3,No.4, pp386-397, December 1977.
[3] W. Diffie and M. Hellman,"New Directions in Cryptography", IEEE
Transactions on Information Theory,vol.IT-22,pp472-492,1976.
[4] Elsayed Mohammed, .E. Emarah and KH. El-Shennawy, "A Blind
Signature Scheme based on Elgamal Signature", Seventeenth National
Radio Science Conference Feb.22-24, 2000, Minufiya University, Egypt.
[5] Jacques Patarin, "Hidden Field Equations (HFE) and Isomorphism of
Polynomials (IP): two new families of Asymmetric Algorithms",
Eurocrypt-96, Springer Verlag, pp.33-48.
[6] Mukesh Kumar Singh, "Public Key Cryptography with Matrices",
Proceedings of the IEEE Workshop on Information Assurance, United
States Military Academy pp146-152, June 2004.
[7] H.J. Nussbaumer, "Fast Fourier Transform and Convolution
Algorithms", second edition, Springer-Verlag Berlin Heidelberg, New
York.
[8] Ramesh C. Agarwal and C. Sidney Burrus, "Number Theoretic
Transforms to Implement Fast Digital Convolution", Proceedings
of the IEEE, vol.63, No.4, April 1975.
[9] Ronald L. Rivest, Adi Shamir and Leonard M. Adleman, "A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems",
Communications of the ACM, vol21, no2, pp.120-126, Feb 1978.
[10] Tom M. Apostol, "Introduction to Analytic Number Theory", Springer-
Verlag 1976.
[11] Taher Elgamal,"A public Key Cryptosystem and a Signature Scheme
Based on Discrete Logarithms", IEEE Transactions on Information
Theory, vol.IT31, No4, July 1985.
[12] Vassil S. Dimitrov, Todor V. Cooklev and Borislav Donevsky," Number
Theoretic Transforms Over the Golden Section Quadratic Field", IEEE
Transactions on signal Processing, vol.43, No.8, August 1995.