FAST DISTINGUISHING ATTACK ON NTRUCipher + ENCRYPTION SCHEME

Abstract

The NTRUCipher encryption system was proposed in 2017 as a symmetric version of the encryption scheme NTRUEncrypt, which is currently one of the fastest post-quantum cryptographic algorithms based on lattices in Euclidean space. The purpose of building NTRUCipher is to create a symmetric encryption scheme for practical applications, the security of which, similarly asymmetric, is based on the difficulty of solving only one computational problem. Preliminary exploring of this encryption scheme have been conducted, however the question of NTRUCipher’s security against distinguishing attacks aimed at constructing statistical criteria for distinguishing sequences of encrypted messages and purely random sequences.

This article shows that the NTRUCipher and even its natural improvement NTRUCipher+ proposed by analogy with the well-known provable secure version of asymmetric NTRU encryption scheme, are vulnerable to distinguishing attacks. Fast distinguishing attack on the NTRUCipher+ and (for a special case) even faster modification of this attack are proposed. Analytical estimates of both attacks’ complexity are obtained, from which follows that they have polynomial time complexity and can be implemented in real-time (for standard parameters of the cipher). The obtained results show that other general constructions should be used to build symmetric NRTU-like encryption schemes.