PSI-Sum

Unlike standard PSI, PSI-Sum reveals only the aggregate sum of values linked to intersecting elements. Neither party learns which specific items were in the intersection, only the total. This is critical for applications like private revenue attribution where knowing how much overlap exists matters more than which customers overlap.

• Protects individual intersection membership
• Reveals only aggregate statistics
• Prevents re-identification via set membership

PSI-Sum builds on Labeled PSI primitives, where one party holds set elements with associated integer values (labels). The protocol computes the intersection and sums the labels corresponding to matched elements. The label holder learns nothing; the querier learns only the sum.

• Extends Labeled PSI with summation logic
• One party provides (item, value) pairs
• Other party provides query items

Many PSI-Sum constructions leverage additively homomorphic encryption (e.g., Paillier) to perform summation directly on ciphertexts. The server encrypts its values, the client homomorphically adds only those corresponding to matched elements, and the server decrypts the final sum without learning which elements contributed.

• Enables computation on encrypted values
• Server never sees client's query set
• Client never sees server's individual values

Advanced PSI-Sum protocols support threshold conditions, where the sum is revealed only if the intersection size exceeds a minimum cardinality. This prevents inference attacks where a sum over a single element would expose an individual's value.

• Protects against singleton intersection attacks
• Enforces minimum group size k
• Combines cardinality testing with summation

PSI-Sum enables privacy-preserving business analytics across organizations that cannot share raw data. Common use cases include:

• Ad conversion measurement: Summing purchase values from overlapping users without revealing who converted
• Cross-bank fraud detection: Aggregating suspicious transaction values across institutions
• Healthcare cohort analysis: Summing treatment costs for overlapping patient populations

PSI-Sum protocols inherit the security model of their underlying PSI construction, typically achieving semi-honest security with efficient implementations. Maliciously secure variants exist using zero-knowledge proofs to verify correct summation, though at higher computational cost.

• Semi-honest: Standard for most deployments
• Malicious: Verifiable computation of the sum
• No information leakage beyond the aggregate

The direct predecessor to PSI-Sum. In Labeled PSI, one party's set elements have associated data labels, and the other party learns only the labels corresponding to the intersection. PSI-Sum extends this by aggregating those labels (e.g., summing values) rather than revealing them individually.

• Key difference: PSI-Sum reveals only the aggregate, not individual labels
• Use case: Private contact discovery with associated metadata
• Protocols: Often built on OPRF or OT-based constructions

A privacy-preserving variant that reveals only the size of the intersection, not the elements themselves. PSI-Sum can be seen as a generalization where the aggregate function is COUNT.

• Reveals: |X ∩ Y| only
• PSI-Sum relationship: PSI-Sum with all values set to 1 is equivalent to PSI Cardinality
• Applications: Measuring audience overlap without exposing identities
• Efficiency: Often more communication-efficient than full PSI

Cryptographic methods that allow a central server to compute the sum of model updates from multiple clients without inspecting individual contributions. PSI-Sum solves a related problem for set intersection rather than gradient aggregation.

• Federated learning context: Google's Secure Aggregation for Gboard
• Techniques: Secret sharing, pairwise masking
• PSI-Sum connection: Both compute sums over private inputs without revealing individual values
• Threat model: Typically semi-honest server with curious-but-honest clients

A form of encryption that permits computation directly on ciphertexts. PSI-Sum protocols can leverage HE to compute the sum of intersecting values without decrypting individual contributions.

• Additive HE: Particularly relevant for sum computation (e.g., Paillier)
• Fully Homomorphic Encryption (FHE): Enables arbitrary computation but with higher overhead
• PSI-Sum integration: Encrypt values, compute sum homomorphically, decrypt only the aggregate
• Performance trade-off: Higher computation cost but minimal round complexity

A protocol where a client learns the output of a PRF keyed by a server on the client's input, without the server learning the input or the client learning the key. OPRFs are a core building block for many efficient PSI and PSI-Sum constructions.

• PSI-Sum usage: Encode values as OPRF outputs, then sum matching results
• Security: Prevents the server from learning client set elements
• Efficiency: Can be built from OT extension for high throughput
• Variants: Verifiable OPRFs add proof of correct evaluation

An extension of private set intersection from two to multiple parties. Multiparty PSI-Sum allows a group to compute the sum of values associated with the intersection of their collective datasets.

• Complexity: Grows with the number of parties
• Approaches: Star topology (central server) or peer-to-peer
• PSI-Sum extension: Each party contributes values; only the aggregate sum over the global intersection is revealed
• Applications: Cross-institutional aggregate analytics, supply chain visibility