pith. sign in

arxiv: 2604.14909 · v1 · submitted 2026-04-16 · 💻 cs.CR

Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

Xinpeng Yang , Meng Hao , Chenkai Weng , Robert H. Deng , Yonggang Wen , Tianwei Zhang This is my paper

Pith reviewed 2026-05-10 11:07 UTC · model grok-4.3

classification 💻 cs.CR
keywords fuzzy private set intersectionoblivious programmable PRFsecret sharingLp distanceprivate set intersectionsymmetric-key cryptographysecure computation
0
0 comments X

The pith

Fuzzy private set intersection for Lp distances achieves linear complexity using an oblivious programmable PRF with secret-shared outputs and a logarithmic prefix technique.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops protocols for fuzzy private set intersection where two parties compute the items from one set that lie within a distance threshold of the other set without revealing non-matching data. It replaces expensive homomorphic encryption with cheaper symmetric-key operations by introducing an oblivious programmable PRF whose outputs are secret-shared between the parties. The resulting protocols have communication and computation costs that grow linearly with set sizes, element dimension, and threshold value. A prefix technique is added to make the threshold dependence logarithmic rather than linear, which helps when the allowed distance is large. Experiments show these protocols run 9 to 145 times faster and use 3 to 19 times less communication than the best prior constructions.

Core claim

We propose efficient FPSI protocols for Lp distance metrics primarily leveraging significantly cheaper symmetric-key operations. Our protocols achieve linear communication and computation complexity in the set sizes m,n, the dimension d, and the distance threshold δ. Our core building block is an oblivious programmable PRF with secret-shared outputs, which may be of independent interest. Furthermore, we incorporate a prefix technique that reduces the dependence on the distance threshold δ to logarithmic, which is particularly suitable for large δ. We implement our FPSI protocols and compare them with state-of-the-art constructions, demonstrating speedups of 12~145× in running time and a 3~8×

What carries the argument

An oblivious programmable PRF with secret-shared outputs, which lets one party program the function obliviously while both parties receive additive shares of the PRF values so that only matching elements under the distance threshold can be identified without extra leakage.

Load-bearing premise

The oblivious programmable PRF with secret-shared outputs can be built efficiently and proven secure under standard assumptions, and the prefix technique does not introduce new leakage.

What would settle it

A re-implementation of the protocols on the same benchmarks that fails to show at least a 9× speedup in running time or a 3× reduction in communication compared to the cited prior works would falsify the efficiency claims.

Figures

Figures reproduced from arXiv: 2604.14909 by Chenkai Weng, Meng Hao, Robert H. Deng, Tianwei Zhang, Xinpeng Yang, Yonggang Wen.

Figure 1
Figure 1. Figure 1: Construction of so-OPPRF from so-OPRF. pair (qj , wi) sharing the same ID and returns qj to the receiver if and only if dist(qj , wi) ≤ δ. In this work, we follow this fuzzy PSI paradigm, but introduce new techniques to realize the fuzzy mapping and fuzzy matching phases with linear complexity in the set size and dimension, primarily using lightweight symmetric-key operations1 . 2.2. OPPRF with Shared Outp… view at source ↗
Figure 2
Figure 2. Figure 2: Construction of fuzzy mapping from so-OPPRF [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: Functionality of fuzzy PSI. 3.3. Oblivious Key-Value Store An oblivious key-value store (OKVS) [44] is a data structure consisting of two algorithms: Encode takes as input a set of key-value pairs and outputs a data structure, and Decode takes as input a key and the data structure and outputs a value. The obliviousness implies that if the OKVS encodes random values, the data structure is independent of the… view at source ↗
Figure 5
Figure 5. Figure 5: Functionality of oblivious PRF with secret-shared [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 8
Figure 8. Figure 8: Functionality of oblivious programmable PRF with [PITH_FULL_IMAGE:figures/full_fig_p008_8.png] view at source ↗
Figure 10
Figure 10. Figure 10: Procedure of local mapping and its variant with [PITH_FULL_IMAGE:figures/full_fig_p008_10.png] view at source ↗
Figure 12
Figure 12. Figure 12: Protocol of fuzzy PSI for L∞ distance. dependent of any other assignments. Then, we have that IDwi := PRF(k, ListR[ki∥wi,ki ] + . . .). According to the functionality of si-OPRF, IDwi is computationally indis￾tinguishable from a uniformly random value. Therefore, a union bound shows that the probability of that there exists i, i′ ∈ [n] such that i ̸= i ′ and IDwi = IDwi ′ ∈ F is at most n 2/|F|. With |F| … view at source ↗
Figure 12
Figure 12. Figure 12: We show the protocol’s correctness as follows. [PITH_FULL_IMAGE:figures/full_fig_p010_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Protocol of fuzzy PSI for Lp distance. protocol includes a Boolean-to-arithmetic conversion (B2A) protocol, since the outputs of our so-OPPRF protocol reside in a binary field F2 ℓ that does not support computing arithmetic operations of the Lp distance. B2A converts the outputs of so-OPPRF into arithmetic shares, which are suitable for subsequent computation. In addition, unlike the private equality test… view at source ↗
Figure 14
Figure 14. Figure 14: Protocol of random equality-conditional selec [PITH_FULL_IMAGE:figures/full_fig_p011_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Protocol of fuzzy mapping with prefix optimiza [PITH_FULL_IMAGE:figures/full_fig_p011_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Protocol of fuzzy PSI with prefix optimization [PITH_FULL_IMAGE:figures/full_fig_p012_16.png] view at source ↗
Figure 15
Figure 15. Figure 15: The main difference over our non-prefix fuzzy [PITH_FULL_IMAGE:figures/full_fig_p012_15.png] view at source ↗
Figure 17
Figure 17. Figure 17: Functionality of MUX. Functionality FssPEQT Parameters: Sender S and receiver R. Protocol: 1) Wait for input x0 from S and x1 from R. 2) Select r0 randomly, and set r1 = 1 − r0 if x0 = x1 otherwise set r1 = −r0. 3) Output r0 to R and r1 to S [PITH_FULL_IMAGE:figures/full_fig_p017_17.png] view at source ↗
Figure 19
Figure 19. Figure 19: Protocol for computing list for p = 1 and p = 2. The protocol can extend to arbitrary p. Protocol ΠgetDistancep Parameters: Sender inputs {s S h }h∈[µ] ∈ F µ×p , q ∈ U, σ ∈ {0, 1}. Receiver inputs {s R h }h∈[µ] ∈ F µ×p . Functionality FMult. Denote µ = log δ. Protocol: 1) S computes {qh}h∈[µ] := AllPrefix(q, µ). 2) For h ∈ [µ], S computes eh := |q − UpBound(qh)| if σ = 0 and eh = |q − LowBound(qh)| otherw… view at source ↗
Figure 20
Figure 20. Figure 20: Protocol for computing distance for p = 1 and p = 2. The protocol can extend to arbitrary p. We show that the output by SimS is indistinguishable from the real protocol. According to the security property of fuzzy mapping in Theorem 2, the simulated view of SimFMap S is indistinguishable from the real execution. Besides, the only difference is {r S j,k}j∈[m],k∈[d] . They are random secret shares in the re… view at source ↗
Figure 21
Figure 21. Figure 21: Protocol of fuzzy PSI with prefix optimization [PITH_FULL_IMAGE:figures/full_fig_p018_21.png] view at source ↗
read the original abstract

Private set intersection (PSI) enables a sender holding a set $Q$ of size $m$ and a receiver holding a set $W$ of size $n$ to securely compute the intersection $Q \cap W$. Fuzzy PSI (FPSI) is a PSI variant where the receiver learns the items $q \in Q$ for which there exists some $w \in W$ satisfying $\mathsf{dist}(q, w) \le \delta$ under a given distance metric. Although several FPSI works are proposed for $L_{p}$ distance metrics with $p \in [1, \infty]$, they either heavily rely on expensive homomorphic encryptions, or incur undesirable complexity, e.g., exponential to the element dimension, both of which lead to poor practical efficiency. In this work, we propose efficient FPSI protocols for $L_{p \in [1, \infty]}$ distance metrics, primarily leveraging significantly cheaper symmetric-key operations. Our protocols achieve linear communication and computation complexity in the set sizes $m,n$, the dimension $d$, and the distance threshold $\delta$. Our core building block is an oblivious programmable PRF with secret-shared outputs, which may be of independent interest. Furthermore, we incorporate a prefix technique that reduces the dependence on the distance threshold $\delta$ to logarithmic, which is particularly suitable for large $\delta$. We implement our FPSI protocols and compare them with state-of-the-art constructions. Experimental results demonstrate that our protocols consistently and significantly outperform existing works across all settings. Specifically, our protocols achieve a speedup of $12{\sim}145\times$ in running time and a reduction of $3{\sim}8\times$ in communication cost compared to Gao et al.~(ASIACRYPT'24) and a speedup of $9{\sim}80\times$ in running time and a reduction of $5{\sim}19\times$ in communication cost compared to Dang et al.~(CCS'25).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes efficient fuzzy private set intersection (FPSI) protocols for L_p distance metrics (p ∈ [1, ∞]) that achieve linear communication and computation complexity in the set sizes m, n, dimension d, and logarithmic dependence on the distance threshold δ. The core innovation is an oblivious programmable PRF with secret-shared outputs, augmented by a prefix technique; the protocols rely primarily on symmetric-key operations rather than homomorphic encryption. Implementation results claim speedups of 12–145× and communication reductions of 3–8× versus Gao et al. (ASIACRYPT’24), and 9–80× speedups with 5–19× communication savings versus Dang et al. (CCS’25).

Significance. If the security reductions for the new OPRF primitive and prefix technique hold under standard assumptions, the work would constitute a meaningful practical advance in FPSI by replacing expensive public-key operations with cheaper symmetric primitives while retaining linear scaling. The experimental comparisons supply concrete evidence of improvement and the new primitive may have independent utility; these are clear strengths.

major comments (2)
  1. [§4] §4 (OPRF construction): the security definition and reduction for the oblivious programmable PRF with secret-shared outputs must explicitly show that sharing the outputs introduces no additional leakage beyond the intended functionality and preserves both obliviousness and programmability; this is load-bearing for the end-to-end FPSI security claim.
  2. [§5.2] §5.2 (prefix technique): the argument that the prefix method reduces δ dependence to O(log δ) while preserving security for arbitrary L_p metrics must rule out hidden exponential factors or p-specific failures; the current sketch leaves open whether the reduction is metric-independent.
minor comments (2)
  1. [Table 1] Table 1 and experimental setup: clarify the exact parameter ranges (m, n, d, δ, p) over which the 12–145× and 9–80× speedups were measured, and whether they include all overheads such as setup.
  2. [§2] Notation: the distinction between the receiver’s set W and the sender’s set Q is clear in the abstract but should be restated at the start of the protocol description for readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The two major comments identify areas where the security arguments can be strengthened with additional detail. We will incorporate expanded proofs and lemmas in the revised manuscript to address both points explicitly.

read point-by-point responses

  1. Referee: [§4] §4 (OPRF construction): the security definition and reduction for the oblivious programmable PRF with secret-shared outputs must explicitly show that sharing the outputs introduces no additional leakage beyond the intended functionality and preserves both obliviousness and programmability; this is load-bearing for the end-to-end FPSI security claim.

    Authors: We agree that greater explicitness is warranted. In the revised manuscript we will augment Section 4 with a formal security definition for the secret-shared OPRF that models output sharing via additive secret sharing over a finite field. We will prove via a sequence of hybrids that the sharing introduces no leakage beyond the ideal functionality: each share is uniformly random and independent of the input given the output, so the receiver’s view is simulatable. The reduction will establish that both obliviousness (the receiver learns nothing about unprogrammed points) and programmability (the sender can set function values without revealing the key) are preserved, reducing directly to the security of the underlying OPRF under standard assumptions (random-oracle or PRF security). This will be stated as a standalone theorem before the FPSI composition. revision: yes

  2. Referee: [§5.2] §5.2 (prefix technique): the argument that the prefix method reduces δ dependence to O(log δ) while preserving security for arbitrary L_p metrics must rule out hidden exponential factors or p-specific failures; the current sketch leaves open whether the reduction is metric-independent.

    Authors: We thank the referee for highlighting the need for a tighter argument. The prefix technique is applied to the binary representation of the computed distance value and is therefore independent of the concrete L_p metric; the metric only affects the black-box distance oracle. In the revision we will add a formal lemma in Section 5.2 showing that the technique incurs exactly O(log δ) OPRF invocations with no hidden exponential factors in δ or d. The security reduction will be metric-agnostic: the simulator uses the ideal FPSI functionality to answer prefix queries, and the view is indistinguishable regardless of p because only the comparison outcome (distance ≤ δ) is revealed. We will explicitly rule out p-specific failures by noting that the reduction never relies on properties unique to any particular p. revision: yes

Circularity Check

0 steps flagged

No significant circularity; construction builds on standard primitives with independent security claims.

full rationale

The paper introduces an oblivious programmable PRF with secret-shared outputs as a core building block (positioned as potentially of independent interest) and a prefix technique for logarithmic dependence on δ. These are presented as new constructions under standard assumptions, with linear complexity claims and empirical speedups derived from implementation comparisons rather than by definition or self-citation reduction. No equations or steps reduce the target results to fitted inputs or prior self-citations by construction. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on the abstract, the work introduces a new OPRF variant but does not postulate new entities or free parameters; it builds on existing crypto primitives. The central claim rests on the existence and efficiency of the secret-shared OPRF and the correctness of the prefix technique.

axioms (1)
  • standard math The security of the underlying OPRF and secret sharing primitives holds under standard assumptions.
    Typical for cryptographic protocol papers; no specific new axioms mentioned.

pith-pipeline@v0.9.0 · 5679 in / 1384 out tokens · 59475 ms · 2026-05-10T11:07:37.960848+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

79 extracted references · 79 canonical work pages

  1. [1]

    A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party,

    C. Meadows, “A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party,” in 1986 IEEE Symposium on Security and Privacy. IEEE, 1986, pp. 134–134

    work page 1986

  2. [2]

    Efficient private matching and set intersection,

    M. J. Freedman, K. Nissim, and B. Pinkas, “Efficient private matching and set intersection,” inInternational conference on the theory and applications of cryptographic techniques. Springer, 2004, pp. 1–19

    work page 2004

  3. [3]

    When private set intersection meets big data: an efficient and scalable protocol,

    C. Dong, L. Chen, and Z. Wen, “When private set intersection meets big data: an efficient and scalable protocol,” inProceedings of the 2013 ACM SIGSAC conference on Computer & communications security, 2013, pp. 789–800

    work page 2013

  4. [4]

    Phasing: Private set intersection using permutation-based hashing,

    B. Pinkas, T. Schneider, G. Segev, and M. Zohner, “Phasing: Private set intersection using permutation-based hashing,” in24th USENIX Security Symposium (USENIX Security 15), 2015, pp. 515–530

    work page 2015

  5. [5]

    Psi from paxos: Fast, malicious private set intersection,

    B. Pinkas, M. Rosulek, N. Trieu, and A. Yanai, “Psi from paxos: Fast, malicious private set intersection,” inAnnual International Confer- ence on the Theory and Applications of Cryptographic Techniques. Springer, 2020, pp. 739–767

    work page 2020

  6. [6]

    Blazing fast psi from improved okvs and subfield vole,

    S. Raghuraman and P. Rindal, “Blazing fast psi from improved okvs and subfield vole,” inProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2022, pp. 2505–2517

    work page 2022

  7. [7]

    Unbalanced circuit-psi from oblivious key-value retrieval,

    M. Hao, W. Liu, L. Peng, H. Li, C. Zhang, H. Chen, and T. Zhang, “Unbalanced circuit-psi from oblivious key-value retrieval,” in33rd USENIX Security Symposium (USENIX Security 24), 2024, pp. 6435– 6451

    work page 2024

  8. [8]

    Better password protections in chrome - how it works,

    Google, “Better password protections in chrome - how it works,” 2019, last accessed 11 November

    work page 2019

  9. [9]

    Available: https://security.googleblog.com/2019/12/ better-password-protections-in-chrome.html

    [Online]. Available: https://security.googleblog.com/2019/12/ better-password-protections-in-chrome.html

    work page 2019

  10. [10]

    Efficient and pri- vate set intersection of human genomes,

    L. Shen, X. Chen, D. Wang, B. Fang, and Y . Dong, “Efficient and pri- vate set intersection of human genomes,” in2018 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). IEEE, 2018, pp. 761–764

    work page 2018

  11. [11]

    Fuzzy labeled private set intersection with applications to private real-time biometric search,

    E. Uzun, S. P. Chung, V . Kolesnikov, A. Boldyreva, and W. Lee, “Fuzzy labeled private set intersection with applications to private real-time biometric search,” in30th USENIX Security Symposium (USENIX Security 21), 2021, pp. 911–928

    work page 2021

  12. [12]

    Structure-aware private set intersection, with applications to fuzzy matching,

    G. Garimella, M. Rosulek, and J. Singh, “Structure-aware private set intersection, with applications to fuzzy matching,” inAnnual International Cryptology Conference. Springer, 2022, pp. 323–352

    work page 2022

  13. [13]

    Computation efficient structure- aware psi from incremental function secret sharing,

    G. Garimella, B. Goff, and P. Miao, “Computation efficient structure- aware psi from incremental function secret sharing,” inAnnual Inter- national Cryptology Conference. Springer, 2024, pp. 309–345

    work page 2024

  14. [14]

    Fuzzy private set intersection with large hyperballs,

    A. van Baarsen and S. Pu, “Fuzzy private set intersection with large hyperballs,” inAnnual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2024, pp. 340– 369

    work page 2024

  15. [15]

    Efficient fuzzy private set intersection from fuzzy mapping,

    Y . Gao, L. Qi, X. Liu, Y . Luo, and L. Wang, “Efficient fuzzy private set intersection from fuzzy mapping,” inInternational Conference on the Theory and Application of Cryptology and Information Security. Springer, 2024, pp. 36–68

    work page 2024

  16. [16]

    Fast fuzzy psi from symmetric-key techniques,

    C. Zhang, Y . Chen, Y . Cao, Y . Bai, S. Li, J. Lin, A. Wang, and X. Wang, “Fast fuzzy psi from symmetric-key techniques,”Cryptol- ogy ePrint Archive, 2025

    work page 2025

  17. [17]

    Efficient fuzzy psi based on prefix representation,

    C. Dang, X. Zhou, and B. Liang, “Efficient fuzzy psi based on prefix representation,” inProceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, 2025, pp. 2204–2218

    work page 2025

  18. [18]

    Distance- aware ot with application to fuzzy psi,

    L. Piske, J. Singh, N. Trieu, V . Kolesnikov, and V . Zikas, “Distance- aware ot with application to fuzzy psi,” inProceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Secu- rity, 2025, pp. 4679–4691

    work page 2025

  19. [19]

    Fuzzy private set intersection from vole,

    A. van Baarsen and S. Pu, “Fuzzy private set intersection from vole,” inInternational Conference on the Theory and Application of Cryptology and Information Security. Springer, 2025, pp. 327–360

    work page 2025

  20. [20]

    Fuzzy psi via oblivious protocol routing,

    D. Richardson, M. Rosulek, and J. Xu, “Fuzzy psi via oblivious protocol routing,”Cryptology ePrint Archive, 2024

    work page 2024

  21. [21]

    New framework for structure-aware psi from distributed function secret sharing,

    D. Bui, G. Garimella, P. Miao, and P. V . L. Pham, “New framework for structure-aware psi from distributed function secret sharing,” in International Conference on the Theory and Application of Cryptol- ogy and Information Security. Springer, 2025, pp. 294–326

    work page 2025

  22. [22]

    Distance-aware private set intersection,

    A. Chakraborti, G. Fanti, and M. K. Reiter, “Distance-aware private set intersection,” in32nd USENIX Security Symposium (USENIX Security 23), 2023, pp. 319–336

    work page 2023

  23. [23]

    Fuzzy private matching,

    L. Chmielewski and J.-H. Hoepman, “Fuzzy private matching,” in 2008 Third International Conference on Availability, Reliability and Security. IEEE, 2008, pp. 327–334

    work page 2008

  24. [24]

    Efficient fuzzy match- ing and intersection on private datasets,

    Q. Ye, R. Steinfeld, J. Pieprzyk, and H. Wang, “Efficient fuzzy match- ing and intersection on private datasets,” inInternational Conference on Information Security and Cryptology. Springer, 2009, pp. 211– 228

    work page 2009

  25. [25]

    Polylogarithmic private approximations and efficient matching,

    P. Indyk and D. Woodruff, “Polylogarithmic private approximations and efficient matching,” inTheory of Cryptography Conference. Springer, 2006, pp. 245–264

    work page 2006

  26. [26]

    Assumption-free fuzzy psi via predicate encryption,

    E.-O. Blass and G. Noubir, “Assumption-free fuzzy psi via predicate encryption,”Cryptology ePrint Archive, 2025

    work page 2025

  27. [27]

    Efficient concurrent covert computation of string equality and set intersection,

    C. Cho, D. Dachman-Soled, and S. Jarecki, “Efficient concurrent covert computation of string equality and set intersection,” inCryp- tographers’ Track at the RSA Conference. Springer, 2016, pp. 164– 179

    work page 2016

  28. [28]

    Approximate psi with near-linear communication,

    W. Chongchitmate, S. Lu, and R. Ostrovsky, “Approximate psi with near-linear communication,”Cryptology ePrint Archive, 2024

    work page 2024

  29. [29]

    Robust record link- age blocking using suffix arrays and bloom filters,

    T. De Vries, H. Ke, S. Chawla, and P. Christen, “Robust record link- age blocking using suffix arrays and bloom filters,”ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 5, no. 2, pp. 1–27, 2011

    work page 2011

  30. [30]

    Composite bloom filters for secure record linkage,

    E. A. Durham, M. Kantarcioglu, Y . Xue, C. Toth, M. Kuzu, and B. Malin, “Composite bloom filters for secure record linkage,”IEEE transactions on knowledge and data engineering, vol. 26, no. 12, pp. 2956–2968, 2013

    work page 2013

  31. [31]

    Composing differential privacy and secure computation: A case study on scaling private record linkage,

    X. He, A. Machanavajjhala, C. Flynn, and D. Srivastava, “Composing differential privacy and secure computation: A case study on scaling private record linkage,” inProceedings of the 2017 ACM SIGSAC conference on computer and communications security, 2017, pp. 1389–1406

    work page 2017

  32. [32]

    Private record matching using differential privacy,

    A. Inan, M. Kantarcioglu, G. Ghinita, and E. Bertino, “Private record matching using differential privacy,” inProceedings of the 13th International Conference on Extending Database Technology, 2010, pp. 123–134

    work page 2010

  33. [33]

    Sfour: a protocol for cryptographi- cally secure record linkage at scale,

    B. Khurram and F. Kerschbaum, “Sfour: a protocol for cryptographi- cally secure record linkage at scale,” in2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 2020, pp. 277–288

    work page 2020

  34. [34]

    Cryptographically secure private record linkage using locality-sensitive hashing,

    R. Wei and F. Kerschbaum, “Cryptographically secure private record linkage using locality-sensitive hashing,”Proceedings of the VLDB Endowment, vol. 17, no. 2, pp. 79–91, 2023

    work page 2023

  35. [35]

    Mainzelliste se- cureepilinker (mainsel): privacy-preserving record linkage using se- cure multi-party computation,

    S. Stammler, T. Kussel, P. Schoppmann, F. Stampe, G. Tremper, S. Katzenbeisser, K. Hamacher, and M. Lablans, “Mainzelliste se- cureepilinker (mainsel): privacy-preserving record linkage using se- cure multi-party computation,”Bioinformatics, vol. 38, no. 6, pp. 1657–1668, 2022

    work page 2022

  36. [36]

    Privacy-preserving record linkage using local sen- sitive hash and private set intersection,

    A. Adir, E. Aharoni, N. Drucker, E. Kushnir, R. Masalha, M. Mirkin, and O. Soceanu, “Privacy-preserving record linkage using local sen- sitive hash and private set intersection,” inInternational Conference on Applied Cryptography and Network Security. Springer, 2022, pp. 398–424

    work page 2022

  37. [37]

    Locality preserving hashing,

    K. Zhao, H. Lu, and J. Mei, “Locality preserving hashing,” inPro- ceedings of the AAAI conference on artificial intelligence, vol. 28, no. 1, 2014

    work page 2014

  38. [38]

    Leskovec, A

    J. Leskovec, A. Rajaraman, and J. D. Ullman,Mining of massive data sets. Cambridge university press, 2020

    work page 2020

  39. [39]

    Space/time trade-offs in hash coding with allowable errors,

    B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,”Communications of the ACM, vol. 13, no. 7, pp. 422–426, 1970

    work page 1970

  40. [40]

    Calibrating noise to sensitivity in private data analysis,

    C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” inTheory of cryptography conference. Springer, 2006, pp. 265–284

    work page 2006

  41. [41]

    Min-wise independent permutations,

    A. Z. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher, “Min-wise independent permutations,” inProceedings of the thirtieth annual ACM symposium on Theory of computing, 1998, pp. 327–336

    work page 1998

  42. [42]

    Efficient two-round ot extension and silent non-interactive secure computation,

    E. Boyle, G. Couteau, N. Gilboa, Y . Ishai, L. Kohl, P. Rindal, and P. Scholl, “Efficient two-round ot extension and silent non-interactive secure computation,” inProceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 2019, pp. 291–308

    work page 2019

  43. [43]

    Expand-convolute codes for pseudorandom correlation generators from lpn,

    S. Raghuraman, P. Rindal, and T. Tanguy, “Expand-convolute codes for pseudorandom correlation generators from lpn,” inAnnual Inter- national Cryptology Conference. Springer, 2023, pp. 602–632

    work page 2023

  44. [44]

    Practical multi-party private set intersection from symmetric-key techniques,

    V . Kolesnikov, N. Matania, B. Pinkas, M. Rosulek, and N. Trieu, “Practical multi-party private set intersection from symmetric-key techniques,” inProceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1257–1272

    work page 2017

  45. [45]

    Obliv- ious key-value stores and amplification for private set intersection,

    G. Garimella, B. Pinkas, M. Rosulek, N. Trieu, and A. Yanai, “Obliv- ious key-value stores and amplification for private set intersection,” inAdvances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part II 41. Springer, 2021, pp. 395–425

    work page 2021

  46. [46]

    Amortizing circuit-PSI in the mul- tiple sender/receiver setting,

    A. van Baarsen and M. Stevens, “Amortizing circuit-PSI in the mul- tiple sender/receiver setting,”IACR Communications in Cryptology, vol. 1, no. 3, 2024

    work page 2024

  47. [47]

    Im- proved alternating-moduli prfs and post-quantum signatures,

    N. Alamati, G.-V . Policharla, S. Raghuraman, and P. Rindal, “Im- proved alternating-moduli prfs and post-quantum signatures,” inAn- nual International Cryptology Conference. Springer, 2024, pp. 274– 308

    work page 2024

  48. [48]

    Effi- cient circuit-based psi with linear communication,

    B. Pinkas, T. Schneider, O. Tkachenko, and A. Yanai, “Effi- cient circuit-based psi with linear communication,” inAdvances in Cryptology–EUROCRYPT 2019: 38th Annual International Confer- ence on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part III 38. Springer, 2019, pp. 122–153

    work page 2019

  49. [49]

    V ole-psi: fast oprf and circuit-psi from vector-ole,

    P. Rindal and P. Schoppmann, “V ole-psi: fast oprf and circuit-psi from vector-ole,” inAnnual international conference on the theory and applications of cryptographic techniques. Springer, 2021, pp. 901–930

    work page 2021

  50. [50]

    Exploring crypto dark matter: New simple prf candidates and their applications,

    D. Boneh, Y . Ishai, A. Passel`egue, A. Sahai, and D. J. Wu, “Exploring crypto dark matter: New simple prf candidates and their applications,” inTheory of Cryptography Conference. Springer, 2018, pp. 699–729

    work page 2018

  51. [51]

    Mpc-friendly symmetric cryptography from al- ternating moduli: Candidates, protocols, and applications,

    I. Dinur, S. Goldfeder, T. Halevi, Y . Ishai, M. Kelkar, V . Sharma, and G. Zaverucha, “Mpc-friendly symmetric cryptography from al- ternating moduli: Candidates, protocols, and applications,” inAnnual International Cryptology Conference. Springer, 2021, pp. 517–547

    work page 2021

  52. [52]

    Crypto dark matter on the torus: Oblivious prfs from shallow prfs and tfhe,

    M. R. Albrecht, A. Davidson, A. Deo, and D. Gardham, “Crypto dark matter on the torus: Oblivious prfs from shallow prfs and tfhe,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2024, pp. 447–476

    work page 2024

  53. [53]

    Cryptflow2: Practical 2-party secure inference,

    D. Rathee, M. Rathee, N. Kumar, N. Chandran, D. Gupta, A. Rastogi, and R. Sharma, “Cryptflow2: Practical 2-party secure inference,” in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, 2020, pp. 325–342

    work page 2020

  54. [54]

    libOTe: an efficient, portable, and easy to use Oblivious Transfer Library,

    P. Rindal and L. Roy, “libOTe: an efficient, portable, and easy to use Oblivious Transfer Library,” https://github.com/osu-crypto/libOTe

    work page

  55. [55]

    Ferret: Fast ex- tension for correlated ot with small communication,

    K. Yang, C. Weng, X. Lan, J. Zhang, and X. Wang, “Ferret: Fast ex- tension for correlated ot with small communication,” inProceedings of the 2020 ACM SIGSAC Conference on Computer and Communi- cations Security, 2020, pp. 1607–1626

    work page 2020

  56. [56]

    Softspokenot: Quieter ot extension from small-field silent vole in the minicrypt model,

    L. Roy, “Softspokenot: Quieter ot extension from small-field silent vole in the minicrypt model,” inAnnual international cryptology conference. Springer, 2022, pp. 657–687

    work page 2022

  57. [57]

    Semi- homomorphic encryption and multiparty computation,

    R. Bendlin, I. Damg ˚ard, C. Orlandi, and S. Zakarias, “Semi- homomorphic encryption and multiparty computation,” inAnnual International Conference on the Theory and Applications of Cryp- tographic Techniques. Springer, 2011, pp. 169–188

    work page 2011

  58. [58]

    A new approach to practical active-secure two-party computation,

    J. B. Nielsen, P. S. Nordholt, C. Orlandi, and S. S. Burra, “A new approach to practical active-secure two-party computation,” inAnnual Cryptology Conference. Springer, 2012, pp. 681–700. Appendix A. Threat Model and Security Proof A.1. Threat Model Similar to prior works [13], [14], [16], [18], we consider static semi-honest probabilistic polynomial-time...

    work page 2012

  59. [59]

    Wait for input(x 0, b0)fromSand(x 1, b1)fromR

    work page

  60. [60]

    Selectr 0 randomly, and setr 1 =x 0 +x 1 −r 0 ifb 0 + b1 = 1otherwise setr 1 =−r 0

    work page

  61. [61]

    Figure 17: Functionality of MUX

    Outputr 0 toRandr 1 toS. Figure 17: Functionality of MUX. FunctionalityF ssPEQT Parameters:SenderSand receiverR. Protocol:

    work page

  62. [62]

    Wait for inputx 0 fromSandx 1 fromR

    work page

  63. [63]

    Selectr 0 randomly, and setr 1 = 1−r 0 ifx 0 =x 1 otherwise setr 1 =−r 0

    work page

  64. [64]

    Figure 18: Functionality of secret-shared PEQT

    Outputr 0 toRandr 1 toS. Figure 18: Functionality of secret-shared PEQT. For each queryx /∈ {q j}j∈[m],Sim S definesF(x) := F ′(x)−OKVS.Decode(D, x). 2)Sim S appends({f S i :=y S i }i∈[n],O F ,O F ′ )in the view. We show that the view of adversary simulated bySim has the identical distribution as its view in the real-world execution. For programmed points...

    work page

  65. [65]

    Fori∈[n], k∈[d], compute{w 0,i,k,h}h∈[µ] := Decompose([wi,k −δ, w i,k])and{w 1,i,k,h}h∈[µ] := Decompose([wi,k + 1, wi,k +δ])

    work page

  66. [66]

    Ifp= 1: •List p :={(ID wi ∥k∥σ∥w σ,i,k,h,0∥|w ∗ − wi,k|)}i∈[n],k∈[d],σ∈[0,1],h∈[µ], where w∗ :=UpBound(w σ,i,k,h)ifσ= 0and w∗ :=LowBound(w σ,i,k,h)otherwise

    work page

  67. [67]

    Ifp= 2: •List p :={(ID wi ∥k∥σ∥w σ,i,k,h,0∥|w ∗ − wi,k|∥|w∗ −w i,k|2)}i∈[n],k∈[d],σ∈[0,1],h∈[µ], wherew ∗ :=UpBound(w σ,i,k,h)ifσ= 0 andw ∗ :=LowBound(w σ,i,k,h)otherwise

    work page

  68. [68]

    The protocol can extend to arbitraryp

    PadList p into sizen·d·2·µand outputsList p Figure 19: Protocol for computing list forp= 1andp= 2. The protocol can extend to arbitraryp. ProtocolΠ getDistancep Parameters:Sender inputs{s S h }h∈[µ] ∈F µ×p ,q∈U, σ∈ {0,1}. Receiver inputs{s R h }h∈[µ] ∈F µ×p. Functionality FMult. Denoteµ= logδ. Protocol: 1)Scomputes{q h}h∈[µ] :=AllPrefix(q, µ)

    work page

  69. [69]

    Forh∈[µ],Scomputese h :=|q−UpBound(q h)|if σ= 0ande h =|q−LowBound(q h)|otherwise

    work page

  70. [70]

    Ifp= 1: •Forh∈[µ],Scomputesd S h :=e h +s S h andR computesd R h :=s R h

    work page

  71. [71]

    •Forh∈[µ], i∈[1, p],SandRinvokeF Mult where Sinputse h andRinputss R h,1.Sreceivesm S h and Rreceivesm R h

    Ifp= 2: •Forh∈[µ],Sparsess S h =s S h,1∥sS h,2 ∈F 2 andR parsess R h =s R h,1∥sR h,2 ∈F 2. •Forh∈[µ], i∈[1, p],SandRinvokeF Mult where Sinputse h andRinputss R h,1.Sreceivesm S h and Rreceivesm R h . •Forh∈[µ],Scomputesd S h :=e 2 h + 2eh ·s S h,1 + 2mS h +s S h,2 andd R h := 2mR h +s R h,2. 5)Soutputs{d S h }h∈[µ] andRoutputs{d R h }h∈[µ]. Figure 20: Pro...

    work page

  72. [72]

    Forj∈[m], k∈[d],Scomputes{q j,k,h}h∈[µ] := AllPrefix(qj,k, µ). 4)SandRinvoke functionalityF so-OPPRF, whereRinputsList p andSinputs {IDqj ∥k∥σ∥q j,k,h}σ∈[0,1],j∈[m],k∈[d],h∈[µ] .Sreceives {eS σ,j,k,h∥vS σ,j,k,h}σ∈[0,1],j∈[m],k∈[d],h∈[µ] andR receives{e R σ,j,k,h∥vR σ,j,k,h}σ∈[0,1],j∈[m],k∈[d],h∈[µ]

    work page

  73. [73]

    Forσ∈[0,1], j∈[m], k∈[d], h∈[µ],SandR invoke functionalityF B2A, whereSinputsv S σ,j,k,h and Rinputsv R σ,j,k,h.Sreceivess S σ,j,k,h andRreceives sR σ,j,k,h

    work page

  74. [74]

    Forσ∈[0,1], j∈[m], k∈[d],SandRinvoke ΠgetDistancep, whereSinputs({s S σ,j,k,h}h∈[µ], qj,k, σ), Rinputs{s R σ,j,k,h}h∈[µ].Sreceives{d S σ,j,k,h}h∈[µ] and Rreceives{d R σ,j,k,h}h∈[µ]

    work page

  75. [75]

    Forj∈[m], k∈[d],SandRinvokeF EQSel, where Sinputs{e S σ,j,k,h, dS σ,j,k,h}σ∈[0,1],h∈[µ] andRinputs {eR σ,j,k,h, dR σ,j,k,h}σ∈[0,1],h∈[µ].Sreceivesr S j,k andR receivesr R j,k

    work page

  76. [76]

    Forj∈[m],Scomputesr S j := P k∈[d]rS j,k, andR computesr R j :=P k∈[d]rR j,k

    work page

  77. [77]

    Forj∈[m],SandRinvoke functionalityF Interval, whereSinputsr S j andRinputsr R j .Rreceivesb j := 1(rS j +r R j ≤δ p)

    work page

  78. [78]

    Ours-prefix

    Forj∈[m],RandSinvoke functionalityF OT, where Rinputsb j andSinputs(⊥, q j).Rreceives OT outputs zj. 11)RoutputsZ:={z j |b j = 1forj∈[m]}. Figure 21: Protocol of fuzzy PSI with prefix optimization forL p distance. |t|p fort∈[−δ, δ], i∈[n], k∈[d].Sim R appends ({rR j,k}j∈[m],k∈[d] ,O F )to the view. 3)Sim R randomly samples{d R j,k}j∈[m],k∈[d] and appends ...

    work page 1901

  79. [79]

    It significantly improves the performance of a known construction by contributing a new primitive - an OPPRF with secret shared outputs - which may be of independent interest

    The paper provides a valuable step forward in the estab- lished field of Fuzzy-PSI. It significantly improves the performance of a known construction by contributing a new primitive - an OPPRF with secret shared outputs - which may be of independent interest

    work page