# Single Trace Side Channel Analysis on NTRU Implementation
## 1 Introduction  
The currently used public key cryptography (PKC) such as RSA and Elliptic Curve Cryptography (ECC) are no longer secure if the quantum computer is developed running the Shor algorithm [1; 2; 3]. Due to the recent advances in quantum computing, post-quantum cryptography (PQC) is an active area of research. Moreover, the national institute of standards and technology (NIST) announced a project to define new standards for the PKC [4]. There are five categories studied for PQC: lattice-based cryptography, multivariate-based cryptography, hash-based cryptography, code-based cryptography, and isogeny-based cryptography. Among those categories, lattice-based cryptography is one of the prominent candidates due to the fast performance with a practical key size. In the same context, the largest number of candidates submitted to NIST project belong to the lattice-based cryptography. One of the well known lattice-based cryptography is NTRU, which is an abbreviation of N-th degree truncated polynomial ring.  
NTRU proposed in 1996 by [PERSON] et al. [5] is an encryption algorithm based on the shortest vector problem. NTRU has attracted much attention to the researchers due to the faster speed than classical cryptosystems by more than two orders of magnitude on the same security level. Regarding the implementation, only the encryption code was open to the public until 2017. After the patent release in 2017, all of the source code was available. Currently, two kinds of implementation are proposed in the literature, one released on GitHub in 2017 and the other submitted on NIST standardization project. We distinguish the prior one as NTRU Open Source and the latter as NTRUEncrypt, and also thealgorithm itself as NTRU. Although NTRU has withstood various mathematical attacks, the security of its implementation is an open question.  
After the proposal of the side channel analysis (SCA) by [PERSON] et al. [6] in 1996, most of the cryptosystems consider a SCA as a de facto standard in nowadays. Additionally, since the resistance of a SCA is included as a requirement in FIPS140-2 (Federal Information Processing Standard publication 140-2), NTRU should consider the resistance against SCA to substitute the RSA and ECC. Moreover, the NIST standardization project suggests a resistance to SCA for the submitted candidates. The SCA is an attack using additional information such as time, sound, and power consumption during the operation of a cryptographic device. Among these methods, power analysis attack such as the differential power analysis (DPA) and simple power analysis (SPA) is known to be the most practical method. The SPA performs by analyzing a single power consumption trace of the device. The DPA is a statistical approach by exploiting a number of power traces related to secret data. Even though the cryptographic algorithm is theoretically safe, the private key or secret message can be exposed by the side-channel leakage when executing the algorithm. In this regard, there are previous studies on SCA on NTRU by [PERSON] et al. [7] and [PERSON] et al. [8]. They performed DPA on NTRU and revealed the secret key. However, whether other types of power analysis can be performed has not been analyzed so far.