Title: Efficient post-quantum private set-intersection protocol

Authors: Sumit Kumar Debnath; Nibedita Kundu; Tanmay Choudhury

Addresses: Department of Mathematics, National Institute of Technology Jamshedpur, Jamshedpur-831014, India ' Department of Mathematics, The LNM Institute of Information Technology, Jaipur-302031, India ' Department of Mathematics, National Institute of Technology Jamshedpur, Jamshedpur-831014, India

Abstract: 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.

Keywords: private set intersection; PSI; APSI; Bloom filter; post-quantum cryptography; lattice-based cryptosystem.

DOI: 10.1504/IJICS.2022.122381

International Journal of Information and Computer Security, 2022 Vol.17 No.3/4, pp.405 - 423

Received: 25 Mar 2019
Accepted: 29 Jul 2019
Published online: 22 Apr 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article