Efficient Fuzzy PSI under One-Sided Assumptions

arXiv:2608.17770v1 [cs.CR] 18 Aug 2026

Efficient Fuzzy PSI under One-Sided Assumptions Xinpeng Yang

Meng Hao∗

Yanxue Jia

Nanyang Technological University Singapore XINPENG004@e.ntu.edu.sg

Singapore Management University Singapore menghao303@gmail.com

Illinois Institute of Technology Chicago, Illinois, USA yjia12@illinoistech.edu

Chenkai Weng

Yonggang Wen

Tianwei Zhang

Arizona State University Tempe, Arizona, USA chenkai.weng@asu.edu

Nanyang Technological University Singapore ygwen@ntu.edu.sg

Nanyang Technological University Singapore tianwei.zhang@ntu.edu.sg

Abstract Fuzzy private set intersection (PSI) enables two parties to identify approximately matching elements between their input sets, where two elements are considered a match if their distance is at most a threshold 𝛿 under a given metric. Although substantial progress has been made, existing constructions for general Minkowski distances either rely on strong two-sided geometric separation assumptions or incur substantial overhead under one-sided assumptions. In this work, we present the first concretely efficient fuzzy PSI protocols for general 𝐿𝑝 ∈ [1,∞] distances under one-sided assumptions, relying solely on lightweight symmetric-key primitives. Our constructions support both sender-sided and receiver-sided settings. We further study sparser input distributions and present more efficient protocols tailored to this case. To reduce the overhead scaling with 𝛿, we non-trivially incorporate prefix trie techniques into our protocols, achieving 𝑂 (log 𝛿) complexity for general 𝐿𝑝 ∈ [1,∞] distances for the first time, improving upon 𝑂 ((log 𝛿)𝑑 ) or 𝑂 (𝛿) complexities of prior works. Extensive experiments, across a wide range of parameter settings, show that our protocols significantly outperform prior works under the same assumptions. Specifically, against van Baarsen and Pu (EUROCRYPT’24), our protocols achieve up to 239× faster computation and up to 20× lower communication. Against Dang et al. (CCS’25), we achieve up to 518× speedup and up to 63× communication reduction. Against Bui et al. (ASIACRYPT’25), we achieve up to 4818× faster computation and up to 282× lower communication.

CCS Concepts • Security and privacy → Cryptography.

Keywords Fuzzy Private Set Intersection; MPC ∗ Meng Hao is the corresponding author

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. Conference acronym ’XX, Woodstock, NY © 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/XXXXXXX.XXXXXXX

ACM Reference Format: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, and Tianwei Zhang. 2018. Efficient Fuzzy PSI under One-Sided Assumptions. In Proceedings of Make sure to enter the correct conference title from your rights confirmation email (Conference acronym ’XX). ACM, New York, NY, USA, 28 pages. https://doi.org/XXXXXXX.XXXXXXX

1

Introduction

Standard private set intersection (PSI) [8, 11, 12, 16, 18, 19, 22, 25, 26, 28, 33] has been studied for decades, with significant progress made in both efficiency and scalability. It enables two parties to compute their common elements without revealing any information about non-matching ones. PSI has found applications in contact tracing [19, 33], ad conversion measurement [18], and others [1, 20]. However, its exact-matching requirement limits applicability in settings where data are inherently noisy or imprecise, such as biometric identification or location services. Fuzzy PSI [6, 10, 13–15, 27, 30–32, 34, 35] generalizes this functionality to support approximate matching. Specifically, in a 𝑑dimensional space, let the sender hold a set 𝑄 = {𝒒 1, . . . , 𝒒𝑚 } and the receiver hold a set 𝑊 = {𝒘1, . . . , 𝒘𝑛 }. Fuzzy PSI outputs to the receiver all elements 𝒒 ∈ 𝑄 for which there exists some 𝒘 ∈ 𝑊 satisfying dist(𝒒, 𝒘) ≤ 𝛿, where 𝛿 is the matching threshold and dist(·, ·) denotes a predefined distance metric, e.g., general 𝐿𝑝 ∈ [1,∞] distances. To ensure practical efficiency, most existing fuzzy PSI protocols rely on geometric separation assumptions over the input sets. These works can be broadly divided into two categories based on the underlying assumptions: one-sided and two-sided. Protocols based on two-sided assumptions [10, 13, 31, 32, 34, 35] generally achieve better efficiency. For example, under the assumption that points held by both the sender and receiver are pairwise separated by at least 2𝛿 or 4𝛿, the state-of-the-art construction [32] realizes concretely efficient fuzzy PSI using lightweight OPRF. However, such two-sided assumptions may be unrealistic in practice and can limit its applicability to real-world scenarios. To relax these constraints, recent works [6, 10, 14, 31] have proposed fuzzy PSI protocols under one-sided assumptions, where only one party’s inputs are required to satisfy certain assumptions while the other party may hold arbitrary inputs. However, existing constructions either rely on heavyweight cryptographic primitives (e.g., AHE [23, 24]) or do not support general 𝐿𝑝 ∈ [1,∞] distances. Specifically, van Baarsen and Pu [31], later improved by Dang et al. [10], proposed the first fuzzy PSI protocols for general 𝐿𝑝 ∈ [1,∞]

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

distances using AHE. Concurrently, another line of work [6, 14] achieves fuzzy PSI using symmetric-key techniques (e.g., function secret sharing [4, 5]), but supports only the 𝐿∞ distance. Moreover, these works incur undesirable asymptotic communication and computation overhead in the distance threshold 𝛿. The protocol of [31] scales linearly as 𝑂 (𝛿), while the constructions in [6, 10, 14] incur computation or communication complexity of 𝑂 ((log 𝛿)𝑑 ). Consequently, the efficiency of these protocols deteriorates with larger 𝛿, particularly in real-world applications where 𝛿 represents a normalized integer of some high-precision floatingpoint value and may thus be large. In summary, existing works for general 𝐿𝑝 ∈ [1,∞] distances either (1) rely on strong geometric separation assumptions on both parties’ inputs, or (2) incur substantial computation and communication overhead under one-sided assumptions. Motivated by these limitations, we raise the following question: Can we construct efficient fuzzy PSI protocols for general 𝐿𝑝 ∈ [1,∞] distances under one-sided assumptions?

1.1

Our Contributions

To address these limitations, we propose a fuzzy PSI for general 𝐿𝑝 ∈ [1,∞] distances with two key features: (1) it operates under weaker one-sided assumptions (for either sender or receiver), and (2) it relies solely on lightweight symmetric-key primitives, thus achieving significant improvements in both communication and computation efficiency. We summarize our contributions as follows. (1) General fuzzy PSI under one-sided assumptions. We propose concretely efficient fuzzy PSI protocols for general 𝐿𝑝 ∈ [1,∞] distances under one-sided assumptions, relying solely on lightweight symmetric-key primitives. The core intermediate techniques are efficient protocols for multi-point fuzzy matching, which support one party holding multiple inputs without imposing any assumption. Building on this, we present new constructions of fuzzy PSI supporting both the sender-sided and receiver-sided assumptions. (2) Logarithmic complexity in threshold 𝛿. We non-trivially incorporate prefix-trie techniques into our protocols. Unlike prior works that incur superlinear complexity 𝑂 ((log 𝛿)𝑑 ), we design an efficient dimension-by-dimension filtering mechanism to prune the exponential search space. As a result, our optimized protocol achieves logarithmic complexity 𝑂 (log 𝛿) in the distance threshold 𝛿. (3) Extension for sparser distributions. We further consider sparser input distributions under one-sided assumptions and design more efficient fuzzy PSI protocols tailored to this setting. The key idea is to reverse the roles of the sender and receiver in the spatial hashing procedure, which balances their respective workloads and yields improved concrete performance. (4) Implementation and evaluation. We implement all proposed protocols and conduct extensive experiments across a wide range of parameter settings. Our protocols significantly outperform all prior works under assumptions of comparable strength, achieving one to three orders of magnitude improvement in efficiency.

Xinpeng Yang et al.

2

Related Work

We introduce related works of fuzzy PSI under one-sided assumptions and defer other works to Appendix D. Table 1 compares our protocols with prior works in terms of techniques, assumptions, and asymptotic complexity. Specifically, Garimella et al. [15] proposed the first fuzzy PSI protocol for 𝐿∞ distance, using a customized scheme of Function Secret Sharing (FSS) [4, 5] to test whether the sender’s points fall within the receiver’s 𝛿-radius 𝐿∞ balls. Their construction requires the receiver’s balls to be disjoint, while the sender’s points could be arbitrary. Depending on the distances between the ball centers, they consider different settings, but the computational complexity remains 𝑂 (𝛿 𝑑 ) in all cases. Following works [6, 14] improved upon this via prefix trie optimizations, reducing the complexity to 𝑂 ((log 𝛿)𝑑 ) for both communication and computation. These two constructions rely on the mini-universe assumption, under which each ball maps uniquely to a distinct vertex of the space and the sender’s points remain unconstrained. A common limitation of this line of work [6, 14, 15] is that it supports only 𝐿1 and 𝐿∞ distances, with no known efficient instantiation for general 𝐿𝑝 distances. Subsequently, van Baarsen and Pu [31] studied fuzzy PSI under the one-sided 2𝛿-apart assumption, where only the receiver’s points are required to be at least 2𝛿 apart from each other. Their construction is built on a DDH-based set membership test, achieving 𝑂 (𝛿) complexity in threshold 𝛿. To support arbitrary 𝐿𝑝 distances, they require a stronger 4𝛿-apart assumption, and the overhead scales as 𝑂 (𝛿 𝑝 ) since the sender must enumerate all possible 𝑝-th power distances. Similarly, Dang et al. [10] further optimized this construction via prefix trie techniques under the same 4𝛿-apart assumption, reducing the complexity to 𝑂 ((log 𝛿)𝑑 ). More recently, Richardson et al. [30] and Piske et al. [27] proposed fuzzy PSI protocols based on symmetric-key techniques under the disjoint hash assumption, which requires each point to map to a unique representation. In particular, Richardson et al. [30] map elements into bins via spatial hashing and, assuming that each bin of both parties contains at most one element, compare items within corresponding bins. However, as illustrated by Piske et al. [27], their constructions based on Garbled Circuits incur substantial communication and computational overhead. Subsequently, Piske et al. [27] introduced more efficient fuzzy PSI protocols based on a new primitive called distance-aware OT, which transfers values conditioned on the distance between inputs. However, their theoretical construction under one-sided assumptions additionally leaks the density of the arbitrarily distributed receiver set and incurs complexity with an additional multiplicative dependence on this density. Moreover, their concrete instantiation ultimately relies on a two-sided assumption, requiring both the sender’s and receiver’s points to map to unique blocks or cells.

3 Preliminary 3.1 Notation We use 𝜅 and 𝜆 to denote the computational and statistical security parameters, respectively. We use [𝑎, 𝑏] to denote the set {𝑎, . . . , 𝑏} and [𝑎] to denote the set {1, . . . , 𝑎}. For a set 𝑆, |𝑆 | denotes its $

cardinality. We write 𝑟 ← F to denote that 𝑟 is sampled uniformly

Efficient Fuzzy PSI under One-Sided Assumptions

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Table 1: Comparisons of existing fuzzy PSI protocols under one-sided assumptions. The sender holds 𝑚 points and the receiver holds 𝑛 points in a 𝑑-dimensional space, and 𝛿 is the distance threshold. Note that our assumptions are either equivalent to or strictly weaker than existing ones; a detailed analysis is provided in Appendix F. Metric

Protocol

Technique

Assumption

Communication

[6]

FSS AHE AHE AHE GC OPRF so-OPPRF so-OPPRF so-OPPRF so-OPPRF AHE AHE GC OPRF so-OPPRF so-OPPRF so-OPPRF so-OPPRF

R, mini-universe R, 2𝛿-apart R, 4𝛿-apart R, 4𝛿-apart S ∗, disj. hash S ∗ , disj. hash R/S, unique cell R/S, unique cell R/S, unique block R/S, unique block R, 2𝛿 (𝑑 1/𝑝 + 1)-apart R, 2𝛿 (𝑑 1/𝑝 + 1)-apart S ∗, disj. hash S ∗ , disj. hash R/S, unique cell R/S, unique cell R/S, unique block R/S, unique block

𝑂 (𝑑𝑛 log 𝛿 + 𝑚2𝑑 (log 𝛿)𝑑 ) 𝑂 (𝛿𝑑𝑛 + 2𝑑 𝑚) 𝑂 (𝛿2𝑑 𝑑𝑛 + 𝑚) 𝑂 (𝑑 log 𝛿 (𝑛2𝑑 + 𝑚)) 𝑂 (𝑑 log 𝛿 (𝑛2𝑠 + 𝑚2𝑑 −𝑠 )) 𝑂 (𝑑 (𝛿𝑚 + 2𝑑 𝑛)) 𝑂 (𝑑 (𝛿𝑛 + 2𝑑 𝑚)) 𝑂 (log 𝛿𝑑 (𝑛 + 2𝑑 𝑚)) 𝑂 (𝑑 (𝑚 + 𝛿2𝑑 𝑛)) 𝑂 (log 𝛿𝑑 (2𝑑 𝑛 + 𝑚)) 𝑂 (𝛿2𝑑 𝑑𝑛 + 𝛿 𝑝 𝑚) 𝑂 (2𝑑 𝑝 (𝑑𝑛 log 𝛿 + 𝑚(log 𝛿)𝑑 ) + 𝑑𝑚 log 𝛿) 𝑂 (𝑑 log(𝑑𝛿)(𝑛2𝑑 + 𝑚2𝑑 −𝑠 )) 𝑂 (𝑑 (𝛿𝑚 + 2𝑑 𝑛)) 𝑂 (𝑑 (𝛿𝑛 + 2𝑑 𝑚) + 𝑝 log 𝛿2𝑑 𝑚) 𝑂 (log 𝛿 (𝑑𝑛 + 2𝑑 𝑑𝑚 + 2𝑑 𝑝𝑚)) 𝑂 (𝑑 (𝑚 + 𝛿2𝑑 𝑛) + 𝑝 log 𝛿𝑚) 𝑂 (log 𝛿 (2𝑑 𝑑𝑛 + 𝑑𝑚 + 𝑝𝑚))

[31] 𝐿∞

𝐿𝑝

[10] [30] [27] Ours Ours-Px Ours Ours-Px [31] [10] [30] [27] Ours Ours-Px Ours Ours-Px

Computation Sender Receiver 𝑂 (𝑚2𝑑 (log 𝛿)𝑑 ) 𝑂 ((log 𝛿)𝑑 𝑛 + 𝑑𝑚 log 𝛿) 𝑂 (2𝑑 𝑑𝑚) 𝑂 (𝛿𝑑𝑛 + 2𝑑 𝑚) 𝑂 (𝑑𝑚) 𝑂 (𝛿2𝑑 𝑑𝑛 + 𝑚) 𝑂 (2𝑑 𝑑𝑛 log 𝛿 + 𝑚(log 𝛿)𝑑 ) 𝑂 (𝑑𝑚 log 𝛿) 𝑂 (2𝑑 −𝑠 𝑑𝑚 log 𝛿) 𝑂 (2𝑠 𝑑𝑛 log 𝛿) 𝑂 (𝛿𝑑𝑚) 𝑂 (𝑑2𝑑 𝑛 + 𝑚) 𝑂 (2𝑑 𝑑𝑚) 𝑂 (𝑑 (𝛿𝑛 + 2𝑑 𝑚)) 𝑂 (log 𝛿2𝑑 𝑑𝑚) 𝑂 (log 𝛿𝑑 (𝑛 + 2𝑑 𝑚)) 𝑂 (𝑑𝑚) 𝑂 (𝑑 (𝑚 + 𝛿2𝑑 𝑛)) 𝑂 (log 𝛿𝑑𝑚) 𝑂 (log 𝛿𝑑 (2𝑑 𝑛 + 𝑚)) 𝑂 ((𝑑 + 𝛿 𝑝 )𝑚) 𝑂 (𝛿2𝑑 𝑑𝑛 + 𝑚) 𝑂 (2𝑑 (𝑑𝑝𝑛 log 𝛿 + 𝑚(log 𝛿)𝑑 )) 𝑂 (𝑚(𝑑𝑝 log 𝛿 + 2𝑑 (log 𝛿)𝑑 )) 𝑂 (𝑑𝑚2𝑑 −𝑠 log(𝑑𝛿)) 𝑂 (𝑑𝑛2𝑠 log(𝑑𝛿)) 𝑂 (𝛿𝑑𝑚) 𝑂 (𝑑2𝑑 𝑛 + 𝑚) 𝑂 ((𝑑 + 𝑝 log 𝛿)2𝑑 𝑚) 𝑂 (𝑑 (𝛿𝑛 + 2𝑑 𝑚) + 𝑝 log 𝛿2𝑑 𝑚) 𝑂 (log 𝛿 (2𝑑 𝑑𝑚 + 2𝑑 𝑝𝑚)) 𝑂 (log 𝛿 (𝑑𝑛 + 2𝑑 𝑑𝑚 + 2𝑑 𝑝𝑚)) 𝑂 ((𝑑 + 𝑝 log 𝛿)𝑚) 𝑂 (𝑑 (𝑚 + 𝛿2𝑑 𝑛) + 𝑝 log 𝛿𝑚) 𝑂 (log 𝛿 (𝑑𝑚 + 𝑝𝑚)) 𝑂 (log 𝛿 (2𝑑 𝑑𝑛 + 𝑑𝑚 + 𝑝𝑚))

– R/S denotes that the set of receiver or sender satisfies the assumption. – S ∗ denotes that the protocols of [27, 30] require an additional assumption on the receiver’s inputs to instantiate the concrete protocol. – Our protocols for sender-sided and receiver-sided assumptions have the same asymptotic complexity when 𝑚 = 𝑛 , we report one complexity. – Mini-universe assumption requires that each 𝐿∞ ball maps uniquely to a distinct mini-universe. – 2𝛿 /4𝛿 -apart means the distance between any two points of the set is at least 2𝛿 or 4𝛿 apart. 2𝛿 (𝑑 1/𝑝 + 1) -apart is the generalization of the 4𝛿 -apart for 𝐿𝑝 distances. – Disj. hash is short for disjoint hash assumption, which means the spatial hashing scheme maps at most one point to the same cell. – Unique block/unique cell means in spatial hashing, each cell intersects with at most one 𝐿∞ ball and each cell contains at most one point, respectively.

at random from space F. We use 1{event} to denote the indicator function that equals 1 if event occurs and 0 otherwise. All protocols in this work are proven secure in the semi-honest model and the formal definition is deferred to Appendix G.1.

3.2

Fuzzy PSI

We formally define the ideal functionality of fuzzy PSI in Figure 1, following prior works [10, 31, 32]. Given a threshold 𝛿 and a distance metric dist(·, ·), the functionality takes as input a set from each party and outputs to the receiver all sender elements within distance 𝛿 of some receiver element. Functionality FFPSI Parameters: Sender S and receiver R with input sizes 𝑚, 𝑛, respectively. Distance metric dist(·, ·) and threshold 𝛿. Functionality: (1) Wait for input 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ U𝑑 ×𝑚 from S and 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ U𝑑 ×𝑛 from R. (2) Output {𝒒 𝑗 | ∃𝑖 ∈ [𝑛], dist(𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿 } to R.

Figure 1: Functionality of fuzzy PSI.

3.3

Spatial Hashing and Assumptions

Spatial Hashing. To avoid the quadratic complexity of naively comparing every pair of inputs, similar to prior fuzzy PSI under one-sided assumptions [10, 15, 31, 32], we adopt the spatial hashing

technique, which partitions the space U𝑑 into cells of side length 2𝛿. For a point 𝒙, we define two algorithms: (1) cell2𝛿 (𝒙) → C maps 𝒙 to the identifier of the cell containing 𝑥 it, where C = 𝑖𝑑 1 ∥𝑖𝑑 2 ∥ · · · ∥𝑖𝑑𝑑 and 𝑖𝑑𝑘 = ⌊ 2𝛿𝑘 ⌋ for 𝑘 ∈ [𝑑]. (2) neigh2𝛿 (𝒙) → {C𝑧 }𝑧 ∈ [2𝑑 ] maps 𝒙 to the set of identifiers of all cells intersecting the 𝐿𝑝 ∈ [1,∞] ball of radius 𝛿 centered at 𝒙. By default, the output is padded to 2𝑑 cells using random values. mini-universe [6, 14]

disj. hash

Section 5

Section 7

[27, 30]

unique cell

unique block

2𝛿-apart [15, 31]

2𝛿-disj. proj.

4𝛿-apart

[10, 13, 31, 32, 34]

[10, 31]

Figure 2: Relationships of existing assumptions. An arrow indicates the direction from the weaker to the stronger assumption, and a double-headed arrow indicates equivalence. Assumptions. Our protocols operate under two different onesided assumptions: unique cell and unique block. The unique cell assumption requires that each cell contains at most one point, i.e., every point occupies a distinct cell.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Definition 3.1 (Uniqe Cell). A set 𝑊 ∈ U𝑛×𝑑 satisfies the unique cell assumption if every cell in spatial hashing contains at most one point 𝒘 ∈ 𝑊 . In other words, for any two distinct points 𝒘, 𝒘 ′ ∈ 𝑊 , cell2𝛿 (𝒘) ≠ cell2𝛿 (𝒘 ′ ). The unique block assumption is sparser, requiring that each cell intersects with at most one 𝐿∞ ball, i.e., every point’s 𝐿∞ ball occupies a distinct block of side length 4𝛿 comprising 2𝑑 cells.

Xinpeng Yang et al.

3.5

An oblivious programmable pseudorandom function (OPPRF) [21] allows the sender to program a pseudorandom function with a set of key-value pairs. When evaluated at a programmed point, the receiver obtains the corresponding programmed value directly; otherwise, it obtains a uniformly random value.

Definition 3.2 (Uniqe Block). A set 𝑊 ∈ U𝑛×𝑑 satisfies the unique block assumption if each cell intersects with at most one 𝐿𝑝 ∈ [1,∞] ball centered at 𝒘 ∈ 𝑊 . In other words, for any two distinct points 𝒘, 𝒘 ′ ∈ 𝑊 , neigh2𝛿 (𝒘) ∩ neigh2𝛿 (𝒘 ′ ) = ∅.

Functionality Fso-OPPRF Parameters: Sender S and receiver R with input sizes 𝑚, 𝑛, respectively. Functionality: (1) Wait for input 𝐿 = { (𝑞 𝑗 , 𝑧 𝑗 ) } 𝑗 ∈ [𝑚] ⊆ U × F from S and 𝑋 = {𝑥𝑖 }𝑖 ∈ [𝑛] ⊆ U from R. (2) Sample a random function 𝐹 : U → F such that 𝐹 (𝑞) = 𝑧 for (𝑞, 𝑧 ) ∈ 𝐿. (3) For 𝑖 ∈ [𝑛], compute 𝑦𝑖 := 𝐹 (𝑥𝑖 ) and sample 𝑦𝑖S , 𝑦𝑖R ← F such that 𝑦𝑖S + 𝑦𝑖R = 𝑦𝑖 ∈ F. (4) Output {𝑦𝑖S }𝑖 ∈ [𝑛] and O 𝐹 to S and {𝑦𝑖R }𝑖 ∈ [𝑛] to R.

We provide a comparison of existing assumptions in Figure 2. For clarity, all assumptions are stated with respect to the 𝐿∞ distance; their relationships extend analogously to general 𝐿𝑝 distances. Notably, all existing assumptions in the literature are either equivalent to or strictly stronger than the unique cell assumption. We defer the formal definitions and detailed analysis of these assumptions to Appendix F.

3.4

Prefix Trie

Chakraborti et al. [7] first introduced the prefix trie technique, which was subsequently studied and formalized by [6, 10, 14, 32]. Let 𝑥 = 𝑥 ℓ 𝑥 ℓ −1 · · · 𝑥 1 ∈ {0, 1}ℓ be a binary string. We adopt the notation of [10]: • UpBound(𝑥 ℓ 𝑥 ℓ −1 · · · 𝑥𝑘 ) = 𝑥 ℓ 𝑥 ℓ −1 · · · 𝑥𝑘 ∥11 · · · 1 • LowBound(𝑥 ℓ 𝑥 ℓ −1 · · · 𝑥𝑘 ) = 𝑥 ℓ 𝑥 ℓ −1 · · · 𝑥𝑘 ∥00 · · · 0 • Interval(𝑥 ℓ 𝑥 ℓ −1 · · · 𝑥𝑘 ) = {𝑥 ℓ · · · 𝑥𝑘 ∥𝑥 ∗ }𝑥 ∗ ∈ {0,1}𝑘 −1 van Baarsen and Pu [32] further summarized the technique and gave the following theorem. Theorem 3.1 ([32]). Given an integer interval [𝑞−𝛿, 𝑞+𝛿] ∈ Z2𝛿+1 2ℓ and a point 𝑤 ∈ Z2ℓ , there are two algorithms with 𝜇, 𝜇 ′ = 𝑂 (log 𝛿): (1) PxTrie(𝑞 − 𝛿, 𝑞 + 𝛿) → {𝑞˜1, . . . , 𝑞˜ 𝜇 }: The PxTrie algorithm succinctly encodes the interval [𝑞 − 𝛿, 𝑞 + 𝛿] into 𝜇 prefix nodes 𝜇 {𝑞˜1, . . . , 𝑞˜ 𝜇 } ∈ Z2ℓ that cover the entire interval without overlap. Specifically, 𝜇 ≤ 2 + log 𝛿 when 𝛿 is a power of 2. (2) PxPath(𝑤, 𝛿) → {𝑤˜ 1, . . . , 𝑤˜ 𝜇 ′ }: The PxPath algorithm expands each query point 𝑤 ∈ Z2ℓ into a path of prefix nodes 𝜇′ {𝑤˜ 1, . . . , 𝑤˜ 𝜇 ′ } ∈ Z2ℓ , where 𝜇 ′ := 2 + log 𝛿. Then, it holds that 𝑤˜ 𝑡 ∈ {𝑞˜1, . . . , 𝑞˜ 𝜇 } for some unique 𝑡 ∈ [𝜇 ′ ] if and only if 𝑤 ∈ [𝑞 − 𝛿, 𝑞 + 𝛿]. For clarity, we assume throughout this paper that 𝛿 is a power of 2. We set 𝜇 to its maximum value, giving 𝜇 = 𝜇 ′ = 2 + log 𝛿. The output of PxTrie(𝑞 − 𝛿, 𝑞 + 𝛿) is always padded to 𝜇 prefixes using the default random values. Additionally, we give the following property: the outputs of PxTrie(·, ·) and PxPath(·) share at most one common element. A formal proof is provided in Appendix G.10. Lemma 3.1. For any point 𝑤 ∈ {0, 1}ℓ and interval 𝐼 = [𝑞−𝛿, 𝑞+𝛿], the following holds: ( 1, if 𝑤 ∈ [𝑞 − 𝛿, 𝑞 + 𝛿], |PxPath(𝑤, 𝛿) ∩ PxTrie(𝑞 − 𝛿, 𝑞 + 𝛿)| = 0, otherwise.

Oblivious Programmable PRF (with Secretshared Outputs)

Figure 3: Functionality of oblivious programmable PRF with secret-shared outputs. Yang et al. [34] extended the standard OPPRF to support secretshared outputs, yielding the so-OPPRF. Rather than revealing the outputs directly to the receiver, the so-OPPRF splits it into additive secret shares: when evaluated at a programmed point, both parties obtain shares of the corresponding programmed value; otherwise, they obtain uniformly random shares. The so-OPPRF can be efficiently instantiated from a secret-shared oblivious pseudorandom function (ss-OPRF) [2] and an OKVS. We give the ideal functionality of so-OPPRF in Figure 3.

3.6

Other Building Blocks

Our protocols additionally rely on several standard functionalities, including interval test FInterval , private equality test FEq , secure comparison FssCMP , multiplexer FMUX , and oblivious transfer FOT . We defer the formal functionalities to Appendix E.

4

Technical Overview

We first introduce the notation used throughout this overview. Let S (the sender) hold a set 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] of size 𝑚, and let R (the receiver) hold a set 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] of size 𝑛. Each element is a vector in a 𝑑-dimensional space, i.e., 𝒒 𝑗 , 𝒘𝑖 ∈ U𝑑 . We denote by 𝑞 𝑗,𝑘 the 𝑘th coordinate of vector 𝒒 𝑗 . For clarity, we focus on the 𝐿∞ distance in this technical overview and detail how to extend to general 𝐿𝑝 distances in Section 5. As shown in Figure 4, our starting point of the following technical overview is fuzzy matching (Section 4.1), which can be viewed as a special case of fuzzy PSI in which each party holds a single element. Then, we show how to extend fuzzy matching to multipoint fuzzy matching (Section 4.2), where one party holds multiple points without any assumptions. We identify two possible methods of multi-point fuzzy matching to achieve fuzzy PSI: 1-to-𝑛 fuzzy matching (the upper part of Figure 4), where the sender holds a

Efficient Fuzzy PSI under One-Sided Assumptions

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

2𝛿 so-OPPRF + EqRand

1-to-1 Fuzzy Matching

so-OPPRF

1-to-𝑛 Fuzzy Matching

+ sender-sided assumption

𝒒

Revisiting OPPRF-Based Fuzzy Matching

In fuzzy matching, each party holds a single element, denoted by 𝒒 and 𝒘, respectively. The receiver learns 𝒒 if dist(𝒒, 𝒘) ≤ 𝛿, and learns nothing otherwise. Recently, van Baarsen and Pu [32] presented the state-of-the-art fuzzy matching protocol based on OPPRF (see Section 3.5). At a high level, their key idea is to perform an interval membership test via OPPRF for each dimension and then aggregate the results across all dimensions. Concretely, for each dimension 𝑘, the sender samples a uniformly random value 𝑠𝑘 and programs all points in the interval [𝑞𝑘 − 𝛿, 𝑞𝑘 + 𝛿] to the same output 𝑠𝑘 . Accordingly, the receiver then evaluates the programmed PRF at input 𝑤𝑘 to obtain Í 𝑟𝑘 for each 𝑘 ∈ [𝑑]. Finally, the sender sends 𝒒 ⊕ 𝐻 ( 𝑘 ∈ [𝑑 ] 𝑠𝑘 ) to the receiver for an appropriate hash function 𝐻 , and the receiver Í Í recovers 𝒒 if and only if 𝑘 ∈ [𝑑 ] 𝑟𝑘 = 𝑘 ∈ [𝑑 ] 𝑠𝑘 . This follows because if dist(𝒒, 𝒘) ≤ 𝛿, then for every 𝑘 ∈ [𝑑], we have 𝑤𝑘 ∈ [𝑞𝑘 − 𝛿, 𝑞𝑘 + 𝛿], implying 𝑟𝑘 = 𝑠𝑘 by correctness of OPPRF and thus Í Í ∗ 𝑘 ∈ [𝑑 ] 𝑟 𝑘 = 𝑘 ∈ [𝑑 ] 𝑠𝑘 . Otherwise, if there exists some 𝑘 ∈ [𝑑] such that 𝑤𝑘 ∗ ∉ [𝑞𝑘 ∗ − 𝛿, 𝑞𝑘 ∗ + 𝛿], then 𝑟𝑘 ∗ ≠ 𝑠𝑘 ∗ except with negligible Í Í probability and thus 𝑘 ∈ [𝑑 ] 𝑟𝑘 ≠ 𝑘 ∈ [𝑑 ] 𝑠𝑘 . Their scheme relies exclusively on symmetric-key operations and achieves substantial efficiency improvements over prior AHE-based approaches [13, 31]. However, the above construction cannot be extended to the setting where the receiver holds multiple points. For example, suppose the receiver holds two points 𝒘, 𝒘 ′ such that in some dimension 𝑘, both 𝑤𝑘 , 𝑤𝑘′ fall within the same interval [𝑞𝑘 −𝛿, 𝑞𝑘 +𝛿] programmed by the sender. By the correctness of OPPRF, the receiver will obtain the same 𝑟𝑘 on these two evaluations. This leads to leakage when there is no match with 𝒒: the receiver can infer that the sender has encoded an interval covering both 𝑤𝑘 and 𝑤𝑘′ in dimension 𝑘. Such a collision leaks the distribution of the sender’s input. To extend this OPPRF-based fuzzy matching to fuzzy PSI, where both the sender and receiver hold multiple points, [32] prevents this leakage by imposing two-sided assumptions on both parties. Alternative constructions [10, 31] address the above issue with expensive AHE, thereby keeping the OPPRF outputs hidden from

𝒒

𝒘𝑖 1 𝒘𝑖 2

𝑚-to-1 + receiver-sided Fuzzy Matching assumption

𝒘𝑖 2

Figure 4: Two approaches to fuzzy PSI, where 𝑚 is the sender input size and 𝑛 is the receiver input size. Both approaches only impose an assumption on one of the parties.

4.1

𝑦 𝒘𝑖 1

𝑚-to-𝑛 Fuzzy PSI

single point and the receiver holds 𝑛 arbitrary points, and 𝑚-to-1 fuzzy matching (the lower part of Figure 4), where the receiver holds a single point and the sender holds 𝑚 arbitrary points. Finally, building on multi-point fuzzy matching, we realize fully fledged fuzzy PSI protocols under sender-sided or receiver-sided assumptions (Section 4.3). In addition, we further optimize our fuzzy PSI protocols using prefix-trie techniques (Section 4.4).

2𝛿

𝑦

𝑥 No Leakage

𝑥 Partial Leakage

Figure 5: A counterexample for the strawman construction. In the right case, 𝒘𝑖 1 and 𝒘𝑖 2 share the same 𝑥-coordinate and both fall within the programmed interval of 𝒒 along the 𝑦dimension, and are therefore mapped to the same value.

the receiver. In the following, we show how to achieve multi-point fuzzy matching without relying on heavy public-key primitives.

4.2

Multi-point Fuzzy Matching without Assumptions

We propose two variants of multi-point fuzzy matching: 1-to-𝑛 fuzzy matching, where the receiver holds 𝑛 arbitrarily distributed points, and 𝑚-to-1 fuzzy matching, where the sender holds 𝑚 arbitrarily distributed points. 4.2.1 1-to-𝑛 Fuzzy Matching. We first introduce our design for the 1-to-𝑛 fuzzy matching protocol, in which the receiver holds multiple arbitrary points without any additional assumptions. To address the partial-matching leakage arising from individual dimensions in [32], our key insight is to secret-share the OPPRF output for each dimension so that neither party learns the OPPRF outputs in the clear. We instantiate this approach using shared-output OPPRF (soOPPRF) [34] (see Section 3.5). Below, we first present a strawman construction that exhibits subtle privacy leakage, and then show how to eliminate it using additional techniques. Strawman Construction. Let the sender hold a single point 𝒒 and the receiver hold multiple points 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] . Similar to [32], for each dimension 𝑘, the sender samples a random 𝑠𝑘 and programs the so-OPPRF with key-value pairs {(𝑞𝑘 + 𝑡, 𝑠𝑘 )}𝑡 ∈ [ −𝛿,𝛿 ] . Then, for each 𝒘𝑖 ∈ 𝑊 and 𝑘 ∈ [𝑑], the receiver evaluates the so-OPPRF on S R input 𝑤𝑖,𝑘 , which outputs shares 𝑟𝑖,𝑘 and 𝑟𝑖,𝑘 to the two parties, respectively. The secret-sharing form avoids the receiver inferring the sender’s input from OPPRF outputs of some dimensions. After that, both parties locally aggregate their shares across all dimensions Í Í S R by computing 𝑟𝑖S = 𝑘 ∈ [𝑑 ] 𝑟𝑖,𝑘 and 𝑟𝑖R = 𝑘 ∈ [𝑑 ] 𝑟𝑖,𝑘 , respectively. Í S Finally, the sender sends all 𝑟𝑖 and 𝒒 ⊕ 𝐻 ( 𝑘 ∈ [𝑑 ] 𝑠𝑘 ) to the receiver for an appropriate hash function 𝐻 . The receiver subsequently reconstructs 𝑟𝑖 = 𝑟𝑖S + 𝑟𝑖R and recovers 𝒒 if and only if there exists Í some 𝑟𝑖 = 𝑘 ∈ [𝑑 ] 𝑠𝑘 . Partial-matching Leakage. While the above construction appears correct, it introduces subtle privacy leakage. Specifically, although the so-OPPRF outputs remain secret-shared in each dimension, additional information is leaked once the aggregated values 𝑟𝑖

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

are revealed to the receiver. As illustrated in Figure 5 (right), consider a two-dimensional space in which two distinct receiver points 𝒘𝑖 1 and 𝒘𝑖 2 share the same 𝑥-coordinate and both lie within the programmed interval of 𝒒 along the 𝑦-coordinate. During the so-OPPRF evaluation, the two points are mapped to the same random value for the 𝑥-coordinate. Since 𝒘𝑖 1 and 𝒘𝑖 2 fall within the same programmed interval along the 𝑦-dimension, they are mapped to the same programmed value as well. Consequently, after reconstructing from the shares 𝑟𝑖S1 and 𝑟𝑖S2 , the receiver obtains two identical aggregate values, i.e., 𝑟𝑖 1 = 𝑟𝑖 2 . This collision reveals that there exists a sender point 𝒒 that is close to both 𝒘𝑖 1 and 𝒘𝑖 2 in certain dimensions, even though neither receiver point actually matches 𝒒. The root cause of this leakage is that the aggregated values 𝑟𝑖 for non-matching receiver points may coincide, revealing partial information about the sender’s input. To eliminate this leakage, we observe that it suffices to re-randomize the secret shares of 𝑟𝑖 for non-matching inputs, while leaving those of matching inputs unchanged to preserve correctness. Enhance Security. To realize this, we introduce a new building block called equality-conditional randomization (EqRand), which randomizes values conditioned on an equality check. Concretely, it takes two pairs (𝑐 1, 𝑥 1 ) from the sender and (𝑐 2, 𝑥 2 ) from the receiver as input, and outputs random shares (𝑦1, 𝑦2 ) to the respective parties such that 𝑦1 + 𝑦2 = 𝑥 1 + 𝑥 2 if 𝑐 1 = 𝑐 2 ; otherwise, 𝑦1 + 𝑦2 is uniformly random. It remains to define an appropriate matching condition. To determine whether a receiver point 𝒘𝑖 matches the sender point 𝒒, we additionally program a zero indicator 0 together with the target value 𝑠𝑘 , encoding each key-value pair as 0∥𝑠𝑘 . If 𝒘𝑖 matches the sender point 𝒒, it is mapped to 0 in every dimension, so the aggregated indicator remains 0. Otherwise, the aggregated indicator is uniformly random. Specifically, the sender programs the so-OPPRF with key-value pairs1 {(𝑘 ∥𝑞𝑘 + 𝑡, 0∥𝑠𝑘 )}𝑘 ∈ [𝑑 ],𝑡 ∈ [-𝛿,𝛿 ] , and the receiver evaluates it on each input 𝑘 ∥𝑤𝑖,𝑘 as before. The two parties obtain packed R R S S R S shares 𝑒𝑖,𝑘 ∥𝑟𝑖,𝑘 and 𝑒𝑖,𝑘 ∥𝑟𝑖,𝑘 , respectively, where 𝑒𝑖,𝑘 and 𝑒𝑖,𝑘 are shares of the indicator. They then aggregate these shares across all dimensions 𝑘 ∈ [𝑑] to obtain (𝑒𝑖R , 𝑟𝑖R ) and (𝑒𝑖S , 𝑟𝑖S ). By the correctness of so-OPPRF, if 𝒘𝑖 matches 𝒒, then 𝑒𝑖R and 𝑒𝑖S are the shares of 0, i.e., 𝑒𝑖R + 𝑒𝑖S = 0. Otherwise, the shares 𝑟𝑖R and 𝑟𝑖S must be re-randomized to prevent collisions. The sender and receiver therefore invoke EqRand with inputs (−𝑒𝑖S , 𝑟𝑖S ) and (𝑒𝑖R , 𝑟𝑖R ), using the equality 𝑒𝑖R = −𝑒𝑖S as the matching condition, and obtain fresh shares 𝑣𝑖R and 𝑣𝑖S , respectively. Consequently, the sender can then send 𝑣𝑖S without incurring leakage, and the receiver reconstructs 𝑣𝑖 = 𝑣𝑖R + 𝑣𝑖S . Finally, as described above, the sender masks 𝒒 under the key 𝑠 using a one-time pad, and the receiver attempts to unmask using each 𝑣𝑖 , recovering 𝒒 only when 𝒘𝑖 matches 𝒒. 4.2.2 𝑚-to-1 Fuzzy Matching. This mirrored path leads to a symmetric setting, where the sender holds multiple points 𝒒 𝑗 ∈ 𝑄 and the receiver holds a single point 𝒘. Since our multi-point fuzzy matching primitive aims to be assumption-free, directly letting the 1 Here, we encode the dimension index 𝑘 into each key to allow a single so-OPPRF

instance for all dimensions, though it can also be instantiated separately for each dimension as in [32].

Xinpeng Yang et al.

sender program all its points into the so-OPPRF, as in the 1-to-𝑛 setting, may cause collisions among the key-value pairs. Our key insight is to switch the roles in the so-OPPRF routine: the sender evaluates the so-OPPRF instead of programming it. This role switching yields a more natural construction. A key difference from the 1-to-𝑛 setting is that, for each sender point 𝒒 𝑗 , the two parties obtain secret shares 𝑒 𝑗R and 𝑒 𝑗S , which are sufficient to jointly determine whether 𝒒 𝑗 matches the receiver point 𝒘. As a result, the random target value 𝑠𝑘 is no longer needed, and the receiver only programs the indicator 0. Concretely, the receiver programs the so-OPPRF with key-value pairs {(𝑘 ∥𝑤𝑘 +𝑡, 0)}𝑘 ∈ [𝑑 ],𝑡 ∈ [ −𝛿,𝛿 ] , and the sender evaluates it on inR S puts {𝑘 ∥𝑞 𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ] . The two parties obtain shares 𝑒 𝑗,𝑘 and 𝑒 𝑗,𝑘 , Í R R and aggregate them across dimensions to obtain 𝑒 𝑗 = 𝑘 ∈ [𝑑 ] 𝑒 𝑗,𝑘 Í S and 𝑒 𝑗S = 𝑘 ∈ [𝑑 ] 𝑒 𝑗,𝑘 . By the correctness of so-OPPRF, the sender point 𝒒 𝑗 matches the receiver point if and only if 𝑒 𝑗R +𝑒 𝑗S = 0, equivalently, 𝑒 𝑗R = −𝑒 𝑗S . Then, transferring matching elements becomes considerably simpler. The two parties invoke the private equality test FEq to compare 𝑒 𝑗R and −𝑒 𝑗S , from which the receiver obtains a bit 𝑏 𝑗 . If 𝑏 𝑗 = 0, then 𝒒 𝑗 has no match; otherwise, 𝒒 𝑗 matches the receiver point 𝒘. They then invoke FOT with 𝑏 𝑗 as the selection bit to transfer 𝒒 𝑗 to the receiver. A notable advantage of this construction is that, since the target value 𝑠𝑘 is eliminated and the shares 𝑒 𝑗R and 𝑒 𝑗S remain private throughout, no secret value is ever revealed to either party. Consequently, invoking EqRand is unnecessary. This stands in contrast to the 1-to-𝑛 setting in Section 4.2.1, where the aggregated shares are revealed to the receiver and EqRand is required to prevent the receiver from observing identical outputs across multiple inputs.

4.3

Fuzzy PSI under One-sided Assumptions

We now turn to the full 𝑚-to-𝑛 fuzzy PSI construction. Having established two assumption-free multi-point fuzzy matching protocols in the preceding section, extending each to the 𝑚-to-𝑛 setting follows the standard paradigm: imposing a separation assumption on the single-input party to allow it to program additional points without collision. To satisfy this requirement, we leverage spatial hashing techniques [10, 31, 32], partitioning the space into cells of side length 2𝛿 and assuming that each cell contains at most one point from the single-input party, while the other party’s inputs remain unconstrained. We refer to this as the unique cell assumption (see Section 3.3). For each point, we define C𝑗S (resp. C𝑖R ) as the cell identifier of the cell containing 𝒒 𝑗 (resp. 𝒘𝑖 ). Depending on which party satisfies the unique cell assumption, we distinguish two cases: the sender-sided assumption and the receiver-sided assumption, each giving rise to a corresponding 𝑚-to-𝑛 fuzzy PSI construction. Sender-sided unique cell assumption. In this case, each cell contains at most one sender point. Each sender point 𝒒 𝑗 is therefore associated with a unique cell identifier C𝑗S = cell2𝛿 (𝒒 𝑗 ), which the sender concatenates with its programmed keys to build the keyvalue pairs as {(C𝑗S ∥𝑘 ∥𝑞 𝑗,𝑘 +𝑡, 0∥𝑠 𝑗,𝑘 )} 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑡 ∈ [-𝛿,𝛿 ] , ensuring that no two key-value pairs collide. Accordingly, as mentioned in [31, 32], the receiver is supposed to evaluate the so-OPPRF at inR puts {C𝑖,𝑧 ∥𝑘 ∥𝑤𝑖,𝑘 }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] to maintain correctness, where

Efficient Fuzzy PSI under One-Sided Assumptions R {C𝑖,𝑧 }𝑧 ∈ [2𝑑 ] = neigh2𝛿 (𝒘𝑖 ) (see Section 3.3) denotes the identifiers of all neighboring cells for 𝒘𝑖 . This is because two mutually matching points do not necessarily reside in the same cell; they may also fall into neighboring cells. Then, after evaluation, the two parR R S S ties obtain packed shares 𝑒𝑖,𝑘,𝑧 ∥𝑟𝑖,𝑘,𝑧 and 𝑒𝑖,𝑘,𝑧 ∥𝑟𝑖,𝑘,𝑧 , respectively. The remaining steps follow the same process in multi-point fuzzy matching. For the detailed construction, we refer the reader to Section 5.2. Receiver-sided unique cell assumption. In this case, each cell contains at most one receiver point. Symmetrically, the receiver concatenates the cell identifier C𝑖R with its programmed keys to form the key-value pairs {(C𝑖R ∥𝑘 ∥𝑤𝑖,𝑘 + 𝑡, 0)}𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑡 ∈ [-𝛿,𝛿 ] , ensuring collision-freedom. The sender then evaluates the so-OPPRF at S S inputs {C𝑗,𝑧 ∥𝑘 ∥𝑞 𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] , where {C𝑗,𝑧 }𝑧 ∈ [2𝑑 ] denotes all candidate cell identifiers for 𝒒 𝑗 . Then, after evaluation, the two R S parties obtain shares 𝑒 𝑗,𝑘,𝑧 and 𝑒 𝑗,𝑘,𝑧 , respectively. The remaining steps also follow the same process in multi-point fuzzy matching. For the detailed construction, we refer the reader to Section 5.3.

4.4

Optimizations from Prefix Trie Techniques without Superlinear Overhead

In this section, we describe how to non-trivially incorporate prefixtrie techniques [10, 32] into our protocol to achieve 𝑂 (log 𝛿) complexity in 𝛿, in contrast to the superlinear 𝑂 ((log 𝛿)𝑑 ) complexity incurred by prior works [10, 32]. For clarity, we focus on the construction under the receiver-sided assumption; the sender-sided case follows analogously and is deferred to Appendix I.1. Dang et al. [10] and van Baarsen and Pu [32] introduced an optimization that represents each interval [𝑤𝑖,𝑘 − 𝛿, 𝑤𝑖,𝑘 + 𝛿] via 𝜇 = 𝑂 (log 𝛿) prefixes, reducing the number of programmed points from 𝑂 (𝛿) to 𝑂 (log 𝛿). As a trade-off, however, the sender must evaluate the OPPRF along all 𝜇 prefix paths of 𝑞 𝑗,𝑘 to maintain correctness, obtaining outputs {𝑒 𝑗,𝑘,ℎ }ℎ∈ [𝜇 ] . For each dimension 𝑘, since the sender has no knowledge of which prefix is valid, it must Í exhaustively search all combinations 𝑘 ∈ [𝑑 ] 𝑒 𝑗,𝑘,ℎ𝑘 for ℎ𝑘 ∈ [𝜇] and compare each against the target value, yielding a complexity2 of 𝑂 ((log 𝛿)𝑑 ) (or 𝑂 ((2 log 𝛿)𝑑 ) for 𝐿𝑝 distance [10]). Dimension-by-dimension Filtering. Our key observation is that, for each dimension, at most one prefix can match the target interval, rendering all other prefixes unnecessary. This allows both parties to prune the search space on a per-dimension basis by discarding non-matching prefixes, rather than enumerating all prefix combinations across dimensions as in [10, 32]. Since the exponential blowup in prior works arises precisely from taking the Cartesian product of per-dimension prefix sets, retaining only one candidate prefix per dimension collapses the search space from 𝑂 ((log 𝛿)𝑑 ) combinations to 𝑂 (𝑑 · log 𝛿). Specifically, we denote the prefixes of the interval centered at 𝑤𝑖,𝑘 as {𝑤𝑖,𝑘,ℎ }ℎ∈ [𝜇 ] = PxTrie(𝑤𝑖,𝑘 − 𝛿, 𝑤𝑖,𝑘 + 𝛿), and the prefix paths of 𝑞 𝑗,𝑘 as {𝑞 𝑗,𝑘,ℎ }ℎ∈ [𝜇 ] = PxPath(𝑞 𝑗,𝑘 , 𝛿), where 𝜇 = 𝑂 (log 𝛿) denotes the number of prefixes. The sender evaluates the so-OPPRF at S R S inputs C𝑗,𝑧 ∥𝑘 ∥𝑞 𝑗,𝑘,ℎ , and the parties obtain shares 𝑒 𝑗,𝑘,𝑧,ℎ and 𝑒 𝑗,𝑘,𝑧,ℎ .

2 This can be reduced to 𝑂 ( (log 𝛿 ) 𝑑/2 ) via the meet-in-the-middle technique, but the

complexity still grows rapidly for large 𝛿 .

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

According to Lemma 3.1, if 𝑞 𝑗,𝑘 falls within [𝑤𝑖,𝑘 −𝛿, 𝑤𝑖,𝑘 +𝛿], there R S exists exactly one ℎ ∗ ∈ [𝜇] such that 𝑒 𝑗,𝑘,𝑧,ℎ ∗ + 𝑒 𝑗,𝑘,𝑧,ℎ ∗ = 0. ∗ To extract this unique index ℎ and drop out all other nonmatching indices, we introduce a new primitive termed conditional 𝑓 ,𝜇 selection FConSel in Figure 10. Concretely, it takes two tuples of 𝜇 secret-shared values (𝑒 1R , . . . , 𝑒 𝜇R ) and (𝑒 1S , . . . , 𝑒 𝜇S ) as input, and outputs two random shares (𝑦1, 𝑦2 ) such that 𝑦1 + 𝑦2 = 𝑒ℎR∗ + 𝑒ℎS∗ if there exists a unique index ℎ ∗ ∈ [𝜇] with 𝑓 (𝑒ℎR∗ , 𝑒ℎS∗ ) = 1, and 𝑦1 + 𝑦2 is uniformly random otherwise. Here, we instantiate the condition function 𝑓 as an equality check Eq and use the equality R S 𝑒 𝑗,𝑘,𝑧,ℎ = −𝑒 𝑗,𝑘,𝑧,ℎ as the condition. Consequently, for each dimension 𝑘, both parties input their Eq,𝜇 R S per-prefix shares {𝑒 𝑗,𝑘,𝑧,ℎ }ℎ∈ [𝜇 ] and {−𝑒 𝑗,𝑘,𝑧,ℎ }ℎ∈ [𝜇 ] to FConSel and R S receive a single pair of fresh shares (𝑣 𝑗,𝑘,𝑧 , 𝑣 𝑗,𝑘,𝑧 ). Lemma 3.1 ensures that at most one prefix matches per dimension, so this functionality is well-defined. After this process, each dimension retains exactly one candidate prefix, and therefore yields just one combination across all dimensions, in contrast to the 𝑂 ((log 𝛿)𝑑 ) combinations in prior works. The complexity of FConSel is 𝑂 (log 𝛿) for each dimension, and 𝑂 (𝑑 · log 𝛿) across all dimensions. R S Given the shares (𝑣 𝑗,𝑘,𝑧 , 𝑣 𝑗,𝑘,𝑧 ), with the prefix index eliminated, the remaining steps follow the same procedure as in the nonoptimized construction of Section 4.3.

5

Fuzzy PSI under Unique Cell Assumptions

In this section, we present our protocols for general 𝐿𝑝 ∈ [1,∞] distances under one-sided unique cell assumptions. That is, only one party (either the sender or the receiver) is required to have at most one point in each cell, while the other party’s set may follow an arbitrary distribution.

𝑓

Functionality FConRand Parameters: Sender S and Receiver R. Condition predicate function 𝑓 (·, ·) where 𝑓 can be an equality or a comparison function. Functionality: (1) Wait for input (𝑒 S , 𝑣 S ) from S and (𝑒 R , 𝑣 R ) from R. (2) Compute 𝑏 := 𝑓 (𝑒 S , 𝑒 R ) (3) Generate random shares 𝑧 S , 𝑧 R such that 𝑧 S + 𝑧 R = 𝑣 S + 𝑣 R if 𝑏 = 1, and sample 𝑧 S , 𝑧 R uniformly at random otherwise. (4) Output 𝑧 S to S and 𝑧 R to R

Figure 6: Functionality of conditional randomization.

5.1

Building Block

Before presenting our fuzzy PSI construction, we introduce a building block for preventing information leakage. Specifically, it takes two tuples (𝑒 S , 𝑣 S ) and (𝑒 R , 𝑣 R ) as input from the respective parties, and randomizes the values 𝑣 S and 𝑣 R depending on whether the conditions 𝑒 S and 𝑒 R satisfy a predefined criterion 𝑓 . The ideal functionality of Conditional Randomization is given in Figure 6. We realize this functionality efficiently via a customized secretshared multiplexer protocol [29]. The conditional function 𝑓 (·, ·) returns a boolean result based on a specified condition, and can be

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Xinpeng Yang et al.

Protocol Π ConRand

∞ Protocol Π𝐿FPSI

Parameters: Functionality FMUX , FssPEQT and FssCMP . Threshold 𝛿 𝑝 Input: S inputs (𝑒 S , 𝑣 S ) and R inputs (𝑒 R , 𝑣 R ). Protocol: (1) If 𝑓 = Eq, S and R invoke FssPEQT , where S inputs 𝑒 S and R inputs 𝑒 R . S receives 𝑏 S , and R receives 𝑏 R where 𝑏 R ⊕ 𝑏 S = 1{𝑒 R = 𝑒 S }. (2) If 𝑓 = Cmp, S and R invoke FssCMP , where S inputs 𝑒 S and R inputs 𝑒 R . S receives 𝑏 S , and R receives 𝑏 R where 𝑏 R ⊕ 𝑏 S = 1{𝑒 R + 𝑒 S ≤ 𝛿 𝑝 }. (3) S randomly samples 𝑟 S and R randomly samples 𝑟 R . (4) S and R invoke FMUX , where S inputs (1 ⊕ 𝑏 S , 𝑟 S ) and R inputs (𝑏 R , 𝑟 R ). S receives 𝑚 S and R receives 𝑚 R . (5) S outputs 𝑧 S := 𝑣 S + 𝑚 S and R outputs 𝑧 R := 𝑣 R + 𝑚 R .

Parameters: Sender S and receiver R with input sizes 𝑚 and 𝑛. Threshold 𝛿. Bit length 𝜆 ′ = 𝜆 + 𝑑 + log 𝑚𝑛, ℓ = 𝜆 + 𝑑 + log 𝑛 and 𝑢 = log|U| Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ U𝑑 ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ U𝑑 ×𝑛 . Protocol: (1) For 𝑗 ∈ [𝑚], S computes C𝑗S = cell2𝛿 (𝒒 𝑗 ). For 𝑖 ∈ [𝑛], R R } computes { C𝑖,𝑧 𝑧 ∈ [2𝑑 ] = neigh2𝛿 (𝒘𝑖 )

𝑓

Figure 7: Protocol of conditional randomization.

instantiated with either an equality or a comparison function. Depending on the choice of 𝑓 , we refer to this functionality as Equalityconditional Randomization (EqRand) or Comparison-conditional Randomization (CmpRand) in the remainder of this paper. The protocol is given in Figure 7 and we defer the proof in Appendix G.8.

5.2

Protocols for Sender-sided Setting

Since we have already presented the main idea for the 𝐿∞ distance in Section 4.2.1 and Section 4.3, we directly provide the detailed protocol in Figure 8. Its security proof is deferred to Appendix G.2. ∞ Theorem 5.1. The protocol Π𝐿FPSI in Figure 8 securely realizes the functionality FFPSI for 𝐿∞ distance against semi-honest adversaries Eq in the (Fso-OPPRF ,FConRand )-hybrid model, assuming 𝐻 is a random oracle.

𝐿𝑝 distance. We here focus on how to support arbitrary 𝐿𝑝 distances. Our key observation is the fact that dist𝑝 (𝒘𝑖 , 𝒒 𝑗 ) ≤ 𝛿 implies dist∞ (𝒘𝑖 , 𝒒 𝑗 ) ≤ 𝛿, and we therefore could reuse most parts of the 𝐿∞ construction with only minor modifications. In the 𝐿∞ setting, the sender programs the value 0∥𝑠 𝑗,𝑘 , where 0 serves as an indicator of whether 𝒘𝑖 is close to some 𝒒 𝑗 , as described in Section 4.2.1. For 𝐿𝑝 distance, the sender instead encodes |𝑡 |𝑝 ∥𝑠 𝑗,𝑘 , where |𝑡 |𝑝 captures the per-dimension distance contribution when 𝑤𝑖,𝑘 − 𝑞 𝑗,𝑘 = 𝑡 for some 𝑡 ∈ [−𝛿, 𝛿]. The receiver proceeds as before, R evaluating the so-OPPRF at C𝑖,𝑧 ∥𝑘 ∥𝑤𝑖,𝑘 . After aggregating across R S all dimensions, 𝑑𝑖,𝑧 and 𝑑𝑖,𝑧 are secret shares of the 𝑝-th power of the distance between 𝒘𝑖 and the candidate 𝒒 𝑗 , provided they are potentially matched. To avoid the similar leakage mentioned in R Section 4.2.1, we invoke the CmpRand to randomize shares 𝑟𝑖,𝑧 and S R S 𝑝 𝑟𝑖,𝑧 depending on the comparison condition 𝑑𝑖,𝑧 + 𝑑𝑖,𝑧 ≤ 𝛿 . The remaining steps are identical to those in the 𝐿∞ setting, allowing the receiver to obtain all valid matches. We defer the detailed protocol in Figure 23 of Appendix H.1.

5.3

Protocols for Receiver-sided Setting

Since we have presented our idea in Section 4.2.2 and Section 4.3, we directly give the protocol under the receiver-sided assumption

(2) S sets List = { ( C𝑗S ∥𝑘 ∥𝑞 𝑗,𝑘 + 𝑡, 0ℓ ∥𝑠 𝑗,𝑘 ) } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑡 ∈ [−𝛿,𝛿 ] Í $ and computes 𝑠 𝑗 = 𝑘 ∈ [𝑑 ] 𝑠 𝑗,𝑘 where 𝑠 𝑗,𝑘 ← F2𝜅 . (3) R and S invoke functionality Fso-OPPRF where S inR ∥𝑘 ∥𝑤 } puts List and R inputs { C𝑖,𝑧 𝑖,𝑘 𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] . R R ∥𝑟 R } receives {𝑒𝑖,𝑘,𝑧 , and S receives 𝑖,𝑘,𝑧 𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] S ∥𝑟 S } {𝑒𝑖,𝑘,𝑧 and O 𝐹 . 𝑖,𝑘,𝑧 𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] R = Í R (4) For 𝑖 ∈ [𝑛], 𝑧 ∈ [2𝑑 ], R computes 𝑒𝑖,𝑧 𝑘 ∈ [𝑑 ] 𝑒𝑖,𝑘,𝑧 and Í R = R , and S computes 𝑒 S = Í S 𝑟𝑖,𝑧 𝑟 𝑒 𝑘 ∈ [𝑑 ] 𝑖,𝑘,𝑧 𝑘 ∈ [𝑑 ] 𝑖,𝑘,𝑧 and 𝑖,𝑧 S =Í S . 𝑟𝑖,𝑧 𝑟 𝑘 ∈ [𝑑 ] 𝑖,𝑘,𝑧 Eq

(5) For 𝑖 ∈ [𝑛], 𝑧 ∈ [2𝑑 ], R and S invoke FConRand where R R , 𝑟 R ) and S inputs (−𝑒 S , 𝑟 S ). R receives 𝑣 R and inputs (𝑒𝑖,𝑧 𝑖,𝑧 𝑖,𝑧 𝑖,𝑧 𝑖,𝑧 S . S receives 𝑣𝑖,𝑧 S to R, who reconstructs (6) For 𝑖 ∈ [𝑛], 𝑧 ∈ [2𝑑 ], S sends 𝑣𝑖,𝑧 S R 𝑣𝑖,𝑧 = 𝑣𝑖,𝑧 + 𝑣𝑖,𝑧 . ′

(7) S computes 𝑋 = {𝐻𝜆 ′ +𝑑𝑢 (𝑠 𝑗 ) ⊕ (0𝜆 ∥𝒒 𝑗 ) } 𝑗 ∈ [𝑚] and sends shuffled 𝑋 to R. (8) R sets 𝐼 = ∅ and parses 𝑋 as {𝑥 𝑗 } 𝑗 ∈ [𝑚] . For 𝑗 ∈ [𝑚], 𝑖 ∈ ′ [𝑛], 𝑧 ∈ [2𝑑 ], if 𝐻𝜆 ′ +𝑑𝑢 (𝑣𝑖,𝑧 ) ⊕ 𝑥 𝑗 = 0𝜆 ∥𝒒, R updates 𝐼 = 𝐼 ∪ {𝒒}.

Figure 8: Protocol of fuzzy PSI for 𝐿∞ distance under sendersided unique cell assumption. for 𝐿∞ distance in Figure 9. The security proof is deferred to Appendix G.4. ∞ Theorem 5.2. The protocol Π𝐿FPSI in Figure 9 securely realizes the functionality FFPSI for 𝐿∞ distance against semi-honest adversaries in the (Fso-OPPRF ,FEq ,FOT )-hybrid model.

𝐿𝑝 distance. We next show how to extend the protocol to 𝐿𝑝 distance. Similarly, the receiver now programs |𝑡 |𝑝 in place of 0 as in the 𝐿∞ setting. As noted in Section 4.2.2, invoking conditional randomization is unnecessary under the receiver-sided assumption, since the receiver does not reconstruct 𝑟 𝑗,𝑧 . By the correctness of R S Fso-OPPRF , 𝑟 𝑗,𝑧 and 𝑟 𝑗,𝑧 are secret shares of the 𝑝-th power of the distance between 𝒘𝑖 and the candidate 𝒒 𝑗 . It therefore suffices to test R S whether 𝑟 𝑗,𝑧 + 𝑟 𝑗,𝑧 falls within interval [0, 𝛿 𝑝 ]. A natural approach would be to invoke the secure comparison FssCMP ; however, since the output need not be secret-shared, we instead realize this check via an interval test (see Appendix E), following [7, 32]. 𝛿𝑝 Specifically, the two parties invoke functionality FInterval , and R S the receiver obtains outputs 𝑏 𝑗,𝑧 = 1{𝑟 𝑗,𝑧 + 𝑟 𝑗,𝑧 ≤ 𝛿 𝑝 }. Since 𝑞 𝑗 may match multiple receiver elements, the receiver aggregates the Ô per-cell results as 𝑏 𝑗 = 𝑧 ∈ [2𝑑 ] 𝑏 𝑗,𝑧 . Finally, 𝑏 𝑗 serves as the choice bit, and the sender transfers the matching elements to the receiver

Efficient Fuzzy PSI under One-Sided Assumptions

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

∞ Protocol Π𝐿FPSI

Functionality FConSel

Parameters: Sender S and receiver R with input sizes 𝑚 and 𝑛. Threshold 𝛿. Bit length ℓ = 𝜆 + 𝑑 + log 𝑚. Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ U𝑑 ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ U𝑑 ×𝑛 . Protocol: (1) For 𝑖 ∈ [𝑛], R computes C𝑖R = cell2𝛿 (𝒘𝑖 ). S shuffles 𝑄 and S } computes { C𝑗,𝑧 𝑧 ∈ [2𝑑 ] = neigh2𝛿 (𝒒 𝑗 ) for 𝑗 ∈ [𝑚]. (2) R sets List = { ( C𝑖R ∥𝑘 ∥𝑤𝑖,𝑘 + 𝑡, 0ℓ ) }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑡 ∈ [-𝛿,𝛿 ] . (3) R and S invoke functionality Fso-OPPRF where R inputs S ∥𝑘 ∥𝑞 List and S inputs { C𝑗,𝑧 𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] . R reR ceives {𝑒 𝑗,𝑘,𝑧 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] and O 𝐹 , and S receives

Parameters: Sender S and Receiver R. Condition function 𝑓 (·, ·) where 𝑓 can be an equality or a comparison function. Input size 𝜇 Functionality: (1) Wait for input (𝑒 1S , · · ·, 𝑒 𝜇S ) from S and (𝑒 1R , · · ·, 𝑒 𝜇R ) from R, where there exists at most one (𝑒𝑖S , 𝑒𝑖R ) with 𝑓 (𝑒𝑖S , 𝑒𝑖R ) = 1. (2) Compute 𝑏𝑖 := 𝑓 (𝑒𝑖S , 𝑒𝑖R ) for all 𝑖 ∈ [𝜇 ]. (3) Generate random shares 𝑧 S , 𝑧 R such that 𝑧 S + 𝑧 R = 𝑒𝑖S + 𝑒𝑖R if there exists 𝑏𝑖 = 1, and sample 𝑧 S , 𝑧 R uniformly at random otherwise. (4) Output 𝑧 S to S and 𝑧 R to R.

𝑓 ,𝜇

Figure 10: Functionality of conditional selection.

{𝑒 S𝑗,𝑘,𝑧 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] . Í (4) For 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ], R computes 𝑣 R𝑗,𝑧 = 𝑘 ∈ [𝑑 ] 𝑒 R𝑗,𝑘,𝑧 , and S Í S S computes 𝑣 𝑗,𝑧 = 𝑘 ∈ [𝑑 ] 𝑒 𝑗,𝑘,𝑧 . (5) For 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ], R and S invoke FEq where R inputs 𝑣 R𝑗,𝑧 and S inputs −𝑣 S𝑗,𝑧 . R receives 𝑏 𝑗,𝑧 = 1{𝑣 R𝑗,𝑧 = −𝑣 S𝑗,𝑧 }. Ô

Eq,𝜇

Protocol Π ConSel Parameters: Ideal functionality FMUX and FssPEQT . Input: S inputs {𝑒𝑖S }𝑖 ∈ [𝜇 ] and R inputs {𝑒𝑖R }𝑖 ∈ [𝜇 ] where there exists at most one 𝑒𝑖S = 𝑒𝑖R . Protocol: (1) S and R invoke FssPEQT , where S inputs {𝑒𝑖S }𝑖 ∈ [𝜇 ] and R inputs {𝑒𝑖R }𝑖 ∈ [𝜇 ] . S receives {𝑏𝑖S }𝑖 ∈ [𝜇 ] ∈ {0, 1} 𝜇 , and R receives {𝑏𝑖R }𝑖 ∈ [𝜇 ] ∈ {0, 1} 𝜇 . É S R := (2) S computes 𝑏 S := 𝑖 ∈ [𝜇 ] 𝑏𝑖 and R computes 𝑏 É R 𝑖 ∈ [𝜇 ] 𝑏𝑖 .

(6) For 𝑗 ∈ [𝑚], R computes 𝑏 𝑗 = 𝑧 ∈ [2𝑑 ] 𝑏 𝑗,𝑧 . (7) For 𝑗 ∈ [𝑚], R and S invoke functionality FOT where R inputs 𝑏 𝑗 and S inputs (⊥, 𝒒 𝑗 ). R receives 𝒖 𝑗 . (8) R outputs 𝐼 = {𝒖 𝑗 | 𝑏 𝑗 = 1 for 𝑗 ∈ [𝑚] }.

Figure 9: Protocol of fuzzy PSI for 𝐿∞ distance under receiversided unique cell assumption.

(3) S randomly samples 𝑟 S and R randomly samples 𝑟 R . (4) S and R invoke FMUX , where S inputs (1 ⊕ 𝑏 S , 𝑟 S ) and R inputs (𝑏 R , 𝑟 R ). S receives 𝑚 S and R receives 𝑚 R . (5) S outputs 𝑚 S and R outputs 𝑚 R .

via an OT protocol. We defer the detailed protocol in Figure 24 of Appendix H.2.

6

Optimized Fuzzy PSI from Prefix Trie

In this section, we optimize our protocols to achieve 𝑂 (log 𝛿) complexity in the threshold 𝛿 via prefix trie techniques. We introduce a core building block that resolves the exponential complexity arising from the incorporation of prefix trie techniques. 𝑓 ,𝜇 The ideal functionality is given in Figure 10. Functionality FConSel takes as input two sets of 𝜇 values and selects a unique pair based on a condition 𝑓 . Specifically, if there exists a unique index 𝑖 such that 𝑓 (𝑒𝑖S , 𝑒𝑖R ) = 1, it outputs fresh random shares summing to 𝑒𝑖S + 𝑒𝑖R ; otherwise, it outputs uniformly random shares. For each dimension, this functionality acts as a filter, extracting only one prefix and discarding all non-matching prefixes, thereby avoiding exponential complexity. It is worth noting that this functionality is predicated on there being at most one pair of inputs satisfying 𝑓 , as it produces only a single pair of outputs. The uniqueness of the matching prefix is established in Lemma 3.1, ensuring that this functionality can be safely adopted without compromising correctness when we instantiate the 𝑓 as an equality test function Eq in our protocol. The concrete construction is presented in Figure 11, and we refer to it as Equality-conditional Selection (EqSel). When 𝜇 = 1, this functionality reduces to a special case of EqRand in which the value 𝑓 is the condition itself. Its correctness follows that of FConRand , and we defer the security proof to Appendix G.9. We have presented our idea to incorporate prefix trie in Section 4.4, and the prefix-optimized protocol under the receiver-sided assumption for 𝐿∞ distance is illustrated in Figure 12. We defer the

Figure 11: Protocol of equality-conditional selection.

security proof in Appendix G.6. The protocols for 𝐿𝑝 distances can be optimized analogously, and we defer the details to Appendix I. ∞ Theorem 6.1. The protocol Π𝐿FPSI-Px in Figure 12 securely realizes the functionality FFPSI for 𝐿∞ distance against semi-honest adverEq,𝜇 saries in the (Fso-OPPRF ,FConSel ,FEq ,FOT )-hybrid model.

7

Fuzzy PSI for Unique Block Assumptions

We further consider a sparser distribution, termed unique block (refer to Appendix F), in which each cell intersects with at most one 𝐿∞ ball centered at a receiver point. This distribution guarantees that each receiver point’s 𝐿∞ ball occupies a unique block and is therefore associated with a collision-free set of 2𝑑 neighboring cells. Unlike the unique cell setting, our insight is to reverse the roles of the two parties in the spatial hashing procedure: the receiver programs all 2𝑑 candidate cells without collision, while the sender evaluates only the single cell containing its point. This shifts the 2𝑑 factor from the evaluation side to the programming side. As noted in [34], programming the so-OPPRF primarily involves OKVS [28] encoding operations, which is substantially cheaper than evaluating the so-OPPRF; exploiting this asymmetry therefore yields a more efficient construction.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Xinpeng Yang et al.

∞ Protocol Π𝐿FPSI-Px

∞ Protocol Π𝐿FPSI

Parameters: Threshold 𝛿. Bit length ℓ = 𝜆 + 𝑑 + log 𝑚𝑑𝜇. Prefix length 𝜇 = log 𝛿 + 2 Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ U𝑑 ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ U𝑑 ×𝑛 . Protocol: (1) For 𝑖 ∈ [𝑛], R computes C𝑖R = cell2𝛿 (𝒘𝑖 ). S shuffles 𝑄 and S } computes { C𝑗,𝑧 𝑧 ∈ [2𝑑 ] = neigh2𝛿 (𝒒 𝑗 ) for 𝑗 ∈ [𝑚]. (2) R sets List = { ( C𝑖R ∥𝑘 ∥ 𝑤˜ 𝑖,𝑘,ℎ , 0ℓ ) }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ] where { 𝑤˜ 𝑖,𝑘,ℎ }ℎ∈ [𝜇 ] = PxTrie(𝑤𝑖,𝑘 − 𝛿, 𝑤𝑖,𝑘 + 𝛿 ). S ∥𝑘 ∥ 𝑞˜ (3) S computes query = { C𝑗,𝑧 𝑗,𝑘,ℎ } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ],ℎ∈ [𝜇 ] where {𝑞˜ 𝑗,𝑘,ℎ }ℎ∈ [𝜇 ] = PxPath(𝑞 𝑗,𝑘 , 𝛿 ). (4) R and S invoke functionality Fso-OPPRF where R inputs List and S inputs query. R receives {𝑒 R𝑗,𝑘,𝑧,ℎ } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ],ℎ∈ [𝜇 ] and O 𝐹 , and S receives

Parameters: Sender S and receiver R with input sizes 𝑚 and 𝑛. Threshold 𝛿. Bit length ℓ = 𝜆 + log 𝑚. Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ U𝑑 ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ U𝑑 ×𝑛 . Protocol: R } (1) For 𝑖 ∈ [𝑛], R computes { C𝑖,𝑧 𝑧 ∈ [2𝑑 ] = neigh2𝛿 (𝒘𝑖 ). S shuffles 𝑄 and computes C𝑗S = cell2𝛿 (𝒒 𝑗 ) for 𝑗 ∈ [𝑚]. R ∥𝑘 ∥𝑤 ℓ (2) R sets List = { ( C𝑖,𝑧 𝑖,𝑘 + 𝑡, 0 ) }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ],𝑡 ∈ [-𝛿,𝛿 ] . (3) R and S invoke functionality Fso-OPPRF where R inputs List and S inputs { C𝑗S ∥𝑘 ∥𝑞 𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ] . R receives {𝑒 R𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ] and O 𝐹 , and S receives {𝑒 S𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ] . Í (4) For 𝑗 ∈ [𝑚], R computes 𝑟 𝑗R = 𝑘 ∈ [𝑑 ] 𝑒 R𝑗,𝑘 , and S computes Í 𝑟 𝑗S = 𝑘 ∈ [𝑑 ] 𝑒 S𝑗,𝑘 . (5) For 𝑗 ∈ [𝑚], R and S invoke functionality FEq where R inputs 𝑟 𝑗R and S inputs −𝑟 𝑗S . R receives 𝑏 𝑗 = 1{𝑟 𝑗R = −𝑟 𝑗S }. (6) For 𝑗 ∈ [𝑚], R and S invoke functionality FOT where R inputs 𝑏 𝑗 and S inputs (⊥, 𝒒 𝑗 ). R receives 𝒖 𝑗 . (7) R outputs {𝒖 𝑗 | 𝑏 𝑗 = 1 for 𝑗 ∈ [𝑚] }.

{𝑒 S𝑗,𝑘,𝑧,ℎ } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ],ℎ∈ [𝜇 ] . (5) For 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑 ], 𝑧 ∈ [2𝑑 ], R and S invoke funcEq,𝜇 tionality FConSel where R inputs {𝑒 R𝑗,𝑘,𝑧,ℎ }ℎ∈ [𝜇 ] and S inputs { −𝑒 S𝑗,𝑘,𝑧,ℎ }ℎ∈ [𝜇 ] . R receives 𝑣 R𝑗,𝑘,𝑧 and S receives 𝑣 S𝑗,𝑘,𝑧 . R =Í R (6) For 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ], R computes 𝑟 𝑗,𝑧 𝑘 ∈ [𝑑 ] 𝑣 𝑗,𝑘,𝑧 , and S Í S = S computes 𝑟 𝑗,𝑧 𝑘 ∈ [𝑑 ] 𝑣 𝑗,𝑘,𝑧 . (7) For 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ], R and S invoke functionality FEq where R and S inputs −𝑟 S . R receives 𝑏 R R inputs 𝑟 𝑗,𝑧 𝑗,𝑧 = 1{𝑟 𝑗,𝑧 = 𝑗,𝑧 S }. −𝑟 𝑗,𝑧 Ô (8) For 𝑗 ∈ [𝑚], R computes 𝑏 𝑗 = 𝑧 ∈ [2𝑑 ] 𝑏 𝑗,𝑧 . (9) For 𝑗 ∈ [𝑚], R and S invoke functionality FOT where R inputs 𝑏 𝑗 and S inputs (⊥, 𝒒 𝑗 ). R receives 𝒖 𝑗 . (10) R outputs 𝐼 = {𝒖 𝑗 | 𝑏 𝑗 = 1 for 𝑗 ∈ [𝑚] }.

Figure 12: Protocol of prefix-optimized fuzzy PSI for 𝐿∞ distance under receiver-sided unique cell assumption. The detailed protocol for 𝐿∞ distance is presented in Figure 13 and the security proof is deferred to Appendix G.7. Constructions for general 𝐿𝑝 distances and their prefix-optimized variants are provided in Appendix J. ∞ Theorem 7.1. The protocol Π𝐿FPSI in Figure 13 securely realizes the functionality FFPSI for 𝐿∞ distance against semi-honest adversaries in the (Fso-OPPRF ,FEq ,FOT )-hybrid model.

8

Evaluation

We provide a full implementation of our protocols, available at https://github.com/Th0masAndy/FPSI-One-Sided. All experiments are conducted on a single server equipped with AMD EPYC 9554 processor and 512 GB of RAM, with the sender and receiver emulated as two separate threads. Each experiment is repeated ten times, and we report the average total running time and communication cost. We set the computational and statistical security parameters to 𝜅 = 128 and 𝜆 = 40, respectively. For implementation, we adopt the so-OPPRF from [2, 34], silent OT from libOTe3 , secret-shared comparison from [17], and instantiate hash functions using BLAKE34 . 3 https://github.com/osu-crypto/libOTe 4 https://github.com/BLAKE3-team/BLAKE3

Figure 13: Protocol of fuzzy PSI for 𝐿∞ distance under receiver-sided unique block assumption. Comparison Baselines. We compare our protocols with state-ofthe-art fuzzy PSI constructions under one-sided assumptions [6, 10, 31]. The evaluation is divided according to two assumptions: unique cell and unique block. Under the unique cell assumption, we compare against [6, 31], as our unique cell assumption is strictly weaker than the 2𝛿-apart assumption of [31] and equivalent to the miniuniverse assumption of [6]. Under the unique block assumption, we compare against [10, 31], since our unique block assumption is strictly weaker than the 4𝛿-apart assumption used in [10, 31]. Please refer to Appendix F for detailed comparisons of different assumptions. For fair comparison with [6], we double its radius parameter, as [6] defines 𝐿∞ balls with side length 𝛿 rather than 2𝛿. Since these baselines [6, 10, 31] consider only receiver-sided assumptions, we evaluate our protocols under the same receiversided setting. Our sender-sided results are deferred to Appendix K.2.

8.1

Performance on Unique Cell Assumptions

We compare our protocols with the state-of-the-art constructions [6, 31] for 𝐿∞ distance under the unique cell assumption in Table 2. The results show that our protocols outperform prior works in both communication and computation across most parameter settings. Since existing works do not support general 𝐿𝑝 distance under this assumption, we present our results for 𝐿1 and 𝐿2 distances in Appendix K.1. Communication. Against van Baarsen and Pu [31], our best protocol reduces communication by up to 20× at 𝑑 = 2, with the advantage growing substantially as 𝛿 increases, a direct consequence of our sublinear dependence on 𝛿 versus the linear growth of [31]. At higher dimensions (𝑑 = 4, 6), [31] achieves lower communication at small 𝛿 = 32, but our protocols overtake it as 𝛿 grows beyond 64 or 128. Against Bui et al. [6], our protocols achieve up to 282× communication reduction at 𝑑 = 6, where the communication of [6]

Efficient Fuzzy PSI under One-Sided Assumptions

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Table 2: The communication (MB) and running time (s) of fuzzy PSI for 𝐿∞ distance under the unique cell assumption. Results of our protocols for 𝐿𝑝 distance are reported in Appendix K.1, as existing works do not support this setting. “—” indicates out-of-memory or execution timeout (> 2.5h). The best result is marked in green. Size 𝑚 =𝑛

Dim. 𝑑

2

28

4

6

2

212

4

6

2

216

4

6

Protocol van Baarsen et al. [31] Bui et al. [6] Ours Ours-Px van Baarsen et al. [31] Bui et al. [6] Ours Ours-Px van Baarsen et al. [31] Bui et al. [6] Ours Ours-Px van Baarsen et al. [31] Bui et al. [6] Ours Ours-Px van Baarsen et al. [31] Bui et al. [6] Ours Ours-Px van Baarsen et al. [31] Bui et al. [6] Ours Ours-Px van Baarsen et al. [31] Bui et al. [6] Ours Ours-Px van Baarsen et al. [31] Bui et al. [6] Ours Ours-Px van Baarsen et al. [31] Bui et al. [6] Ours Ours-Px

𝛿 = 32 Comm Time 3.11 1.77 3.56 1.48 2.59 0.19 3.26 0.41 6.34 3.72 52.45 10.53 8.61 0.36 15.23 1.23 10.14 6.43 3070.90 2048.17 39.37 1.38 82.97 5.25 49.75 29.07 38.18 3.57 24.57 0.94 31.45 2.15 101.50 59.81 819.28 155.32 4.06 120.25 223.49 13.23 162.25 106.67 — — 612.54 21.07 1311.37 83.49 796.00 478.07 583.20 39.28 376.23 12.40 484.52 27.98 1624.00 970.83 13078.68 2522.63 63.12 1907.65 3579.83 219.52 2596.00 1818.51 — — 9787.03 344.87 21121.37 1380.11

𝛿 = 64 Comm Time 6.11 3.47 4.15 1.53 3.27 0.19 3.34 0.39 12.34 7.12 121.79 14.13 9.96 0.44 15.58 1.16 19.14 11.64 11695.09 2755.55 41.41 1.50 83.07 5.30 97.75 56.37 47.55 4.64 35.45 1.18 32.82 2.13 197.50 115.70 1931.30 206.54 142.02 4.85 226.21 14.06 306.25 192.80 — — 645.25 22.27 1315.45 79.59 1564.00 904.65 733.25 55.02 550.66 17.76 506.41 27.71 3160.00 1877.65 30874.60 3446.77 2256.70 75.11 3623.63 218.46 4900.00 3066.45 — — 10311.51 349.66 21186.78 1383.61

blows up due to its 𝑂 ((log 𝛿)𝑑 ) complexity. At 𝑑 = 2, the gap is smaller (1.2–1.7×), as [6] benefits from low-dimensional setting. Computation. The computational advantage is significant across all settings. Against van Baarsen and Pu [31], our protocols achieve speedups of 4–239×, with the largest gains at large 𝛿 and large set sizes, reaching over 200× at 𝑛 = 216 and 𝛿 = 512. Against Bui et al. [6], we achieve speedups of 3–4818×, with the most dramatic gains at 𝑑 = 6, where the running time of [6] becomes prohibitive due to its 𝑂 ((log 𝛿)𝑑 ) complexity. These gains stem primarily from our exclusive use of symmetric-key primitives, avoiding both the superlinear complexity of [6] and the expensive additive homomorphic operations of [31]. Effect of Prefix Optimization. These two variants expose a clear communication-computation tradeoff. The non-optimized protocol scales linearly in 𝛿 and achieves the lowest running time for small 𝛿

𝛿 = 128 Comm Time 12.11 6.95 4.32 1.71 4.63 0.23 3.42 0.43 24.34 14.31 122.19 23.61 12.68 0.57 15.58 1.22 37.14 22.08 11695.82 7516.48 45.50 1.56 83.31 5.21 193.75 112.96 50.18 6.55 57.22 1.89 34.17 2.16 389.50 228.65 1936.54 341.16 185.59 6.30 228.92 12.95 594.25 354.21 — — 710.70 25.39 1319.52 83.74 3100.00 1836.01 775.30 80.48 899.68 31.78 528.06 28.68 6232.00 3778.05 30958.79 5633.09 2955.23 95.62 3666.95 220.18 9508.00 5825.47 — — 11361.00 392.36 21252.35 1437.40

𝛿 = 256 Comm Time 24.11 14.05 4.98 1.73 7.34 0.31 3.77 0.39 48.34 27.77 248.00 28.92 18.12 0.62 15.92 1.27 73.14 43.13 — — 53.64 1.76 83.83 5.29 385.75 222.60 61.06 9.62 100.78 3.26 36.90 2.18 773.50 448.70 3954.58 453.26 272.76 8.79 234.36 13.85 1170.25 690.49 — — 841.68 27.75 1327.71 80.75 6172.00 3693.64 949.34 122.20 1598.21 48.09 571.86 31.23 12376.00 7453.94 — — 4352.80 132.53 3754.61 218.06 18724.00 — — — 13467.23 420.58 21383.25 1506.43

𝛿 = 512 Comm Time 48.11 27.98 5.15 2.07 12.83 0.37 3.77 0.40 96.34 55.63 248.02 42.94 29.06 0.75 16.26 1.28 145.14 83.55 — — 70.08 2.00 84.33 5.61 769.75 442.27 63.69 14.78 188.16 3.94 39.60 2.28 1541.50 887.83 3959.78 704.95 447.53 9.80 239.79 14.13 2322.25 1357.23 — — 1104.24 29.37 1335.89 81.50 12316.00 7499.23 991.39 240.33 2997.97 69.62 615.18 31.37 — — — — 7153.31 168.36 3841.31 220.76 37156.00 — — — 17669.67 488.08 21514.43 1399.69

(32 and 64). The prefix-optimized protocol scales logarithmically in 𝛿, making it superior in communication at large 𝛿; for instance, at 𝛿 = 512 and 𝑑 = 2, it reduces communication by up to 20× over [31] while maintaining a substantial computational advantage.

8.2

Performance on Unique Block Assumptions

We compare our protocols with the state-of-the-art constructions [10, 31] under the unique block assumption. Table 3 reports results for set size 212 as a representative case; other settings exhibit similar trends, since both prior works and our protocols scale linearly with the set size. Communication. Compared to van Baarsen and Pu [31], the communication reduction grows substantially with the threshold: at 𝛿 = 32 we achieve 6–18× reduction, increasing to 34–100× at 𝛿 = 256 and up to 67× at 𝛿 = 512. This rapid scaling is a direct

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Xinpeng Yang et al.

Table 3: The communication (MB) and running time (s) of fuzzy PSI under the unique block assumption. The set size is 𝑚 = 𝑛 = 212 . “—” indicates out-of-memory or execution timeout (> 2.5h). The best result is marked in green. Metric

Dim. 𝑑

2

𝐿∞

4

6

2

𝐿1

4

6

2

𝐿2

4

6

Protocol van Baarsen et al. [31] Dang et al. [10] Ours Ours-Px van Baarsen et al. [31] Dang et al. [10] Ours Ours-Px van Baarsen et al. [31] Dang et al. [10] Ours Ours-Px van Baarsen et al. [31] Dang et al. [10] Ours Ours-Px van Baarsen et al. [31] Dang et al. [10] Ours Ours-Px van Baarsen et al. [31] Dang et al. [10] Ours Ours-Px van Baarsen et al. [31] Dang et al. [10] Ours Ours-Px van Baarsen et al. [31] Dang et al. [10] Ours Ours-Px van Baarsen et al. [31] Dang et al. [10] Ours Ours-Px

𝛿 = 32 Comm Time 195.25 111.97 127.56 14.42 48.64 1.63 29.82 1.92 1560.25 932.15 2289.54 196.76 361.74 10.41 86.59 3.93 9360.25 5507.11 13731.49 1192.01 2141.18 60.29 301.30 8.60 195.77 112.01 312.84 155.45 51.89 1.77 80.24 3.70 1560.77 901.23 3609.97 603.43 367.31 10.78 207.22 8.90 9360.77 5481.36 22946.21 7243.12 2149.07 64.90 604.28 24.96 211.27 112.01 530.49 151.32 52.33 1.74 108.60 4.68 1576.27 896.00 6995.61 627.84 367.74 10.91 263.35 10.25 9376.27 5485.92 43227.86 7374.09 2149.51 63.81 688.17 26.87

𝛿 = 64 Comm Time 387.25 223.08 145.48 16.16 92.21 2.70 33.77 2.07 3096.25 1836.02 1576.67 142.00 710.78 20.49 98.69 4.47 — — 9443.74 821.75 4241.20 124.89 344.08 9.75 388.27 224.03 381.93 207.62 95.50 3.00 93.18 4.56 3097.27 1823.36 4944.93 5443.02 716.39 20.94 241.11 10.50 — — — — 4249.12 129.43 704.89 25.36 451.27 221.86 642.30 212.06 96.40 3.13 126.64 5.12 3160.27 1795.90 7493.30 5470.09 717.29 20.96 306.95 11.92 — — — — 4250.02 128.59 803.11 29.06

consequence of our logarithmic dependence on 𝛿, whereas [31] incurs communication growing linearly in 𝛿 or 𝛿 𝑝 . Against Dang et al. [10], our prefix-optimized protocol consistently reduces communication by 4–63× across all metrics and parameter settings, with the largest gains at higher dimension (𝑑 = 6). We note that our protocol achieves better performance at larger parameter settings, owing to the underlying silent OT [3] used in our implementation, which offers superior amortized communication efficiency for large batch generation. Computation. The computational advantage is even more pronounced. Against van Baarsen and Pu [31], our protocol achieves speedups of 63–1397× across all metrics and dimensions. Against Dang et al. [10], we achieve 8–518× speedups. These dramatic gains stem from two factors. First, our prefix-optimized protocol achieves 𝑂 (log 𝛿) complexity, while [31] scales linearly in 𝛿 and [10] incurs 𝑂 ((log 𝛿)𝑑 ) complexity. Second, our protocols rely exclusively on

𝛿 = 128 Comm Time 771.25 446.28 164.38 19.12 179.38 5.24 37.85 2.37 6168.25 3732.99 2006.78 161.69 1409.32 39.75 110.97 4.89 — — 12016.79 1013.32 8443.85 254.36 386.42 10.76 773.27 454.50 456.06 279.29 182.70 5.58 106.17 5.15 6170.27 3660.91 5517.94 5624.82 1414.96 42.03 275.20 11.76 — — — — 8451.80 258.02 805.00 28.15 1027.27 448.16 766.64 285.79 183.63 5.44 144.30 6.07 6424.27 3604.21 8644.48 5484.85 1415.90 43.00 350.33 13.68 — — — — 8452.74 252.92 917.13 31.56

𝛿 = 256 Comm Time 1539.25 893.64 183.55 18.61 353.82 11.08 41.89 2.56 12312.25 7697.61 2578.55 208.96 2806.88 77.75 123.19 5.51 — — 15450.58 1275.52 16852.49 545.97 429.03 12.25 1543.27 893.72 534.66 359.87 357.28 10.52 119.33 5.55 12316.27 7279.21 6376.92 5695.84 2812.66 83.38 309.72 12.68 — — — — 16860.58 562.71 904.95 31.66 2563.27 891.59 911.44 383.57 358.31 10.79 162.18 6.58 13336.27 7208.44 10379.32 5568.10 2813.70 84.26 394.20 14.97 — — — — 16861.62 548.45 1031.06 35.08

𝛿 = 512 Comm Time 3075.25 1806.35 201.86 25.58 702.82 20.15 45.81 2.82 — — 2866.33 280.98 5603.26 162.37 135.36 5.89 — — 17170.10 1617.10 33544.37 1302.04 472.16 13.39 3083.27 1787.95 618.78 461.89 706.39 20.70 132.42 6.21 — — — — 5609.16 168.24 343.99 14.94 — — — — 33552.58 1333.52 1004.74 40.38 7171.27 1803.15 1092.79 566.46 707.55 20.88 180.02 7.55 — — — — 5610.32 166.81 437.85 16.77 — — — — 33553.74 1311.12 1144.85 45.69

symmetric-key primitives, whereas both [10, 31] depend on expensive public-key operations such as DDH and Paillier. Effect of Prefix Optimization. The prefix-optimized variant attains the best performance in nearly all settings, in contrast to the previous case. This is because, under the unique block assumption, the dominant bottleneck is the receiver programming 2𝑑 ·𝑑·𝑛·(2𝛿+1) key-value pairs, while the sender evaluates at only 𝑑 ·𝑚 points. Incorporating prefix trie techniques reduces the receiver’s overhead by a factor of 𝑂 (𝛿/log 𝛿), while increasing the sender’s overhead by only 𝑂 (log 𝛿), yielding a clear improvement in overall efficiency. Moreover, this advantage becomes more pronounced as the dimension 𝑑 and the threshold 𝛿 increase, indicating that the prefix-optimized variant is well-suited to large-scale settings.

Efficient Fuzzy PSI under One-Sided Assumptions

9

Conclusion

In this work, we presented concretely efficient fuzzy PSI protocols for general 𝐿𝑝 ∈ [1,∞] distances under one-sided assumptions, relying solely on lightweight symmetric-key primitives. The core technique is new multi-point fuzzy matching protocols, upon which we derived protocols flexibly supporting both sender-sided and receiver-sided settings. By incorporating prefix-trie techniques, we further achieved 𝑂 (log 𝛿) complexity in the distance threshold 𝛿, improving upon the 𝑂 ((log 𝛿)𝑑 ) and 𝑂 (𝛿) complexities of prior works. Extensive experiments confirm that our protocols significantly outperform all prior works under the same assumptions.

Acknowledgments This work was supported by the Nanyang Technological University Centre in Computational Technologies for Finance (NTU-CCTF). It was also supported by the National Research Foundation, Singapore, and Cyber Security Agency of Singapore under its National Cybersecurity R&D Programme and CyberSG R&D Cyber Research Programme Office. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of NTU-CCTF, National Research Foundation, Singapore, Cyber Security Agency of Singapore as well as CyberSG R&D Programme Office, Singapore.

References [1] Navid Alamati, Pedro Branco, Nico Döttling, Sanjam Garg, Mohammad Hajiabadi, and Sihang Pu. 2021. Laconic private set intersection and applications. In Theory of Cryptography Conference. Springer, 94–125. [2] Navid Alamati, Guru-Vamsi Policharla, Srinivasan Raghuraman, and Peter Rindal. 2024. Improved alternating-moduli PRFs and post-quantum signatures. In Annual International Cryptology Conference. Springer, 274–308. [3] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. 2019. Efficient two-round OT extension and silent noninteractive secure computation. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 291–308. [4] Elette Boyle, Niv Gilboa, and Yuval Ishai. 2015. Function secret sharing. In Annual international conference on the theory and applications of cryptographic techniques. Springer, 337–367. [5] Elette Boyle, Niv Gilboa, and Yuval Ishai. 2016. Function secret sharing: Improvements and extensions. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 1292–1303. [6] Dung Bui, Gayathri Garimella, Peihan Miao, and Phuoc Van Long Pham. 2025. New Framework for Structure-Aware PSI From Distributed Function Secret Sharing. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 294–326. [7] Anrin Chakraborti, Giulia Fanti, and Michael K Reiter. 2023. Distance-Aware private set intersection. In 32nd USENIX Security Symposium (USENIX Security 23). 319–336. [8] Hao Chen, Kim Laine, and Peter Rindal. 2017. Fast private set intersection from homomorphic encryption. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 1243–1255. [9] Wutichai Chongchitmate, Steve Lu, and Rafail Ostrovsky. 2024. Approximate psi with near-linear communication. Cryptology ePrint Archive (2024). [10] Chengrui Dang, Xv Zhou, and Bei Liang. 2025. Efficient Fuzzy PSI Based on Prefix Representation. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security. 2204–2218. [11] Changyu Dong, Liqun Chen, and Zikai Wen. 2013. When private set intersection meets big data: an efficient and scalable protocol. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. 789–800. [12] Michael J Freedman, Kobbi Nissim, and Benny Pinkas. 2004. Efficient private matching and set intersection. In International conference on the theory and applications of cryptographic techniques. Springer, 1–19. [13] Ying Gao, Lin Qi, Xiang Liu, Yuanchao Luo, and Longxin Wang. 2024. Efficient fuzzy private set intersection from fuzzy mapping. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 36–68. [14] Gayathri Garimella, Benjamin Goff, and Peihan Miao. 2024. Computation efficient structure-aware psi from incremental function secret sharing. In Annual

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

International Cryptology Conference. Springer, 309–345. [15] Gayathri Garimella, Mike Rosulek, and Jaspal Singh. 2022. Structure-aware private set intersection, with applications to fuzzy matching. In Annual International Cryptology Conference. Springer, 323–352. [16] Meng Hao, Weiran Liu, Liqiang Peng, Hongwei Li, Cong Zhang, Hanxiao Chen, and Tianwei Zhang. 2024. Unbalanced Circuit-PSI from Oblivious Key-Value Retrieval. In 33rd USENIX Security Symposium (USENIX Security 24). 6435–6451. [17] Zhicong Huang, Wen-jie Lu, Cheng Hong, and Jiansheng Ding. 2022. Cheetah: Lean and fast secure Two-Party deep neural network inference. In 31st USENIX Security Symposium (USENIX Security 22). 809–826. [18] Mihaela Ion, Ben Kreuter, Erhan Nergiz, Sarvar Patel, Shobhit Saxena, Karn Seth, David Shanahan, and Moti Yung. 2017. Private intersection-sum protocol with applications to attributing aggregate ad conversions. Cryptology ePrint Archive (2017). [19] Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker, and Christian Weinert. 2019. Mobile private contact discovery at scale. In 28th USENIX Security Symposium (USENIX Security 19). 1447–1464. [20] Ágnes Kiss, Jian Liu, Thomas Schneider, N Asokan, and Benny Pinkas. 2017. Private set intersection for unequal set sizes with mobile applications. In Privacy Enhancing Technologies Symposium. De Gruyter, 177–197. [21] Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, and Ni Trieu. 2017. Practical multi-party private set intersection from symmetric-key techniques. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 1257–1272. [22] Catherine Meadows. 1986. 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, 134–134. [23] M. Naor and O. Reingold. 1997. Number-theoretic constructions of efficient pseudo-random functions. In Proceedings 38th Annual Symposium on Foundations of Computer Science. 458–467. doi:10.1109/SFCS.1997.646134 [24] Pascal Paillier. 1999. Public-key cryptosystems based on composite degree residuosity classes. In International conference on the theory and applications of cryptographic techniques. Springer, 223–238. [25] Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. 2020. PSI from PaXoS: Fast, malicious private set intersection. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 739–767. [26] Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. 2015. Phasing: Private set intersection using permutation-based hashing. In 24th USENIX Security Symposium (USENIX Security 15). 515–530. [27] Lucas Piske, Jaspal Singh, Ni Trieu, Vladimir Kolesnikov, and Vassilis Zikas. 2025. Distance-aware OT with application to fuzzy PSI. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security. 4679–4691. [28] Srinivasan Raghuraman and Peter Rindal. 2022. Blazing fast PSI from improved OKVS and subfield VOLE. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2505–2517. [29] Deevashwer Rathee, Mayank Rathee, Nishant Kumar, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. 2020. Cryptflow2: Practical 2-party secure inference. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. 325–342. [30] David Richardson, Mike Rosulek, and Jiayu Xu. 2024. Fuzzy PSI via oblivious protocol routing. Cryptology ePrint Archive (2024). [31] Aron van Baarsen and Sihang Pu. 2024. Fuzzy private set intersection with large hyperballs. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 340–369. [32] Aron van Baarsen and Sihang Pu. 2025. Fuzzy private set intersection from VOLE. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 327–360. [33] Mingli Wu and Tsz Hon Yuen. 2023. Efficient unbalanced private set intersection cardinality and user-friendly privacy-preserving contact tracing. In 32nd USENIX Security Symposium (USENIX Security 23). 283–300. [34] Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H Deng, Yonggang Wen, and Tianwei Zhang. 2026. Efficient fuzzy private set intersection from secret-shared OPRF. In 2026 IEEE Symposium on Security and Privacy (SP). IEEE, 2442–2461. [35] Cong Zhang, Yu Chen, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Anyu Wang, and Xiaoyun Wang. 2025. Fast Fuzzy PSI from Symmetric-Key Techniques. Cryptology ePrint Archive (2025).

A

Open Science

We follow the principles of the Open Science Policy. Our research artifacts, comprising the source code of the proposed protocols, benchmarking scripts, and comprehensive technical documentation, have been consolidated into an open-source repository, which is accessible at https://github.com/Th0masAndy/FPSI-One-Sided.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

B

Ethical Considerations

Stakeholder Identification and Impacts. We organize this section as a stakeholder-based analysis, distinguishing direct stakeholders (those who design, implement, or deploy our fuzzy PSI protocols) from indirect stakeholders (people and organizations affected by systems that rely on them). Direct stakeholders include the research team and organizations that integrate our protocols into privacy-preserving biometric matching systems. Indirect stakeholders include end users whose biometric templates are compared through such systems, regulators responsible for oversight of datasharing practices, and adversaries who may attempt to abuse or subvert these systems. Research Team. Our work involves no human subjects, no physical experiments, and no collection of real-world private data. All evaluations were conducted on synthetic datasets generated specifically for benchmarking, which contain no personally identifiable information. We explicitly acknowledge and respect the intellectual contributions of each team member, ensuring that authorship reflects meaningful involvement. Organizations Deploying Fuzzy PSI. Organizations that operate biometric matching services may adopt our protocols to improve efficiency and security. However, adoption may require non-trivial engineering effort for integration, incur audit costs for cryptographic review, and impose performance constraints in certain settings (e.g., high-dimensional data or large set sizes). We have documented quantitative performance benchmarks and known limitations to help deployers make informed decisions. Cryptography Community and Society. Beneficence. We propose fuzzy PSI protocols that enable parties to identify approximate matches between their data without revealing the underlying records, aligning with data-protection principles Respect for Persons. We have carefully cited prior work to ensure accurate attribution and to avoid plagiarism. Justice. Our constructions rely only on standard cryptographic assumptions and open primitives, with no proprietary dependencies, keeping the core ideas accessible to researchers and practitioners worldwide. Respect for Law and Public Interest. Our research complies with all relevant academic and cryptographic research policies. By advancing the state of the art in fuzzy PSI, this work serves the public interest by enabling privacy-preserving data collaboration that supports compliance with data-protection regulations. Publication Impacts. Our protocols may influence future research on fuzzy matching under additional distance metrics or security models. To reduce misuse or misinterpretation, we clearly state the security model, assumptions, and parameter settings under which the stated guarantees hold.

C

Generative AI Usage

This paper used LLMs (including ChatGPT and Gemini) solely to assist with grammar checking and language polishing. The LLMs did not contribute any conceptual ideas, methodological innovations, experimental designs, or analytical insights to this work. All intellectual contributions originate from the authors. The content provided to the LLMs for linguistic refinement contains no sensitive, personal, or ethically problematic information.

Xinpeng Yang et al.

D

Other Related Work

van Baarsen and Pu [31] proposed the first general fuzzy PSI construction under the “existing disjoint” assumption, requiring that each point in both parties’ sets is at least 2𝛿 apart from all other points in some dimension. The overall complexity scales as 𝑂 ((𝑑𝛿) 2 ), with no additional exponential factor. Gao et al. [13] subsequently improved this to 𝑂 (𝑑𝛿), achieving fully linear complexity for the first time. Their protocol, however, still operates under the same two-sided “existing disjoint” assumption, as the symmetric structure of their construction requires both parties’ inputs to satisfy the condition. Zhang et al. [35] adopted a stronger “𝑠-separate” assumption and proposed an efficient fuzzy PSI protocol from symmetric-key primitives, at the cost of 𝑂 (𝛿 𝑠 ) overhead, which becomes prohibitive for large 𝛿. Dang et al. [10] improved upon Gao et al. [13] under the same assumption via prefix trie techniques, reducing the overhead from 𝑂 (𝑑𝛿) to 𝑂 (𝑑 log 𝛿). This was further improved by Yang et al. [34] via secret-shared OPRF [2], eliminating the reliance on public-key primitives. Recently, van Baarsen and Pu [32] revisited their earlier construction [31] using symmetric-key primitives. Their new protocol relies on spatial hashing to map each point to a unique cell, requiring both parties’ points to be at least 2𝛿 or 4𝛿 apart to prevent additional leakage. Chongchitmate et al. [9] proposed a nearly linear fuzzy PSI protocol, but their construction requires a strong gap assumption: every pair of points across the two sets must be either close or far apart. This is a strict assumption, as it imposes a joint constraint across both parties’ inputs. While these works have achieved substantial efficiency improvements, their advantages rely on two-sided assumptions, which are harder to satisfy in real-world applications. Removing the assumption on either party’s input would render these protocols insecure, inapplicable, or subject to dramatically increased overhead. Two additional constructions operate under the arbitrary distribution setting. The first [14] incurs 𝑂 (𝑚𝑛(log 𝛿)𝑑 ) complexity, which is quadratic in the set sizes 𝑚 and 𝑛. The second [32] achieves 𝑂 ((𝑚 + 𝑛)(log 𝛿)𝑑 ) complexity. However, both constructions suffer from the worse 𝑂 ((log 𝛿)𝑑 ) factor in both communication and computation, making them far from practical. Moreover, they support only 𝐿∞ distance with no known efficient extension to general 𝐿𝑝 ∈ [1,∞] distances; we therefore omit a detailed discussion.

E Other Functionalities E.1 Interval Test Chakraborti et al. [7] introduced an efficient interval test protocol, which runs in 𝑂 (log 𝛿) complexity with respect to the interval size 𝛿. We give the ideal functionality in Figure 14.

𝛿 Functionality FInterval

Parameters: Sender S and receiver R. Threshold 𝛿. Functionality: (1) Wait for input 𝑥 S from S and 𝑥 R from R. (2) Output 1 to R if 𝑥 S + 𝑥 R ≤ 𝛿, otherwise output 0.

Figure 14: Functionality of private interval test.

Efficient Fuzzy PSI under One-Sided Assumptions

E.2

MUX

Functionality FEq

The ideal functionality of MUX is given in Figure 15.

Functionality FMUX Parameters: Sender S and receiver R. Functionality: (1) Wait for input (𝑏 0 , 𝑥 0 ) from S and (𝑏 1 , 𝑥 1 ) from R. (2) Select 𝑟 0 randomly, and set 𝑟 1 = 𝑥 0 + 𝑥 1 − 𝑟 0 if 𝑏 0 ⊕ 𝑏 1 = 1 otherwise set 𝑟 1 = −𝑟 0 . (3) Output 𝑟 0 to R and 𝑟 1 to S.

Figure 15: Functionality of MUX.

E.3

Secret-shared Private Equality Test

The ideal functionality of secret-shared private equality test is given in Figure 16.

Functionality FssPEQT Parameters: Sender S and receiver R. Functionality: (1) Wait for input 𝑥 0 from S and 𝑥 1 from R. (2) Select 𝑟 0 randomly, and set 𝑟 1 = 1 − 𝑟 0 if 𝑥 0 = 𝑥 1 otherwise set 𝑟 1 = −𝑟 0 . (3) Output 𝑟 0 to R and 𝑟 1 to S.

Figure 16: Functionality of secret-shared PEQT.

E.4

Secret-shared Comparison

The ideal functionality of secret-shared comparison is given in Figure 17.

Functionality FssCMP Parameters: Sender S and receiver R. Functionality: (1) Wait for input 𝑥 0 from S and 𝑥 1 from R. (2) Select 𝑟 0 randomly, and set 𝑟 1 = 1 − 𝑟 0 if 𝑥 0 ≥ 𝑥 1 otherwise set 𝑟 1 = −𝑟 0 . (3) Output 𝑟 0 to R and 𝑟 1 to S.

Figure 17: Functionality of secret-shared comparison.

E.5

Private Equality Test

The ideal functionality of private equality test is given in Figure 18.

F

Comparisons of Assumptions

We compare the unique cell assumption of Definition 3.1 with existing assumptions as follows.

F.1

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Unique Cell

Parameters: Sender S and receiver R. Functionality: (1) Wait for input 𝑥 0 from S and 𝑥 1 from R. (2) Set 𝑟 = 1 if 𝑥 0 = 𝑥 1 otherwise set 𝑟 = 0. (3) Output 𝑟 to R

Figure 18: Functionality of private equality test. F.1.1 Comparison with disjoint hash assumption. The disjoint hash assumption [27, 30] (abbreviated as disj. hash in Figure 2) requires the spatial hash to map each point to a distinct cell, which is identical to our unique cell assumption. However, while [27, 30] rely on this assumption in their theoretical constructions, their concrete protocols require additional assumptions on the other party. F.1.2 Comparison with mini-universe assumption. We revisit the mini-universe assumption from [6, 14]. Since [6, 14] defines 𝐿∞ balls of side length 𝛿 rather than 2𝛿, we double the radius parameter to align with our setting. Consider a 𝑑-dimensional space tiled by cells of side length 2𝛿. For any grid vertex 𝒐 = (𝑜 1, 𝑜 2, . . . , 𝑜𝑑 ), where coordinate 𝑜𝑖 is an integer multiple of 2𝛿, we define the miniuniverse with origin 𝒐 as the 𝑑-dimensional hypercube of side length 4𝛿, namely Univ𝒐 := [𝑜 1, 𝑜 1 + 4𝛿) × · · · × [𝑜𝑑 , 𝑜𝑑 + 4𝛿). For any point 𝒙 ∈ U𝑑 , we define Ball𝒙 as the 𝐿∞ ball of side length 2𝛿 with lowerleft corner at 𝒙, namely Ball𝒙 := [𝑥 1, 𝑥 1 + 2𝛿] × · · · × [𝑥𝑑 , 𝑥𝑑 + 2𝛿]. Here, we use closed intervals to align with our definition, since our ball contains exactly 2𝛿 + 1 values in each dimension, while the ball in [6, 14] only contains 2𝛿 values. Definition F.1 (Mini-Universe [6, 14]). A set 𝑊 ∈ U𝑛×𝑑 satisfies the mini-universe assumption if for every 𝒙 ∈ 𝑊 , there exists a unique mini-universe Univ𝒐 containing Ball𝒙 . In other words, for any two distinct points 𝒙, 𝒙 ′ ∈ 𝑊 with Ball𝒙 ⊆ Univ𝒐 and Ball𝒙 ′ ⊆ Univ𝒐 ′ , it holds that Univ𝒐 ≠ Univ𝒐 ′ . Below, we formally prove that the unique cell assumption is equivalent to the mini-universe assumption. Lemma F.1. A set 𝑊 ∈ U𝑛×𝑑 satisfies the unique cell assumption if and only if it satisfies the mini-universe assumption. Proof. We first show that the unique cell assumption implies the mini-universe assumption. Let 𝒙 ∈ 𝑊 lie in the grid cell with lowerleft corner 𝒐, i.e., 𝑥𝑖 ∈ [𝑜𝑖 , 𝑜𝑖 + 2𝛿) for all 𝑖 ∈ [𝑑]. Then 𝑥𝑖 + 2𝛿 < 𝑜𝑖 + 4𝛿, so [𝑥𝑖 , 𝑥𝑖 + 2𝛿] ⊂ [𝑜𝑖 , 𝑜𝑖 + 4𝛿) for all 𝑖 ∈ [𝑑]. Therefore, it holds that Ball𝒙 ⊆ Univ𝒐 , meaning every point in 𝑊 has its ball Ball𝒙 contained in the mini-universe Univ𝒐 determined by its cell’s lower-left corner 𝒐. For any two distinct points 𝒙, 𝒙 ′ ∈ 𝑊 , the unique cell assumption gives cell2𝛿 (𝒙) ≠ cell2𝛿 (𝒙 ′ ), so 𝒐 ≠ 𝒐 ′ and hence Univ𝒐 ≠ Univ𝒐 ′ . Thus the mini-universe containing each ball is unique. We next show that the mini-universe assumption implies the unique cell assumption. Let 𝒙 ∈ 𝑊 with Ball𝒙 ⊆ Univ𝒐 for some corner 𝒐. Since Ball𝒙 = [𝑥 1, 𝑥 1 + 2𝛿] × · · · × [𝑥𝑑 , 𝑥𝑑 + 2𝛿] and Univ𝒐 = [𝑜 1, 𝑜 1 + 4𝛿) × · · · × [𝑜𝑑 , 𝑜𝑑 + 4𝛿), the containment implies 𝑜𝑖 ≤ 𝑥𝑖 < 𝑜𝑖 + 2𝛿 for all 𝑖 ∈ [𝑑]. Since each 𝑜𝑖 is an integer multiple of 2𝛿, the region [𝑜 1, 𝑜 1 + 2𝛿) × · · · × [𝑜𝑑 , 𝑜𝑑 + 2𝛿) is precisely the

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

grid cell with lower-left corner 𝒐, and 𝒙 lies in this cell. For any two distinct points 𝒙, 𝒙 ′ ∈ 𝑊 with Ball𝒙 ⊆ Univ𝒐 and Ball𝒙 ′ ⊆ Univ𝒐 ′ , the mini-universe assumption gives Univ𝒐 ≠ Univ𝒐 ′ , hence 𝒐 ≠ 𝒐 ′ . By the above argument, 𝒙 and 𝒙 ′ lie in distinct cells, so cell2𝛿 (𝒙) ≠ cell2𝛿 (𝒙 ′ ). □ The difference between the two assumptions stems solely from how the 𝐿∞ ball of a point is defined: our construction centers the ball at the point, whereas the structure-aware PSI [6, 14] places the ball’s lower-left corner at the point. Despite this difference in convention, the two assumptions impose the same distributional constraint on the input set.

Xinpeng Yang et al.

2𝛿 (𝑑 1/𝑝 + 1). In particular, for 𝑝 = ∞, this reduces to dist∞ (𝒘, 𝒘 ′ ) ≥ 4𝛿. The following lemma from [31] illustrates that the 4𝛿-apart assumption is strictly stronger than the unique block assumption. Lemma F.3 ([31]). Suppose there are multiple 𝛿-radius 𝐿𝑝 balls (𝑝 ∈ [1, ∞]) distributed in a 𝑑-dimensional space which is tiled by cells of side length 2𝛿. If these balls’ centers are at least 2𝛿 (𝑑 1/𝑝 + 1) apart from each other, then there exists at most one ball intersecting with the same cell. Specifically, if 𝑝 = ∞, this holds for 𝐿∞ balls with 4𝛿-apart centers.

F.1.3 Comparison with 2𝛿-apart assumption. We recall the 2𝛿-apart assumption from [31] as follows.

G Security Proof G.1 Threat Model

Definition F.2 (2𝛿-apart). A set𝑊 ∈ U𝑛×𝑑 satisfies the 2𝛿-apart assumption if for any two distinct points 𝒘, 𝒘 ′ ∈ 𝑊 , dist𝑝 (𝒘, 𝒘 ′ ) ≥ 2𝛿𝑑 1/𝑝 . Specifically, if 𝑝 = ∞, this reduces to dist∞ (𝒘, 𝒘 ′ ) ≥ 2𝛿.

Similar to prior works [6, 10, 13, 31, 32, 34], we consider static semihonest probabilistic polynomial-time (PPT) adversaries. Namely, a PPT adversary A passively corrupts either the sender S or the receiver R at the beginning of the protocol and honestly follows the protocol specification. We use the standard simulation-based security definition for secure two-party computation. Our construction invokes multiple sub-protocols, and we use the hybrid model to describe them. By convention, a protocol invoking a functionality F is referred to as the F -hybrid model. We give the formal security definition as follows.

The following lemma from [31] illustrates that the 2𝛿-apart assumption is strictly stronger than the unique cell assumption. Intuitively, the unique cell assumption permits the 𝐿∞ balls of input points to overlap as long as their centers fall into distinct cells, whereas the 2𝛿-apart assumption ensures that these 𝐿∞ balls are pairwise disjoint. Lemma F.2 ([31]). Suppose there are multiple 𝐿𝑝 balls (𝑝 ∈ [1, ∞]) with radius 𝛿 lying in a 𝑑-dimensional space which is tiled by cells with side length 2𝛿. If these balls’ centers are at least 2𝛿𝑑 1/𝑝 apart, then for each cell, there is at most one center of the balls lying in this cell. Specifically, if 𝑝 = ∞, then the unique center holds for disjoint balls since 2𝛿𝑑 1/𝑝 degrades to 2𝛿 in this case. F.1.4 Comparison with 2𝛿-disjoint projection assumption. The 2𝛿disjoint projection assumption (abbreviated as 2𝛿-disj. proj. in Figure 2), adopted in [10, 13, 15, 31, 32, 34], requires that for every point 𝒘 ∈ 𝑊 , there exists a dimension 𝑘 such that |𝑤𝑘 − 𝑤𝑘′ | ≥ 2𝛿 for all 𝒘 ′ ∈ 𝑊 \ {𝒘}. It is strictly stronger than the unique cell assumption for general 𝐿𝑝 distances, since |𝑤𝑘 − 𝑤𝑘′ | ≥ 2𝛿 for some dimension 𝑘 implies cell2𝛿 (𝒘) ≠ cell2𝛿 (𝒘 ′ ). To the best of our knowledge, all existing constructions relying on the 2𝛿-disjoint projection assumption require it to hold for both parties’ input sets, and no known technique extends it to the onesided setting.

F.2

Unique Block

We compare the unique block assumption of Definition 3.2 with existing assumptions as follows. F.2.1 Comparison with unique cell assumption. We note that the unique block assumption is strictly stronger than the unique cell assumption, as it requires the 𝐿∞ balls to have no common cells and therefore their centers fall into different cells. F.2.2 Comparison with 4𝛿-apart assumption. We recall the 4𝛿-apart assumption from [31] as follows. Definition F.3 (4𝛿-apart). A set𝑊 ∈ U𝑛×𝑑 satisfies the 4𝛿-apart assumption if for any two distinct points 𝒘, 𝒘 ′ ∈ 𝑊 , dist𝑝 (𝒘, 𝒘 ′ ) ≥

Definition G.1. Let viewΠS (𝑥, 𝑦) and viewΠR (𝑥, 𝑦) be the views of S and R in a protocol Π, respectively, where 𝑥 is the input of S and 𝑦 is the input of R. Let out(𝑥, 𝑦) be the protocol’s output of both parties and F (𝑥, 𝑦) be the functionality’s output. Π is said to securely compute a functionality F in the semi-honest model if for every PPT adversary A there exists PPT simulators Sim S and Sim R such that for all inputs 𝑥 and 𝑦, {viewΠS (𝑥, 𝑦), out(𝑥, 𝑦)} ≈𝑐 {Sim S (𝑥, FS (𝑥, 𝑦)), F (𝑥, 𝑦)}, {viewΠR (𝑥, 𝑦), out(𝑥, 𝑦)} ≈𝑐 {Sim R (𝑦, FR (𝑥, 𝑦)), F (𝑥, 𝑦)}.

G.2 𝐿∞ Distance under Sender-sided Unique Cell Assumptions Proof. Correctness. We first consider that for some 𝒒 𝑗 ∈ 𝑄, there exists 𝒘𝑖 ∈ 𝑊 such that dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿. By the correctness R of spatial hashing, there exists an index 𝑧 ∗ ∈ [2𝑑 ] such that C𝑖,𝑧 ∗ = S C𝑗 . Since dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, it holds that |𝑞 𝑗,𝑘 − 𝑤𝑖,𝑘 | ≤ 𝛿 for all 𝑘 ∈ [𝑑]. Therefore, for each 𝑘 ∈ [𝑑], there exists 𝑡𝑘 ∈ [−𝛿, 𝛿] such that 𝑞 𝑗,𝑘 + 𝑡𝑘 = 𝑤𝑖,𝑘 . By the correctness of functionality Fso-OPPRF , R R S S ℓ 𝑒𝑖,𝑘,𝑧 ∗ ∥𝑟 𝑖,𝑘,𝑧 ∗ and 𝑒𝑖,𝑘,𝑧 ∗ ∥𝑟 𝑖,𝑘,𝑧 ∗ are the shares of 0 ∥𝑠 𝑗,𝑘 . And then the R S R S aggregated shares 𝑒𝑖,𝑧 ∗ and 𝑒𝑖,𝑧 ∗ are the shares of 0ℓ , 𝑟𝑖,𝑧 ∗ and 𝑟 𝑖,𝑧 ∗ Í R S are the shares of 𝑠 𝑗 = 𝑘 ∈ [𝑑 ] 𝑠 𝑗,𝑘 . Since 𝑒𝑖,𝑧 ∗ + 𝑒𝑖,𝑧 ∗ = 0, by the Eq

R S correctness of functionality FConRand , it holds that 𝑣𝑖,𝑧 ∗ + 𝑣 𝑖,𝑧 ∗ = 𝑠 𝑗 . Then, the R reconstructs 𝑣𝑖,𝑧 ∗ = 𝑠 𝑗 . After shuffling, there must be ′ 𝑥 𝑗 ∗ ∈ 𝑋 and 𝑥 𝑗 ∗ = 𝐻𝜆′ +𝑑𝑢 (𝑠 𝑗 ) ⊕ (0𝜆 ∥𝒒 𝑗 ). Finally, the R unmasks 𝑥 𝑗 ∗ by 𝐻𝜆′ +𝑑𝑢 (𝑣𝑖,𝑧 ∗ ) ⊕ 𝑥 𝑗 ∗ and correctly gets 𝒒 𝑗 . We then consider that for some 𝒒 𝑗 ∈ 𝑄, it holds dist∞ (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿 for any 𝒘𝑖 ∈ 𝑊 . We consider the following two cases. (1) The first case, there exists an index 𝑧 ∗ ∈ [2𝑑 ] such that R S C𝑖,𝑧 ∗ = C𝑗 . Since dist∞ (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿, it holds that there exists an

Efficient Fuzzy PSI under One-Sided Assumptions

index 𝑘 ∗ ∈ [𝑑] such that |𝑞 𝑗,𝑘 ∗ − 𝑤𝑖,𝑘 ∗ | > 𝛿. By the correctness of R R S S functionality Fso-OPPRF , the outputs 𝑒𝑖,𝑘 ∗ ,𝑧 ∗ ∥𝑟 𝑖,𝑘 ∗ ,𝑧 ∗ and 𝑒𝑖,𝑘 ∗ ,𝑧 ∗ ∥𝑟 𝑖,𝑘 ∗ ,𝑧 ∗ R R are uniformly random. Then, after aggregation, the shares 𝑒𝑖,𝑧 ∗ ∥𝑟𝑖,𝑧 ∗ S S and 𝑒𝑖,𝑧 ∥𝑟 are also uniformly random. By the correctness of ∗ 𝑖,𝑧 ∗ Eq

R S functionality FConRand , the new shares 𝑣𝑖,𝑧 ∗ and 𝑣 𝑖,𝑧 ∗ are uniformly random. After reconstruction, 𝑣𝑖,𝑧∗ is uniformly random. R (2) The second case, for any 𝑧 ∈ [2𝑑 ], it holds that C𝑖,𝑧 ≠ C𝑗S . By R R the correctness of functionality Fso-OPPRF , the outputs 𝑒𝑖,𝑘,𝑧 ∥𝑟𝑖,𝑘,𝑧 S S 𝑑 and 𝑒𝑖,𝑘,𝑧 ∥𝑟𝑖,𝑘,𝑧 are uniformly random for all 𝑧 ∈ [2 ], 𝑘 ∈ [𝑑]. Similarly, 𝑣𝑖,𝑧 is uniformly random. In both cases, 𝑣𝑖,𝑧 is uniformly random for all 𝑖 ∈ [𝑛], 𝑧 ∈ [2𝑑 ]. By setting the bit length of 𝑠 𝑗 as 𝜅 > 𝜆 + 𝑑 + log 𝑚𝑛, the probability of 𝑣𝑖,𝑧 = 𝑠 𝑗 for some 𝑗 ∈ [𝑚] is at most 2−𝜆 , which is negligible. On the other hand, if 𝑣𝑖,𝑧 ≠ 𝑠 𝑗 , the decryption 𝐻𝜆′ +𝑑𝑢 (𝑣𝑖,𝑧 ) ⊕ 𝑥 𝑗 is uniformly random for all 𝑖 ∈ [𝑛], 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ]. By setting 𝜆 ′ = 𝜆 + 𝑑 + log 𝑚𝑛, the probability of valid decryption is at most 2−𝜆 , which is negligible. A union bound shows that the receiver can obtain 𝒒 𝑗 with the probability at most 2−𝜆 (2 − 2−𝜆 ) < 2−𝜆+1 , which is negligible. This completes the correctness proof. Corrupted sender. The simulator Sim S receives the sender’s input 𝑄 and proceeds as follows:

(1) Sim S maintains a table for queries of the random oracle 𝐻 . For each query to 𝐻 , Sim S returns a consistent random value. (2) Sim S emulates Fso-OPPRF by sampling uniformly random S S shares 𝑒𝑖,𝑘,𝑧 , 𝑟𝑖,𝑘,𝑧 for 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑], 𝑧 ∈ [2𝑑 ], and sampling a random function 𝐹 such that 𝐹 (C𝑗S ∥𝑘 ∥𝑞 𝑗,𝑘 + 𝑡) = 0ℓ ∥𝑠 𝑗,𝑘 S S for 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], 𝑡 ∈ [−𝛿, 𝛿], and sends 𝑒𝑖,𝑘,𝑧 , 𝑟𝑖,𝑘,𝑧 and O 𝐹 to A. Eq (3) Sim S emulates FConRand by sampling uniformly random shares S 𝑣𝑖,𝑧 for 𝑖 ∈ [𝑛], 𝑧 ∈ [2𝑑 ], and sends them to A. Indistinguishability. The adversary’s view in the real execution is identically distributed to its view in the simulated execution. S S This follows because the values 𝑒𝑖,𝑘,𝑧 , 𝑟𝑖,𝑘,𝑧 received from Fso-OPPRF Eq

S and 𝑣𝑖,𝑧 from FConRand are uniformly random in the real world and are sampled from the same distribution by the simulator in the ideal world. Moreover, the random function oracle O 𝐹 subject to 𝐹 (C𝑗S ∥𝑘 ∥𝑞 𝑗,𝑘 + 𝑡) = 0ℓ ∥𝑠 𝑗,𝑘 , both of which are independent of S’s actual input 𝑄. Therefore, the view in the real-world execution is identically distributed to its view in the simulation. Corrupted receiver. We show the simulator Sim R (𝑊 , 𝐼 ):

(1) Sim R maintains a table for queries of the random oracle 𝐻 . For each query to 𝐻 , Sim R returns a consistent random value. (2) Sim R emulates Fso-OPPRF by sampling uniformly random R R shares 𝑒𝑖,𝑘,𝑧 , 𝑟𝑖,𝑘,𝑧 for 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑], 𝑧 ∈ [2𝑑 ], and sends R R 𝑒𝑖,𝑘,𝑧 , 𝑟𝑖,𝑘,𝑧 to A. Eq

(3) Sim R emulates FConRand by sampling uniformly random shares R 𝑣𝑖,𝑧 for 𝑖 ∈ [𝑛], 𝑧 ∈ [2𝑑 ], and sends them to A. (4) For each 𝒒 𝑗 ∈ 𝐼 , Sim R samples uniformly random 𝑠 𝑗 and sets S R R 𝑣𝑖,𝑧 = 𝑠 𝑗 − 𝑣𝑖,𝑧 for all 𝑖 ∈ [𝑛] and 𝑧 ∈ [2𝑑 ] such that C𝑖,𝑧 = C𝑗S S and dist(𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿. For the remaining 𝑣𝑖,𝑧 ’s, Sim R samples S uniformly random values. Sim R sends these 𝑣𝑖,𝑧 to A.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

(5) Sim R initializes an empty set 𝑋 . For each 𝒒 𝑗 ∈ 𝐼 , where there R exists 𝒘𝑖 and 𝑧 ∈ [2𝑑 ] such that C𝑖,𝑧 = C𝑗S and dist(𝒒 𝑗 , 𝒘𝑖 ) ≤ ′ 𝜆 𝛿, it computes 𝑥 = 𝐻 (𝑠 𝑗 ) ⊕ (0 ∥𝒒 𝑗 ) and adds 𝑥 to 𝑋 . For the remaining 𝑚 − |𝐼 | points, Sim R samples uniformly random strings of length 𝜆 ′ + 𝑑 · 𝑢 and adds them to 𝑋 . Sim R shuffles 𝑋 and sends them to A. Indistinguishability. We prove security via a sequence of hybrids. Hybrid H0 . This is the real execution of the protocol. Hybrid H1 . This hybrid is identical to H0 , except that Sim R acts Eq as Fso-OPPRF and FConRand , but follows the specification of these functionalities and uses the real sender’s input 𝑄. This is only a conceptual change, and hence the adversary’s view in Hybrid H0 and Hybrid H1 are identically distributed. Hybrid H2 . This hybrid is identical to H1 , except for the following S R modifications. For each 𝒒 𝑗 ∈ 𝐼 , Sim R sets 𝑣𝑖,𝑧 = 𝑠 𝑗 −𝑣𝑖,𝑧 for all R 𝑖 ∈ [𝑛] and 𝑧 ∈ [2𝑑 ] such that C𝑖,𝑧 = C𝑗S and dist(𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿. S For the remaining 𝑣𝑖,𝑧 ’s, Sim R samples uniformly random values. Besides, for each 𝒒 𝑗 ∈ 𝐼 , it computes 𝑥 = 𝐻 (𝑠 𝑗 ) ⊕ ′ (0𝜆 ∥𝒒 𝑗 ) and adds 𝑥 to 𝑋 . For the remaining 𝑚 − |𝐼 | points, Sim R samples uniformly random strings of length 𝜆 ′ + 𝑑 · 𝑢 and adds them to 𝑋 . In H1 , for each 𝒘𝑖 and 𝑧 ∈ [2𝑑 ] such that there is no 𝒒 𝑗 ∈ 𝑄 R satisfying C𝑖,𝑧 = C𝑗S and dist(𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, there exists at least S R ∗ one 𝑘𝑖 such that 𝑒𝑖,𝑘 ∗ ,𝑧 and 𝑒𝑖,𝑘 ∗ ,𝑧 are uniformly random by 𝑖

𝑖

S R the correctness of so-OPPRF. This implies 𝑒𝑖,𝑧 and 𝑒𝑖,𝑧 are uniformly random. By setting the bit length as ℓ = 𝜆 + 𝑑 + log 𝑛, S R a union bound shows that 𝑒𝑖,𝑧 ≠ −𝑒𝑖,𝑧 with overwhelming Eq

S probabilities. According to the correctness of FConRand , 𝑣𝑖,𝑧 𝑑 for the above 𝒘𝑖 and 𝑧 ∈ [2 ] is uniformly random and hence identical in both worlds. Besides, the above analysis implies that 𝑠 𝑗 for 𝒒 𝑗 ∉ 𝐼 is hidden from A. Moreover, due to |𝑠 𝑗 | = 𝜅, the probability that the adversary queries 𝐻 on 𝑠 𝑗 is negligi′ ble. Then, for each 𝒒 𝑗 ∉ 𝐼 , 𝐻 (𝑠 𝑗 ) ⊕ (0𝜆 ∥𝒒 𝑗 ) yields a string identically distributed to a uniform random string. Therefore, the adversary’s view of Hybrid H2 is computationally indistinguishable from that of Hybrid H1 . Hybrid H3 . This hybrid is identical to H2 , except that Sim R simuEq lates Fso-OPPRF and FConRand as follows. In particular, Sim R R R R samples uniformly random shares 𝑒𝑖,𝑘,𝑧 , 𝑟𝑖,𝑘,𝑧 , 𝑣𝑖,𝑧 for 𝑖 ∈ 𝑑 [𝑛], 𝑘 ∈ [𝑑], 𝑧 ∈ [2 ], and sends them to A. Since they are uniformly random shares from the adversary’s view, the adversary’s view in Hybrid H2 and Hybrid H3 are identically distributed.

Observe that Hybrid H3 is exactly the simulated execution produced by Sim R . Therefore, the real and ideal executions are computationally indistinguishable, completing the proof. □

G.3 𝐿𝑝 Distance under Sender-sided Unique Cell Assumptions Proof. Correctness. We first consider that for some 𝒒 𝑗 ∈ 𝑄, there exists 𝒘𝑖 ∈ 𝑊 such that dist𝑝 (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿 and therefore dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿. By the correctness of spatial hashing, there exists

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Xinpeng Yang et al.

R S an index 𝑧 ∗ ∈ [2𝑑 ] such that C𝑖,𝑧 ∗ = C𝑗 . Since dist𝑝 (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, it holds that |𝑞 𝑗,𝑘 − 𝑤𝑖,𝑘 | ≤ 𝛿 for all 𝑘 ∈ [𝑑]. Therefore, for each 𝑘 ∈ [𝑑], there exists 𝑡𝑘 ∈ [−𝛿, 𝛿] such that C𝑗S ∥𝑘 ∥𝑞 𝑗,𝑘 + 𝑡𝑘 = R R 𝑤𝑖,𝑘 . By the correctness of functionality Fso-OPPRF , 𝑒𝑖,𝑘,𝑧 ∗ ∥𝑟 𝑖,𝑘,𝑧 ∗ and S S 𝑝 𝑒𝑖,𝑘,𝑧 ∗ ∥𝑟𝑖,𝑘,𝑧 ∗ are the shares of |𝑡𝑘 | ∥𝑠 𝑗,𝑘 . And by the correctness of Í R S 𝑝 functionality FB2A , 𝑑𝑖,𝑧 ∗ and 𝑑𝑖,𝑧 ∗ are the shares of 𝑘 ∈ [𝑑 ] |𝑡𝑘 | = Í Í 𝑝 𝑝 𝑝 𝑘 ∈ [𝑑 ] (|𝑞 𝑗,𝑘 − 𝑤 𝑖,𝑘 |) . Since 𝑘 ∈ [𝑑 ] (|𝑞 𝑗,𝑘 − 𝑤 𝑖,𝑘 |) ≤ 𝛿 , by the Cmp R S correctness of functionality FConRand , it holds that 𝑣𝑖,𝑧 ∗ + 𝑣 𝑖,𝑧 ∗ = 𝑠 𝑗 . Then, the R reconstructs 𝑣𝑖,𝑧 ∗ = 𝑠 𝑗 . After shuffling, there must be ′ 𝑥 𝑗 ∗ ∈ 𝑋 and 𝑥 𝑗 ∗ = 𝐻𝜆′ +𝑑𝑢 (𝑠 𝑗 ) ⊕ (0𝜆 ∥𝒒 𝑗 ). Finally, the R unmasks 𝑥 𝑗 ∗ by 𝐻𝜆′ +𝑑𝑢 (𝑣𝑖,𝑧 ∗ ) ⊕ 𝑥 𝑗 ∗ and correctly gets 𝒒 𝑗 . We then consider that for some 𝒒 𝑗 ∈ 𝑄, it holds dist𝑝 (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿 for any 𝒘𝑖 ∈ 𝑊 . We consider the following three cases. R (1) The first case: for any 𝑧 ∈ [2𝑑 ], it holds that C𝑖,𝑧 ≠ C𝑗S . By R R the correctness of functionality Fso-OPPRF , the outputs 𝑒𝑖,𝑘,𝑧 ∥𝑟𝑖,𝑘,𝑧 S S 𝑑 and 𝑒𝑖,𝑘,𝑧 ∥𝑟𝑖,𝑘,𝑧 are uniformly random for all 𝑧 ∈ [2 ], 𝑘 ∈ [𝑑]. By R S the correctness of FB2A , after aggregation, the shares 𝑑𝑖,𝑧 and 𝑑𝑖,𝑧 Cmp

are also uniformly random. By the correctness of FConRand , the R S new shares 𝑣𝑖,𝑧 and 𝑣𝑖,𝑧 are uniformly random. Therefore, after reconstruction, 𝑣𝑖,𝑧 is uniformly random. (2) The second case: there exists an index 𝑧 ∗ ∈ [2𝑑 ] such that R S C𝑖,𝑧 ∗ = C𝑗 but dist∞ (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿. Then there exists an index ∗ 𝑘 ∈ [𝑑] such that |𝑞 𝑗,𝑘 ∗ − 𝑤𝑖,𝑘 ∗ | > 𝛿. By the correctness of funcR R S S tionality Fso-OPPRF , the outputs 𝑒𝑖,𝑘 ∗ ,𝑧 ∗ ∥𝑟 𝑖,𝑘 ∗ ,𝑧 ∗ and 𝑒𝑖,𝑘 ∗ ,𝑧 ∗ ∥𝑟 𝑖,𝑘 ∗ ,𝑧 ∗ are uniformly random. By the correctness of FB2A , after aggregation, R S the shares 𝑑𝑖,𝑧 ∗ and 𝑑𝑖,𝑧 ∗ are also uniformly random. Similarly, 𝑣 𝑖,𝑧 ∗ is uniformly random. R (3) The third case: there exists an index 𝑧 ∗ ∈ [2𝑑 ] such that C𝑖,𝑧 ∗ = S C𝑗 and dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿. By the correctness of functionality Í R S 𝑝 Fso-OPPRF and FB2A , it holds that 𝑑𝑖,𝑧 ∗ +𝑑𝑖,𝑧 ∗ = 𝑘 ∈ [𝑑 ] (|𝑤 𝑖,𝑘 − 𝑞 𝑗,𝑘 |) R S 𝑝 Since dist𝑝 (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿, therefore 𝑑𝑖,𝑧 ∗ + 𝑑𝑖,𝑧 ∗ > 𝛿 . By the corCmp

R S rectness of functionality FConRand , the outputs 𝑣𝑖,𝑧 ∗ and 𝑣 𝑖,𝑧 ∗ are uniformly random. After reconstruction, 𝑣𝑖,𝑧∗ is also uniformly random. In all cases, 𝑣𝑖,𝑧 is uniformly random for all 𝑖 ∈ [𝑛], 𝑧 ∈ [2𝑑 ]. By setting the bit length of 𝑠 𝑗 as 𝜅 > 𝜆 + 𝑑 + log 𝑛𝑚, the probability of 𝑣𝑖,𝑧 = 𝑠 𝑗 for some 𝑗 ∈ [𝑚] is at most 2−𝜆 , which is negligible. On the other hand, if 𝑣𝑖,𝑧 ≠ 𝑠 𝑗 , the decryption 𝐻𝜆′ +𝑑𝑢 (𝑣𝑖,𝑧 ) ⊕ 𝑥 𝑗 is uniformly random for all 𝑖 ∈ [𝑛], 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ]. By setting 𝜆 ′ = 𝜆 + 𝑑 + log 𝑚𝑛, the probability of valid decryption is at most 2−𝜆 , which is negligible. A union bound shows that the receiver can obtain valid 𝒒 𝑗 with the probability at most 2−𝜆 (2 − 2−𝜆 ) < 2−𝜆+1 , which is negligible. This completes the correctness proof. □

G.4 𝐿∞ Distance under Receiver-sided Unique Cell Assumptions Proof. Correctness. We first consider that for some 𝒒 𝑗 ∈ 𝑄, there exists 𝒘𝑖 ∈ 𝑊 such that dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿. By the correctness S of spatial hashing, there exists an index 𝑧 ∗ ∈ [2𝑑 ] such that C𝑗,𝑧 ∗ = C𝑖R . Since dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, it holds that |𝑞 𝑗,𝑘 − 𝑤𝑖,𝑘 | ≤ 𝛿 for all 𝑘 ∈

[𝑑]. Therefore, for each 𝑘 ∈ [𝑑], there exists 𝑡𝑘 ∈ [−𝛿, 𝛿] such that C𝑗S ∥𝑘 ∥𝑞 𝑗,𝑘 +𝑡𝑘 = 𝑤𝑖,𝑘 . By the correctness of functionality Fso-OPPRF , R S ℓ 𝑒 𝑗,𝑘,𝑧 ∗ and 𝑒 𝑗,𝑘,𝑧 ∗ are the shares of 0 . And then the aggregated shares R S ℓ 𝑟 𝑗,𝑧 ∗ and 𝑟 𝑗,𝑧 ∗ are still the shares of 0 . By the correctness of FEq , it holds that 𝑏 𝑗,𝑧 ∗ = 1 and therefore 𝑏 𝑗 = 1. By the correctness of FOT , R correctly gets 𝒒 𝑗 . We then consider that for some 𝒒 𝑗 ∈ 𝑄, it holds dist∞ (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿 for any 𝒘𝑖 ∈ 𝑊 . We consider the following two cases. S R (1) The first case: there exists an index 𝑧 ∗ such that C𝑗,𝑧 ∗ = C𝑖 . ∗ Since dist∞ (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿, it holds that there exists an index 𝑘 ∈ [𝑑] such that |𝑞 𝑗,𝑘 ∗ − 𝑤𝑖,𝑘 ∗ | > 𝛿. By the correctness of functionality R S Fso-OPPRF , the outputs 𝑒 𝑗,𝑘 ∗ ,𝑧 ∗ and 𝑒 𝑗,𝑘 ∗ ,𝑧 ∗ are uniformly random. R S Then, after aggregation, 𝑟 𝑗,𝑧 ∗ and 𝑟 𝑗,𝑧 ∗ are also uniformly random. S (2) The second case: for any 𝑧 ∈ [2𝑑 ], it holds that C𝑗,𝑧 ≠ C𝑖R . R By the correctness of functionality Fso-OPPRF , the outputs 𝑒 𝑗,𝑘,𝑧 and S R S 𝑒 𝑗,𝑘,𝑧 are uniformly random. Then, 𝑟 𝑗,𝑧 and 𝑟 𝑗,𝑧 are also uniformly random. R S In both cases, 𝑟 𝑗,𝑧 and 𝑟 𝑗,𝑧 are uniformly random for all 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ]. By the correctness of functionality FEq , the probability of 𝑏 𝑗,𝑧 = 1 is at most 1/|F|. A union bound shows that the probability of there existing 𝑗 ∈ [𝑚] such that 𝑏 𝑗 = 1 is at most 𝑚2𝑑 /|F|. By setting log|F| = ℓ = 𝜆 + 𝑑 + log 𝑚, the probability 𝑚2𝑑 /|F| = 2−𝜆 is negligible. By the correctness of FOT , R learns nothing about 𝒒 𝑗 . This completes the correctness proof. Corrupted sender. The simulator Sim S receives the sender’s input 𝑄 and proceeds as follows:

(1) Sim S emulates Fso-OPPRF by sampling uniformly random S shares 𝑒 𝑗,𝑘,𝑧 for all 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], and 𝑧 ∈ [2𝑑 ], and sends them to A. (2) Sim S emulates FEq and FOT , both of which output nothing to A. Indistinguishability. The adversary’s view in the real execution is identically distributed to its view in the simulated execution. S This follows because the values 𝑒 𝑗,𝑘,𝑧 received from Fso-OPPRF are uniformly random in the real world and are sampled from the same distribution by the simulator in the ideal world. Corrupted receiver. The simulator Sim R receives the receiver’s input 𝑊 and output 𝐼 , and proceeds as follows: (1) Sim R emulates Fso-OPPRF by sampling uniformly random R shares 𝑒 𝑗,𝑘,𝑧 for all 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], and 𝑧 ∈ [2𝑑 ], and by sampling a random function 𝐹 such that 𝐹 (C𝑖R ∥𝑘 ∥𝑤𝑖,𝑘 + 𝑡) = 0 for all 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑], and 𝑡 ∈ [−𝛿, 𝛿]. It then sends these R shares 𝑒 𝑗,𝑘,𝑧 and O 𝐹 to A. (2) Sim R emulates FEq by padding 𝐼 with ⊥ to size 𝑚 and randomly permuting the padded 𝐼 . For each 𝑗 ∈ [𝑚] and 𝑧 ∈ [2𝑑 ], it sets   1,    𝑏 𝑗,𝑧 =    0, 

if 𝒒 𝑗 = 𝐼 [ 𝑗] ≠ ⊥ and there exists 𝒘𝑖 such that S C𝑖R = C𝑗,𝑧 and dist(𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, otherwise.

Sim R sends all values 𝑏 𝑗,𝑧 to A. (3) Sim R emulates FOT and sends the padded and permuted 𝐼 to A.

Efficient Fuzzy PSI under One-Sided Assumptions

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Indistinguishability. We prove security via a sequence of hybrids.

R S of FB2A , the shares 𝑑 𝑗,𝑘,𝑧 and 𝑑 𝑗,𝑘,𝑧 are still uniformly random. Then,

Hybrid H0 . This is the real execution of the protocol. Hybrid H1 . This hybrid is identical to H0 , except that Sim R acts as Fso-OPPRF , FEq , and FOT , but follows the specification of these functionalities and uses the real sender’s input 𝑄. This is only a conceptual change, and hence the adversary’s view in Hybrid H0 and Hybrid H1 are identically distributed. Hybrid H2 . This hybrid is identical to H1 , except that instead of computing 𝑏 𝑗,𝑧 ’s (resp. 𝒖 𝑗 ’s) according to FEq (resp. FOT ), Sim R derives them utilizing the receiver’s input 𝑊 and output 𝐼 . Specifically, it pads 𝐼 with ⊥ to size 𝑚, applies a random permutation, and for every 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ] sets

R S after aggregation, 𝑟 𝑗,𝑧 and 𝑟 𝑗,𝑧 are also uniformly random. S (2) The second case, there exists an index 𝑧 ∗ such that C𝑗,𝑧 ∗ = R C𝑖 but dist∞ (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿. Therefore, it holds that there exists an index 𝑘 ∗ ∈ [𝑑] such that |𝑞 𝑗,𝑘 ∗ − 𝑤𝑖,𝑘 ∗ | > 𝛿. By the correctness of R S functionality Fso-OPPRF , the outputs 𝑒 𝑗,𝑘 ∗ ,𝑧 ∗ and 𝑒 𝑗,𝑘 ∗ ,𝑧 ∗ are uniformly

  1,    𝑏 𝑗,𝑧 =    0, 

if 𝒒 𝑗 = 𝐼 [ 𝑗] ≠ ⊥ and there exists 𝒘𝑖 such that S C𝑖R = C𝑗,𝑧 and dist(𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, otherwise.

The values 𝑏 𝑗,𝑧 ’s (resp. 𝒖 𝑗 ’s) are returned to A as the outputs of FEq (resp. FOT ). The adversary’s views in Hybrid H1 and Hybrid H2 are identically distributed, because functionality Eq outputs exactly these bits 𝑏 𝑗,𝑧 and the outputs of functionality OT are exactly determined by 𝑏 𝑗,𝑧 and 𝐼 . Hybrid H3 . This hybrid is identical to H2 , except that we replace the sender’s interaction in Fso-OPPRF with a simulation as R follows: sample random shares 𝑒 𝑗,𝑘,𝑧 for all 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], 𝑧 ∈ [2𝑑 ], and sample a random function 𝐹 conditioned on 𝐹 (C𝑖R ∥𝑘 ∥𝑤𝑖,𝑘 + 𝑡) = 0 for all 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑], and 𝑡 ∈ R [−𝛿, 𝛿]. The simulator sends 𝑒 𝑗,𝑘,𝑧 and O 𝐹 to A. By the security of Fso-OPPRF , the adversarial views of Hybrid H2 and Hybrid H3 are identically distributed. Observe that Hybrid H3 is exactly the simulated execution produced by Sim R . Therefore, the real and ideal executions are perfectly indistinguishable, completing the proof. □

G.5 𝐿𝑝 Distance under Receiver-sided Unique Cell Assumptions Proof. Correctness. We first consider that for some 𝒒 𝑗 ∈ 𝑄, there exists 𝒘𝑖 ∈ 𝑊 such that dist𝑝 (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿. By the correctness S of spatial hashing, there exists an index 𝑧 ∗ ∈ [2𝑑 ] such that C𝑗,𝑧 ∗ = R C𝑖 . Since dist𝑝 (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, it holds that |𝑞 𝑗,𝑘 − 𝑤𝑖,𝑘 | ≤ 𝛿 for all 𝑘 ∈ [𝑑]. Therefore, for each 𝑘 ∈ [𝑑], there exists 𝑡𝑘 ∈ [−𝛿, 𝛿] such that R 𝑞 𝑗,𝑘 + 𝑡𝑘 = 𝑤𝑖,𝑘 . By the correctness of functionality Fso-OPPRF , 𝑒 𝑗,𝑘,𝑧 ∗ S R 𝑝 and 𝑒 𝑗,𝑘,𝑧 ∗ are the shares of |𝑡𝑘 | . By the correctness of FB2A , 𝑑 𝑗,𝑘,𝑧 ∗ + Í S R S 𝑝 𝑑 𝑗,𝑘,𝑧 = |𝑡𝑘 |𝑝 . Then, after aggregation, 𝑟 𝑗,𝑧 ∗ + 𝑟 𝑗,𝑧 ∗ = 𝑘 ∈ [𝑑 ] |𝑡𝑘 | = Í ∗ 𝑝 . Since dist (𝒒 , 𝒘 ) ≤ 𝛿, by the correctness |𝑞 − 𝑤 | 𝑝 𝑗 𝑖 𝑖,𝑘 𝑘 ∈ [𝑑 ] 𝑗,𝑘 𝛿𝑝 of FInterval , it holds that 𝑏 𝑗,𝑧 ∗ = 1 and therefore 𝑏 𝑗 = 1. By the correctness of FOT , R correctly gets 𝒒 𝑗 . We then consider that for some 𝒒 𝑗 ∈ 𝑄, it holds dist𝑝 (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿 for any 𝒘𝑖 ∈ 𝑊 . We consider the following three cases. S (1) The first case, for any 𝑧 ∈ [2𝑑 ], it holds that C𝑗,𝑧 ≠ C𝑖R . By the R S correctness of functionality Fso-OPPRF , the outputs 𝑒 𝑗,𝑘,𝑧 and 𝑒 𝑗,𝑘,𝑧

are uniformly random for all 𝑘 ∈ [𝑑], 𝑧 ∈ [2𝑑 ]. By the correctness

R S random. By the correctness of functionality FB2A , 𝑑 𝑗,𝑘 ∗ ,𝑧 ∗ and 𝑑 𝑗,𝑘 ∗ ,𝑧 ∗ R S are also uniformly random. Then, after aggregation, 𝑟 𝑗,𝑧 ∗ and 𝑟 𝑗,𝑧 ∗ are also uniformly random. R S In the first two cases, 𝑟 𝑗,𝑧 and 𝑟 𝑗,𝑧 are uniformly random for all 𝑝

𝛿 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ]. By the correctness of functionality FInterval , the probability of 𝑏 𝑗,𝑧 = 1 is at most 𝛿 𝑝 /|F|. A union bound shows that the probability of there existing 𝑗 ∈ [𝑚] such that 𝑏 𝑗 = 1 is at most 𝑚2𝑑 𝛿 𝑝 /|F|. By setting log|F| = ℓ = 𝜆 + 𝑑 + log 𝑚 + 𝑝 log 𝛿, the probability 𝑚2𝑑 𝛿 𝑝 /|F| = 2−𝜆 is negligible. By the correctness of FOT , R learns nothing about 𝒒 𝑗 . S R (3) The third case, there exists an index 𝑧 ∗ such that C𝑗,𝑧 ∗ = C𝑖 and dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿. By the correctness of functionality Fso-OPPRF R S 𝑝 𝑝 and FB2A , 𝑟 𝑗,𝑧 ∗ + 𝑟 𝑗,𝑧 ∗ = dist𝑝 (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿 . By the correctness of 𝑝

𝛿 functionality FInterval and FOT , R learns nothing about 𝒒 𝑗 . This completes the correctness proof.

□

G.6 𝐿∞ Distance under Receiver-sided Unique Cell Assumptions with Prefix Optimization Proof. Correctness. We first consider that for some 𝒒 𝑗 ∈ 𝑄, there exists 𝒘𝑖 ∈ 𝑊 such that dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿. By the correctness S of spatial hashing, there exists an index 𝑧 ∗ ∈ [2𝑑 ] such that C𝑗,𝑧 ∗ = R C𝑖 . Since dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, it holds that |𝑞 𝑗,𝑘 − 𝑤𝑖,𝑘 | ≤ 𝛿 for all 𝑘 ∈ [𝑑]. Therefore, for each 𝑘 ∈ [𝑑], 𝑞 𝑗,𝑘 ∈ [𝑤𝑖,𝑘 − 𝛿, 𝑤𝑖,𝑘 + 𝛿]. By Lemma 3.1, there exists exactly one index ℎ ∗ ∈ [𝜇] such that 𝑞˜ 𝑗,𝑘,ℎ∗ ∈ {𝑤˜ 𝑖,𝑘,ℎ }ℎ∈ [𝜇 ] . By the correctness of functionality Fso-OPPRF , R S ℓ 𝑒 𝑗,𝑘,𝑧 ∗ ,ℎ ∗ and 𝑒 𝑗,𝑘,𝑧 ∗ ,ℎ ∗ are the shares of 0 . By the correctness of funcEq,𝜇

R S R S tionality FConSel , 𝑣 𝑗,𝑘,𝑧 ∗ +𝑣 𝑗,𝑘,𝑧 ∗ = 𝑒 𝑗,𝑘,𝑧 ∗ ,ℎ ∗ +𝑒 𝑗,𝑘,𝑧 ∗ ,ℎ ∗ = 0. Then, after R S aggregation, 𝑟 𝑗,𝑧 ∗ +𝑟 𝑗,𝑧 ∗ = 0. By the correctness of functionality FEq , ∗ 𝑏 𝑗,𝑧 = 1 and therefore 𝑏 𝑗 = 1. By the correctness of functionality FOT , R correctly obtains 𝒒 𝑗 . We then consider that for some 𝒒 𝑗 ∈ 𝑄, it holds dist∞ (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿 for any 𝒘𝑖 ∈ 𝑊 . We consider the following two cases. S R (1) The first case, there exists an index 𝑧 ∗ such that C𝑗,𝑧 ∗ = C𝑖 . ∗ Since dist∞ (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿, it holds that there exists an index 𝑘 ∈ [𝑑] such that |𝑞 𝑗,𝑘 ∗ − 𝑤𝑖,𝑘 ∗ | > 𝛿, therefore 𝑞 𝑗,𝑘 ∗ ∉ [𝑤𝑖,𝑘 ∗ − 𝛿, 𝑤𝑖,𝑘 ∗ + 𝛿]. By Lemma 3.1, it holds that {𝑞˜ 𝑗,𝑘,ℎ }ℎ∈ [𝜇 ] ∩ {𝑤˜ 𝑖,𝑘,ℎ }ℎ∈ [𝜇 ] = ∅. By R the correctness of functionality Fso-OPPRF , the outputs 𝑒 𝑗,𝑘 ∗ ,𝑧 ∗ ,ℎ and S 𝑒 𝑗,𝑘 ∗ ,𝑧 ∗ ,ℎ are uniformly random for all ℎ ∈ [𝜇]. Then, by the correctEq,𝜇

R S ness of functionality FConSel , 𝑣 𝑗,𝑘,𝑧 ∗ and 𝑣 𝑗,𝑘,𝑧 ∗ are uniformly random. R S After aggregation, 𝑟 𝑗,𝑧 ∗ and 𝑟 𝑗,𝑧 ∗ are also uniformly random. S (2) The second case, for any 𝑧 ∈ [2𝑑 ], it holds that C𝑗,𝑧 ≠ C𝑖R . R By the correctness of functionality Fso-OPPRF , the outputs 𝑒 𝑗,𝑘,𝑧 and

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY S R S 𝑒 𝑗,𝑘,𝑧 are uniformly random. Then, 𝑟 𝑗,𝑧 and 𝑟 𝑗,𝑧 are also uniformly random. R S In both cases, 𝑟 𝑗,𝑧 and 𝑟 𝑗,𝑧 are uniformly random for all 𝑗 ∈ 𝑑 [𝑚], 𝑧 ∈ [2 ]. By the correctness of functionality FEq , the probability of 𝑏 𝑗,𝑧 = 1 is at most 1/|F|. A union bound shows that the probability of there existing 𝑗 ∈ [𝑚] such that 𝑏 𝑗 = 1 is at most 𝑚2𝑑 /|F|. By setting log|F| = ℓ = 𝜆 + 𝑑 + log 𝑚, the probability 𝑚2𝑑 /|F| = 2−𝜆 is negligible. By the correctness of FOT , R learns nothing about 𝒒 𝑗 . This completes the correctness proof. Corrupted sender. The simulator Sim S receives the sender’s input 𝑄 and proceeds as follows:

(1) Sim S emulates Fso-OPPRF by sampling uniformly random S shares 𝑒 𝑗,𝑘,𝑧,ℎ for all 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], 𝑧 ∈ [2𝑑 ], and ℎ ∈ [𝜇] and sends them to A. Eq,𝜇 (2) Sim S emulates FConSel by sampling uniformly random shares S 𝑣 𝑗,𝑘,𝑧 for all 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], and 𝑧 ∈ [2𝑑 ], and sends them to A. (3) Sim S emulates FEq and FOT , both of which output nothing to A. Indistinguishability. The adversary’s view in the real execution is identically distributed to its view in the simulated execution. S This follows because the values 𝑒 𝑗,𝑘,𝑧,ℎ received from Fso-OPPRF and Eq,𝜇

S 𝑣 𝑗,𝑘,𝑧 from FConSel are uniformly random in the real world and are sampled from the same distribution by the simulator in the ideal world. Corrupted receiver. The simulator Sim R receives the receiver’s input 𝑊 and output 𝐼 , and proceeds as follows:

(1) Sim R emulates Fso-OPPRF by sampling uniformly random R shares 𝑒 𝑗,𝑘,𝑧,ℎ for all 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], 𝑧 ∈ [2𝑑 ], ℎ ∈ [𝜇], and by sampling a random function 𝐹 such that 𝐹 (C𝑖R ∥𝑘 ∥𝑤˜ 𝑖,𝑘,ℎ ) = 0 for all 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑], and ℎ ∈ [𝜇]. It then sends these R shares 𝑒 𝑗,𝑘,𝑧,ℎ and O 𝐹 to A. Eq,𝜇

(2) Sim R emulates FConSel by sampling uniformly random shares R 𝑣 𝑗,𝑘,𝑧 for all 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], and 𝑧 ∈ [2𝑑 ], and sends them to A. (3) Sim R emulates FEq by padding 𝐼 with ⊥ to size 𝑚 and randomly permuting the padded 𝐼 . For each 𝑗 ∈ [𝑚] and 𝑧 ∈ [2𝑑 ], it sets   1,    𝑏 𝑗,𝑧 =    0, 

if 𝒒 𝑗 = 𝐼 [ 𝑗] ≠ ⊥ and there exists 𝒘𝑖 such that S C𝑖R = C𝑗,𝑧 and dist(𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, otherwise.

Sim R sends all values 𝑏 𝑗,𝑧 to A. (4) Sim R emulates FOT and sends the padded and permuted 𝐼 to A. Indistinguishability. We prove security via a sequence of hybrids. Hybrid H0 . This is the real execution of the protocol. Hybrid H1 . This hybrid is identical to H0 , except that Sim R acts as Eq,𝜇 Fso-OPPRF , FConSel , FEq , and FOT , but follows the specification of these functionalities and uses the real sender’s input 𝑄. This is only a conceptual change, and hence the adversary’s view in Hybrid H0 and Hybrid H1 are identically distributed.

Xinpeng Yang et al.

Hybrid H2 . This hybrid is identical to H1 , except that instead of computing 𝑏 𝑗,𝑧 ’s (resp. 𝒖 𝑗 ’s) according to FEq (resp. FOT ), Sim R derives them utilizing the receiver’s input 𝑊 and output 𝐼 . Specifically, it pads 𝐼 with ⊥ to size 𝑚, applies a random permutation, and for every 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ] sets   1,    𝑏 𝑗,𝑧 =    0, 

if 𝒒 𝑗 = 𝐼 [ 𝑗] ≠ ⊥ and there exists 𝒘𝑖 such that S C𝑖R = C𝑗,𝑧 and dist(𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, otherwise.

The values 𝑏 𝑗,𝑧 ’s (resp. 𝒖 𝑗 ’s) are returned to A as the outputs of FEq (resp. FOT ). The adversary’s views in Hybrid H1 and Hybrid H2 are identically distributed, because functionality Eq outputs exactly these bits 𝑏 𝑗,𝑧 and the outputs of functionality OT are exactly determined by 𝑏 𝑗,𝑧 and 𝐼 . Hybrid H3 . This hybrid is identical to H2 , except that we replace Eq,𝜇 the sender’s interaction in Fso-OPPRF and FConSel with a simulation as follows. Sim R emulates Fso-OPPRF by sampling R uniformly random shares 𝑒 𝑗,𝑘,𝑧,ℎ for all 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], 𝑧 ∈ [2𝑑 ], ℎ ∈ [𝜇], and by sampling a random function 𝐹 such that 𝐹 (C𝑖R ∥𝑘 ∥𝑤˜ 𝑖,𝑘,ℎ ) = 0 for all 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑], and ℎ ∈ [𝜇]. R It then sends these shares 𝑒 𝑗,𝑘,𝑧,ℎ and O 𝐹 to A. Then, Sim R Eq,𝜇

R emulates FConSel by sampling uniformly random shares 𝑣 𝑗,𝑘,𝑧

for all 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], and 𝑧 ∈ [2𝑑 ], and sends them to A. Eq,𝜇 By the security of Fso-OPPRF and FConSel , the adversarial views of Hybrid H2 and Hybrid H3 are identically distributed. Observe that Hybrid H3 is exactly the simulated execution produced by Sim R . Therefore, the real and ideal executions are perfectly indistinguishable, completing the proof. □

G.7 𝐿∞ Distance under Receiver-sided Unique Block Assumptions Proof. Correctness. We first consider that for some 𝒒 𝑗 ∈ 𝑄, there exists 𝒘𝑖 ∈ 𝑊 such that dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿. By the correctness of spatial hashing, there exists an index 𝑧 ∗ ∈ [2𝑑 ] such that C𝑗S = R C𝑖,𝑧 ∗ . Since dist∞ (𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, it holds that |𝑞 𝑗,𝑘 − 𝑤 𝑖,𝑘 | ≤ 𝛿 for all 𝑘 ∈ [𝑑]. Therefore, for each 𝑘 ∈ [𝑑], there exists 𝑡𝑘 ∈ [−𝛿, 𝛿] such that 𝑞 𝑗,𝑘 + 𝑡𝑘 = 𝑤𝑖,𝑘 . By the correctness of functionality Fso-OPPRF , R S 𝑒 𝑗,𝑘 and 𝑒 𝑗,𝑘 are the shares of 0ℓ . And then the aggregated shares 𝑟 𝑗R and 𝑟 𝑗S are still the shares of 0ℓ . By the correctness of FEq , it holds that 𝑏 𝑗 = 1. By the correctness of FOT , R correctly obtains 𝒒 𝑗 . We then consider that for some 𝒒 𝑗 ∈ 𝑄, it holds dist∞ (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿 for any 𝒘𝑖 ∈ 𝑊 . We consider the following two cases. R (1) The first case: there exists an index 𝑧 ∗ such that C𝑗S = C𝑖,𝑧 ∗. ∗ Since dist∞ (𝒒 𝑗 , 𝒘𝑖 ) > 𝛿, it holds that there exists an index 𝑘 ∈ [𝑑] such that |𝑞 𝑗,𝑘 ∗ − 𝑤𝑖,𝑘 ∗ | > 𝛿. By the correctness of functionality R S Fso-OPPRF , the outputs 𝑒 𝑗,𝑘 ∗ and 𝑒 𝑗,𝑘 ∗ are uniformly random. Then, after aggregation, 𝑟 𝑗R and 𝑟 𝑗S are also uniformly random. R (2) The second case: for any 𝑧 ∈ [2𝑑 ], it holds that C𝑗S ≠ C𝑖,𝑧 . By R S the correctness of functionality Fso-OPPRF , the outputs 𝑒 𝑗,𝑘 and 𝑒 𝑗,𝑘 are uniformly random. Then, 𝑟 𝑗R and 𝑟 𝑗S are also uniformly random.

Efficient Fuzzy PSI under One-Sided Assumptions

In both cases, 𝑟 𝑗R and 𝑟 𝑗S are uniformly random for all 𝑗 ∈ [𝑚]. By the correctness of functionality FEq , the probability of 𝑏 𝑗 = 1 is at most 1/|F|. A union bound shows that the probability of there existing 𝑗 ∈ [𝑚] such that 𝑏 𝑗 = 1 is at most 𝑚/|F|. By setting log|F| = ℓ = 𝜆 + log 𝑚, the probability 𝑚/|F| = 2−𝜆 is negligible. By the correctness of FOT , R learns nothing about 𝒒 𝑗 . This completes the correctness proof. Corrupted sender. The simulator Sim S receives the sender’s input 𝑄 and proceeds as follows: (1) Sim S emulates Fso-OPPRF by sampling uniformly random S shares 𝑒 𝑗,𝑘 for all 𝑗 ∈ [𝑚] and 𝑘 ∈ [𝑑], and sends them to A. (2) Sim S emulates FEq and FOT , both of which output nothing to A. Indistinguishability. The adversary’s view in the real execution is identically distributed to its view in the simulated execution. S This follows because the values 𝑒 𝑗,𝑘 received from Fso-OPPRF are uniformly random in the real world and are sampled from the same distribution by the simulator in the ideal world. Corrupted receiver. The simulator Sim R receives the receiver’s input 𝑊 and output 𝐼 , and proceeds as follows: (1) Sim R emulates Fso-OPPRF by sampling uniformly random R shares 𝑒 𝑗,𝑘 for all 𝑗 ∈ [𝑚] and 𝑘 ∈ [𝑑], and by sampling R a random function 𝐹 such that 𝐹 (C𝑖,𝑧 ∥𝑘 ∥𝑤𝑖,𝑘 + 𝑡) = 0 for all 𝑑 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑], 𝑧 ∈ [2 ], and 𝑡 ∈ [−𝛿, 𝛿]. It then sends these R shares 𝑒 𝑗,𝑘 and O 𝐹 to A. (2) Sim R emulates FEq by padding 𝐼 with ⊥ to size 𝑚 and randomly permuting the padded 𝐼 . For each 𝑗 ∈ [𝑚], it sets

  1,    𝑏𝑗 =    0, 

if 𝒒 𝑗 = 𝐼 [ 𝑗] ≠ ⊥ and there exists 𝒘𝑖 and 𝑧 ∈ [2𝑑 ] R such that C𝑖,𝑧 = C𝑗S and dist(𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, otherwise.

Sim R sends all values 𝑏 𝑗 to A. (3) Sim R emulates FOT and sends the padded and permuted 𝐼 to A. Indistinguishability. We prove security via a sequence of hybrids. Hybrid H0 . This is the real execution of the protocol. Hybrid H1 . This hybrid is identical to H0 , except that Sim R acts as Fso-OPPRF , FEq , and FOT , but follows the specification of these functionalities and uses the real sender’s input 𝑄. This is only a conceptual change, and hence the adversary’s view in Hybrid H0 and Hybrid H1 are identically distributed. Hybrid H2 . This hybrid is identical to H1 , except that instead of computing 𝑏 𝑗 ’s (resp. 𝒖 𝑗 ’s) according to FEq (resp. FOT ), Sim R derives them utilizing the receiver’s input 𝑊 and output 𝐼 . Specifically, it pads 𝐼 with ⊥ to size 𝑚, applies a random permutation, and for every 𝑗 ∈ [𝑚] sets   1,    𝑏𝑗 =    0, 

if 𝒒 𝑗 = 𝐼 [ 𝑗] ≠ ⊥ and there exists 𝒘𝑖 and 𝑧 ∈ [2𝑑 ] R such that C𝑖,𝑧 = C𝑗S and dist(𝒒 𝑗 , 𝒘𝑖 ) ≤ 𝛿, otherwise.

The values 𝑏 𝑗 ’s (resp. 𝒖 𝑗 ’s) are returned to A as the outputs of FEq (resp. FOT ).

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

The adversary’s views in Hybrid H1 and Hybrid H2 are identically distributed, because functionality Eq outputs exactly these bits 𝑏 𝑗 and the outputs 𝒖 𝑗 of functionality OT are exactly determined by 𝑏 𝑗 and 𝐼 . Hybrid H3 . This hybrid is identical to H2 , except that we replace the sender’s interaction in Fso-OPPRF with a simulation as folR lows: sample random shares 𝑒 𝑗,𝑘 for all 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑], and R sample a random function 𝐹 conditioned on 𝐹 (C𝑖,𝑧 ∥𝑘 ∥𝑤𝑖,𝑘 + 𝑑 𝑡) = 0 for all 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑], 𝑧 ∈ [2 ], and 𝑡 ∈ [−𝛿, 𝛿]. The R simulator sends {𝑒 𝑗,𝑘 } and O 𝐹 to A. By the security of Fso-OPPRF , the adversary’s view of Hybrid H2 and Hybrid H3 are identically distributed. Observe that Hybrid H3 is exactly the simulated execution produced by Sim R . Therefore, the real and ideal executions are perfectly indistinguishable, completing the proof. □

G.8

Security Proof of FConRand

Proof. Correctness. For any 𝑒 S and 𝑒 R such that 𝑓 (𝑒 S , 𝑒 R ) = 1, the outputs 𝑏 S and 𝑏 R are secret shares of 1. By the correctness of FMUX , the MUX outputs 𝑚 S and 𝑚 R are secret shares of 0, and hence 𝑧 S + 𝑧 R = 𝑣 S + 𝑣 R . Conversely, for any 𝑒 S and 𝑒 R such that 𝑓 (𝑒 S , 𝑒 R ) = 0, the outputs 𝑏 S and 𝑏 R are secret shares of 0. Since 𝑟 S and 𝑟 R are sampled uniformly at random, by the correctness of FMUX , 𝑚 S and 𝑚 R are uniformly random, and consequently 𝑣 S +𝑚 S and 𝑣 R +𝑚 R are each uniformly random. This completes the correctness proof. Corrupted sender. The simulator Sim S receives the sender’s input (𝑒 S , 𝑣 S ) and output 𝑧 S , and proceeds as follows: (1) Sim S emulates FssPEQT /FssCMP by sampling uniformly random shares 𝑏 S and sends it to A. (2) Sim S emulates FMUX by computing 𝑚 S = 𝑧 S − 𝑣 S and sends it to A. Indistinguishability. The adversary’s view in the real execution is identically distributed to its view in the simulated execution. This follows because the values 𝑏 S received from FssPEQT /FssCMP are uniformly random in the real execution and are sampled from the same distribution by the simulator in the ideal execution. Moreover, the value 𝑚 S is identically distributed in both worlds conditioned on the relation 𝑧 S = 𝑣 S + 𝑚 S . Therefore, the joint distribution of the adversary’s view is identical in the real and ideal executions. Corrupted receiver. Since the protocol execution is symmetric, the security of the corrupted receiver follows similarly. This completes the proof. □

G.9

Security Proof of FConSel

Proof. Corrupted sender. The simulator Sim S receives the sender’s input {𝑒𝑖S }𝑖 ∈ [𝜇 ] and output 𝑚 S , and proceeds as follows: (1) Sim S emulates FssPEQT /FssCMP by sampling uniformly random shares 𝑏𝑖S for 𝑖 ∈ [𝜇] and sends them to A. (2) Sim S emulates FMUX and sends 𝑚 S to A. Indistinguishability. The adversary’s view in the real execution is identically distributed to its view in the simulated execution. This follows because the values 𝑏𝑖S received from FssPEQT /FssCMP are

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

uniformly random in the real execution and are sampled from the same distribution by the simulator in the ideal execution. Moreover, the output 𝑚 S is identically distributed in both worlds. Therefore, the joint distribution of the adversary’s view is identical in the real and ideal executions. Corrupted receiver. Since the protocol execution is symmetric, the security of the corrupted receiver follows similarly. This completes the proof. □

G.10

Proof of Lemma 3.1

Proof. By definition 3.1 of [10], let {𝑏 𝑗 } 𝑗 ∈ [𝜇 ] = PxTrie(𝑞 −𝛿, 𝑞 + 𝛿). Then: Ø [𝑞 − 𝛿, 𝑞 + 𝛿] = Interval(𝑏 𝑗 )

Xinpeng Yang et al.

𝑓 ,𝜇

Functionality FExtConSel Parameters: Sender S and Receiver R. Condition function 𝑓 (·, ·) where 𝑓 can be an equality or a comparison function. Input size 𝜇 Functionality: (1) Wait for input { (𝑒 1S , 𝑟 1S ), · · ·, (𝑒 𝜇S , 𝑟 𝜇S ) } from S and { (𝑒 1R , 𝑟 1R ), · · ·, (𝑒 𝜇R , 𝑟 𝜇R ) } from R, where there exists at most one (𝑒𝑖S , 𝑒𝑖R ) with 𝑓 (𝑒𝑖S , 𝑒𝑖R ) = 1. (2) Compute 𝑏𝑖 := 𝑓 (𝑒𝑖S , 𝑒𝑖R ) for all 𝑖 ∈ [𝜇 ]. (3) If exist 𝑏𝑖 = 1, generate two random shares such that 𝑧 S + 𝑧 R = 𝑟𝑖S + 𝑟𝑖R . Otherwise, generate two random shares (𝑧 S , 𝑧 R ). (4) Output 𝑧 S to S and 𝑧 R to R.

Figure 19: Functionality of Extended Conditional Selection.

𝑗 ∈ [𝜇 ]

and for any 𝑏 ∈ {𝑏 𝑗 } 𝑗 ∈ [𝜇 ] , if a binary string 𝑏 ′ is a prefix of 𝑏, then: Eq,𝜇

Interval(𝑏 ′ ) ⊈ [𝑞 − 𝛿, 𝑞 + 𝛿] Therefore, for any 𝑏 𝑗 , we have Interval(𝑏 𝑗 ) ⊆ [𝑞 − 𝛿, 𝑞 + 𝛿]. Let 𝑘 𝑗 be the number of wildcards in 𝑏 𝑗 . Since the length of the interval |Interval(𝑏 𝑗 )| = 2𝑘 𝑗 cannot exceed the total length of the range 2𝛿 + 1, it holds that 2𝑘 𝑗 ≤ 2𝛿 + 1, which implies 𝑘 𝑗 ≤ ⌊log2 (2𝛿 + 1)⌋. Case 1: 𝑤 ∈ [𝑞 − 𝛿, 𝑞 + 𝛿]. First, we show existence. Since 𝑤 ∈ [𝑞 −𝛿, 𝑞 +𝛿], the completeness property of definition 3.1 of [10] ensures there exists an index 𝑗 ∗ ∈ [𝜇] such that 𝑤 ∈ Interval(𝑏 𝑗 ∗ ). By the definition of Interval(·), 𝑏 𝑗 ∗ must be a prefix of 𝑤. As derived above, the wildcard count of 𝑏 𝑗 ∗ satisfies 𝑘 𝑗 ∗ ≤ ⌊log2 (2𝛿 + 1)⌋. By the definition of PxPath(𝑤, 𝛿) provided in section 3.4, 𝑏 𝑗 ∗ is a valid prefix on the path of root-to-𝑤 within this wildcard bound. Thus, 𝑏 𝑗 ∗ ∈ PxPath(𝑤, 𝛿) ∩ PxTrie(𝑞 − 𝛿, 𝑞 + 𝛿), and the intersection is non-empty. Next, we show uniqueness by contradiction. Suppose there exist two distinct nodes 𝑥, 𝑦 in the intersection. Since 𝑥, 𝑦 ∈ PxPath(𝑤, 𝛿), both are prefixes of 𝑤, implying one must be a prefix of the other. However, definition 3.1 of [10] states that for any 𝑏 ∈ PxTrie, its proper prefixes 𝑏 ′ must satisfy Interval(𝑏 ′ ) ⊈ [𝑞 − 𝛿, 𝑞 + 𝛿]. This prefix-free property ensures that no node in PxTrie can be a prefix of another, contradicting the existence of both 𝑥 and 𝑦. Thus, the intersection size is exactly 1. Case 2: 𝑤 ∉ [𝑞 − 𝛿, 𝑞 + 𝛿]. We show the intersection is empty by contradiction. Suppose there exists some 𝑏𝑖 ∈ PxPath(𝑤, 𝛿) ∩ PxTrie(𝑞 − 𝛿, 𝑞 + 𝛿). The membership 𝑏𝑖 ∈ PxPath(𝑤, 𝛿) implies 𝑏𝑖 is a prefix of 𝑤, so 𝑤 ∈ Interval(𝑏𝑖 ). The membership 𝑏𝑖 ∈ PxTrie(𝑞 −𝛿, 𝑞 +𝛿) implies Interval(𝑏𝑖 ) ⊆ [𝑞 −𝛿, 𝑞 +𝛿] per definition 3.1 of [10]. It follows that 𝑤 ∈ [𝑞 − 𝛿, 𝑞 + 𝛿], which contradicts the assumption. Hence, the intersection must be empty. Combining the above two cases completes the proof. □

H

Additional Protocols under Unique Cell Assumptions H.1 Sender-sided Setting The protocol for 𝐿𝑝 distances under sender-sided unique cell assumption is given in Figure 23. The proof is given in Appendix G.3.

Protocol Π ExtConSel Parameters: Ideal functionality FMUX and FssPEQT . Input: S inputs { (𝑒𝑖S , 𝑟𝑖S ) }𝑖 ∈ [𝜇 ] and R inputs { (𝑒𝑖R , 𝑟𝑖R ) }𝑖 ∈ [𝜇 ] . Protocol: (1) S and R invoke FssPEQT , where S inputs {𝑒𝑖S }𝑖 ∈ [𝜇 ] and R inputs {𝑒𝑖R }𝑖 ∈ [𝜇 ] . S receives {𝑏𝑖S }𝑖 ∈ [𝜇 ] ∈ {0, 1} 𝜇 , and R receives {𝑏𝑖R }𝑖 ∈ [𝜇 ] ∈ {0, 1} 𝜇 . (2) S and R invoke FMUX , where S inputs { (𝑏𝑖S , 𝑟𝑖S ) }𝑖 ∈ [𝜇 ] and R inputs { (𝑏𝑖R , 𝑟𝑖R ) }𝑖 ∈ [𝜇 ] . S receives {𝑡𝑖S }𝑖 ∈ [𝜇 ] and R receives {𝑡𝑖R }𝑖 ∈ [𝜇 ] . Í Í (3) S computes 𝑡 S := 𝑖 ∈ [𝜇 ] 𝑡𝑖S and R computes 𝑡 R := 𝑖 ∈ [𝜇 ] 𝑡𝑖R É S S R := (4) S computes 𝑏 := 𝑖 ∈ [𝜇 ] 𝑏𝑖 and R computes 𝑏 É R 𝑖 ∈ [𝜇 ] 𝑏𝑖 . (5) S randomly samples 𝑟 S and R randomly samples 𝑟 R . (6) S and R invoke FMUX , where S inputs (1 − 𝑏 S , 𝑟 S ) and R inputs (𝑏 R , 𝑟 R ). S receives 𝑚 S and R receives 𝑚 R . (7) S outputs 𝑧 S = 𝑚 S + 𝑡 S and R outputs 𝑧 R = 𝑚 R + 𝑡 R .

Figure 20: Protocol of Extended Equality-conditional Selection.

H.2

Receiver-sided Setting

The protocol for 𝐿𝑝 distances under the receiver-sided unique cell assumption is given in Figure 24. The proof is given in Appendix G.5.

I Additional Prefix-optimized Protocols I.1 Sender-sided Setting The prefix-optimized protocol under the sender-sided unique cell assumption for 𝐿∞ distances is given in Figure 25. The protocol for 𝐿𝑝 distances can be optimized analogously, and we omit the details for brevity. The core idea follows Section 4.4. Here, we ex𝑓 ,𝜇 𝑓 ,𝜇 tend FConSel to a more general functionality FExtConSel that handles 𝑓 ,𝜇

additional inputs. Specifically, FExtConSel takes as input a set of tuples, each consisting of a condition and an associated value to be randomized, and randomizes each value depending on whether its 𝑓 ,𝜇 condition is satisfied. FConSel can be viewed as a special case where the condition itself serves as the value. The ideal functionality of

Efficient Fuzzy PSI under One-Sided Assumptions

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

matched prefix interval 𝑞˜ 𝑗,𝑘,ℎ = 𝑤˜ 𝑖,𝑘,ℎ′

𝑞∗ = 𝑤∗

𝑞 𝑗,𝑘 |𝑞 ∗ − 𝑞 𝑗,𝑘 |

𝑤𝑖,𝑘

|𝑤𝑖,𝑘 − 𝑤 ∗ |

|𝑤𝑖,𝑘 − 𝑞 𝑗,𝑘 | (a) Left sub-interval: 𝑞 𝑗,𝑘 < 𝑤𝑖,𝑘 , upper endpoint 𝑞 ∗ = 𝑤 ∗ . matched prefix interval 𝑞˜ 𝑗,𝑘,ℎ = 𝑤˜ 𝑖,𝑘,ℎ′

𝑤𝑖,𝑘

𝑞∗ = 𝑤∗

|𝑤 ∗ − 𝑤𝑖,𝑘 |

𝑞 𝑗,𝑘 |𝑞 𝑗,𝑘 − 𝑞 ∗ |

|𝑞 𝑗,𝑘 − 𝑤𝑖,𝑘 | (b) Right sub-interval: 𝑞 𝑗,𝑘 > 𝑤𝑖,𝑘 , lower endpoint 𝑞 ∗ = 𝑤 ∗ .

Figure 21: An example to compute the distances with prefix trie techniques

Protocol Π getDist

construction. We therefore adopt the approach of [10], where the receiver programs the distance from 𝑤𝑖,𝑘 to the endpoint of the interval covered by its prefix. The sender then evaluates the soOPPRF to obtain shares of this distance and computes the total distance via MPC multiplication and addition. Specifically, let {𝑤˜ 𝑖,𝑘,ℎ ′ }ℎ ′ ∈ [𝜇 ] and {𝑞˜ 𝑗,𝑘,ℎ }ℎ∈ [𝜇 ] denote the prefixes of 𝑤𝑖,𝑘 and 𝑞 𝑗,𝑘 , respectively, with upper endpoints 𝑤 ∗ and 𝑞 ∗ . The receiver programs |𝑤𝑖,𝑘 − 𝑤 ∗ | via the so-OPPRF, and the sender evaluates at 𝑞˜ 𝑗,𝑘,ℎ . In addition, the sender knows 𝑞 𝑗,𝑘 and 𝑞 ∗ locally, therefore it can compute |𝑞 ∗ − 𝑞 𝑗,𝑘 | directly. If 𝑞˜ 𝑗,𝑘,ℎ matches some 𝑤˜ 𝑖,𝑘,ℎ ′ , then 𝑞 ∗ = 𝑤 ∗ , and the distance decomposes as |𝑤𝑖,𝑘 − 𝑞 𝑗,𝑘 | = |𝑤𝑖,𝑘 − 𝑤 ∗ | + |𝑞 ∗ − 𝑞 𝑗,𝑘 |. Since |𝑤𝑖,𝑘 − 𝑤 ∗ | is secretshared between the two parties and |𝑞 ∗ − 𝑞 𝑗,𝑘 | is known to the sender, the 𝑝-th power can be expanded via the binomial theorem: 𝑝   ∑︁ 𝑝 |𝑤𝑖,𝑘 − 𝑞 𝑗,𝑘 |𝑝 = |𝑤𝑖,𝑘 − 𝑤 ∗ |𝑐 · |𝑞 ∗ − 𝑞 𝑗,𝑘 |𝑝 −𝑐 . 𝑐 𝑐=0 This decomposition holds when 𝑞 𝑗,𝑘 ≤ 𝑤𝑖,𝑘 ; the symmetric case 𝑞 𝑗,𝑘 > 𝑤𝑖,𝑘 is handled using the lower endpoint instead. To cover both cases, we split [𝑤𝑖,𝑘 − 𝛿, 𝑤𝑖,𝑘 + 𝛿] into [𝑤𝑖,𝑘 − 𝛿, 𝑤𝑖,𝑘 ] and [𝑤𝑖,𝑘 + 1, 𝑤𝑖,𝑘 + 𝛿], applying the upper endpoint to the left subinterval and the lower endpoint to the right. We use 𝜎 ∈ {0, 1} to index the two sub-intervals. The two cases are illustrated in Figure 21, and the detailed sub-protocol for computing the distance is given in Figure 22.

𝑝

˜ 𝜎 ) ∈ F × U × U × {0, 1}. R inputs Parameters: S inputs (𝑠 S , 𝑞, 𝑞, 𝑠 R ∈ F. Functionality FMult . 𝜇 = log 𝛿 + 1. Protocol: ˜ if 𝜎 = 0 (1) S computes 𝑒 := |𝑞 − 𝑞 ∗ | where 𝑞 ∗ = UpBound(𝑞) ˜ otherwise. and 𝑞 ∗ = LowBound(𝑞) (2) If 𝑝 = 1: • S computes 𝑑 S := 𝑠 S + 𝑒 and R computes 𝑑 R := 𝑠 R . (3) If 𝑝 = 2: • S computes 𝑦 S = 𝑠 S + 𝑒 and R sets 𝑦 R = 𝑠 R . • S and R invoke FMult where S inputs 𝑦 S and R inputs 𝑦 R . S receives 𝑚 S and R receives 𝑚 R . • S computes 𝑑 S := 𝑦 S · 𝑦 S + 2 · 𝑚 S and R computes 𝑑 R := 𝑦 R · 𝑦 R +2·𝑚 R where 𝑑 S +𝑑 R = (𝑦 S +𝑦 R ) 2 = (𝑠 S +𝑒 +𝑠 R ) 2 . (4) S outputs 𝑑 S and R outputs 𝑑 R .

Figure 22: Protocol for computing distance for 𝑝 = 1 and 𝑝 = 2. The protocol can be extended to arbitrary 𝑝. 𝑓 ,𝜇

FExtConSel is given in Figure 19, and its instantiation, which follows 𝑓 ,𝜇

the same structure as FConSel , is presented in Figure 20. 𝑓 ,𝜇

We note that when invoking FExtConSel , there is no need to addiR S tionally invoke EqRand, as the output shares 𝑣𝑖,𝑧 and 𝑣𝑖,𝑧 are already re-randomized for non-matching points 𝒘𝑖 .

I.2

Receiver-sided Setting

The prefix-optimized protocol under the receiver-sided unique cell assumption for 𝐿𝑝 distances is given in Figure 26. Since each prefix covers a range of points rather than a single value, the receiver cannot program the exact 𝑝-th power distance |𝑡 |𝑝 as in the 𝐿∞

J

Additional Protocols under Unique Block Assumptions

The protocol under the receiver-sided unique block assumption for 𝐿𝑝 distances is given in Figure 27. The key difference from the 𝐿∞ construction is that the receiver programs the 𝑝-th power of the 𝛿𝑝 per-dimension distance rather than 0, and invokes FInterval to test whether the aggregated distance falls within the threshold 𝛿 𝑝 . The prefix-optimized variant for 𝐿∞ distance follows the approach of Section 4.4, and the detailed protocol is given in Figure 28. The construction for general 𝐿𝑝 distances follows the same idea as in Appendix I.2, with the prefix-optimized protocol given in Figure 29. The protocols under the sender-sided unique block assumption follow analogously, and we omit the details for brevity.

K Additional Experimental Results K.1 Performance of our protocols for 𝐿𝑝 distances under unique cell assumption We present the results of our protocols for 𝐿𝑝 distances under the receiver-sided unique cell assumption in Table 4. As no existing work supports 𝐿𝑝 distances under this assumption, we omit a direct comparison.

K.2

Performance of our protocols under the sender-sided unique cell assumption

We present the results of our protocols for 𝐿∞ , 𝐿1 , and 𝐿2 distances under the sender-sided unique cell assumption in Table 5. As no existing work operates under this assumption, we omit a direct comparison.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Xinpeng Yang et al.

𝐿𝑝

Protocol Π FPSI Parameters: Sender S and receiver R with input sizes 𝑚 and 𝑛. Threshold 𝛿. Bit length 𝜆 ′ = 𝜆 + 𝑑 + log 𝑚𝑛, ℓ = 𝜆 + 𝑑 + log 𝑛 + 𝑝 log 𝛿, and 𝑢 = log|U|. Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ U𝑑 ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ U𝑑 ×𝑛 . Protocol: R } (1) For 𝑗 ∈ [𝑚], S computes C𝑗S = cell2𝛿 (𝒒 𝑗 ). For 𝑖 ∈ [𝑛], R computes { C𝑖,𝑧 𝑧 ∈ [2𝑑 ] = neigh2𝛿 (𝒘𝑖 ). n o Í $ S 𝑝 (2) S sets List = C𝑗 ∥𝑘 ∥𝑞 𝑗,𝑘 + 𝑡, |𝑡 | 𝑠 𝑗,𝑘 and computes 𝑠 𝑗 = 𝑘 ∈ [𝑑 ] 𝑠 𝑗,𝑘 where 𝑠 𝑗,𝑘 ← F2𝜅 . 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑡 ∈ [-𝛿,𝛿 ]

R ∥𝑘 ∥𝑤 } (3) R and S invoke functionality Fso-OPPRF where S inputs List and R inputs { C𝑖,𝑧 𝑖,𝑘 𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] . R receives R ∥𝑟 R } S ∥𝑟 S } {𝑒𝑖,𝑘,𝑧 and S receives {𝑒𝑖,𝑘,𝑧 and O 𝐹 . 𝑖,𝑘,𝑧 𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] 𝑖,𝑘,𝑧 𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] S R . S receives 𝑑 S R . (4) For 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑 ], 𝑧 ∈ [2𝑑 ], S and R invoke FB2A , where S inputs 𝑒𝑖,𝑘,𝑧 and R inputs 𝑒𝑖,𝑘,𝑧 and R receives 𝑑𝑖,𝑘,𝑧 𝑖,𝑘,𝑧 Í Í Í Í R R R R S S S S . 𝑑 (5) For 𝑖 ∈ [𝑛], 𝑧 ∈ [2 ], R computes 𝑑𝑖,𝑧 = 𝑘 ∈ [𝑑 ] 𝑑𝑖,𝑘,𝑧 and 𝑟𝑖,𝑧 = 𝑘 ∈ [𝑑 ] 𝑟𝑖,𝑘,𝑧 , and S computes 𝑑𝑖,𝑧 = 𝑘 ∈ [𝑑 ] 𝑑𝑖,𝑘,𝑧 and 𝑟𝑖,𝑧 = 𝑘 ∈ [𝑑 ] 𝑟𝑖,𝑘,𝑧 Cmp

R , 𝑟 R ) and S inputs (𝑑 S , 𝑟 S ). R receives 𝑣 R and S receives 𝑣 S . (6) For 𝑖 ∈ [𝑛], 𝑧 ∈ [2𝑑 ], R and S invoke FConRand where R inputs (𝑑𝑖,𝑧 𝑖,𝑧 𝑖,𝑧 𝑖,𝑧 𝑖,𝑧 𝑖,𝑧 S S R . 𝑑 (7) For 𝑖 ∈ [𝑛], 𝑧 ∈ [2 ], S sends 𝑣𝑖,𝑧 and R reconstructs 𝑣𝑖,𝑧 = 𝑣𝑖,𝑧 + 𝑣𝑖,𝑧 ′

(8) S computes 𝑋 = {𝐻𝜆 ′ +𝑑𝑢 (𝑠 𝑗 ) ⊕ (0𝜆 ∥𝒒 𝑗 ) } 𝑗 ∈ [𝑚] and sends shuffled 𝑋 to R. ′ (9) R sets 𝐼 = ∅ and parses 𝑋 as {𝑥 𝑗 } 𝑗 ∈ [𝑚] . For 𝑗 ∈ [𝑚], 𝑖 ∈ [𝑛], 𝑧 ∈ [2𝑑 ], if 𝐻𝜆 ′ +𝑑𝑢 (𝑣𝑖,𝑧 ) ⊕ 𝑥 𝑗 = 0𝜆 ∥𝒒, update 𝐼 = 𝐼 ∪ {𝒒}.

Figure 23: Protocol of fuzzy PSI for 𝐿𝑝 distance under sender-sided unique cell assumption. 𝐿𝑝

Protocol Π FPSI Parameters: Sender S and receiver R with input sizes 𝑚 and 𝑛. Threshold 𝛿. Bit length ℓ = 𝜆 + 𝑑 + log 𝑚 + 𝑝 log 𝛿. Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ U𝑑 ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ U𝑑 ×𝑛 . Protocol: S } (1) For 𝑖 ∈ [𝑛], R computes C𝑖R = cell2𝛿 (𝒘𝑖 ). For 𝑗 ∈ [𝑚], S computes { C𝑗,𝑧 𝑧 ∈ [2𝑑 ] = neigh2𝛿 (𝒒 𝑗 ). R 𝑝 (2) R sets List = { ( C𝑖 ∥𝑘 ∥𝑤𝑖,𝑘 + 𝑡, |𝑡 | ) }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑡 ∈ [-𝛿,𝛿 ] S ∥𝑘 ∥𝑞 R (3) R and S invoke functionality Fso-OPPRF where R inputs List and S inputs { C𝑗,𝑧 𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] . R receives {𝑒 𝑗,𝑘,𝑧 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] and O 𝐹 and S receives {𝑒 S𝑗,𝑘,𝑧 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ] . (4) For 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑 ], 𝑧 ∈ [2𝑑 ], R and S invoke functionality FB2A , where R inputs 𝑒 R𝑗,𝑘,𝑧 and S inputs 𝑒 S𝑗,𝑘,𝑧 . R receives 𝑑 R and S receives 𝑗,𝑘,𝑧 𝑑 S𝑗,𝑘,𝑧 . R = (5) For 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ], R computes 𝑟 𝑗,𝑧

Í R S S 𝑘 ∈ [𝑑 ] 𝑑 𝑗,𝑘,𝑧 and S computes 𝑟 𝑗,𝑧 = 𝑘 ∈ [𝑑 ] 𝑑 𝑗,𝑘,𝑧 . 𝑝 R and S inputs 𝑟 S . R receives 𝑏 R S 𝛿 𝑝 (6) For 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ], R and S invoke functionality FInterval where R inputs 𝑟 𝑗,𝑧 𝑗,𝑧 = 1{𝑟 𝑗,𝑧 + 𝑟 𝑗,𝑧 ≤ 𝛿 }. 𝑗,𝑧 Ô Í

(7) For 𝑗 ∈ [𝑚], R computes 𝑏 𝑗 = 𝑧 ∈ [2𝑑 ] 𝑏 𝑗,𝑧 . (8) For 𝑗 ∈ [𝑚], R and S invoke functionality FOT where R inputs 𝑏 𝑗 and S inputs (⊥, 𝒒 𝑗 ). R receives 𝒖 𝑗 . (9) R outputs 𝐼 = {𝒖 𝑗 | 𝑏 𝑗 = 1 for 𝑗 ∈ [𝑚] }.

Figure 24: Protocol of fuzzy PSI for 𝐿𝑝 distance under receiver-sided unique cell assumption.

Efficient Fuzzy PSI under One-Sided Assumptions

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

∞ Protocol Π𝐿FPSI-Px

Parameters: Sender S and receiver R with input sizes 𝑚 and 𝑛. Threshold 𝛿. Bit length 𝜆 ′ = 𝜆 + 𝑑 + log 𝑚𝑛, ℓ = 𝜆 + 𝑑 + log 𝑛𝑑𝜇 and 𝑢 = log|U|. Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ U𝑑 ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ U𝑑 ×𝑛 . Protocol: R } (1) For 𝑗 ∈ [𝑚], S computes C𝑗S = cell2𝛿 (𝒒 𝑗 ). For 𝑖 ∈ [𝑛], R computes { C𝑖,𝑧 𝑧 ∈ [2𝑑 ] = neigh2𝛿 (𝒘𝑖 ). $

(2) S encodes List = { ( C𝑗S ∥𝑘 ∥ 𝑞˜ 𝑗,𝑘,ℎ , 0ℓ ∥𝑠 𝑗,𝑘 ) } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ] where 𝑠 𝑗,𝑘 ← F2𝜅 and {𝑞˜ 𝑗,𝑘,ℎ }ℎ∈ [𝜇 ] = PxTrie(𝑞 𝑗,𝑘 −𝛿, 𝑞 𝑗,𝑘 + 𝛿 ). R ∥𝑘 ∥ 𝑤 ˜ 𝑖,𝑘,ℎ }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ],ℎ∈ [𝜇 ] where { 𝑤˜ 𝑖,𝑘,ℎ }ℎ∈ [𝜇 ] = PxPath(𝑤𝑖,𝑘 , 𝛿 ) (3) R computes query = { C𝑖,𝑧 R R ∥𝑟𝑖,𝑘,𝑧,ℎ }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ],ℎ∈ [𝜇 ] and S (4) R and S invoke functionality Fso-OPPRF where S inputs List and R inputs query. R receives {𝑒𝑖,𝑘,𝑧,ℎ S S receives {𝑒𝑖,𝑘,𝑧,ℎ ∥𝑟𝑖,𝑘,𝑧,ℎ }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ],ℎ∈ [𝜇 ] . Eq,𝜇

R R S S (5) For 𝑖 ∈ [𝑛], 𝑘 ∈ [𝑑 ], 𝑧 ∈ [2𝑑 ], R and S invoke FExtConSel where R inputs { (𝑒𝑖,𝑘,𝑧,ℎ , 𝑟𝑖,𝑘,𝑧,ℎ ) }ℎ∈ [𝜇 ] and S inputs { (−𝑒𝑖,𝑘,𝑧,ℎ , 𝑟𝑖,𝑘,𝑧,ℎ ) }ℎ∈ [𝜇 ] . R R S . receives 𝑣𝑖,𝑘,𝑧 and S receives 𝑣𝑖,𝑘,𝑧 Í R =Í R S S 𝑑 (6) For 𝑖 ∈ [𝑛], 𝑧 ∈ [2 ], R computes 𝑣𝑖,𝑧 𝑘 ∈ [𝑑 ] 𝑣𝑖,𝑘,𝑧 . S computes 𝑣𝑖,𝑧 = 𝑘 ∈ [𝑑 ] 𝑣𝑖,𝑘,𝑧 . S S R 𝑑 (7) For 𝑖 ∈ [𝑛], 𝑧 ∈ [2 ], S sends 𝑣𝑖,𝑧 and R reconstructs 𝑣𝑖,𝑧 = 𝑣𝑖,𝑧 + 𝑣𝑖,𝑧 . Í (8) For 𝑗 ∈ [𝑚], S computes 𝑠 𝑗 = 𝑘 ∈ [𝑑 ] 𝑠 𝑗,𝑘 . ′ (9) S computes 𝑋 = {𝐻𝜆 ′ +𝑑𝑢 (𝑠 𝑗 ) ⊕ (0𝜆 ∥𝒒 𝑗 ) } 𝑗 ∈ [𝑚] and sends shuffled 𝑋 to R. ′ (10) R sets 𝐼 = ∅ and parses 𝑋 as {𝑥 𝑗 } 𝑗 ∈ [𝑚] . For 𝑗 ∈ [𝑚], 𝑖 ∈ [𝑛], 𝑧 ∈ [2𝑑 ], if 𝐻𝜆 ′ +𝑑𝑢 (𝑣𝑖,𝑧 ) ⊕ 𝑥 𝑗 = 0𝜆 ∥𝒒, update 𝐼 = 𝐼 ∪ {𝒒}.

Figure 25: Protocol of prefix-optimized fuzzy PSI for 𝐿∞ distance under sender-sided unique cell assumption. 𝐿𝑝

Protocol ΠFPSI-Px Parameters: Sender S and receiver R with input sizes 𝑚 and 𝑛. Threshold 𝛿. Bit length ℓ = 𝜆 + 𝑑 + log 𝑚 + 𝑝 log 𝛿. Prefix length 𝜇 = 1 + log 𝛿 Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ U𝑑 ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ U𝑑 ×𝑛 . Protocol: S } (1) For 𝑖 ∈ [𝑛], R computes C𝑖R = cell2𝛿 (𝒘𝑖 ). For 𝑗 ∈ [𝑚], S computes { C𝑗,𝑧 𝑧 ∈ [2𝑑 ] = neigh2𝛿 (𝒒 𝑗 ). R ∗ (2) R sets List = { ( C𝑖 ∥𝑘 ∥𝜎 ∥ 𝑤˜ 𝑖,𝑘,ℎ,𝜎 , |𝑤 − 𝑤𝑖,𝑘 | ) }𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ],𝜎 ∈ [0,1] where { 𝑤˜ 𝑖,𝑘,ℎ,0 }ℎ∈ [𝜇 ] = PxTrie(𝑤𝑖,𝑘 − 𝛿, 𝑤𝑖,𝑘 ) and { 𝑤˜ 𝑖,𝑘,ℎ,1 }ℎ∈ [𝜇 ] = PxTrie(𝑤𝑖,𝑘 + 1, 𝑤𝑖,𝑘 + 𝛿 ) and 𝑤 ∗ = UpBound( 𝑤˜ 𝜎,𝑖,𝑘,ℎ ) if 𝜎 = 0 otherwise 𝑤 ∗ = LowBound( 𝑤˜ 𝜎,𝑖,𝑘,ℎ ). S ∥𝑘 ∥𝜎 ∥ 𝑞˜ (3) S computes query = { C𝑗,𝑧 𝑗,𝑘,ℎ } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ],ℎ∈ [𝜇 ],𝜎 ∈ [0,1] where {𝑞˜ 𝑗,𝑘,ℎ }ℎ∈ [𝜇 ] = PxPath(𝑞 𝑗,𝑘 , 𝛿/2). (4) R and S invoke functionality Fso-OPPRF where R inputs List and S inputs query. R receives {𝑒 R𝑗,𝑘,𝑧,ℎ,𝜎 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ],ℎ∈ [𝜇 ],𝜎 ∈ [0,1] and S receives {𝑒 S𝑗,𝑘,𝑧,ℎ,𝜎 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ],ℎ∈ [𝜇 ],𝜎 ∈ [0,1] . (5) For 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑 ], 𝑧 ∈ [2𝑑 ], ℎ ∈ [𝜇 ], 𝜎 ∈ [0, 1], R and S invoke functionality FB2A , where R inputs 𝑒 R𝑗,𝑘,𝑧,ℎ,𝜎 and S inputs 𝑒 S𝑗,𝑘,𝑧,ℎ,𝜎 . R receives 𝑠 R𝑗,𝑘,𝑧,ℎ,𝜎 and S receives 𝑠 S𝑗,𝑘,𝑧,ℎ,𝜎 . (6) For 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑 ], 𝑧 ∈ [2𝑑 ], ℎ ∈ [𝜇 ], 𝜎 ∈ [0, 1], R and S invoke ΠgetDist where R inputs 𝑠 R𝑗,𝑘,𝑧,ℎ,𝜎 and S inputs (𝑠 S𝑗,𝑘,𝑧,ℎ,𝜎 , 𝑞 𝑗,𝑘 , 𝑞˜ 𝑗,𝑘,ℎ , 𝜎 ). R 𝑝

receives 𝑣 R𝑗,𝑘,𝑧,ℎ,𝜎 and S receives 𝑣 S𝑗,𝑘,𝑧,ℎ,𝜎 . (7) For 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑 ], 𝑧 ∈ [2𝑑 ], R

Cmp,2·𝜇

where R inputs {𝑣 R𝑗,𝑘,𝑧,ℎ,𝜎 }ℎ∈ [𝜇 ],𝜎 ∈ [0,1] and S inputs S R S {𝑣 𝑗,𝑘,𝑧,ℎ,𝜎 }ℎ∈ [𝜇 ],𝜎 ∈ [0,1] . R receives 𝑑 𝑗,𝑘,𝑧 and 𝑑 𝑗,𝑘,𝑧 . Í R =Í R S S (8) For 𝑗 ∈ [𝑚], 𝑧 ∈ [2𝑑 ], R computes 𝑟 𝑗,𝑧 𝑘 ∈ [𝑑 ] 𝑑 𝑗,𝑘,𝑧 and S computes 𝑟 𝑗,𝑧 = 𝑘 ∈ [𝑑 ] 𝑑 𝑗,𝑘,𝑧 . 𝑝 R S . R receives 𝑏 R S 𝛿 𝑑 𝑝 (9) For 𝑗 ∈ [𝑚], 𝑧 ∈ [2 ], R and S invoke functionality FInterval where R inputs 𝑟 𝑗,𝑧 and S inputs 𝑟 𝑗,𝑧 𝑗,𝑧 = 1{𝑟 𝑗,𝑧 + 𝑟 𝑗,𝑧 ≤ 𝛿 }. Ô and S invoke functionality FConSel

(10) For 𝑗 ∈ [𝑚], R computes 𝑏 𝑗 = 𝑧 ∈ [2𝑑 ] 𝑏 𝑗,𝑧 . (11) For 𝑗 ∈ [𝑚], R and S invoke functionality FOT where R inputs 𝑏 𝑗 and S inputs (⊥, 𝒒 𝑗 ). R receives 𝒖 𝑗 . (12) R outputs 𝐼 = {𝒖 𝑗 | 𝑏 𝑗 = 1 for 𝑗 ∈ [𝑚] }.

Figure 26: Protocol of prefix-optimized fuzzy PSI for 𝐿𝑝 distance under receiver-sided unique cell assumption.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Xinpeng Yang et al.

𝐿𝑝

Protocol Π FPSI Parameters: Distance threshold 𝛿. Bit length ℓ = 𝜆 + log 𝑚 + 𝑝 log 𝛿. Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ U𝑑 ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ U𝑑 ×𝑛 . Protocol: R } S (1) For 𝑖 ∈ [𝑛], R computes { C𝑖,𝑧 𝑧 ∈ [2𝑑 ] = neigh2𝛿 (𝒘𝑖 ). For 𝑗 ∈ [𝑚], S computes C𝑗 = cell2𝛿 (𝒒 𝑗 ). R ∥𝑘 ∥𝑤 𝑝)} (2) R sets List = { ( C𝑖,𝑧 + 𝑡,|𝑡 | 𝑖,𝑘 𝑖 ∈ [𝑛],𝑘 ∈ [𝑑 ],𝑧 ∈ [2𝑑 ],𝑡 ∈ [-𝛿,𝛿 ] (3) R and S invoke functionality Fso-OPPRF where R inputs List and S inputs { C𝑗S ∥𝑘 ∥𝑞 𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ] . R receives {𝑒 R𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ] and S receives {𝑒 S𝑗,𝑘 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ] . (4) For 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑 ], S and R invoke functionality FB2A , where S inputs 𝑒 S𝑗,𝑘 and R inputs 𝑒 R𝑗,𝑘 . S receives 𝑠 S𝑗,𝑘 and R receives 𝑠 R𝑗,𝑘 . Í Í (5) For 𝑗 ∈ [𝑚], R computes 𝑟 𝑗R = 𝑘 ∈ [𝑑 ] 𝑠 R𝑗,𝑘 and S computes 𝑟 𝑗S = 𝑘 ∈ [𝑑 ] 𝑠 S𝑗,𝑘 𝑝

𝛿 (6) For 𝑗 ∈ [𝑚], R and S invoke functionality FInterval where R inputs 𝑟 𝑗R and S inputs 𝑟 𝑗S . R receives 𝑏 𝑗 = 1{𝑟 𝑗R + 𝑟 𝑗S ≤ 𝛿 𝑝 }. (7) For 𝑗 ∈ [𝑚], R and S invoke functionality FOT where R inputs 𝑏 𝑗 and S inputs (⊥, 𝒒 𝑗 ). R receives 𝒖 𝑗 . (8) R outputs 𝐼 = {𝒖 𝑗 | 𝑏 𝑗 = 1 for 𝑗 ∈ [𝑚] }.

Figure 27: Protocol of fuzzy PSI for 𝐿𝑝 distance under receiver-sided unique block assumption. ∞ Protocol Π𝐿FPSI-Px

Parameters: Distance threshold 𝛿. Bit length 𝜇 = log 𝛿 + 2 and ℓ = 𝜆 + log(𝑚𝑑𝜇 ) Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ U𝑑 ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ U𝑑 ×𝑛 . Protocol: R } S (1) For 𝑖 ∈ [𝑛], R computes { C𝑖,𝑧 𝑧 ∈ [2𝑑 ] = neigh2𝛿 (𝒘𝑖 ). S shuffles 𝑄 and computes C𝑗 = cell2𝛿 (𝒒 𝑗 ) for 𝑗 ∈ [𝑚]. R ℓ (2) R sets List = { ( C𝑖,𝑧 ∥𝑘 ∥ 𝑤˜ 𝑖,𝑘,ℎ , 0 ) }𝑖 ∈ [𝑛],𝑧 ∈ [2𝑑 ],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ] where { 𝑤˜ 𝑖,𝑘,ℎ }ℎ∈ [𝜇 ] = PxTrie(𝑤𝑖,𝑘 − 𝛿, 𝑤𝑖,𝑘 + 𝛿 ) (3) S computes { C𝑗S ∥𝑘 ∥ 𝑞˜ 𝑗,𝑘,ℎ } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ] where {𝑞˜ 𝑗,𝑘,ℎ }ℎ∈ [𝜇 ] = PxPath(𝑞 𝑗,𝑘 , 𝛿 ) (4) R and S invoke functionality Fso-OPPRF where R inputs List and S inputs { C𝑗S ∥𝑘 ∥ 𝑞˜ 𝑗,𝑘,ℎ } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ] . R receives {𝑒 R𝑗,𝑘,ℎ } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ] and S receives {𝑒 S𝑗,𝑘,ℎ } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ] . Eq,𝜇

R and S (5) For 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑 ], R and S invoke functionality FConSel where R inputs {𝑒 R𝑗,𝑘,ℎ }ℎ∈ [𝜇 ] and S inputs { −𝑒 S𝑗,𝑘,ℎ }ℎ∈ [𝜇 ] . R receives 𝑟 𝑗,𝑘 S . receives 𝑟 𝑗,𝑘

(6) For 𝑗 ∈ [𝑚], R computes 𝑟 𝑗R =

Í R S S 𝑘 ∈ [𝑑 ] 𝑟 𝑗,𝑘 . S computes 𝑟 𝑗 = 𝑘 ∈ [𝑑 ] 𝑟 𝑗,𝑘 R (7) For 𝑗 ∈ [𝑚], R and S invoke functionality FEq where R inputs 𝑟 𝑗 and S inputs −𝑟 𝑗S . R receives 𝑏 𝑗 = 1{𝑟 𝑗R = −𝑟 𝑗S }. Í

(8) For 𝑗 ∈ [𝑚], R and S invoke functionality FOT where R inputs 𝑏 𝑗 and S inputs (⊥, 𝒒 𝑗 ). R receives 𝒖 𝑗 . (9) R outputs {𝒖 𝑗 | 𝑏 𝑗 = 1 for 𝑗 ∈ [𝑚] }.

Figure 28: Protocol of prefix-optimized fuzzy PSI for 𝐿∞ distance under receiver-sided unique block assumption.

Efficient Fuzzy PSI under One-Sided Assumptions

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

𝐿𝑝

Protocol ΠFPSI-Px Parameters: Distance threshold 𝛿. Bit length ℓ = 𝜆 + log 𝑚 + 𝑝 log 𝛿. Input: S inputs 𝑄 = {𝒒 𝑗 } 𝑗 ∈ [𝑚] ∈ U𝑑 ×𝑚 and R inputs 𝑊 = {𝒘𝑖 }𝑖 ∈ [𝑛] ∈ U𝑑 ×𝑛 . Protocol: R } S (1) For 𝑖 ∈ [𝑛], R computes { C𝑖,𝑧 𝑧 ∈ [2𝑑 ] = neigh2𝛿 (𝒘𝑖 ). S shuffles 𝑄 and computes C𝑗 = cell2𝛿 (𝒒 𝑗 ) for 𝑗 ∈ [𝑚]. R ∥𝑘 ∥𝜎 ∥ 𝑤 ˜ 𝑖,𝑘,ℎ,𝜎 , |𝑤 ∗ − 𝑤𝑖,𝑘 | ) }𝑖 ∈ [𝑛],𝑧 ∈ [2𝑑 ],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ],𝜎 ∈ [0,1] where { 𝑤˜ 𝑖,𝑘,ℎ,0 }ℎ∈ [𝜇 ] = PxTrie(𝑤𝑖,𝑘 − 𝛿, 𝑤𝑖,𝑘 ) and (2) R sets List = { ( C𝑖,𝑧 { 𝑤˜ 𝑖,𝑘,ℎ,1 }ℎ∈ [𝜇 ] = PxTrie(𝑤𝑖,𝑘 + 1, 𝑤𝑖,𝑘 + 𝛿 ) and 𝑤 ∗ = UpBound( 𝑤˜ 𝑖,𝑘,ℎ,𝜎 ) if 𝜎 = 0 otherwise 𝑤 ∗ = LowBound( 𝑤˜ 𝑖,𝑘,ℎ,𝜎 ). (3) S computes { C𝑗S ∥𝑘 ∥𝜎 ∥ 𝑞˜ 𝑗,𝑘,ℎ } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ],𝜎 ∈ [0,1] where {𝑞˜ 𝑗,𝑘,ℎ }ℎ∈ [𝜇 ] = PxPath(𝑞 𝑗,𝑘 , 𝛿/2). (4) R and S invoke functionality Fso-OPPRF where R inputs List and S inputs { C𝑗S ∥𝑘 ∥𝜎 ∥ 𝑞˜ 𝑗,𝑘,ℎ } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ],𝜎 ∈ [0,1] . R receives {𝑣 R𝑗,𝑘,ℎ,𝜎 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ],𝜎 ∈ [0,1] and S receives {𝑣 S𝑗,𝑘,ℎ,𝜎 } 𝑗 ∈ [𝑚],𝑘 ∈ [𝑑 ],ℎ∈ [𝜇 ],𝜎 ∈ [0,1] . (5) For 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑 ], ℎ ∈ [𝜇 ], 𝜎 ∈ [0, 1], S and R invoke functionality FB2A , where R inputs 𝑣 R𝑗,𝑘,ℎ,𝜎 and S inputs 𝑣 S𝑗,𝑘,ℎ,𝜎 . R receives 𝑠 R𝑗,𝑘,ℎ,𝜎 and S receives 𝑠 S𝑗,𝑘,ℎ,𝜎 . (6) For 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑 ], ℎ ∈ [𝜇 ], 𝜎 ∈ [0, 1], S and R invoke ΠgetDist , where R inputs 𝑠 R𝑗,𝑘,ℎ,𝜎 and S inputs (𝑠 S𝑗,𝑘,ℎ,𝜎 , 𝑞 𝑗,𝑘 , 𝑞˜ 𝑗,𝑘,ℎ , 𝜎 ). R receives 𝑝

𝑑R and S receives 𝑑 S𝑗,𝑘,ℎ,𝜎 . 𝑗,𝑘,ℎ,𝜎 Cmp,2·𝜇

where R inputs {𝑑 R } and S inputs {𝑑 S𝑗,𝑘,ℎ,𝜎 }ℎ∈ [𝜇 ],𝜎 ∈ [0,1] . R 𝑗,𝑘,ℎ,𝜎 ℎ∈ [𝜇 ],𝜎 ∈ [0,1] R S receives 𝑟 𝑗,𝑘 and S receives 𝑟 𝑗,𝑘 Í R and S computes 𝑟 S = Í S (8) For 𝑗 ∈ [𝑚], R computes 𝑟 𝑗R = 𝑘 ∈ [𝑑 ] 𝑟 𝑗,𝑘 𝑘 ∈ [𝑑 ] 𝑟 𝑗,𝑘 . 𝑗 𝑝 R 𝛿 (9) For 𝑗 ∈ [𝑚], S and R invoke functionality FInterval , where R inputs 𝑟 𝑗 and S inputs 𝑟 𝑗S . R receives 𝑏 𝑗 := 1(𝑟 𝑗S + 𝑟 𝑗R ≤ 𝛿 𝑝 ). (10) For 𝑗 ∈ [𝑚], R and S invoke functionality FOT , where R inputs 𝑏 𝑗 and S inputs (⊥, 𝒒 𝑗 ). R receives OT outputs 𝒖 𝑗 . (7) For 𝑗 ∈ [𝑚], 𝑘 ∈ [𝑑 ], R and S invoke functionality FConSel

(11) R outputs {𝒖 𝑗 | 𝑏 𝑗 = 1 for 𝑗 ∈ [𝑚] }.

Figure 29: Protocol of prefix-optimized fuzzy PSI for 𝐿𝑝 distance under receiver-sided unique block assumption. Table 4: The communication (MB) and running time (s) of our protocols for 𝐿𝑝 distance under the receiver-sided unique cell assumption. Size 𝑚 =𝑛

Dim. 𝑑 2

28

4 6 2

212

4 6 2

216

4 6

Metric 𝐿1 𝐿2 𝐿1 𝐿2 𝐿1 𝐿2 𝐿1 𝐿2 𝐿1 𝐿2 𝐿1 𝐿2 𝐿1 𝐿2 𝐿1 𝐿2 𝐿1 𝐿2

𝛿 = 32 Comm Time 3.52 0.23 3.66 0.27 14.24 0.63 14.68 0.58 69.90 2.31 72.38 2.37 36.73 1.26 39.21 1.26 204.80 6.43 214.72 6.10 1098.49 32.75 1139.51 35.11 567.83 14.77 608.85 17.04 3261.14 112.59 3425.32 100.17 17578.29 622.81 18255.49 621.42

𝛿 = 64 Comm Time 4.23 0.28 4.41 0.30 15.63 0.65 16.53 0.64 72.43 2.36 75.42 2.46 48.10 1.40 51.09 1.50 228.55 6.67 240.46 6.71 1139.36 33.70 1188.59 36.70 750.43 19.13 799.66 19.92 3642.86 113.98 3839.89 112.74 18237.60 655.66 19050.23 627.93

𝛿 = 128 Comm Time 5.62 0.28 5.82 0.28 18.39 0.70 19.32 0.78 77.01 2.62 80.48 2.58 70.37 1.86 73.84 1.95 274.09 7.31 287.97 7.72 1212.97 32.79 1270.34 37.35 1107.61 26.11 1164.98 27.85 4374.04 120.13 4603.68 129.88 19421.77 606.16 20368.92 628.95

𝛿 = 256 Comm Time 8.36 0.32 8.94 0.44 23.96 0.84 25.00 0.90 85.66 2.61 89.64 2.70 114.44 2.73 118.41 3.02 363.26 9.08 380.23 10.46 1352.21 38.21 1417.80 40.73 1814.41 40.05 1879.99 48.77 5804.69 156.48 6084.17 167.54 21658.27 688.11 22740.88 749.81

𝛿 = 512 Comm Time 13.83 0.53 14.39 0.58 34.95 0.91 36.12 1.20 102.53 2.82 107.01 3.61 202.10 4.24 206.58 5.17 539.68 12.76 558.78 16.17 1622.54 42.32 1696.37 54.99 3220.26 70.40 3294.09 79.57 8634.00 211.10 8948.50 283.50 25996.49 799.07 27215.29 1119.00

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Xinpeng Yang et al.

Table 5: The communication (MB) and running time (s) of our protocols under the sender-sided unique cell assumption. Size 𝑚 =𝑛

Dim. 𝑑 2

28

4

6

2

212

4

6

2

216

4

6

Metric 𝐿∞ 𝐿1 𝐿2 𝐿∞ 𝐿1 𝐿2 𝐿∞ 𝐿1 𝐿2 𝐿∞ 𝐿1 𝐿2 𝐿∞ 𝐿1 𝐿2 𝐿∞ 𝐿1 𝐿2 𝐿∞ 𝐿1 𝐿2 𝐿∞ 𝐿1 𝐿2 𝐿∞ 𝐿1 𝐿2

𝛿 = 32 Comm Time 2.34 0.26 3.20 0.37 3.20 0.34 8.54 0.55 13.67 0.84 13.67 0.68 40.03 1.83 68.85 2.68 68.85 2.70 25.33 1.11 35.65 1.60 35.65 1.58 124.07 4.88 201.03 7.34 201.03 7.40 628.55 23.78 1082.43 38.90 1082.43 40.07 393.99 18.72 551.86 25.32 551.86 25.20 1976.03 93.68 3196.50 169.05 3196.50 148.73 10056.07 492.81 17297.40 875.75 17297.40 870.23

𝛿 = 64 Comm Time 3.02 0.25 3.89 0.37 3.89 0.39 9.89 0.51 15.03 0.88 15.03 0.84 42.07 1.80 70.90 2.41 70.90 2.76 36.21 1.29 46.53 1.72 46.53 1.76 145.84 5.25 222.80 7.74 222.80 7.98 661.26 23.91 1115.14 40.96 1115.14 40.82 568.43 21.57 726.30 31.87 726.30 28.25 2325.08 98.78 3545.55 145.08 3545.55 162.31 10580.55 505.97 17821.89 837.55 17821.89 835.03

𝛿 = 128 Comm Time 4.38 0.34 5.24 0.40 5.24 0.46 12.61 0.64 17.74 0.87 17.74 0.90 46.15 1.98 74.98 2.78 74.98 2.76 57.98 1.77 68.30 2.19 68.30 2.24 189.41 5.86 266.36 8.72 266.36 8.57 726.72 24.79 1180.59 40.51 1180.59 41.64 917.44 28.09 1075.31 35.44 1075.31 35.62 3023.61 113.03 4244.08 163.49 4244.08 156.41 11630.04 522.84 18871.38 832.43 18871.38 808.55

𝛿 = 256 Comm Time 7.10 0.41 7.96 0.55 7.96 0.55 18.05 0.73 23.18 0.99 23.18 0.96 54.30 2.24 83.12 2.95 83.12 2.87 101.55 2.52 111.86 3.03 111.86 3.11 276.58 7.20 353.54 10.18 353.54 10.20 857.69 28.92 1311.57 45.02 1311.57 44.12 1615.98 41.79 1773.85 47.82 1773.85 53.31 4421.18 139.09 5641.65 196.81 5641.65 190.25 13730.14 600.87 20971.48 963.54 20971.48 987.70

𝛿 = 512 Comm Time 12.53 0.49 13.40 0.64 13.40 0.67 28.93 0.94 34.06 1.16 34.06 1.17 70.67 2.30 99.49 2.95 99.49 3.22 188.72 4.19 199.04 4.51 199.04 4.58 451.02 10.36 527.98 14.20 527.98 13.40 1119.79 32.37 1573.67 49.11 1573.67 52.33 3013.60 69.55 3171.47 75.53 3171.47 90.51 7217.55 192.08 8438.03 249.97 8438.03 260.12 17932.58 669.67 25173.92 1027.60 25173.92 1015.14

Related documents

• On the continuity of the Tukey depth function for fuzzy data#1012512
• Theoretical aspects of the VLSI implementation of fuzzy algorithms : Application to the design automation of current mode fuzzy units#445126
• Exploring Side-Channel Protections in Hardware Implementations of PQC ML-KEM Verification#324821
• Optical nonlinearity in quantum and classical spatial information processing#293630
• A STOCHASTIC PROGRAMMING APPROACH TO THE SINGLEMACHINE MAKESPAN PROBLEM WITH RANDOMBREAKDOWNS#309425