The NTRU lattice is a promising candidate to construct practical cryptosystems, in particular key encapsulation mechanism (KEM), resistant to quantum computing attacks. Nevertheless, there are still some inherent obstacles to NTRU-based KEM schemes in having integrated performance, taking security, bandwidth, error probability, and computational efficiency \emph{as a whole}, that is as good as and even better than their \{R,M\}LWE-based counterparts. In this work, we solve this problem by presenting a new family of NTRU-based KEM schemes, referred to as CTRU and CNTR. By bridging low-dimensional lattice codes and high-dimensional NTRU-lattice-based cryptography with careful design and analysis, to the best of our knowledge CTRU and CNTR are the first NTRU-based KEM schemes with scalable ciphertext compression via only one \emph{single} ciphertext polynomial, and are the first that could outperform \{R,M\}LWE-based KEM schemes in integrated performance. For instance, compared to Kyber that is currently the only standardized KEM by NIST, on the recommended parameter set CNTR-768 has about
12% smaller ciphertext size while encapsulating 384-bit keys compared to the fixed 256-bit key size of Kyber, security strengthened by
(8,7) bits for classical and quantum security respectively, and significantly lower error probability (
2−230 of CNTR-768 vs.
2−164 of Kyber-768). In comparison with the state-of-the-art AVX2 implementation of Kyber-768, CNTR-768 is faster by 1.9X in KeyGen, 2.6X in Encaps, and 1.2X in Decaps, respectively. When compared to the NIST Round 3 finalist NTRU-HRSS, our CNTR-768 has about
15% smaller ciphertext size, and the security is strengthened by
(55,49) bits for classical and quantum security respectively. As for the AVX2 implementation, CNTR-768 is faster than NTRU-HRSS by 19X in KeyGen, 2.3X in Encaps, and 1.6X in Decaps, respectively.
We present BAT – an IND-CCA secure key encapsulation mechanism (KEM) that is based on NTRU but follows an encryption/decryption paradigm distinct from classical NTRU KEMs. It demonstrates a new approach of decrypting NTRU ciphertext since its introduction 25 years ago. Instead of introducing an artificial masking parameter p to decrypt the ciphertext, we use 2 linear equations in 2 unknowns to recover the message and the error. The encryption process is therefore close to the GGH scheme. However, since the secret key is now a short basis (not a vector), we need to modify the decryption algorithm and we present a new NTRU decoder. Thanks to the improved decoder, our scheme works with a smaller modulus and yields shorter ciphertexts, smaller than RSA-4096 for 128-bit classical security with comparable public-key size and much faster than RSA or even ECC. Meanwhile, the encryption and decryption are still simple and fast in spite of the complicated key generation. Overall, our KEM has more compact parameters than all current lattice-based schemes and a practical efficiency. Moreover, due to the similar key pair structure, BAT can be of special interest in some applications using Falcon signature that is also the most compact signature in the round 3 of the NIST post-quantum cryptography standardization. However, different from Falcon, our KEM does not rely on floating-point arithmetic and can be fully implemented over the integers.
Key encapsulation mechanism (KEM) is an important key distribution mechanism that not only allows both sender and receiver to safely share a random session key, but also can be mainly applied to construct a hybrid public key encryption scheme. In this paper, we give an positive answer to the question of if it is possible to build an efficient KEM over lattices. More precisely, we design an efficient KEM scheme in standard model based on ideal lattices. We prove that the proposed scheme captures indistinguishability against active chosen ciphertext attacks (IND-CCA) under the ring learning with errors problem, or more formally, IND-CCA security. Compared with the current CCA secure KEM schemes based on lattices in the standard model, our scheme has shorter public key, secret key and encapsulation ciphertext. In addition, our KEM scheme realizes IND-CCA security in the standard model.
In this article, we propose a double-NTRU (D-NTRU)-based key encapsulation mechanism (KEM) for the key agreement requirement of the post-quantum world. The proposed KEM is obtained by combining one-way D-NTRU encryption and Dent's KEM design method. The main contribution of this article is to construct a D-NTRU-based KEM that provides indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2) security. The IND-CCA2 analysis and primal/dual attack resistance of the proposed D-NTRU KEM are examined in detail. A comparison with similar protocols is provided regarding parameters, public/secret keys, and ciphertext sizes. The proposed scheme presents arithmetic simplicity and IND-CCA2 security that does not require any padding mechanism.
Recent developments have been made in the construction of cryptosystems with security based on the hardness of the lattice isomorphism problem (LIP). Due to lattice conjectures, one may expect in the future that breaking such schemes is computationally harder than most current lattice-based cryptosystems. To the best of our knowledge, there have not been any attempts to concretely instantiate a key encapsulation mechanism (KEM) based on LIP. In this work, we propose the first instance of such a KEM, following the framework of Ducas and van Woerden (EUROCRYPT 2022), using simple lattices. We present a randomness extractor derived from a hash function based on the short integer solution problem; define a concrete set of parameters for instantiating the scheme; provide a rigorous security estimation of an attacker trying to decode an encapsulated key through reductions to hard lattice problems; and use well-known methods to convert the IND-CPA secure KEM into an IND-CCA2 secure KEM, comparing the latter with other modern lattice-based KEMs. The resulting security is estimated under the assumption that an adversary cannot efficiently solve related instances of LIP, which is a consequence of the lack of cryptanalysis towards identifying isomorphism between lattices.
The Secure Shell (SSH) protocol is one of the first security protocols on the Internet to upgrade itself to resist attacks against future quantum computers, with the default adoption of the “quantum (otherwise, classically)” secure hybrid key exchange in OpenSSH from April 2022. However, there is a lack of a comprehensive security analysis of this quantum-resistant version of SSH in the literature: related works either focus on the hybrid key exchange in isolation and do not consider security of the overall protocol, or analyze the protocol in security models which are not appropriate for SSH, especially in the “post-quantum” setting. In this paper, we remedy the state of affairs by providing a thorough post-quantum cryptographic analysis of SSH. We follow a “top-down” approach wherein we first prove security of SSH in a more appropriate model, namely, our post-quantum extension of the so-called authenticated and confidential channel establishment (ACCE) protocol security model; our extension which captures “harvest now, decrypt later” attacks could be of independent interest. Then we establish the cryptographic properties of SSH's underlying primitives, as concretely instantiated in practice, based on our protocol-level ACCE security analysis: for example, we prove relevant cryptographic properties of “Streamlined NTRU Prime”, a key encapsulation mechanism (KEM) which is used in recent versions of OpenSSH and TinySSH, in the quantum random oracle model, and address open problems related to its analysis in the literature. Notably, our ACCE security analysis of post-quantum SSH relies on the weaker notion of IND-CPA security of the ephemeral KEMs used in the hybrid key exchange. This is in contrast to prior works which rely on the stronger assumption of IND-CCA secure ephemeral KEMs. Hence we conclude the paper with a discussion on potentially replacing IND-CCA secure KEMs in current post-quantum implementations of SSH with simpler and faster IND-CPA secure counterparts, and also provide the corresponding benchmarks.