Linear Complexity Malicious Private Set Intersection

15 concepts8 papers1 proposal

Private Set Intersection (PSI) allows two parties, Alice and Bob, to compute the intersection of their private datasets without revealing anything about the elements outside the intersection. In an ideal world, this computation would scale linearly with the number of elements ($O(n)$). However, achieving this efficiency becomes challenging when we shift from a semi-honest model (where parties follow the protocol but try to learn extra information) to a malicious model (where parties can actively cheat, alter inputs, or deviate from the steps).

Historically, protecting against malicious behavior required heavy cryptographic machinery. For example, representing sets as high-degree polynomials and proving correct evaluation via zero-knowledge proofs often forced the computational or communication complexity to scale quadratically ($O(n^2)$) or quasi-linearly ($O(n \log^2 n)$). As Jihye Kim 0001 et al. highlight, this created a frustrating trade-off: applications either had to accept weak security guarantees or suffer severe performance bottlenecks that made large-scale deployment impossible.

The core breakthrough in modern PSI research is the realization that we can bypass these quadratic bottlenecks. By combining advanced data structures with localized cryptographic verification, recent protocols achieve true linear complexity ($O(n)$) in both computation and communication, even in the presence of actively malicious adversaries.


The Core Insight: Decoupling Elements to Avoid All-to-All Comparisons

To achieve linear complexity, a protocol must avoid comparing every element of Alice's set against every element of Bob's set. Instead, it must process each element a constant number of times.

An early intuition for how to achieve this linear scaling via algebraic properties was introduced by Myungsun Kim et al. in the semi-honest setting. Instead of using complex polynomials, the authors mapped set elements to unique prime numbers. By leveraging the fundamental theorem of arithmetic, set operations can be transformed into multiplication and divisibility checks under homomorphic encryption. Because multiplying and dividing independent prime factors bypasses the need for pairwise comparisons, the computational complexity scales strictly linearly ($O(k)$ where $k$ is the set cardinality).

To port this linear efficiency into the malicious model, however, the protocol must prevent an adversary from selectively altering inputs or intermediate states to probe the other party's set. Modern malicious-secure protocols achieve this by combining independent element processing with lightweight verification structures.


Mechanism 1: Oblivious Functions and Hash-Based Alignment

One of the most prominent ways to achieve linear-time malicious PSI is through Oblivious Pseudorandom Functions (OPRFs). An OPRF allows Bob to evaluate a pseudorandom function on his inputs using a secret key held by Alice, without Alice learning Bob's inputs or Bob learning the key.

Alice (Key: K)                                Bob (Element: x)
      |                                              |
      |========== Blinded Element H(x)^r ===========>|
      |                                              |
      |<========= Signed Element (H(x)^r)^K =========|
      |                                              |
      |                                     Unblinds to get OPRF(x)

Carmit Hazay et al. demonstrated that by pairing OPRFs with perfectly hiding commitments, parties can securely evaluate set elements in constant rounds and linear time. The OPRF maps each element to a random-looking token. If Alice and Bob share an element, their tokens match; if they do not, the tokens look completely random. Because each element is passed through the OPRF independently, the computation scales linearly with the size of the input sets, and the commitments ensure that a malicious party cannot change their inputs mid-protocol.

To make these comparisons efficient inside secure circuits (like Garbled Circuits), researchers turn to advanced hashing techniques:

  • Cuckoo Hashing: Benny Pinkas et al. utilized Cuckoo hashing to map elements into highly structured tables with minimal bin sizes. By organizing data so that elements can only reside in a tiny, predictable number of positions, the underlying secure circuit only needs to perform a near-linear number of comparisons, yielding massive practical speedups in runtime and circuit size.
  • Oblivious Key-Value Stores (OKVS): Rather than just hashing into bins, sets can be encoded into compact algebraic structures. Zhengtao Jiang et al. designed a lightweight OKVS structure (called 3H-GCG) that allows parties to embed their datasets into sparse matrices. This approach minimizes storage overhead and accelerates the oblivious state transitions required for both semi-honest and malicious settings.

Mechanism 2: Homomorphic Encryption with Localized Proofs

Another major paradigm relies on Homomorphic Encryption (HE), where computations are performed directly on encrypted data. In an outsourced or cloud-based setting, this allows a third party to do the heavy lifting without seeing the underlying data.

Florian Kerschbaum demonstrated that combining homomorphic encryption with Bloom filters enables outsourced PSI with optimal linear complexity. The Bloom filter compresses the set into a linear bit-array, and the homomorphic layer allows the cloud provider to compute the intersection while completely hiding the client's total set size and preventing malicious manipulation by the server.

Alice (Set A) --------> Encrypted Bloom Filter -------\
                                                       v
                                               [ Cloud Provider ] ---> Encrypted Intersection
                                                       ^
Bob (Set B)   --------> Encrypted Bloom Filter -------/

When operating in a direct two-party setting without a cloud provider, malicious security requires ensuring that the party performing the homomorphic operations doesn't inject malformed ciphertexts. Xin Liu et al. solved this by pairing the Paillier cryptosystem with cut-and-choose mechanisms and zero-knowledge proofs. Instead of validating the global consistency of a massive polynomial (which causes a quadratic explosion), the protocol uses localized proofs to verify that each step of the linear homomorphic evaluation was executed honestly. This keeps the total computational complexity bound tightly to $O(n)$ while requiring only five communication rounds.


Maximizing Communication Efficiency

While achieving $O(n)$ computational complexity solves the CPU bottleneck, the sheer volume of data transmitted over the network remains a challenge when scaling to millions of items, especially in labeled PSI (where elements are tied to data payloads, like usernames paired with phone numbers).

To mitigate this, Alexander Bienstock et al. introduced a technique known as oblivious ciphertext compression. When executing batch private information retrieval or labeled PSI, protocols often generate sparse vectors containing many encrypted zeros or dummy values. The authors developed a method to compress these ciphertexts without revealing which slots contain actual data or what the data is. This optimization reduces communication overhead by 65% to 88% compared to previous state-of-the-art methods, ensuring that linear-complexity malicious PSI remains highly practical over real-world networks.

Key Foundational Work

Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model (2010) — contributed 5 concept elements to this direction.
Mutual Private Set Intersection with Linear Complexity (2011) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_complexity_malicious_apsi_7828df0c,
  title = {linear complexity malicious APSI},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-complexity-malicious-apsi/rdr_7828df0cf3ae4133bb29e0fe6316121c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_linear_complexity_malicious_apsi_7828df0c_v1,
  title = {linear complexity malicious APSI},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-complexity-malicious-apsi/rdr_7828df0cf3ae4133bb29e0fe6316121c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake