Post-Quantum PSI

Replaces classical Diffie-Hellman with problems like Learning With Errors (LWE) and Ring-LWE. These lattice problems are conjectured to be hard for quantum computers due to the lack of efficient quantum algorithms for solving the Shortest Vector Problem (SVP).

• Mechanism: Security relies on the difficulty of solving noisy linear equations.
• Advantage: Enables fully homomorphic encryption (FHE) compatibility for circuit-based PSI.

Classical OT Extension (IKNP) relies on symmetric primitives that are vulnerable to Grover's algorithm. Post-quantum PSI utilizes lattice-based OT protocols or Oblivious Linear-function Evaluation (OLE).

• Core Swap: Replaces hash-based correlation-robustness with lattice-based correlation.
• Result: Maintains the efficiency of OT Extension while achieving quantum resistance.

Some post-quantum PSI designs leverage the Syndrome Decoding problem, a hard problem in coding theory. Protocols using quasi-cyclic codes (like HQC) offer an alternative to lattices.

• Use Case: Often used in Vector OLE (VOLE) constructions for high-speed unbalanced PSI.
• Benefit: Provides a diverse cryptographic assumption to hedge against future lattice-specific breakthroughs.

Supersingular Isogeny Diffie-Hellman (SIDH) and its successors provide a drop-in replacement for ECDH in classical PSI protocols. Isogeny-based cryptography offers the smallest key sizes among post-quantum candidates.

• Application: Ideal for bandwidth-constrained PSI where minimizing communication complexity is critical.
• Note: Requires careful parameter selection to avoid known mathematical attacks on isogeny paths.

To mitigate transition risk, many implementations use hybrid key exchange combining classical ECDH with post-quantum Key Encapsulation Mechanisms (KEMs) like Kyber.

• Strategy: The intersection is secure unless both the classical discrete log problem and the lattice problem are broken simultaneously.
• Compliance: Aligns with NIST and BSI migration guidelines for critical infrastructure.

Post-quantum PSI replaces SHA-2/SHA-3 with quantum-safe commitment schemes and correlation-robust hash functions designed to resist quantum pre-image attacks.

• Technique: Utilizes Unitary Group Commitments or lattice-based trapdoor commitments.
• Impact: Prevents a quantum adversary from opening a commitment to a different value, ensuring the binding property of the protocol.

The primary mathematical foundation for post-quantum PSI. Lattice problems like Learning With Errors (LWE) and Ring-LWE are believed to be hard for both classical and quantum computers.

• Relies on the hardness of finding short vectors in high-dimensional lattices
• Enables constructions like FHE-based PSI and VOLE in the quantum setting
• Standardized by NIST (e.g., Kyber, Dilithium) for key encapsulation and signatures
• Provides worst-case to average-case reductions for security proofs

A cryptographic primitive enabling computation directly on encrypted data. In the post-quantum context, lattice-based FHE schemes like TFHE and CKKS allow PSI protocols to evaluate intersection logic without decrypting inputs.

• Enables FHE-based PSI with minimal round complexity
• Supports labeled PSI where associated data remains encrypted
• Post-quantum security relies on the Ring-LWE assumption
• Trade-off: higher computational cost vs. lower communication

A foundational two-party protocol where a sender transmits one of many messages without knowing which was selected. Post-quantum OT must replace Diffie-Hellman assumptions with lattice-based or code-based alternatives.

• Essential building block for garbled circuit and OT extension protocols
• Post-quantum instantiations use LWE-based or code-based constructions
• Enables IKNP-style extensions for efficient batch processing
• Critical for converting semi-honest protocols to malicious security

A cryptographic primitive generating long vectors of correlated oblivious linear evaluations. VOLE-based PSI protocols achieve exceptional speed by replacing expensive public-key operations with fast symmetric-key computation.

• Powers state-of-the-art protocols like Ferret OT
• Post-quantum security from learning parity with noise (LPN) or lattice assumptions
• Enables unbalanced PSI with sublinear communication in the smaller set
• Dramatically reduces computational overhead vs. traditional OT-based PSI

The strongest adversarial model guaranteeing protocol correctness even when an attacker arbitrarily deviates from the specification. Post-quantum malicious security requires quantum-extractable commitments and zero-knowledge proofs based on lattice assumptions.

• Prevents input substitution and output manipulation attacks
• Achieved through cut-and-choose techniques or authenticated garbling
• Post-quantum instantiations use SIS-based commitment schemes
• Essential for contact discovery and financial applications

A real-world PSI application allowing users to discover which contacts also use a service without revealing their entire address book. Post-quantum contact discovery must scale to hundreds of millions of users while resisting quantum adversaries.

• Typically uses asymmetric PSI where only the client learns the intersection
• Requires unbalanced PSI optimization for large server sets
• Post-quantum security critical for long-term messaging privacy
• Deployed by Signal, WhatsApp, and other encrypted messaging platforms