Cryptology ePrint Archive: Report 2018/998

A Key Recovery Attack on Streamlined NTRU Prime

Chen Li

Abstract: For years, researchers have been engaged in finding new cryptography schemes with high security and efficiency that can resist against the attacking from quantum computers. Lattice-based cryptography scheme is believed as a promising candidate. But to achieve both high efficiency and high security is not easy. Until recently, some Lattice-based schemes with enough efficiency have been proposed and submitted to the post-quantum cryptography standardization project that initiated by NIST. Streamlined NTRU Prime is one of them. Basing on a new``strong" ring and applying the ``modern key encapsulation mechanism" approach, Streamlined NTRU Prime aims to provide IND-CCA security.

However, in this paper, we identify a simple property of the new ``strong" ring. Using this property and also taking advantage of the information leakage from the decapsulation feedback, we provide an efficient key recovery attack on the Streamlined NTRU Prime. Our attack does not only break most instances of Streamlined NTRU Prime, but also shows an evidence that modifying a public key encryption scheme into a key encapsulation mechanism scheme does not naturally provide higher security.

Category / Keywords: NTRU Prime, key encapsulation mechanism, IND-CCA security, post-quantum cryptography

Date: received 16 Oct 2018, last revised 20 Oct 2018, withdrawn 3 Dec 2018

Contact author: morn_l at msn com

Available format(s): (-- withdrawn --)

Note: A notation is corrected.

Version: 20181203:081710 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]