A Tree-Based FHE Approach for Private Set Intersection

Abstract

Private Set Intersection (PSI) allows two parties to compute the intersection of their datasets without revealing any additional information. Fully Homomorphic Encryption (FHE) based PSI schemes offer strong security guarantees but typically rely on hashing or oblivious transfer, resulting in two major limitations: (1) communication complexity linear in the size of client dataset and logarithmic in server dataset, that is, O(|X|log(|Y|)), and (2) high memory usage when encoding large multi-digit numbers using SIMD packing. In this work, we propose a tree-structured representation for storing multi-digit numbers under FHE. Instead of packing entire numbers into slots, each digit is stored at a different depth of the tree, allowing homomorphic comparison to be performed digit-wise. This significantly reduces the dependency on dataset size, and communication complexity to O(|d|²), where |d| is the number of digits in each number. We implement our protocol using TenSEAL library and experimentally demonstrate reductions in communication and memory usage. Our design introduces a new direction for performing PSI over encrypted datasets containing large numeric values.