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.
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.
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.
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.
Current improvements in quantum computing present a substantial challenge to classical cryptographic systems, which typically rely on problems that can be solved in polynomial time using quantum algorithms. Consequently, post-quantum cryptography (PQC) has emerged as a promising solution to emerging quantum-based cryptographic challenges. The greatest threat is public-key cryptosystems, which are primarily responsible for key exchanges. In PQC, key encapsulation mechanisms (KEMs) are crucial for securing key exchange protocols, particularly in Internet communication, virtual private networks (VPNs), and secure messaging applications. CRYSTALS-Kyber and NTRU are two well-known PQC KEMs offering robust security in the quantum world. However, even when quantum computers are functional, they are not easily accessible. IoT devices will not be able to utilize them directly, so there will still be a requirement to protect IoT devices from quantum attacks. Concerns such as limited computational power, energy efficiency, and memory constraints in devices such as those used in IoTs, embedded systems, and smart cards limit the use of these techniques in constrained environments. These concerns always arise there. To address this issue, this study conducts a broad comparative analysis of Kyber and NTRU, with special focus on their security, performance, and implementation efficiency in such environments (IOT/constrained environments). In addition, a case study was conducted by applying KEMs to a low-power embedded device to analyze their performance in real-world scenarios. These results offer an important comparison for cyber security engineers and cryptographers who are involved in integrating post-quantum cryptography into resource-constrained devices.