Barış Bülent KIRLAR, Ferdi ELVERDİ, Sedat AKLEYLEK

Efficient Nyberg-Rueppel type of NTRU digital signature algorithm

Message recovery is an important property in Nyberg-Rueppel type digital signature algorithms. However, the security of Nyberg-Rueppel type digital signature algorithms depends on the hard problems which might be vulnerable to quantum attacks. Therefore, quantum resistant Nyberg-Rueppel type digital signature algorithms with message recovery property are needed. Since NTRU-based cryptosystems are one of the best studied quantum-resistant schemes, using traditional NTRU encryption scheme has several advantages on the message recovery property. In this paper, we define Nyberg-Rueppel type of NTRU digital signature algorithm. It is carried out by combining NTRU-based encryption and signature algorithms. In the proposed scheme, efficient message recovery property is achieved with the help of NTRU. Then, we compare the computational cost of our Nyberg-Rueppel type signature scheme with the others in terms of the arithmetic complexity. According to the asymptotic complexity results, the proposed scheme has better arithmetic complexity than Nyberg-Rueppel type schemes. We also discuss the security properties of the proposed scheme by modifying attacks on Nyberg-Rueppel type algorithms and lattice-based algorithms.

PDF

___

[1] Abe M, Okamoto T. A signature scheme with message recovery as secure as discrete logarithm. Advances in Cryptology - Asiacrypt 1999; LNCS 1716: 378-389.
[2] Accredited Standards Committee X9. Lattice-based polynomial public key establishment algorithm for the financial services industry. 2010.
[3] Ajtai M, Dwork C. A public key cryptosystem with worst-case/average-case equivalence. ECCC 1996; TR96-065.
[4] Akleylek S, Çevik N. MaTRU-KE revisited: CCA2-secure key establishment protocol based on MaTRU. International Journal of Communication Systems 2020; 33 (7): e4326.
[5] Ashraf M, Kırlar BB. Message transmission for GH-public key cryptosystem. Journal of Computational and Applied Mathematics 2014; 259: 578-585.
[6] Buchmann J, May A, Vollmer U. Perspectives for cryptographic long-term security. Communications of the ACM 2006; 49: 50-55.
[7] Chen, Q et al. NTRU:A submission to the NIST post-quantum standardization effort. NIST PQC Project, 2019.
[8] Coglianese M, Goi BM. MaTRU a new NTRU-based cryptosystem. In Proceedings of INDOCRYPT 2005; LNCS 3797: 232-243.
[9] Dai W, Whyte W, Zhang Z. Optimizing polynomial convolution for NTRUEncrypt. IACR eprint Archive 2018; 229.
[10] Das D, Hoffstein J, Pipher J, Whyte W, Zhang Z. Modular lattice signatures, revisited. Designs, Codes and Cryptography 2019; 88 (3): 1-28.
[11] Ducas L, Nguyen PQ. Learning a zonotope and more: cryptanalysis of NTRUSign countermeasures. Advances in Cryptology - Asiacrypt 2012: LNCS 7658: 433-450.
[12] Ducas L, Durmus A, Lepoint T, Lyubashevsky V. Lattice signatures and bimodal gaussians. Advances in Cryptology - CRYPTO 2013; LNCS 8042: 40-56.
[13] Gentry C, Szydlo M. Cryptanalysis of the revised NTRU signature scheme. Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques EUROCRYPT 2002; 299-320.
[14] Goldreich O, Goldwasser S, Halevi S. Public-key cryptosystems from lattice reduction problems. Advances in Cryptology - CRYPT0 1997; LNCS 1294: 112-131.
[15] Gong G, Harn L, Wu H. The GH public-key cryptosystem. Selected Areas in Cryptography - SAC 2001; LNCS 2259: 284-300.
[16] Hoffstein J, Pipher J, Silverman JH. NTRU: A ring-based public key cryptosystem. Algorithmic Number Theory (ANTS) 1998; LNCS 1423: 267-288.
[17] Hoffstein J, Pipher J, Silverman JH. NSS: An NTRU lattice-based signature scheme. International Conference on the Theory and Applications of Cryptographic Techniques EUROCRYPT 2001; LNCS 2045: 211-228.
[18] Hoffstein J, Pipher J, Silverman JH. NTRUSign: digital signatures using the NTRU lattice. Topics in Cryptology - CT-RSA 2003; LNCS 2612: 122-140.
[19] Hoffstein J, Pipher J, Silverman JH. An Introduction to Mathematical Cryptography, New York: Springer, 2008.
[20] Hoffstein J, Pipher J, Schanck JM, Silverman JH, Whyte W. Transcript secure signatures based on modular lattices. IACR eprint Archive 2014; 457.
[21] Howgrave-Graham N. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. Advances in Cryptology CRYPTO 2007: LNCS 4622: 150-169.
[22] IEEE Std 1363.1-2008. IEEE Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices. 2008.
[23] Johnson D, Menezes A, Vanstone S. The elliptic curve digital signature algorithm (ECDSA). International Journal of Information Security 2001; 1 (1): 36-63.
[24] Karabsi AH, Atani RE. ILTRU: An NTRU-like public key cryptosystem over ideal lattices. IACR eprint Archive 2015; 549.
[25] Kırlar BB. Efficient message transmission via twisted Edwards curves. Mathematica Slovaca 2020; 70 (6): 1511-1520.
[26] Koblitz N. Elliptic curves cryptosystems. Mathematics of Computation 1987; 48: 203-209.
[27] Lenstra AK, Verheul ER. An overview of the XTR public key system. In Alster K, Urbanowicz J, Williams HC (editors). Public-Key Cryptography and Computational Number Theory 2001. Warsaw, Poland: Walter de Gruyter, 2001; 151-181.
[28] Lenstra AK, Lenstra HW, Lovász L. Factoring polynomials with rational coefficients. Mathematische Annalen 1982; 261 (4): 515-534.
[29] Malekian E, Zakerolhosseini A, Mashatani A. QTRU: a lattice attack resistant version of NTRU. IACR eprint Archive 2009; 386.
[30] Miyaji A. Weakness in message recovery signature schemes based on discrete logarithm problems 1. IEICE Japan Technical Reports, ISEC95-7, 1995.
[31] Nevins M, Karimianpour C, Miri A. NTRU over rings beyond Z. Designs, Codes and Cryptography 2010; 56: 65-78.
[32] Nguyen PQ, Regev O. Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. Journal of Cryptology 2009; 22 (2): 139-160.
[33] NIST. Post-Quantum Cryptography Project 2017.
[34] Nyberg K, Rueppel RA. A new signature scheme based on the DSA giving message recovery. Proceedings of the 1st ACM Conference on Computer and Communications Security 1993; 58-61.
[35] Nyberg K, Rueppel RA. Message recovery for signature schemes based on the discrete logarithm problem. Designs, Codes and Cryptography 1996; 7 (1-2): 61-81.
[36] Rivest RL, Shamir A, Adleman L. A method for obtaining digital signatures and public key cryptosystem. Communications of the ACM 1978; 21: 120-126.
[37] Schanck J. Practical lattice cryptosystems: NTRUEncrypt and NTRUMLS. M.Sc. Thesis. University of Waterloo, Canada, 2015.
[38] Schnorr CP. Fast LLL-type lattice reduction. Information and Computation 2006; 204: 1-25.
[39] Shor P. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994; 124-134.
[40] Silverman JH. Almost inverses and fast NTRU key creation. NTRU Cryptosystems. Technical Note # 014, 1999.
[41] Singh S, Padhye S. Generalisations of NTRU cryptosystem. Security and Communication Networks 2016; 9: 6315- 6334.
[42] Steinfeld R. NTRU cryptosystem: recent developments and emerging mathematical problems in finite polynomial rings. Niederreiter H, Ostafe A, Panario D, Winterhof A (editors). Algebraic Curve and Finite Fields: Cryptography and Other Applications 2014. Berlin, Germany: De Gruyter, 2014; 179-212.
[43] Yashoda T, Dahan X, Sakurai K. Characterizing NTRU-variants using group ring evaluating their lattice security. IACR eprint Archive 2015; 1170.
[44] Yeun CY. Digital signature with message recovery and authenticated encryption (signcryption) a comparison. IMA - Cryptography and Coding 1999; LNCS 1746: 307-312.
[45] Wang H, Ma Z, Ma CG. An efficient quantum meet-in-the-middle attack against NTRU-2005. Chinese Science Bulletin 2013; 58 (28-29): 3514-3518.