Continuous Key Agreement (CKA) is a two-party protocol used in double-ratchet protocols such as signal. It enables continuous and synchronous key distribution that generates a fresh key to encrypt each transaction in messenger apps. It guarantees forward secrecy and post-compromise security. In recent years, the post-quantum versions of the double-ratchet protocol and CKA have been intensively studied. In Eurocrypt 2019, Alwenet al. suggest a generic construction of CKA based on the Key Encapsulation Mechanism (KEM), achieving the post-quantum CKA from post-quantum KEMs. They also mention that the bandwidth can be reduced by half using ElGamal KEM. In this paper, we generalize this idea by defining a new primitive called Decomposable Key Encapsulation Mechanism (DKEM) and instantiate it with the promising lattice-based schemes such as CRYSTALS-KYBER and SABER. Using DKEM instantiated with CRYSTALS-KYBER (resp. SABER) and security category 1 parameters, our CKA achieves 51% (resp. 48%) reduced bandwidths compared to the generic construction from KEM. We also implement our CKA on both Intel Xeon E5-1650 v3 and ARMv8 Cortex-A72 processors, respectively, and show that the performance of sender algorithm is improved from 79.29 to 96.94% (resp. from 74.64 to 91.04%) when instantiated with CRYSTALS-KYBER (resp. SABER).
Continuous Key Agreement (CKA) is a two-party protocol used in double-ratchet protocols such as signal. It enables continuous and synchronous key distribution that generates a fresh key to encrypt each transaction in messenger apps. It guarantees forward secrecy and post-compromise security. In recent years, the post-quantum versions of the double-ratchet protocol and CKA have been intensively studied. In Eurocrypt 2019, Alwenet al. suggest a generic construction of CKA based on the Key Encapsulation Mechanism (KEM), achieving the post-quantum CKA from post-quantum KEMs. They also mention that the bandwidth can be reduced by half using ElGamal KEM. In this paper, we generalize this idea by defining a new primitive called Decomposable Key Encapsulation Mechanism (DKEM) and instantiate it with the promising lattice-based schemes such as CRYSTALS-KYBER and SABER. Using DKEM instantiated with CRYSTALS-KYBER (resp. SABER) and security category 1 parameters, our CKA achieves 51% (resp. 48%) reduced bandwidths compared to the generic construction from KEM. We also implement our CKA on both Intel Xeon E5-1650 v3 and ARMv8 Cortex-A72 processors, respectively, and show that the performance of sender algorithm is improved from 79.29 to 96.94% (resp. from 74.64 to 91.04%) when instantiated with CRYSTALS-KYBER (resp. SABER).
Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digitalsignature, encryption, and key-establishment protocols, have created significant interest in post-quantum cryptographic schemes. This paper introduces Kyber (part of CRYSTALS - Cryptographic Suite for Algebraic Lattices - a package submitted to NIST post-quantum standardization effort in November 2017), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM), based on hardness assumptions over module lattices. Our KEM is most naturally seen as a successor to the NEWHOPE KEM (Usenix 2016). In particular, the key and ciphertext sizes of our new construction are about half the size, the KEM offers CCA instead of only passive security, the security is based on a more general (and flexible) lattice problem, and our optimized implementation results in essentially the same running time as the aforementioned scheme. We first introduce a CPA-secure public-key encryption scheme, apply a variant of the Fujisaki-Okamoto transform to create a CCA-secure KEM, and eventually construct, in a black-box manner, CCA-secure encryption, key exchange, and authenticated-key-exchange schemes. The security of our primitives is based on the hardness of Module-LWE in the classical and quantum random oracle models, and our concrete parameters conservatively target more than 128 bits of postquantum security.
The Signal protocol provides end-to-end security even when service providers are only partially trusted; however, it still lacks deniable authentication and does not resist quantum attacks in the messaging phase. This paper therefore presents a post-quantum enhancement of Signal that is efficient in both communication cost and end-to-end message latency. In the key-agreement phase, a lattice-based Gandalf ring signature is combined with the Kyber-1024 KEM to construct a pre-key mechanism that provides both post-quantum security and deniable authentication. In the messaging phase, a pair of post-quantum ratchets is layered on top of the classical Double Ratchet to form a classical-post-quantum hybrid ratchet, while the Skye key-derivation function and erasure-code-based block encapsulation reduce communication overhead. Experimental and analytical results show that the scheme preserves Signal’s end-to- end, forward, and post-compromise security, achieves practical post-quantum security and deniable authentication, and keeps the additional cryptographic delay negligible compared with typical network latency.
In emerging environments such as cloud computing and the Internet of Things (IoT), secure authentication and key negotiation play a crucial role in protecting data transmitted over public networks. However, many existing authentication protocols are still designed based on classical public-key cryptography primitives, and quantum computing may threaten their security. To address this challenge, we propose a post-quantum authentication and key agreement protocol that uses the lattice-based Kyber key encapsulation mechanism (KEM). Our proposed protocol integrates cryptographic authentication, smart card protection, and post-quantum key encapsulation mechanisms, enabling mutual authentication between users and servers and securely establishing session keys. The security of the protocol is formally analyzed in the Real-or-Random (ROR) model under the random oracle assumption and the IND-CCA security of the underlying KEM scheme. Furthermore, through informal security analysis, we have further demonstrated that the protocol possesses important security properties, including anonymity, untraceability, perfect forward confidentiality, and resistance to known attacks. In addition, the computational cost and communication overhead of the proposed scheme are evaluated and compared with several representative authentication protocols. The results show that the proposed protocol can provide strong security while maintaining low computational cost and communication overhead.
Post-quantum cryptography (PQC) must secure large-scale communication systems against quantum adversaries where classical hardness alone is insufficient and purely quantum schemes remain impractical. Lattice-based key encapsulation mechanisms (KEMs) such as CRYSTALS-Kyber provide efficient quantum-resistant primitives but rely solely on computational hardness assumptions that are susceptible to hybrid classical-quantum attacks. To overcome this limitation, we introduce the first Clauser-Horne-Shimony-Holt (CHSH)-certified Kyber protocol, which embeds quantum non-locality verification directly within the key exchange phase. The proposed design integrates CHSH entanglement tests using Einstein-Podolsky-Rosen (EPR) pairs to yield measurable quantum advantage values exceeding classical correlation limits, thereby coupling information--theoretic quantum guarantees with lattice-based computational security. Formal reductions demonstrate that any polynomial-time adversary breaking the proposed KEM must either solve the Module Learning With Errors (Module-LWE) problem or a Quantum Merlin-Arthur (QMA)-complete instance of the 2-local Hamiltonian problem, under the standard complexity assumption QMA ⊂ NP. The construction remains fully compatible with the Fujisaki-Okamoto (FO) transform, preserving chosen-ciphertext attack (CCA) security and Kyber's efficiency profile. The resulting CHSH-augmented Kyber scheme therefore establishes a mathematically rigorous, hybrid post-quantum framework that unifies lattice cryptography and quantum non-locality to achieve verifiable, composable, and forward-secure key agreement.
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.
The emergence of quantum computing poses an existential threat to classical cryptographic systems that form the backbone of contemporary digital security infrastructure. RSA, the most widely deployed public-key cryptosystem, relies on the computational hardness of integer factorization, a problem efficiently solvable by quantum computers using Shor's algorithm. This impending vulnerability has catalyzed the development of post-quantum cryptographic alternatives designed to withstand both classical and quantum attacks. CRYSTALS-Kyber, standardized by NIST as ML-KEM, represents the forefront of latticebased key encapsulation mechanisms, offering quantum resistance through the Module Learning With Errors (MLWE) problem. This paper presents a comprehensive comparative analysis of RSA and Kyber, examining their mathematical foundations, security architectures, operational characteristics, and performance metrics across diverse computational environments. The study investigates the fundamental trade-offs between legacy systems optimized for classical threat models and emerging quantum-resistant algorithms designed for future-proof security. Through detailed analysis of key generation, encryption/encapsulation, decryption/decapsulation operations, and security guarantees, this research establishes the technical rationale behind NIST's selection of Kyber as the primary post-quantum key establishment mechanism. The findings demonstrate that while RSA maintains advantages in key size efficiency, Kyber's superior performance profile, quantum resilience, and robust security foundation position it as the essential successor for securing digital communications in the quantum era. This comprehensive study provides critical insights for organizations transitioning from classical to post-quantum cryptographic infrastructure