Abstract
We consider the NTRU encryption scheme as lately suggested for use, and study the connection between inverting the NTRU primitive (i.e., the one-way function over the message and the blinding information which underlies the NTRU scheme) and recovering the NTRU secret key (universal breaking). We model the inverting algorithms as black-box oracles and do not take any advantage of the internal ways by which the inversion works (namely, it does not have to be done by following the standard decryption algorithm). This allows for secret key recovery directly from the output on several inversion queries even in the absence of decryption failures. Our oracles might be queried on both valid and invalid challenges e, however they are not required to reply (correctly) when their input is invalid. We show that key recovery can be reduced to inverting the NTRU function. The efficiency of the reduction highly depends on the specific values of the parameters. As a side-result, we connect the collisions of the NTRU function with decryption failures which helps us gain a deeper insight into the NTRU primitive.
Chapter PDF
Similar content being viewed by others
References
EESS: Consortium for Efficient Embedded Security. Efficient Embedded Security Standards #1: Implementation Aspects of NTRU and NSS, draft version 3.0 edition (July 2001)
Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
Boneh, D., Venkatesan, R.: Breaking RSA May Not Be Equivalent to Factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 59–71. Springer, Heidelberg (1998)
Coppersmith, D., Shamir, A.: Lattice Attacks on NTRU. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 52–61. Springer, Heidelberg (1997)
Gama, N., Nguyen, P.Q.: New Chosen-Ciphertext Attacks on NTRU. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 89–106. Springer, Heidelberg (2007)
Gentry, C.: Key Recovery and Message Attacks on NTRU-Composite. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 182–194. Springer, Heidelberg (2001)
Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: Hybrid Lattice Reduction and Meet in the Middle Resistant Parameter Selection for NTRUEncrypt, http://grouper.ieee.org/groups/1363/lattPK/submissions/ChoosingNewParameters.pdf
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A Ring-Based Public Key Cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)
Hoffstein, J., Silverman, J.H.: Protecting NTRU Against Chosen Ciphertext and Reaction Attacks. Technical report, NTRU Cryptosystems (2000), http://citeseer.ist.psu.edu/hoffstein00protecting.html
Hoffstein, J., Silverman, J.H.: Reaction Attacks Against the NTRU Public Key Cryptosystem. Technical Report, NTRU Cryptosystems, Report #015, version 2 (June 2000), http://citeseer.ist.psu.edu/hoffstein00reaction.html
Howgrave-Graham, N.: A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 150–169. Springer, Heidelberg (2007)
Howgrave-Graham, N., Nguyen, P.Q., Pointcheval, D., Proos, J., Silverman, J.H., Singer, A., Whyte, W.: The Impact of Decryption Failures on the Security of NTRU Encryption. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 226–246. Springer, Heidelberg (2003)
Howgrave-Graham, N., Silverman, J.H., Whyte, W.: Choosing Parameter Sets for NTRUEncrypt with NAEP and SVES-3. Technical Report, NTRU CRYPTOSYSTEMS (2005)
Hong, J., Han, J., Kwon, D., Han, D.: Chosen-Ciphertext Attacks on Optimized NTRU. Cryptology ePrint Archive: Report 2002/188 (2002)
Jaulmes, É., Joux, A.: A Chosen-Ciphertext Attack against NTRU. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 20–35. Springer, Heidelberg (2000)
Hoffstein, J., Silverman, J.: Optimizations for NTRU. Technical report, NTRU Cryptosystems (June 2000), http://citeseer.ist.psu.edu/693057.html
Näslund, M., Shparlinski, I., Whyte, W.: On the Bit Security of NTRUEncrypt. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 62–70. Springer, Heidelberg (2002)
May, A.: Cryptanalysis of NTRU-107 (1999), http://www.informatik.tu-darmstadt.de/KP/publications/01/CryptanalysisOfNTRU.ps
Nguyen, P.Q., Pointcheval, D.: Analysis and Improvements of NTRU Encryption Paddings.. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 210–225. Springer, Heidelberg (2002)
Paillier, P., Villar, J.L.: Trading One-Wayness Against Chosen-Ciphertext Security in Factoring-Based Encryption.. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 252–266. Springer, Heidelberg (2006)
Rabin, M.O.: Digital Signatures and Public-Key Functions as Intractable as Factorization. Technical report, Cambridge (1979)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mol, P., Yung, M. (2008). Recovering NTRU Secret Key from Inversion Oracles. In: Cramer, R. (eds) Public Key Cryptography – PKC 2008. PKC 2008. Lecture Notes in Computer Science, vol 4939. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78440-1_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-78440-1_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78439-5
Online ISBN: 978-3-540-78440-1
eBook Packages: Computer ScienceComputer Science (R0)