A New Provably Secure Cryptosystem Using Dedekind Domain Direct Product Approach

Amir Hassani Karbasi


We would like to prevent, detect, and protect communication and information systems' attacks, which include unauthorized reading of a message of file and traffic analysis or active attacks, such as modification of messages or files, and denial of service by providing cryptographic techniques. If we prove that an encryption algorithm is based on mathematical NP-hard problems, we can prove its security. In this paper, we present a new NTRU-Like public-key cryptosystem with security provably based on the worst-case hardness of the approximate lattice problems (NP-hard problems) in some structured lattices (ideal lattices) in order to attain the applicable objectives of preserving the confidentiality of communication and information system resources (includes hardware, software, firmware, information/data, and telecommunications). Our proposed scheme is an improvement of ETRU cryptosystem. ETRU is an NTRU-Like public-key cryptosystem based on the Eisenstein integers Z [f_3 ] where f_3 is a primitive cube root of unity. ETRU has heuristic security and it has no proof of security. We show that our cryptosystem has security stronger than that of ETRU, over cartesian product of dedekind domains and extended cyclotomic polynomials. We prove the security of our main algorithm from the R-SIS and R-LWE problems as NP-hard problems.

Full Text:



W. Diffie and M.E. Hellman, "New directions in cryptography," In IEEE Trans. On Information Theory, vol. 22, pp.644-654, 1976.

J. Hoffstein, J. Pipher, J.H. Silverman, "NTRU: a new high speed public-key cryptosystem," Preprint; presented at the rump session of Crypto 1996.

D. Coppersmith, A. Shamir, "Lattice attacks on NTRU," In Fumy, W. (ed.) EUROCRYPT, LNCS, vol. 1233, pp. 52–61. Springer,Heidelberg 1997.

J. Hoffstein, J. Pipher, J.H. Silverman, "NTRU: A ring-based public-key cryptosystem," In Buhler, J.P. (ed.) ANTS, LNCS, vol. 1423, pp.267–288. Springer, Heidelberg 1998.

IEEE P1363. Standard specifications for public-key cryptography, http://grouper.ieee.org/groups/1363/

R.A. Perlner, D.A. Cooper, "Quantum resistant public-key cryptography: a survey," In Proc. of IDtrust, ACM, New York, 2009, pp. 85–93.

K. Jarvis, and M. Nevins, "ETRU: NTRU over the Eisenstein Integers," Designs, Codes and Cryptography, DOI: 10. 1007/s10623-013-9850-3, Springer, 2013.

M. Ajtai and C. Dwork, "A public-key cryptosystem with worst-case/average-case equivalence," In Proceedings of STOC, ACM, 1997, pp.284-293.

V. Lyubashevsky and D. Micciancio, "On bounded distance decoding, unique shortest vectors, and the minimum distance problem," In Proceedings of Crypto, vol. 5677 of LNCS, Springer, 2009, pp. 450-461.

D. Micciancio, "Generalized compact knapsacks, cyclic lattices, and efficient oneway functions," Computational Complexity, vol. 16, no. 4, pp. 365-411, 2007.

V. Lyubashevsky and D. Micciancio, "Generalized compact knapsacks are collision resistant," In Proceedings of ICALP, vol. 4052 of LNCS, Springer, 2006, pp. 144-155.

C. Peikert and A. Rosen, "Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices," In Proceedings of TCC, 2006, pp. 145-166.

O. Regev, "On lattices, learning with errors, random linear codes, and cryptography," Journal of ACM, vol. 56, no. 6, 2009.

D. Stehle, R. Steinfeld, "Making NTRU as Secure as Worst-Case Problems over Ideal Lattices," In Eurocrypt, LNCS 6632, 2011, pp. 27-47.

M., Nevins, C. Karimianpour, A. Miri, "NTRU over rings beyond Z," Des. Codes Cryptogr., vol. 56, no. 1, pp. 65–78, 2010.

V. Lyubashevsky, C. Peikert, O. Regev, "On ideal lattices and learning with errors over rings," In Gilbert, H. (ed.) EUROCRYPT, LNCS,vol. 6110, Springer, Heidelberg 2010, pp. 1–23.

C. Gentry, "Fully homomorphic encryption using ideal lattices," In Proc. of STOC, ACM, New York 2009, pp. 169–178.

V. Lyubashevsky, C. Peikert, O. Regev, "On ideal lattices and learning with errors over rings," Draft version, dated 01/02/2011.

P. Garrett, "Abstract Algebra," University of Minnesota, 2007, pp. 211-217.

R.E. Atani, S.E. Atani, and A.H. Karbasi, "EEH: A GGH-Like Public Key Cryptosystem Over The Eisenstein Integers Using Polynomial Representation," The ISC International Journal of Information Security (IseCure), Vol. 7, No. 2, 2015, pp. 115-126.

A.H. Karbasi and R.E. Atani, "ILTRU: An NTRU-Like Public Key Cryptosystem Over Ideal Lattices," IACR Cryptology ePrint Archive 2015: 549, 2015.

A.H. Karbasi and R.E. Atani, "PSTRU: A provably secure variant of NTRUEncrypt over extended ideal lattices," The 2nd National Industrial Mathematics Conference, Tabriz, Iran, 2015.

A.H. Karbasi and R.E. Atani, "A Survey on Lattice-based Cryptography," (in Persian), Biannual Journal for Cyberspace Security (Monadi AFTA), Vol. 3, No. 1, 2015, pp 3-14.

A.H. Karbasi, M.A. Nia, and R.E. Atani, "Designing of An Anonymous Communication System Using Lattice-based Cryptography," (in Persian), Journal of Electronic and Cyber Defence, Vol. 2, No. 3, 2014, pp. 13-22.

S.E. Atani, R.E. Atani, and A.H. Karbasi, "A Provably Secure Variant of ETRU Based on Extended Ideal Lattices over Direct Product of Dedekind domains," Submitted.

A.H. Karbasi, R.E. Atani, and S.E. Atani, "A New Ring-Based SPHF and PAKE Protocol On Ideal Lattices," Submitted.

S.E. Atani, R.E. Atani, and A.H. Karbasi, "PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem,"INTERNATIONAL JOURNAL OF INFORMATION SECURITY SCIENCE, Vol. 7, No. 1, 2018, pp. 11-19.

S.E. Atani, R.E. Atani, and A.H. Karbasi, "NETRU: A Non-Commutative and Secure Variant of CTRU Cryptosystem," The ISC international journal of information security (IseCure), Vol. 10, No. 1, 2018, pp. 1-9.

DOI: http://dx.doi.org/10.23755/rm.v34i0.404


  • There are currently no refbacks.

Copyright (c) 2018 Amir Hassani Karbasi

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Ratio Mathematica - Journal of Mathematics, Statistics, and Applications. ISSN 1592-7415; e-ISSN 2282-8214.