Crystals-Kyber and Classic-McEliece are two prominent post-quantum key encapsulation mechanisms (KEMs) designed to address the challenges posed by quantum computing to classical cryptographic schemes. While the former has been standardized by the National Institute of Standards and Technology (NIST), the latter is well-known for its exceptional robustness and as one of the finalists of the fourth round of post-quantum cryptography standardization. Private set intersection (PSI) is a privacy-preserving technique that enables two parties, each possessing a dataset, to compute the intersection of their sets without revealing anything else. This can be achieved thanks to homomorphic encryption (HE), which allows computations on encrypted data. In this paper, firstly, we study Kyber and McEliece, apart from being KEMs, as post-quantum public key encryption (PKE), and examine their homomorphic properties. Secondly, we design two different two-party PSI protocols that utilize the homomorphic capabilities of Kyber and McEliece. Thirdly, a practical performance evaluation under NIST’s security levels 1, 3, and 5 is conducted, focusing on three key metrics: storage overhead, communication overhead, and computation cost. Insights indicate that the Kyber-based PSI Protocol, which utilizes the multiplicative homomorphic property, is secure but less efficient. In contrast, the McEliece-based PSI protocol, while efficient in practice, raises concerns regarding its security as a homomorphic encryption scheme.
Crystals-Kyber and Classic-McEliece are two prominent post-quantum key encapsulation mechanisms (KEMs) designed to address the challenges posed by quantum computing to classical cryptographic schemes. While the former has been standardized by the National Institute of Standards and Technology (NIST), the latter is well-known for its exceptional robustness and as one of the finalists of the fourth round of post-quantum cryptography standardization. Private set intersection (PSI) is a privacy-preserving technique that enables two parties, each possessing a dataset, to compute the intersection of their sets without revealing anything else. This can be achieved thanks to homomorphic encryption (HE), which allows computations on encrypted data. In this paper, firstly, we study Kyber and McEliece, apart from being KEMs, as post-quantum public key encryption (PKE), and examine their homomorphic properties. Secondly, we design two different two-party PSI protocols that utilize the homomorphic capabilities of Kyber and McEliece. Thirdly, a practical performance evaluation under NIST’s security levels 1, 3, and 5 is conducted, focusing on three key metrics: storage overhead, communication overhead, and computation cost. Insights indicate that the Kyber-based PSI Protocol, which utilizes the multiplicative homomorphic property, is secure but less efficient. In contrast, the McEliece-based PSI protocol, while efficient in practice, raises concerns regarding its security as a homomorphic encryption scheme.
While tremendous progress has been made towards achieving highly efficient and practical Private Set Intersection (PSI) protocols during the last decade, the development of post-quantum PSI is still far from satisfactory. Existing post-quantum PSI protocols encounter a dilemma: while those based on fully homomorphic encryption (FHE) achieve low online communication, they suffer from significant online computation; conversely, protocols based on post-quantum Oblivious Pseudorandom Functions (OPRFs) exhibit excellent online computational performance but incur substantially high online communication. To overcome this dilemma, we present a lattice-based PSI protocol that achieves optimal online performance in both communication and computation. Our solution introduces two core innovations: a robust signal comparison algorithm based on RLWE key exchange, which determines the intersection through signal consistency rather than direct shared key comparison, and an optimized Oblivious Key–Value Stores (OKVS) implementation featuring a composite key–value mapping for efficient handling of high-dimensional RLWE polynomials. We implement the protocol and conduct extensive benchmarks in both symmetric and asymmetric set-size settings. The results show that our construction achieves the lowest online overhead in both computation and communication among all tests. For example, with asymmetric set sizes (212,11041), the online phase requires only 0.132 s, yielding 19× and 282× improvements over FHE-based (CCS’21) and OPRF-based (EUROCRYPT’25) protocols, respectively. Even at (224,11041), our online communication time is only 0.201 s, which is 226× and 184× that of FHE-based and OPRF-based PSI, respectively. Additionally, our online communication overhead is the lowest in all tests; however, this comes at the cost of heavy offline communication overhead for very large set sizes, revealing a clear trade-off between pre-computation and online efficiency. This work addresses a critical gap in post-quantum PSI by delivering a protocol that achieves balanced online communication and computational overhead, thereby enabling broader practical deployment.
The advent of quantum computers poses a significant threat to the security of classical cryptographic systems. To address this concern, researchers have been actively investigating the development of post-quantum cryptography, which aims to provide encryption schemes that remain secure even in the face of powerful quantum adversaries. To address this serious problem, the National Institute of Standards and Technology (NIST), a body of the US government, has been working on the selection and standardization of cryptographic algorithms through competitive and rigorous evaluation on different fronts. NIST has selected different candidate algorithms to standardize public-key encryption, including key establishment algorithms and digital signature algorithms. This paper reviews some selected cryptosystems, mainly based on lattice- and code-based cryptosystems. These include digital signature algorithms, such as CRYSTALS-Dilithium, code-based cryptosystems, such as McEliece, and key encapsulation methods, specifically, Classic McEliece, BIKE and HQC. We will review these algorithms and discuss their security aspects and the current state-of-the-art in the development of these algorithms post NIST 3rd finalized selection. We will also touch briefly on the differences and practical applications of each of these schema. This review is intended for engineers and practitioners alike.
Group authenticated key exchange protocols (GAKE) are cryptographic tools enabling a group of several users communicating through an insecure channel to securely establish a common shared high-entropy key. In the last years, the need to design cryptographic tools which provide security in the presence of attackers with access to quantum resources has become unquestionable; the field dealing with these types of protocols is usually referred to as Post-Quantum Cryptography. The U.S. National Institute for Standards and Technology (NIST) launched in 2017 an open call to find suitable post-quantum public-key algorithms for standardization. In this work, we design a GAKE that can be instantiated with any key encapsulation mechanism (KEM) that satisfies the strong security notion IND-CCA, matching NIST’s requirements for this primitive. We have implemented our GAKE with the four finalist KEMs from the NIST process: Classic McEliece, Kyber, NTRU, and Saber, making use of the open-source library LibOQS where these algorithms are provided. We have conducted a detailed comparative performance analysis of the resulting GAKE protocols, taking into account all the parameter sets proposed in the submissions. We have also made a performance analysis of all the involved building pieces, including the four finalist KEMs. Finally, we also compare our GAKE with a previous proposal implemented with Kyber.
Private set intersection (PSI) is a cryptographic protocol that enables two parties to securely determine the intersection of their private datasets without revealing anything except the intersection. Most of the existing PSI protocols are based on traditional number theoretic problems, such as discrete logarithm problem and factorisation problem. Unfortunately, these protocols would be broken if efficient quantum computer emerges. The post-quantum PSI is an important alternative to traditional PSI protocols for its potential to resist future attacks of quantum computers. In this work, we present first post-quantum PSI protocol that achieves size-hiding property. Space-efficient probabilistic data structure Bloom filter along with lattice-based public key encryption are used as building blocks of our construction. It attains linear complexity and security in standard model under the decisional learning with errors (DLWE) assumption. Moreover, we extend our post-quantum PSI to its authorised variant APSI retaining all the properties.
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 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