Applications of Viete-Lucas Polynomials in Public-Key Cryptography

Marcin Lawnik


This article presents a new cryptosystem using the newly defined Viete'a-Lucas polynomials over Zp. In the conducted analysis the correctness and safety of the cryptosystem was shown. The analysis also shows, that it is partially homomorphic. Furthermore a fast methods for calculation the value of the Viete-Lucas polynomials were described.


asymmetrical cryptography; Viete-Lucas polynomials; homomorphic encryption

Full Text:

PDF (Polski)


Rivest R., Shamir A., Adleman L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21 (2), 1978.

ElGamal T.: A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory 31(4), 1985.

Diffie W., Hellman M.: New directions in cryptography. IEEE Transactions on Infor-mation Theory 22(6), 1976.

Kocarev L., Tasev Z.: Public-Key Encryption Based on Chebyshev Maps. Proceedings of the IEEE Symposium on Circuits and Systems 3, 2003.

Bergamo P., D’Arco P., De Santis A., Kocarev L.: Security of Public Key Cryptosys-tems based on Chebyshev Polynomials. Circuits and Systems I: Regular Papers, IEEE Transactions on, 52, 2005.

Kocarev L., Makraduli J., Amato P.: Public-Key Encryption Based on Chebyshev Poly-nomials. Circuits, Systems and Signal Processing 24(5), 2005.

Fee G., Monagan M.: Cryptography using Chebyshev polynomials. Proc. 2004 Maple Summer Workshop, 2004.

Mishkovski I., Kocarev L.: Chaos-Based Public-Key Cryptography. [w:] Kocarev L., Shiguo Lian S. (red.): Chaos-Based Cryptography Theory, Algorithms and Applica-tions, Springer, Berlin 2011.

Sun J., Zhao G., Li X.: An Improved Public Key Encryption Algorithm Based on Che-byshev Polynomials. TELKOMNIKA 11(2), 2013.

Vairachilai S., KavithaDevi M.K., Gnanajeyaraman R.: Public Key Cryptosystems using Chebyshev Polynomials Based on Edge Information. 2014 World Congress on Computing and Communication Technologies, 2014.

Hafizul Islam S.K.: Identity-based encryption and digital signature schemes using ex-tended chaotic maps. IACR Cryptology ePrint Archive 2014 (275): 2014.

Lai H., Xiao J., Li L., Yang Y.: Applying Semigroup Property of Enhanced Chebyshev Polynomials to Anonymous Authentication Protocol. Hindawi Publishing Corporation Mathematical Problems in Engineering 454823: 2012.

Li Z., Cui Y., Xu H.: Fast algorithms of public key cryptosystem based on Chebyshev polynomials over finite field. The Journal of China Universities of Posts and Telecom-munications 18(2), 2011.

Algehawi M.B., Samsudin A., Jahani S.: Calculation Enhancement of Chebyshev Poly-nomial over Zp. Malaysian Journal of Mathematical Sciences 7(S), 2013.

Wituła R., Słota D.: On modified Chebyshev polynomials. Journal of Mathematical Analysis and Applications 324(1), 2006.

Fateman R.: Lookup tables, recurrences and complexity. Proc. of ISSAC 89, ACM Press, New York 1989.

M. Bellare, A. Desai, D. Pointcheval, et al., Relations among notions of security for public-key encryption schemes, in: Advances in Cryptology, CRYPTO’98, Springer Berlin, Heidelberg 1998.

Gong L., Li S., Mao Q., Wang D., Dou J.: A homomorphic encryption scheme with adaptive chosen ciphertext security but without random oracle. Theoretical Computer Science 609(1), 2016.

Morris L.: Analysis of partially and fully homomorphic encryption. Homomorphic%20Encryption%20 Paper.pdf, 2013.