Hash-Based Post-Quantum-Safe Proofs of Set Intersection

A transparent, hash-only construction that proves two parties' committed sets intersect — without trusting either party, without a trapdoor setup, and without exposing either set.

What

Two parties commit to their sets once. A verifier later checks whether the committed sets share a member — or that they don't — using only SHA-256-style hash operations against the public commitments. No interactive ceremony. No trusted party. No reliance on discrete-log or pairing assumptions that fall to a quantum adversary.

The construction is built on Bezout coprime-cofactors certification over a hash-based polynomial substrate. The artifact is small, the verification is fast, and the security argument reduces cleanly to the underlying hash's collision resistance.

Why this matters

Existing intersection proofs lean on cryptographic assumptions that don't survive the post-quantum transition. Trusted-setup constructions require a ceremony and a long-lived secret — neither is acceptable for federal records that must hold up under a Q-day adversary and a 7-year retention floor.

• Quantum-safe — CNSA 2.0 / NSM-10 alignment; FIPS 180-4 SHA-256 substrate throughout.
• Transparent — no trusted setup, no toxic waste, no shared secret between prover and verifier.
• Composable — fits inside existing FIPS signature stacks (Ed25519 cloud-KMS-HSM classical + ML-DSA-65 FIPS 204 post-quantum) without modification.
• Substrate-pluggable — the hash function is a parameter, not a hard dependency. The construction migrates with the substrate.

Where it ships

• AML transaction screening — banks prove a watchlist intersects (or doesn't) a transaction stream without exposing either side.
• SBOM provenance — manufacturers prove their bill of materials intersects a federal known-good or known-bad list without disclosing the BoM.
• DSCSA pharma track-and-trace — distributors prove batch lots cross-anchor against FDA records.
• Federal coalition audit — partner nations prove custody records intersect with US records without disclosing the partner ledger.
• Federal procurement — vendor capabilities cross-verified against requirements without either party leaking their full set.

Status

Production reference implementation: hyfstele-hash::pq_set (Rust). 17-page formal specification on file with the USPTO. Patent pending — US Provisional Application No. 64/069,537, filed May 19, 2026.