Distance-Aware OT with Application to Fuzzy PSI
summary
Presents a modular, symmetric-key framework that reduces semi-honest fuzzy PSI to a new primitive distance-aware OT and implements it with shared one-out-of-T OTs, spatial hashing, a sparse-matching OT-extension step and OKVS encoding. Constructions handle Chebyshev, Manhattan and 2D Euclidean norms over small domains and yield practical costs (about 30 seconds for 2^16 items in 2D versus prior ~10 minutes) but leak set sizes and neighborhood density and scale exponentially in dimension. sparse matching and OKVS are the concrete building blocks used.
AI-written summary · about
chapters (14)
- 0:00Fuzzy private set intersection
- 1:53What is fuzzy private set intersection
- 4:53PSI versus fuzzy PSI complexity
- 6:22Three-stage fuzzy PSI framework
- 9:18Distance-aware oblivious transfer
- 13:20Chebyshev and Manhattan norms
- 15:35Sparse matching primitive
- 18:33Sparse matching from OT
- 19:59Spatial hashing for matching
- 22:31Truncated values for matching
- 24:41Final fuzzy PSI protocol
- 27:17Leakage and framework extensions
- 28:45Open problems and future work
- 29:05Q&A
related talks
21mA Framework for Efficient Mixed-Protocol Secure Two-Party Computation
24mLocally Differentially Private Protocols for Frequency Estimation
22mScalable Zero-Knowledge Protocols From Vector-OLE
44mIOP based Zero-Knowledge Proofs
28mProving Obliviousness of Probabilistic Algorithms with Formal Verification
01h 08mTutorial: Security
17mThe Simplest Oblivious Transfer Protocol
21mDecision and Complexity of Dolev-Yao Hyperproperties