Public Key Cryptosystem based on Number Theoretic Transforms

Authors: C. Porkodi, R. Arumuganathan

Abstract:

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.

Keywords: Cryptography, decryption, discrete logarithm problem encryption, Integer Factorization problem, Key agreement, Number Theoretic Transform.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084794

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.