On the Homomorphic Properties of Kyber and McEliece with Application to Post-Quantum Private Set Intersection

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.