Circuit PSI

The core two-party computation engine underlying Circuit PSI. A Boolean circuit representing the intersection function is 'garbled' by one party and evaluated by the other.

• Generator encrypts the circuit gates using symmetric keys.
• Evaluator computes the circuit using oblivious transfer to obtain input keys.
• Result: The evaluator learns the intersection output without either party revealing their raw set elements.
• Enables arbitrary logic beyond simple equality checks, such as threshold-based or fuzzy matching.

A foundational protocol that acts as the input-wire gateway for garbled circuits. In Circuit PSI, OT allows the evaluator to securely select the cryptographic keys corresponding to their private input bits.

• 1-out-of-2 OT: The sender provides two messages; the receiver gets one without the sender knowing which.
• Role in PSI: Prevents the circuit generator from learning the evaluator's set elements during the garbled circuit evaluation.
• Modern protocols use OT Extension to bootstrap millions of OTs from a few base operations.

A powerful primitive for generating correlated randomness at blazing speed. VOLE-based Circuit PSI protocols represent the state-of-the-art in low-communication private set intersection.

• Mechanism: Two parties generate a long vector of values where each element satisfies a linear relationship known only to the sender.
• Advantage: Dramatically reduces the online communication overhead compared to traditional OT-based garbled circuits.
• Example: The Ferret OT protocol leverages VOLE to achieve over 10 million OTs per second on commodity hardware.

A hashing scheme that optimizes how set elements are mapped into the circuit's data structure. It is critical for reducing the size of the Boolean circuit in Circuit PSI.

• Structure: Uses multiple hash functions to place elements into bins, relocating existing items on collision.
• PSI Optimization: Ensures each bin contains at most one element, allowing the circuit to perform a simple equality check rather than a complex set-membership test.
• Result: Drastically reduces the number of non-XOR gates, which are the expensive operations in a garbled circuit.

The strongest adversarial model for Circuit PSI, guaranteeing correctness and privacy even if one party actively deviates from the protocol.

• Threat Model: An adversary can send malformed messages or abort the protocol arbitrarily.
• Circuit PSI Overhead: Achieving malicious security requires adding cut-and-choose checks or authenticated garbling to the circuit, increasing computational cost by 3-10x compared to semi-honest variants.
• Use Case: Essential for high-value financial reconciliation or cross-organizational healthcare analytics where participants may have conflicting incentives.

A protocol variant where only one party (typically the client) learns the intersection result. Circuit PSI naturally supports this output configuration.

• Mechanism: The circuit is designed so the final output wires are only delivered to the designated receiver.
• Contact Discovery: The canonical application. A messaging app user learns which of their contacts are registered without revealing their entire address book to the server.
• Efficiency: Asymmetric Circuit PSI can be optimized by placing the larger set on the server side, which acts as the circuit generator.