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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:64307", author = "C. Porkodi and R. Arumuganathan", title = "Public Key Cryptosystem based on Number Theoretic Transforms", 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.", volume = "2", number = "7", pages = "509-5", }