WPEC 2024 Talk 1a6: Vole-PSI: Fast Private Set Intersection from the LPN Assumption

Abstract. In this talk we present the state of art protocol for performing Private Set Intersection (PSI) for moderate to large set sizes(500+ elements). These protocols are based on a combination of the cryptographic primitive known as Vector Oblivious LinearEvaluation (VOLE) and a linear data structure referred to as a Oblivious Key-Value Store (OKVS). Details of these protocols willbe presented along with a brief description of how other primitives (e.g. OPRF, multi-party PSI) can be constructed from themas well. In addition, we will present how these protocols make use of the Learning Parity with Noise (LPN) assumptions alongwith a discussion on why LPN is believed to be hard for both classical and quantum adversaries. This will primarily focusattacks in to so called linear test framework along with a brief discussion on algebraic attacks.

Join work with: Phillipp Schoppmann, Srinivasan Raghuraman

[Slides] [Video]