FHE-Based PSI

FHE-based PSI protocols typically require only one or two rounds of communication, regardless of set size. The client encrypts its entire set under its own public key and sends the ciphertexts to the server. The server homomorphically evaluates the intersection predicate on the encrypted client set and its own plaintext set, returning only the encrypted result. This contrasts sharply with OT-based protocols, where communication rounds often scale with set size or security parameter.

Unlike traditional PSI protocols that only test for exact equality, FHE-based constructions can evaluate arbitrary Boolean circuits over encrypted data. This enables:

• Threshold-based matching: Intersection on elements within a certain numeric range
• Fuzzy matching: Approximate string or biometric matching using Hamming distance circuits
• Composite predicates: Complex logical conditions combining multiple attributes

The server computes f(Enc(x), y) for any computable function f, not just equality checks.

FHE-based PSI imposes asymmetric computational costs between parties. The client performs relatively lightweight encryption operations, while the server bears the heavy burden of homomorphic evaluation. A typical server-side computation may involve:

• Evaluating a depth-optimized Boolean circuit over thousands of ciphertexts
• Performing homomorphic SIMD packing to batch multiple comparisons into single operations
• Managing noise growth through bootstrapping or careful parameter selection

This asymmetry makes FHE-PSI ideal for client-server architectures where the server has significant compute resources.

FHE-based PSI protocols achieve malicious security with minimal additional overhead compared to semi-honest variants. The core property is that the server operates entirely on ciphertexts it cannot decrypt, so a malicious server gains nothing by deviating from the protocol. A malicious client is constrained by the semantic security of the FHE scheme itself. Additional zero-knowledge proofs of correct encryption are only required if the client must prove its ciphertexts are well-formed, which is often unnecessary when the client learns the output.

FHE schemes are constructed from lattice-based cryptographic assumptions, specifically the Learning With Errors (LWE) and Ring-LWE problems. These problems are believed to be hard for both classical and quantum computers, making FHE-based PSI inherently post-quantum secure. This contrasts with Diffie-Hellman-based PSI protocols, which are vulnerable to Shor's algorithm. For organizations with long-term data confidentiality requirements, FHE-PSI provides a migration path to quantum-resistant private computation.

FHE-based PSI naturally extends to labeled PSI and PSI-sum without protocol redesign. The server can homomorphically compute:

• Labeled PSI: Encrypt associated labels alongside set elements, returning only labels for intersecting items
• PSI-Sum: Homomorphically sum values associated with intersecting elements, revealing only the aggregate
• PSI-Cardinality: Compute the encrypted count of matches without revealing which elements matched

These extensions leverage the composability of homomorphic operations—once data is encrypted, any computable function can be applied.

The foundational cryptographic primitive enabling FHE-based PSI. HE allows computation directly on ciphertexts, generating an encrypted result that, when decrypted, matches the result of operations performed on the plaintext. Fully Homomorphic Encryption (FHE) supports both addition and multiplication on encrypted data, enabling arbitrary circuit evaluation. Leveled HE schemes like BGV and BFV support a predetermined depth of computation, while bootstrappable schemes like CKKS and TFHE enable unbounded computation. In PSI, HE allows one party to encrypt their set and have the other party evaluate the intersection logic homomorphically without ever decrypting the inputs.