Using Extended ChebyshevPolynomials to Construct aTrap-door One-way Function
Wang Dahu，Wei Xueye
1.School of Electronic and Information Engineering
BeijingJiaotongUniversity
Beijing，100044, China
2.State Key Laboratory of Information Security
Institute of Software of ChineseAcademy of Sciences
Beijing，100044, China
Abstract:-We extend Chebyshev polynomials from real field to finite field, and suggest a trap-door one-way function. According to the proposed function, a secure and practical encryption scheme is given.And an entity authentication scheme is presented.
Key-words:-Extended Chebyshev polynomials, Trap-door one-way function, Encryption algorithm, Entity authentication, Security
1. Introduction
It is obvious that the development of a practical public-key scheme depends on discovery of a suitable trap-door one-way function[1-5].The definition of a trap-door one-way function is easy to calculate in one direction and infeasible to calculate in the other direction unless certain additional information is known. We can summarize as following[15]: A trap-door one-way function is a family of invertible function, such that
Y= easy, if k and x are known
X= easy, if k and Y are known
X= infeasible, if Y is known but k is not known
The function is difficult to find, as evidenced by the fact that only several such schemes have received widespread acceptance in the several decades since the concept of public-key cryptography was proposed.
In this paper, we propose one trap-door one-way function based on extended Chebyshev polynomials and theirs performances are analyzed. Theirs application in encryption are given in the end. Section 2 shows the basic properties of the extended Chebyshev polynomials over finite fields, which can be used as a trap-door one-way function. In section 3, we give an encryption scheme based on Section 2. Section 4 provides a entity authentication scheme based on the function in Section2. In the end, we close the paper with conclusion.
2.A trap-door one-way function based on extended Chebyshev map over finite fields
2.1 Extended Chebyshev map over finite fields
Since Chebyshev polynomials have semi-group property[6] [7] [8] on real field R, they also have semi-group property over integer Z. Then we can further extend the definition field and value field of Chebyshev polynomials to finite fieldsZP, where P is a prime number. Over finite field ZP we can definite the Chebyshev polynomials as the following.
Definition 2.1.1[14]：Let n∈Z and variable . The polynomial is recursively defined as
(1)
where and .
Thus, we can get Chebyshev polynomials on finite field ZP as the following:
… (2)
is algebraic polynomial, so we have the following equation:
(3)
According to[7]， the semi-group property of extended Chebyshev polynomials over finite fields is that:
(4)
2.2 A new trap-door one-way function based on extended Chebyshev polynomials over finitefields
We know any Chebyshev polynomial can be written as that:
（5）
In equation （5）, gaining given n and x is very easy, but gaining n given and x is very difficult, and almost unfeasible in computation. The difficulty can be compared with the intractability of discrete logarithm problem. When the value of n in equation（5） is equal to the value of discrete logarithm, solving the n of equation （5） is more difficult and complex than solving discrete logarithm for the existence of other low power elements in equation （5）, such as xn-1, xn-2, and so on. So equation （5） has a good one-way property in computation. Equally, Chebyshev polynomials on finite fields have good one-way property.
In equation （5）, n is equal to a trapdoor. If we know n and x, it is easy and fast to compute by using following fast algorithm. According to the semi-group property of equation (4), and, can be computed by that:
.
The number of iteration is k+k+…+k.
If n isn’t known, the only possible way is to compute for all k=2,…,n, and find whether = one by one. However, if n is a large enough number, it is impossible to do so.
Due to the one-way trapdoor property of Chebyshev polynomials over finite fields, they can be used to construct key public key encryption algorithm and entity authentication scheme. Because we extend the Chebyshev polynomials from x∈[-1, 1] to , the attack by the way of [7] is invalid to our cryptosystem. Moreover, it is clear that our cryptosystem is more secure than RSA and ElGamal system. Here we assume that ZP is a finite field and Zn is an integer ring. All computation of the following is over ZP and Zn.
3. Public key encryption algorithm based on the new trap-door one-way function
For the one-way trapdoor and semi-group properties of Chebyshev polynomials on finite fields, we can use it to construct public key encryption algorithm, which includes three processes: key generation, encryption and decryption.
.
From the equation (4), we know that:
So the message M can be decrypted correctly.
4Entity authentication scheme based on the new trap-door one-door function
Entity authentication is defined as follows:
Definition 4.1.1[14]: Entity authentication is the process whereby one party is assured (through acquisition of corroborative evidence) of the identity of a second party involved in a protocol, and that the second has actually participated (i. e., is active at, or immediately prior to, the time evidence is acquired).
We propose a scheme based on extended Chebyshev polynomials, by means of which a user can efficiently authenticate himself to a server in order to log in. Apart minor implementation details, the scheme works as follows:
Within,let m, and denote by (mod p) the map (mod p) iterated i times, i.e.,
.
It is easy to see that, due to the same theory background, the performances of the scheme are similar to that of encryption scheme above.
5 Conclusion
In conclusion, in this letter we have proposed a trap-door one-way function based on extended Chebyshev polynomials. And we have firstly given encryption scheme and entity authentication algorithm based on extended Chebyshev polynomials over finite fields, which is secure and practical.
From the analyses of this paper, we can conclude that (i) any algebraic polynomials, which have semi-group property of equation (2) and recursion property like equation (1) over real field, can be used to construct a trap-door one-way function. (ii) the proposed function can be used to construct public key encryption algorithm , entity authentication, key agreement algorithm and digital signature algorithm. The detailed study of the proposed function as well as the further application in cryptographyis topics of our future research.
Acknowledgements
The authors gratefully acknowledge the assistance and support of Dr. Ning Hongzhou and State Key Laboratory of Information Security.
References：
[1] Diffie W., HellmanM.E., New directions in cryptography, Information Theory, IEEE, 1976, 22(6): 644-654.
[2] Rivest R.L., Shamir A., Adleman L., Method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 1978, 21(2): 120-126.
[3] Rivest R.L., Shamir A., Adleman L., On digital signatures and public key cryptosystems, MIT Laboratory for Computer Science, Technical Report, 1979.
[4] Elgamal T., A public key cryptosystem and a signature scheme based on discrete logarithms, Information Theory, IEEE, 1985, 31(4): 469-472.
[5] Elgamal T., A public key cryptosystem and a signature scheme based on discrete logarithms, CRYPTO 84 on Advances in Cryptology Proceedings, 1984, 10-18.
[6] Kocarev L., Tasev Z., Public-key encryption based on Chebyshev maps, The 2003 IEEE International Symposium on Circuits and Systems Proceedings, 2003. 28-31.
[7] Pina Bergamo, Paolo D'Arco, Alfredo De Santis, et al., Security of public key cryptosystems based on Chebyshev polynomials, 2004.
[8] DXiao, XLiao, GTang, ChuandongLi.Using Chebyshev chaotic map to construct infinite length hash chains, Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium,25-28 May 2004, Volume: 1 ,Pages:11-12.
[9]Xiao Di，Liao Xiaofeng，Wong K.W. An efficient entire chaos-based scheme for deniable authentication. Chaos, Solitons and Fractals , Issue: 4, February, 2005, Volume: 23, pp. 1327-1331
[10]Kocarev L.Chaos-based cryptography: a brief overview.Circuits and Systems Magazine, IEEE ,Issue: 3 ,2001 Volume: 1 ,Pages:6 – 21
[11]Kocarev L，Sterjev M，AmatoP.RSA encryption algorithm based on torus automorphisms.Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium on ,23-26 May 2004 Volume: 4 ,Pages:IV - 577-80 Vol.4
[12]Kohda Tohru，Fujisaki Hirohi. Jacobian elliptic Chebyshev rational maps.Physica D Issue: 3-4, January 15, 2001, Volume: 148,pp. 242-254
[13] William Stallings. Cryptography and Network Security Principles and Practices .Third Edition.Prentice Hall.2003
[14] A.Menezes, P. van Oorschot, S.Vanstone, Handbook of Applied Cryptography, CRC Press, 1997.
[15]Douglas R. Stinson. Cryptography Theory and Practice, second edition, CRC Press, 2002.
Biography
Wang Dahu was born in Jiangsu, China in 1969. He received his B.S. degree in electronics engineering from TongjiUniversity, Shanghai, China, in 1991, and the M.S. degree in electrical engineering from HenanPolytechnicUniversity in 2003.He is a graduate in school of electronic and information engineering, BeijingJiaotongUniversity, Beijing, China. His research interests include channel code and information security in mobile communication system. His email is . or .
Wei Xueye was born in Shandong, China,in 1964. He received his B.S. and M.S. from Tianjing University, China, in 1987 and 1990,the Ph.D. from Beijing Polytechnic University, China in 1995.He is a Professor in school of electronic and information engineering, BeijingJiaotongUniversity, Beijing, China. His research interests include DSP and nonlinear theory.