Half-Moon Cookie: Private, Similarity-Based Blocklisting with TOCTOU-Attack Resilience
arXiv:2604.15641v1 [cs.CR] 17 Apr 2026
Xinyuan Zhang Duke University
Anrin Chakraborti University of Illinois at Chicago
Abstract—Blocklisting is a common technique for preventing the use of known malicious content. However, conventional blocklisting infrastructures require either the blocklist to be public or clients to reveal their queries to the blocklist server. In this work, we introduce a private blocklisting framework, Half-Moon Cookie, by which a client can check an item against a proprietary blocklist held by a server, to determine whether the item is close to any blocklist element in a metric space. Critically, our design separates the embedding step from the blocklist check, so that performance degrades with their sum and not their product. Still, this check might be too costly to perform on the critical path of using the item, and so our design also supports a very efficient check that an item previously passed the blocklist check. In doing so, we support applications where one client can perform the blocklist check on the item before sending it, and recipients can more efficiently confirm the previous result before using the item, thereby avoiding TOCTOU attacks. We demonstrate how Half-Moon Cookie can be instantiated for similarity-based malware detection, enabling effective identification of malicious executables without revealing client inputs or disclosing the underlying blocklist. Index Terms—Private blocklisting, TOCTOU attacks, Malware detection
1. Introduction Blocklisting is a core primitive of computer security that is relied upon daily to interfere with proliferation or use of malware [65, 85], unsolicited or fraudulent email [39], revoked certificates [11], malicious domains [81], malicious IP subnets [5, 6, 80], child sexual abuse material (CSAM) [3, 4, 37, 73], and other malicious artifacts [2]. When the blocklist and/or the artifacts checked against it are private or proprietary, verifying that an artifact is not on a blocklist might require using a cryptographic protocol to hide the blocklist from the client with the artifact and the artifact from the blocklist server. Performing such a blocklist check immediately prior to artifact use can be impractical in some cases, however, particularly if the blocklist check requires a rich cryptographic functionality (e.g., an approximate set intersection [23, 29, 33, 44, 45] using the client’s artifact and the server’s blocklist) that incurs nontrivial cost. Moving this blocklist check to an
Michael K. Reiter Duke University
earlier, more manageable time can lead to time-ofcheck vs. time-of-use (TOCTOU) vulnerabilities [8], if not paired with a confirmation that a previous check is still valid right before the artifact’s use. In this paper we propose a framework by which a client can perform a blocklist check—even an approximate one—at a server, while ensuring privacy of the artifact from the server and privacy of the blocklist from the client. If this explicit check passes, then the server adds a hiding and binding token for the artifact to an allowlist, which this or another client can later confirm has not been revoked, via an implicit check with the server. Like the explicit check, the implicit check preserves the privacy of the artifact (and the blocklist). However, it is much faster and so more practical to perform immediately before the artifact’s use, rendering TOCTOU attacks less of a threat. Due to our design that allowlists an artifact after confirming it is not similar to anything on a blocklist, we refer to our design as “Half-Moon Cookie,” or “Half Moon,” for short.1 We illustrate the utility of Half Moon with a concrete application to blocklisting of executable content (e.g., binaries, scripts, or bytecode). When receiving executable content, it is prudent for recipients to confirm that the content has been checked against a blocklist. To this end, a variety of content hashing techniques have been developed (e.g., [58, 70, 76]), so that executable content that hashes to values close to blocklist elements are flagged as possibly malicious. However, checking proprietary executable content against a proprietary blocklist mandates that this check be performed in a privacy-preserving way— i.e., to hide the content from the blocklist server and the blocklist from the client—which in turn requires a rich cryptographic functionality to perform this check. In the common case that the content sender is outnumbered by the content receivers and can perform this blocklist check off the critical path of distributing the content, it is far more efficient for the sender to perform this check. Half Moon enables the sender to perform this check once, using an explicit check, and then for each receiver to more efficiently perform an implicit check, just before consuming the content. The approximate blocklist check required in the application above, and that we support in Half Moon, determines whether the hash of the sender’s artifact (in the case above, executable content) lies within a 1. A half-moon, or black-and-white, cookie is a cookie with vanilla frosting on one half and chocolate frosting on the other [7].
prespecified distance to the hash of some blocklist element, i.e., in a metric space defined over the hash function range. A core challenge that we need to solve, then, is to guarantee that the sender embeds (i.e., hashes) its artifact correctly, since without such enforcement, a malicious sender could simply check a hash value different from the hash of its artifact. The most direct approach to do so would be to perform the embedding and check together in a single immutable computation, for which a monolithic garbled circuit is a natural candidate (e.g., [53]). As we will show in Sec. 7, however, this approach does not scale well in the number of blocklist elements (or their clusters). The explicit check of Half Moon thus relies on a garbled circuit only for the embedding phase and improves the circuit cost by making it independent of the size of the blocklist. Finally, the implicit check does not leverage a garbled circuit at all, since the receiver is trusted to embed the received artifact correctly, presuming it desires to know whether this artifact was, in fact, previously checked against the blocklist. Even with making the garbled circuit independent of the size of the blocklist, embedding an executable by hashing it within a garbled circuit is itself costly, since executables tend to be large. We optimize the circuit cost further by decoupling it from the input file size, as well, by leveraging techniques from HarthKitzerow et al. [51], while maintaining full security. In Sec. 6.1.2, we present how to split the embedding phase into reusable and non-reusable garbled circuits to save the computation and communication cost, without leaking the garbler’s input. Without such techniques, the latency of a monolithic garbled circuit is 231× the cost of Half Moon’s embedding, while the network traffic is 43,505× that of Half Moon for an average size email attachment (194 kB). To summarize, our contributions are as follows. • We formally define the Half Moon primitive, and provide a general framework to design Half Moon protocols that support an explicit check and a more efficient implicit check that confirms that the provided artifact previously passed an explicit check. • We provide efficient Half Moon implementations for blocklists that can be embedded into a metric space based on Hamming distance. • We demonstrate how Half Moon can be applied to similarity-based malware defense. We show details for how to instantiate the application and empirically analyze the system performance.
2. Related Work Below we discuss protocols with similar design goals and tools that are relevant to our task. Outsourced malware defense: A driving application for Half Moon is to enable a sender of an executable to perform an explicit check with a policy server so that recipients can more efficiently confirm the result via an implicit check, enabling recipients to avoid TOCTOU attacks. Our framework is best suited to
malware detection by fuzzy hashing [63, 76] and provides the content privacy necessitated by outsourcing this scanning to a third-party service with a proprietary blocklist. CloudAv [69] was the first work to outsource malware scanning to a cloud that runs the anti-virus engines. SplitScreen [28] and RScam [83] enhance client and malware vendor privacy by sending only compact representations of the files/malware signatures over the network, but provide no cryptographic protections to the data. Perhaps closest to our envisioned design, Sun et al. [84] proposed a privacypreserving cloud-based malware detection scheme. However, it works by exactly matching client input files with malware signatures, necessitating a very large blocklist—and resulting high protocol cost—to achieve effective coverage. More distantly related to our work are solutions to perform middlebox functionalities over encrypted traffic and encrypted rules (e.g., [40, 60, 66, 79]) and privacy-preserving spam filtering that combines machine learning classifiers and MPC, functional encryption, or homomorphic encryption [61, 72, 86] to privately filter communication. None of these designs, however, offer a faster, implicit check to confirm that an artifact previously passed a slower, explicit check. Private blocklist matching: A line of research has focused on enabling a client to query whether an item appears on a blocklist while preserving the confidentiality of the client’s input. This paradigm has been adapted to applications such as malware detection [26], spam filtering [54], and credential breach checks [62]. Kogan and Corrigan-Gibbs [57] provide a generic private blocklist lookup construction with two-server PIR. Private Hash Matching [59] is a service designed for end-to-end encrypted messaging, where a server matches a client’s media content against a set of images (e.g., child sexual abuse material) while hiding the server’s hash set or nonmatching content from the client. But none of the above schemes generate a hiding and binding token after the match to allow for faster verifications later on the same content (as in our implicit check). Some OPRF variations bear similarity to our Half Moon primitive, as well. Programmable OPRFs (OPPRF) [30] and oblivious key-value stores (OKVS) [43] both “program” an OPRF so that the server gets a PRF output for an input w iff w matches a server list item, while the output is pseudorandom elsewhere. All solutions above require exact matching against the entire blocklist, which might be too costly for large blocklists. Scannapieco et al. [77] consider approximate matching over database records but rely on a trusted third party to facilitate the check. Enforcing policies on protocol inputs: Several other protocols address the general problem of ensuring that protocol inputs satisfy some predicate. Some (e.g., [22, 27, 91]) outsource the predicate check to a trusted third party, but in our applications, finding a trusted third party is problematic. Others (e.g., [16, 31, 36, 64, 90]) prove in zero knowledge certain properties of an input. However, the proof complexity increases as a function of the property that
needs to be checked. Besides, zero-knowledge policyenforcement designs work only when the matching pattern and policy circuit are public, while Half Moon aims at keeping the server’s blocklist private. Secure computation tools, e.g., garbled circuits, provide a viable alternative for enforcing policies on protocol inputs. For example, Katz et al. [53] proposed a scheme where a garbled circuit is preceded by a predicate-checking circuit to ensure that the input follows certain properties. A similar construction is proposed by Baum [18]. However, a garbled circuit may not be the most efficient primitive for performing a certain task privately [42], especially when dealing with sets of items. Agrawal et al. [14] proposed an MPC scheme by which a party can commit to a value and use this value subsequently in a secure computation, but it supports only covert security, where cheating can be detected rather than fully prevented. Half Moon provides stronger security and privacy guarantees. PSI-based mechanisms: A part of our design relies on approximately matching an item against a set privately (e.g., using fuzzy PSI mechanisms). Structureaware PSIs [44, 45] rely on spatial hashing, which guarantees reasonable compute costs only under certain assumptions about the data in one (or both) of the input sets. Approximate PSI [33] is a similarly motivated concept that also works only under certain distribution assumptions. As it is unclear if these distribution assumptions hold across a variety of applications, we cannot generally use a structure-aware PSI or an approximate PSI as a building block for a Half Moon. textitDistance-aware PSI [29] and Fuzzy PSI [23] perform fuzzy matching over two sets without any data distribution assumptions. While this incurs a higher cost than both structure-aware PSI and approximate PSI, distance-aware PSI and fuzzy PSI can be applied more broadly because it is agnostic to the data distribution. We will use Chakraborti, et al. [29] as a building block, as we detail in App. B. Unlike Chakraborti et al., [29] Blass and Noubir [23] operates directly on binary vector inputs and is therefore not directly compatible with Half Moon. However, all above solutions either assume a semi-honest client or require non-trivial modifications to ensure a consistent client input between the fuzzy PSI matching and the computation of a hiding and binding token to store at S, to enable a subsequent implicit check. Half Moon does not trust the client during an explicit check and, in particular, detects when the client submits inconsistent inputs from embedding to subsequent checking. Beyond general application-agnostic designs, Wang et al. [87] realize an approximate edit-distance check on genome data. Similar to a Half Moon, they utilize an embedding phase and a test phase to compare entries at the client and the server. Also related is similarity-aware compromised credential checking (C3) [71]. These solutions work in semihonest models only, however. In addition, Half Moon removes the assumptions on the structure of input data
by Wang et al. [87] that are tailored to genome data and may not be applicable to other settings.
3. Use-Case Scenario: TOCTOU Attacks in Email Attachments and URLs 3.1. Background The class of vulnerabilities known as time-of-check vs. time-of-use (TOCTOU) describes inconsistencies that occur when a resource is validated as safe for use but, when actually used later, would have been discovered as unsafe if checked at that time [8]. The inconsistency between the earlier check and the later use can occur because the used item was changed since it was checked or the item was not changed but was discovered to be malicious in the interim. TOCTOU vulnerabilities abound, and indeed the Amazon AWS outage in October 2025 has been at least partly attributed to one [21]. In the scenario we consider here, we are concerned with policy enforcement on content, such as an email attachment, received from an untrusted source. We are agnostic to whether the checked content is sent by value (e.g., itself attached to an email) or by reference (e.g., retrieved using a URL in the email). Empirical analyses from major security vendors have confirmed that TOCTOU-style email threats are widespread (e.g., [1, 68]). In a representative TOCTOU exploitation scenario, an organizational user clicks a link that was previously marked as referencing benign content. Between the initial inspection and user interaction, the adversary replaces the linked content with ransomware, enabling credential theft and account takeover that cascade into broader operational and financial damage. A common model of TOCTOU-resistant malware defense (e.g., see Microsoft Defender [67], Symantec Endpoint Protection [24], and Cisco Secure Endpoint [34]) involves the receiving client querying a remote (typically, cloud-based) server that hosts a curated, proprietary blocklist of known malicious artifact descriptors (e.g., distance-preserving hashes [32, 58, 63, 70, 76]), immediately prior to the artifact’s execution. Because the blocklist is maintained by the vendor, it can update the blocklist frequently from threat feeds, without demanding significant clientside resources (e.g., for local signature databases). However, this approach is known to introduce privacy risks by exposing benign content descriptors to the server, and additionally adds query latency on the critical path of execution. The design we consider here improves on this popular model of malware defense in two ways. First, our design improves the interaction with the server to be privacy-preserving for both the checking client’s content and the server’s blocklist. However, the costs of doing so would add to the receiving client’s latency, and so the second improvement we explore is to move the blocklist check to the sending client, so that this expensive check need not be incurred on the critical path of the receiving client using it.
Because the receiving client does not trust the sending client in our scenario, however, it does require evidence that the sending client checked the artifact at the service. A natural approach would be for the service to (blindly) sign the content after confirming that the content is not on its blocklist, and the sending client forwarding the service’s signature on the content to the receiving client. However, if the receiving client verifies that signature only locally, then the TOCTOU vulnerability would be reintroduced, as the content use might occur after the server updated its blocklist, so that it would have now blocked this content. As such, it is necessary for the receiving client to interact with the service at time of use, anyway, to determine if the content was checked against the latest policy.
3.2. Definitions We are concerned with building a three-party primitive, Half-Moon Cookie (Half Moon in short), where a sending client (Csnd ) checks whether its input w is present on a blocklist held by a server (S). If not, the server will add a token to an allowlist so that a receiving client (Crcv ) can confirm that the value w′ it receives from Csnd is present on the allowlist. At the same time, w is hidden from S, while S’s blocklist is hidden from Csnd and Crcv . We start with defining necessary notations. 3.2.1. Notations Let g : K × D → R denote a function family with keyspace K, domain D, and range R. For k ∈ K, we denote by gk : D → R the function with gk (d) = g(k, d) for each d ∈ D. Let R≥0 denote the non-negative real numbers. For the description of the cryptographic primitives, we use F to denote a finite field, and p ∈ F[x] to denote a polynomial whose coefficients are drawn from F. A random polynomial $ p(x) ← F[x] is a polynomial with coefficients uniformly sampled from F. Given two vectors v⃗1 , v⃗2 ∈ Fθ , v⃗1 × v⃗2 ∈ Fθ , and “×” is the Hadamard product. 3.2.2. Half Moon Definition Half Moon takes an input w ∈ U from Csnd , where U is the input universe, and a list of items Ublk ⊂ U from S. The primitive should produce a binding and hiding mapping on w only if w < Ublk ; if w ∈ Ublk , the protocol should abort. Csnd then forwards w to Crcv . Crcv will interact with S to privately test membership of w on the S stored allowlist. That said, there are many scenarios where the blocklist Ublk is too large to be specified directly as an input to a Half Moon protocol (as we will show in Sec. 7). Therefore, we focus on settings where the set Ublk can be embedded into a metric space Fθ with distance metric d : Fθ × Fθ → R≥0 , where F denotes a finite field and R≥0 denotes the non-negative real numbers. The embedded set can be summarized by a much smaller set L ⊂ Fθ . That is, in lieu of specifying Ublk to the protocol directly, S instead specifies a blocklist L ⊂ Fθ , |L| ≪ |Ublk |, and a threshold T such that elements of Ublk , once embedded in Fθ , should
fall within distance T of some elements of L. Since “similarity” is defined for distance metrics, we use metric embedding, which is standard for information retrieval and approximating text data [25]. Mathematically, for an output ⃗z embedded from an element in Ublk , def blockedL,T (⃗z) = ∃⃗l ∈ L : d ⃗z, ⃗l ≤ T should be true. Naturally, such an embedding will not be perfect, and will introduce non-zero false-accept and falsereject rates. Here we consider a randomized embedding function family of the form f : K f × U → Fθ . For instance, the keyspace K f might include the random vectors used for projections in locality-sensitive hashing algorithms (e.g., [38]). We then define trueand false-reject rates as follows: def
$
blk TRRU = min P blockedL,T (⃗z) k f ← K f ,⃗z ← fk f (w) L,T
w∈Ublk
def
blk FRRU = L,T
$ max P blockedL,T (⃗z) k f ← K f ,⃗z ← fk f (w)
w∈U\Ublk
blk is a lower bound on the probaIn words, TRRU L,T bility of blocking an input w that should be blocked, blk and FRRU is an upper bound on the probability of L,T blocking an input w that should not be blocked. As usual, false- and true-accept rates can be defined by blk def blk blk def blk FARU = 1 − TRRU and TARU = 1 − FRRU , reL,T L,T L,T L,T blk spectively. Naturally, we strive to maximize TRRU L,T blk and TARU . The definition implies that inputs are L,T not uniformly distributed, while keys are. This corresponds to the applications, where inputs are userchosen.
Definition 1 (Half-Moon Cookie). A Half-Moon Cookie for blocklist Ublk is a three-party protocol among a sending client (Csnd ), a receiving client (Crcv ), and a server (S), consisting of two phases: explicit check and implicit check. • Explicit Check: Csnd inputs w ∈ U and S inputs Ublk ⊂ U, L ⊂ Fθ , T ∈ R≥0 (with both L and T computed from Ublk ). This phase succeeds with blk probability at least TARU if w < Ublk and with L,T Ublk probability at most FARL,T otherwise. If this phase succeeds, then Csnd outputs 1 and S outputs state ϕ. Otherwise, S aborts and Csnd outputs 0. • Implicit Check: A client C ∈ {Csnd , Crcv } inputs w′ ∈ U and the server S inputs ϕ. This phase succeeds if ϕ contains an output from a successful explicit check using w′ . If so, C outputs 1. Otherwise, C outputs 0. S has no output. We will define the guarantees that we want to provide from these steps depending on the following threat models. 3.2.3. Threat model The threat models we consider for our applications in Sec. 6 are: T1 The server S and receiving client Crcv are honest, but Csnd is malicious, i.e., Csnd deviates from the protocol to circumvent the check. More specifically, a malicious Csnd should be prevented
from causing S to store a token for a blocklisted input during explicit check, which is successfully verified during an honest implicit check initiated by Crcv . The malicious Csnd may also invoke an implicit check or collude with some Crcv to learn more information about the allowlist, including the secrets contributed by S in its computation., tokens stored at S created by itself or by other users. We require that the allowlist token is binding, meaning that Csnd cannot generate an alternative input w′ that is consistent with an existing allowlist token. In addition, the protocol should not leak more information about Ublk to Csnd than the decision (w ∈ Ublk or not) implies. We note that S needs to limit the number of explicit check attempts. Otherwise, Csnd can online guess the blocklist entries. T2 Csnd and Crcv are honest, but S is honest-butcurious. In this case, our concern is still leaking information about w to S from its interaction with Csnd and Crcv . That is, the allowlist token is hiding, and S’s ability to distinguish between different values of w is negligible. We do not consider a threat model in which S is malicious, simply because we do not find that reasonable in our applications, where S is contracted to, say, provide malware defense for Csnd and Crcv . In such cases, S is incentivized to perform policy checking correctly. In App. D, we discuss how to adapt Half Moon against a server maliciously trying to learn w. In addition, Crcv is considered honest since it is incentivized to perform the check correctly. We discuss more in App. D how Half Moon protects against colluding Csnd and Crcv .
4. Preliminaries Oblivious Linear Evaluation (Fole ): OLE is a twoparty cryptographic primitive between a sender (e.g., a client) and a receiver (e.g., a server). The receiver’s input is x ∈ F; the sender’s inputs are u, v ∈ F. The ideal function Fole returns to the receiver ux + v without revealing u and v. No information is revealed to the sender. In our protocols, we will use the maliciously secure OLE construction by Ghosh et al. [48]. Noisy Polynomial Addition (Fnpa ): Ghosh and Simkin [47] introduced a noisy polynomial addition functionality Fnpa that takes as input pairs of vectors ⃗ ∈ Fθ from one party, say a client, and another r⃗1 , w ⃗ ′ ∈ Fθ from another party, say pair of vectors r⃗2 , w a server, and computes a linear combination of these vectors. Specifically, the functionality returns to either ⃗ + r⃗1 × w ⃗ ′, one or both of the parties the vector r⃗2 × w where “×” is the Hadamard product. The functionality ⃗ to the server and r⃗2 , w ⃗ ′ to the does not reveal r⃗1 , w client (beyond what can be learned from the output). One-time pairwise unpredictable function: We will require a function that is one-time pairwise unpredictable. Intuitively, a keyed-function g : K × D → R is one-time pairwise unpredictable if given the output at a specific point under a randomly chosen key, an
adversary cannot guess the output at another distinct point. The function is one-time in the sense that each new invocation of the function requires a new random key selection to preserve unpredictable outputs. Definition 2. A keyed function g : K × D → R, |K| ≥ |R|, is one-time pairwise unpredictable if under a random choice of a key k ∈ K, and for any two distinct pairs of inputs w, w′ ∈ D, and outputs x, y ∈ R 1 P(gk (w) = x) = |R|
(1)
|R| P(gk (w) = x | gk (w ) = y) = |K|
(2)
′
where the probability is over the choice of the key. The first condition in the definition implies that under a random choice of the key the function acts like a random function. The second condition implies that given the evaluation at a specific point, the value at a different point can be predicted with probability |R| . If |K| ≫ |R|, then this probability is small at most |K| and implies that the value is hard to predict. We now extend this notion to a one-time pairwise unpredictable permutation over vectors in a finite field Fθ We define the properties required from such a permutation below. Definition 3. Let F be a finite field and θ ≥ 1. A keyed-function g : K θ × Fθ → Fθ is one-time pairwise ⃗, w ⃗′ ∈ unpredictable over Fθ if for any pair of input w θ ′ θ F for which |⃗ w∆⃗ w | ≥ d , and outputs ⃗x, ⃗y ∈ F , P gk (⃗ w) = ⃗x = |F|1θ P(gk (⃗ w) = ⃗x | gk (⃗ w′ ) = ⃗y) =
(3) |F| d |K|
(4)
where the probability is over the choice of the key ⃗ and w ⃗ ′ differ k ∈ K θ . Here |⃗ w∆⃗ w′ | = d means that w in at least d components. Intuitively, this definition implies that if two vectors disagree on d components, then the evaluations at these components remain unpredictable. If there is a one-time pairwise unpredictable function g : K × F → F, then we can construct a one-time pairwise unpredictable permutation over the metric space Fθ by using θ independent instances of g, one for each dimension in Fθ .
5. Half Moon Framework Half Moon is realized with a general cryptographic framework. In this section, we will describe the individual building blocks of this framework as ideal functionalities, and then show how to combine them. In Sec. 6, we will describe how to realize these ideal functionalities. Recall that Half Moon has two phases that share states, an explicit check and an implicit check. To accommodate both threat models T1 and T2, we will further split the explicit check functionality into two separate ideal functionalities. Specifically, the explicit check can be viewed as a two-step process: i)
Parameters: An embedding function f : K f × U → Fθ ; a non-programmable random oracle H : {0, 1}∗ → Fθ ; and a one-time pairwise unpredictable permutation family over the metric space P : KP θ × Fθ → Fθ . FEM : Embed-and-Map functionality ⃗ ∈ Fθ . S inputs Inputs: Csnd inputs w ∈ U and m θ θ ⃗ ⃗ k f ∈ K f , ⃗s ∈ F , and k1P , k2P ∈ KP . Output: FEM outputs p⃗1 ← Pk1⃗P ( fk f (w)) and p⃗2 ← ⃗ ) to Csnd ; and Pk2⃗P (⃗y) where ⃗y ← ⃗s × H(w, fk f (w), k f , m S has no output. FTC : Test-and-Commit Functionality Inputs: Csnd inputs p⃗1 , p⃗2 ∈ Fθ . S inputs L ⊂ Fθ , ⃗ P , k2 ⃗ P ∈ KP θ . T ∈ R≥0 , and keys k1 L,T Output: If ¬blocked (P−1⃗ ( p⃗1 )), then FTC outputs k1P 1 and nonce to Csnd and ⃗γ ← P−1⃗ ( p⃗1 ) + P−1⃗ ( p⃗2 ) to S. k1P k2P Otherwise, FTC outputs 0 to Csnd ; S aborts and learns {⃗l ∈ L : d P−1⃗ ( p⃗1 ), ⃗l ≤ T }.2 k1P
FIC : Implicit Check Functionality Inputs: Crcv inputs z⃗1 , z⃗2 ∈ Fθ . S inputs ⃗s, ⃗γ ∈ Fθ . ?
Output: FIC outputs ⃗γ′ ← z⃗1 + ⃗s × z⃗2 to S. If ⃗γ = ⃗γ′ , Crcv receives 1; otherwise, Crcv receives 0.
Figure 1: Ideal Functionalities used in Half Moon Embed-and-Map FEM , that embeds Csnd ’s input into the metric space Fθ , and ii) Test-and-Commit FTC , that performs the predicate check blockedL,T (·) on the embedded input against the embedded blocklist L provided by S. Lastly, during implicit check, Crcv and S participate in iii) Implicit check FIC , that allows fast verification on a previously checked input. We present the details for the three ideal functionalities, which are summarized in Fig. 1.
5.1. Embed-and-Map ⃗ , and Given Csnd ’s input w and a random mask m ⃗ P , k2 ⃗ P , and a random mask ⃗s, this S’s keys k f , k1 functionality first computes p⃗1 ← Pk1⃗P ( fk f (w)) and ⃗ )) where f is an p⃗2 ← Pk2⃗P (⃗s × H(w, fk f (w), k f , m embedding function, P : KP θ × Fθ → Fθ is a onetime pairwise unpredictable permutation family, and H is a hash function modeled as a non-programmable random oracle. p⃗1 and p⃗2 are expected to be inputs to the next functionality (i.e., Test-and-Commit). p⃗1 will be used (after inversion) for testing against the blocklist for approximate matching, and p⃗2 will be used for generating a hiding and binding token as an allowlist entry for the implicit check. We highlight that though we split the explicit check into two phases for concrete efficiency, we maintain the security by carefully “stitching” the two phases. p⃗1 and p⃗2 are ⃗ P , k2 ⃗ P under non-invertible to Csnd without the keys k1 the unpredictable permutation P. As we will see, if 2. Note that the server can implicitly learn this information even if the functionality did not return it, as an abort would imply w is close to one of the server’s inputs.
Csnd is malicious and uses p⃗′1 , p⃗1 and/or p⃗′2 , p⃗2 , it
will be unable to find (with overwhelming probabil⃗′ , m ⃗ that matches an allowlist ity) a w′ , w and a m token that will be stored on S. Therefore, Csnd is “forced” to submit a consistent input to FTC that is generated from FEM . This addresses security against ⃗ P , k2 ⃗P a malicious Csnd (threat model T1). S keeps k1 from FEM for the next functionality FTC .
5.2. Test-and-Commit During Test-and-Commit, the functionality FTC first inverts p⃗1 and checks whether P−1⃗ ( p⃗1 ) (which should k1P be equal to fk f (w) if Csnd is honest) is blocklisted. If not, FTC inverts p⃗2 and outputs an allowlist token ⃗γ ← P−1 ( p⃗ ) + P−1⃗ ( p⃗2 ) to S for updating the allowlist. If ⃗P 1 k1 k2P Csnd inputs the same p⃗1 and p⃗2 that it received from ⃗ ). FEM to FTC , then ⃗γ = fk f (w) + ⃗s × H(w, fk f (w), k f , m ⃗ to Crcv Subsequently, Csnd forwards w and m to use in an implicit check, while S adds a new entry to the allowlist. For a successful check, S ⃗ P , k2 ⃗ P stored from FEM , and adds a token discards k1 ⟨nonce, k f , ⃗s, ⃗γ⟩ to its allowlist. We will explain the use of nonce when describing FIC . Csnd only learns whether the explicit check succeeded in setting up an allowlist token, but does not learn the token itself. As we will prove, ⃗γ hides w due to the random oracle; this addresses the security requirements for a semihonest S (threat model T2).
5.3. Implicit Check To achieve TOCTOU resilience, parties Crcv , who ⃗ , must ensure that the receive Csnd ’s input w and m content w remains policy compliant with the blocklist at use time. However, re-executing an explicit check introduces non-trivial overhead since the cost must be at least linear to the size of L. In many applications (e.g., software distribution, email attachments, and CDN delivery), there will be more content receivers than the content sender and it is necessary for such receivers to repeat the check for the same input w. To mitigate this, S will retain an allowlist with ⟨nonce, k f , ⃗s, ⃗γ⟩ from each successful explicit check. Then, Crcv can verify that a content w is not blocklisted only if a previous explicit check succeeded for that input, achieving verification with a computation cost independent of the blocklist size. During implicit check, Crcv can be provided the embedding key k f by S in the clear, because each explicit check requires a new embedding key, and once Csnd has set up ⃗γ during the explicit check, the embedding key does not provide any additional information/advantage to a malicious Csnd in circumventing the policy check. k f is not an input to the one-time unpredictable function, its exposure has no impact on that property. Crcv uses the forwarded input ⃗ from Csnd to re-compute token z⃗1 ← fk f (w) pair w, m ⃗ ) locally. Then S and Crcv and z⃗2 ← H(w, fk f (w), k f , m interactively and privately evaluate ⃗γ′ ← z⃗1 + ⃗s × z⃗2 . Only S receives the output ⃗γ′ and no further information is given to either Crcv or S. S compares ⃗γ′ against the ⃗γ stored from a previous explicit check. Crcv learns
whether the implicit check has succeeded, implying that ⃗γ′ has matched some ⃗γ from an allowlist token ⟨nonce, k f , ⃗s, ⃗γ⟩. As we will show, ⃗γ is computationally binding, and so it is infeasible for a malicious ⃗ ′ that match an Csnd to find some pair of inputs w′ , m ⃗ allowlist token generated from different inputs w, m during an explicit check. We acknowledge that this design inevitably reveals the correspondence between Csnd and Crcv to S. However, we emphasize that this disclosure stems from the underlying system architecture rather than from a weakness of the protocol itself. In many widely deployed systems—particularly email infrastructures [12] and policy enforcement services [13]—the server must observe both the source and the destination of each request. Eliminating such metadata would require substantial complexity and performance overhead and are outside the scope of our system design. Allowlist: So far we have asserted that the implicit check outperforms the explicit check because the allowlist is much smaller than the blocklist; however, this assumption has not yet been formally justified. In the actual implementation, each explicit check adds one entry to the allowlist. S keeps an identifier for each allowlist entry because when Crcv initiates FIC , S will need to forward k f associated with the allowlist entry Crcv is trying to query. Hence, the implicit check is indexed by a nonce nonce and is implemented with a fast hashtable lookup. nonce is generated from the explicit check timestamp and is independent of the file content to avoid potential leakage over w. The storage overhead grows linearly with the number of explicit checks. We argue that this cost is inherent to our security model: each allowlist entry must incorporate a per-explicit-check server secret to prevent clients from probing existing entries, as well as a client secret to prevent the server from mounting offline attacks to recover w. As was discussed in Sec. 3, Half Moon enables resistance to TOCTOU attacks. Specifically, the allowlist is cleared whenever the blocklist is updated, at which point Crcv is redirected to the explicit check so that the updated policy can be applied. In practice, public blocklists are refreshed on timescales ranging from minutes [50, 82], to hours [74], to days [78]. Private blocklists are typically even harder for an attacker to learn or adapt to, and therefore may require updates less frequently. Consequently, the amortized benefit of the implicit check, which avoids repeated explicit check, will generally outweigh the occasional cost incurred by blocklist updates. We note that TOCTOU vulnerabilities are primarily problematic when the inconsistency window is sufficiently large for an adversary to reliably exploit it. Therefore, we design Half Moon to reduce the time window in which a TOCTOU inconsistency can be exploited rather than eliminating the it entirely. First, even under optimal conditions, executing a query requires a non-zero amount of time, which inherently leaves a brief opportunity for a TOCTOU attack. By shrinking this window to the latency of a single query, Half Moon forces an attacker to act within a very
w, m
kf, s, k1P, k2P
FEM
Csnd
L
S
p1, p2
(1)
Csnd
L, T, k1P, k2P
p1, p2
L
…, [nonce, kf, s, 𝛄 ], …
L
…, [nonce, k f, s, 𝛄 ], …
S
FTC 𝛄
nonce (2) nonce, w, m
Csnd
(3)
nonce
Crcv
S
kf
z1, z2
Crcv
s
FIC 𝛄’
≟
𝛄≟𝛄’ (4)
Figure 2: Framework interaction
narrow timeframe, substantially lowering the probability of successful exploitation. Second, there exists an unavoidable delay for newly emerged threats to be reflected in S’s state, creating a potential zero-day exposure. We argue that this residual delay between server-side updates and client-side checks is inherent to any distributed system and does not represent a weakness specific to Half Moon. Putting it all together: We present the framework utilizing these functionalities in Fig. 3, i.e., assuming that FEM , FTC , and FIC are secure in the threat models in Sec. 3.2.3. In Fig. 2, we visualize the interactions among the ideal functionalities, Csnd , Crcv , and S. We present a formal proof of security of the framework in App. D, relative to the properties of P and H , and how to securely instantiate each ideal functionality in App. E. Below we provide a sketch of the proof. Theorem 5.1. Assuming that there are secure protocol realizing FEM , FTC and FIC , the framework described in Fig. 3 securely realizes Half Moon against the adversaries described in Sec. 3.2.3. Proof (sketch): We prove that the Half Moon framework is secure against threat models T1 and T2. Protection against threat model T1: Consider an adversary that interacts with S. During explicit check, the adversary may try to produce a file input w that should be blocked, but is not detected as such due to a false negative under the embedding function f . Since the embedding key k f is randomly selected and unknown to the adversary, we assume that it is hard for the adversary to produce such a false negative. Alternatively, the adversary may produce file in⃗ ,m ⃗ ′ , such that the explicit puts w , w′ and masks m ⃗ as inputs. However, the check succeeds with w, m ⃗ ′ to an honest receiving client adversary sends w′ , m ⃗ ′ succeeds. Crcv and the implicit check with w′ , m This implies that the adversary has tricked S into authenticating an input for an honest Crcv that was not
Half Moon Framework Inputs: Csnd inputs w ∈ U. S inputs L ⊂ Fθ , T ∈ R≥0 , ⃗ P , k2 ⃗ P ∈ KP θ . and k1 Explicit check: $
$
$
⃗ ← Fθ . S selects ⃗s ← Fθ and k f ← 1) Csnd selects m Kf . ⃗. 2) Csnd and S call FEM . Csnd inputs w and m ⃗ P , k2 ⃗ P . Csnd learns p⃗1 ← S inputs k f , ⃗s, k1 Pk1⃗P ( fk f (w)) and p⃗2 ← Pk2⃗P (⃗y) where ⃗y ← ⃗s × ⃗ ). S gets no output. H(w, fk f (w), k f , m 3) Csnd sets p⃗′1 ← p⃗1 , and p⃗′2 ← p⃗2 . 4) Csnd and S call FTC . Csnd inputs p⃗′1 and p⃗′2 . S in⃗ P , and k2 ⃗ P . If ¬blockedL,T (P−1 ( p⃗′ )) puts L, T , k1 ⃗P 1 k1 then Csnd receives 1 and nonce; S receives ⃗γ ← P−1 ( p⃗ ) + P−1⃗ ( p⃗2 ). Otherwise, Csnd receives 0; S ⃗P 1 k1 k2P aborts and learns {⃗l ∈ L : d P−1⃗ ( p⃗′1 ), ⃗l ≤ T }.
blockedL,T ( f (w)) and the value ⃗γ. As mentioned Ublk k f in Fig. 1, when blockedL,T ( f (w)), there would be Ublk k f inevitable leakage to S. So we ensure that the S should learn strictly no information about w ⃗ is selected ranif ¬blockedL,T ( f (w)). Since m Ublk k f domly and H is a non-programmable random oracle, ⃗ ) is uniformly distributed Fθ . Thus, H(w, fk f (w), k f , m ⃗γ hides w from S. □ We provide the full framework proof in App. D.
6. Protocol Description In this section, we will describe how to efficiently realize the ideal functionalities leveraged in the Half Moon framework. Fig. 4a provides a high-level visualization of the explicit check and Fig. 4b visualizes the implicit check.
k1P
6.1. Protocol for Embed-and-Map
Implicit check: ⃗ ←m ⃗ and 5) Csnd sets nonce ← nonce, w ← w, m ⃗ ′ to Crcv . sends nonce′ , w′ and m 6) Crcv sends nonce′ to S. S indexes the allowlist ϕ with nonce′ and obtains ⟨k f , ⃗s, ⃗γ⟩. S sets k′f ← k f , ⃗s′ ← ⃗s, and ⃗γ′ ← ⃗γ. S sends k′f to Crcv . 7) Crcv computes z⃗1 ← fk′f (w′ ) and z⃗2 ← ⃗ ′ ). H(w′ , fk′f (w′ ), k′f , m 8) Crcv and S call FIC . Crcv inputs z⃗1 , z⃗2 , and S inputs ⃗s′ . S receives ⃗γˆ ← z⃗1 + ⃗s′ × z⃗2 . ? 9) S checks whether ⃗γˆ = ⃗γ′ . If so, Crcv receives 1; otherwise, Crcv receives 0. ′
′
′
Figure 3: Half Moon framework verified by a previous explicit check. We will show next that this happens with probability ≤ |F|/|KP |. ⃗ Suppose that the adversary provides inputs w, m to FEM , and p⃗′1 , p⃗′2 to FTC . Let ⃗γ be the allowlist token stored at S after the explicit check. Now consider that ⃗ ′ to Crcv . It must be that the adversary provides w′ , m ⃗γ = fk f (w′ ) + ⃗s × H(w′ , fk f (w′ ), k f , m ⃗ ′)
(5)
Otherwise, the implicit check, where the honest Crcv ⃗ ′ , and the server provides inputs provides inputs w′ , m k f , ⃗γ, ⃗s, will not verify. Since, FTC sets ⃗γ = P−1⃗ ( p⃗′1 ) + P−1⃗ ( p⃗′2 ), we have k1P
k1P
−1 ⃗′ ′ ⃗′ ⃗ ′) P−1 s × H(w′ , fk f (w′ ), k f , m ⃗P ( p1 )+ Pk1 ⃗P ( p2 ) = fk f (w )+⃗ k1
If p⃗′1 , p⃗1 or p⃗′2 , p⃗2 , then ⃗γ is unpredictable ⃗ P , k2 ⃗ P (Definition 3). In that case, the adwithout k1 ⃗ ′ consistent with (5) only with versary produces w′ , m probability ≤ |F|/|KP |. So, it must be that fk f (w′ ) = ⃗ ′ ) = H(w, fk f (w), k f , m ⃗ ). fk f (w) and H(w′ , fk f (w′ ), k f , m Thus, an adversary that produces w , w′ such that ⃗ ′ ) = H(w, fk f (w), k f , m ⃗ ), also finds H(w′ , fk f (w′ ), k f , m a collision in the random oracle H, which happens with negligible probability in O(θ · log |F|). Protection against threat model T2: The only information S obtains from the protocol is whether
Recall that FEM computes p⃗1 ← Pk1⃗P ( fk f (w)) and ⃗ ). Here, p⃗2 ← Pk2⃗P (⃗y) where ⃗y ← ⃗s × H(w, fk f (w), k f , m f is a function mapping w’s input file to a vector in Fθ , that generates close outputs for similar inputs. Ideally, we would like to use a fuzzy hashing scheme, commonly used for malware similarity tests [58, 70, 76]. Unfortunately, none of these schemes produce outputs in Fθ . Instead, we will define f as a composition of two functions as described below. 6.1.1. Malware Hashing and Embedding Function We begin by selecting hashing schemes that embed files into the Hamming space LSH : K f × {0, 1}∗ → {0, 1}δ . We provide more details on how the hashing scheme is selected in Sec. 7. Then, we will define an injective map, MX from bit-vectors to Fθ . Finally, we have fk f (w) = MX (LSHk f (w)). Definition 4 (Hamming to Fθ map). The mapping function MX : {0, 1}δ → Fθ is parameterized by the set of arbitrary points X ← {x1 , . . . , xθ } ⊂ F for θ ≥ 2δ + 1, and works as follows: ⃗ ∈ {0, 1}δ , use an injective 1) Map to set: Given w function m : {0, 1}×[1, δ] → F to create a set Sw⃗ = ⃗ [ j] is the j-th component {m(⃗ w[ j], j)} j∈δ , where w ⃗. of w 2) Create a Q polynomial: Compute a polynomial ew⃗ (x) ← (x − s), a polynomial with roots in s∈Sw⃗
Sw⃗ . 3) Evaluate the polynomial: Evaluate ew⃗ (x) at the points in X and output a vector ⃗v ← ⟨ew⃗ (x1 ), . . . , ew⃗ (xθ )⟩. The function MX is injective for any value θ ≥ δ + 1 because the polynomial ew⃗ (x) has δ roots, and such a polynomial can be uniquely defined by δ + 1 ⃗ ∈ {0, 1}δ points. Also note that given two vectors w ′ δ ⃗ ∈ {0, 1} , and w ⃗ −w ⃗ ′ H ≤ t ⇐⇒ |Sw⃗ ∩ Sw⃗ ′ | ≥ (δ − t) w
(6)
This follows directly from the definition of Hamming distance. It is immediately obvious from (6)
⃗ = LSHk f (w) and w ⃗ ′ = LSHk f (w′ ), then that if w ′ LSHk f (w) − LSHk f (w ) H can be calculated by computing |Sw⃗ ∩ Sw⃗ ′ |. As we will see later, this is exactly how the distance check is performed in FTC . 6.1.2. Embedding with Reusable Garbled Circuits Given the description of the embedding function f , a protocol realizing FEM will interactively compute fk f (w) = MX (LSHk f (w)). While doing so, it hides S’s inputs—the embedding key k f , the keys for the per⃗ P , k2 ⃗ P , and the mask ⃗s—from the Csnd . It mutation k1 ⃗— also hides Csnd ’s inputs—the file w and the mask m from S. We realize this requirement using a garbled circuit. Specifically, upon being provided w ∈ {0, 1}∗ by Csnd , and k f ∈ K f from S, the garbled circuit computes fk f (w), and outputs fk f (w) to Csnd . However, a naive implementation will be impractical because the size of the garbled circuit will scale linearly in the size of the input file w. Since we do not make any assumptions about the input size, the computation and communication will be prohibitive for large files. To address the scalability issues of the naive solution, we employ reusable garbled circuits. Unlike classical Yao garbling [88, 89], which requires a fresh circuit for each execution, reusable garbled circuits allow the evaluator to run the same garbled circuit repeatedly with different inputs. In our case, the evaluator can reuse the same circuit to handle recurring operations over distinct segments of the input (e.g., iterative scans, loop-based processing, or slidingwindow evaluations). These reusable circuits are then combined with non-reusable segments, thereby emulating executing a monolithic garbled circuit in a more efficient manner. Many reusable garbled circuit schemes [15, 49] rely on expensive cryptographic primitives (e.g., FHE) that limit their practicality. In addition, the security guarantees provided by such schemes are stronger than our requirement in Sec. 3.2.3. More specifically, we observe that our requirements are weaker along two axes: 1) We require reusability only between the two parties: Csnd and S. In contrast, FHE-based reusable garbled circuits allow anyone that possesses the corresponding public key to evaluate. 2) The fuzzy hashing algorithm implemented by the garbled circuit need not be kept private within the garbled circuit. The security of embedding relies only on the input embedding key k f of S (the garbler) being kept secret from Csnd (the evaluator). Based on these observations, we employ optimizations grounded in the CRGC framework [51]. Specifically, CRGC obfuscates a Boolean circuit C to C′ and the garbler’s input a to a′ , while maintaining the circuit functionality. In other words, it generates C′ and a such that C(a, b) = C′ (a′ , b) on any evaluator input b. As a result, the evaluator can treat the garbled circuit as a “black-box reusable program”, but cannot infer intermediate states across runs. This reusability, however, is highly restricted to the type of functionality garbled. The security guarantees offered by CRGC
is circuit-structure dependent, and gates that do not fall into the categories for obfuscation may introduce leakage and expose correlations about input labels. We use the CRGC framework by carefully splitting the f functionality into reusable and non-reusable sections according to the specifications of CRGC. Ideally, operations with size linear to the input size will be encoded to a reusable garbled circuit so that Csnd can evaluate the same functionality repeatedly on its input locally. After this, the outputs from the reusable parts will be input to a non-reusable Yao’s garbled circuit, which will be evaluated interactively between Csnd and S through OT. More specifically, we rely on two main security guarantees offered by a CRGC circuit: 1) A balanced gate (i.e., an XOR or XNOR gate) in the reusable section obfuscates the garbler’s input bit under the security assumptions of CRGC [51, Lemma 2]. 2) A gate in the non-reusable section does not leak garbler’s input bit under the security assumptions of Yao’s garbled circuit protocol [51, Lemma 4]. For the components of f whose size scales linearly with the input, we first determine whether they can be compiled into CRGC form by checking whether they consist of the required balanced gates, or whether they can be augmented with additional balanced gates. In practice, this means that the S may insert extra XOR layers that preserve the original functionality while enabling CRGC compatibility. We then combine the resulting reusable CRGC segments with the remaining non-reusable parts. Under this transformation, Csnd is able to evaluate f without learning the embedding key k f held by S. Since S receives no output from the reusable segments, the security under model T2 continues to rely on the standard guarantees of a conventional garbled circuit. For security model T1, Csnd can evaluate fk f on only a single input w, as the non-reusable components are executed once per session. In addition, if Csnd provides inconsistent inputs to different parts of the garbled circuit, Crcv will not be able to recompute ⃗γ from w. We argue that such a deviation by a malicious Csnd is equivalent to supplying an alternative input w′ , w to Crcv , which is formally addressed in App. D. In the open-source CRGC implementation3 an analysis tool enumerates all signal paths originating from the garbler’s input wires to provide a lower bound on potential leakage. The library classifies a generator input as safe if and only if every such path contains at least two balanced gates and that the resulting circuit achieves the level of indistinguishability necessary for secure, reusable garbling. This tool supports our findings and confirms that our design prevents exposure of any bits of k f . Additional background on how CRGC conceals the garbler’s input (i.e., S’s k f ) is provided in App. B.1. 3. https://github.com/chart21/CRGC
6.1.3. H as a non-programmable random oracle In App. D, we model H as a random oracle for the purposes of analysis. However, when evaluating H inside a garbled circuit, H behaves as a nonprogrammable random oracle [41], which can be represented by a circuit of size polynomial in the security parameter and the input length. Our construction follows the standard methodology of treating hash functions as random oracles [19], but we only rely on properties that hold in the non-programmable setting. In particular: • The adversary may freely evaluate H(·) offline. • The simulator is not required to re-program or adapt the oracle output. Therefore, H can be safely instantiated with a fixed hash function embedded directly in the circuit, consistent with the non-programmable RO framework [17]. θ
6.1.4. Unpredictable permutation for F Recall that the output of FEM is an unpredictable permutation applied to fk f (w) and ⃗y, both vectors in Fθ . We construct such an unpredictable permutation from a random linear combination.4 Specifically, Theorem 6.1. For a random selection of a key ⟨⃗κ1 ,⃗κ2 ⟩ ∈ (F \ {0})θ × (F)θ , the function P⟨⃗κ1 ,⃗κ2 ⟩ (⃗v) = ⃗κ1 × ⃗v + ⃗κ2 is a one-time pairwise-unpredictable permutation over Fθ . The proof is in App. A. Protocol: The protocol ΠEM realizing FEM is described in App. C.1. The protocol computes using a reusable garbled circuit p⃗1 ← P⟨κ⃗1 ,κ⃗2 ⟩ (MX (LSHk f (w))) = κ⃗1 × MX (LSHk f (w)) + κ⃗2 , and p⃗2 ← P⟨κ⃗1 ′ ,κ⃗2 ′ ⟩ (⃗y) = κ⃗1 ′ × ⃗y + κ⃗2 ′ , where ⃗y ← ⃗s × H(w, fk f (w), k f , m ⃗ ) and is also computed by the circuit.
6.2. Protocol for Test-and-Commit The functionality FTC privately compares Csnd ’s input fk f (w) to the embedded items in the blocklist, and produces the authentication token. Since we are using an embedding into the Hamming space, FTC must check that whether the Hamming distance between Csnd ’s input and any of the bit-vectors in the blocklist is greater than the threshold. To perform this check privately, we can apply an assumption-free5 fuzzy PSI scheme that compares vectors in the Hamming space, e.g., [23, 29]. However, a naive application does not suffice because fk f (w) is not a bit-vector, but rather a vector in a field Fθ generated using the map MX . (We ignore the unpredictable permutation P, because as we will see the permutation is inverted before performing the distance check.) We overcome this problem by leveraging the mapping function MX (Definition 4), and defining 4. As it will be evident later, using a linear combination means we can efficiently invert the permutation using Fnpa . 5. An assumption-free fuzzy PSI scheme does not require any specific conditions on the data distribution. Since the output of malware hashes are not constrained to any specific distribution, we must leverage assumption-free schemes only.
a metric such that computing the distance between two vectors in Fθ provides the Hamming distance between their preimages under MX . Then, we modify an existing assumption-free fuzzy PSI protocol to compute Hamming distance using this metric. We define the distance metric symmetric uncommon roots (SUR) as follows. For polynomial p(x) ∈ F[x], let R p(x) be its set of (unique) roots. Let S1 △ S2 denote the symmetric difference between sets S1 and S2 , i.e., (S1 \ S2 ) ∪ (S2 \ S1 ). Definition 5 (Symmetric Uncommon Roots ∥·∥SUR ). Let X ← {x1 , . . . , x2δ+1 } be a set 2δ + 1 unique, fixed elements in F. For vector ⃗v = ⟨v1 , . . . , v2δ+1 ⟩ ∈ F2δ+1 , let p⃗v (x) ∈ F[x] be the unique polynomial of degree ≤ 2δ that interpolates the set of points {(xk , vk )}k∈2δ+1 Then, for v⃗1 , v⃗2 ∈ F2δ+1 , def
v⃗1 − v⃗2 SUR = R pv⃗1 (x) △ R pv⃗2 (x) = R pv⃗1 (x) + R pv⃗2 (x) − 2 · R p(x) where p(x) = gcd(pv⃗1 (x), pv⃗2 (x)) is the greatest common divisor of pv⃗1 (x) and pv⃗2 (x). Since the cardinality of symmetric difference between two sets is a metric, SUR is also a metric. Computing Hamming distance from ∥·∥SUR : Given ⃗ ∈ {0, 1}δ and w ⃗ ′ ∈ {0, 1}δ , two bit vectors w ⃗ −w ⃗ ′ H ≤ t ⇐⇒ |Sw⃗ ∩ Sw⃗ ′ | ≥ (δ − t) w 1 ⇐⇒ (2δ − |Sw⃗ △ Sw⃗ ′ |) ≥ (δ − t) 2 (7) ′ ⇐⇒ MX (⃗ w) − MX (⃗ w ) SUR ≤ T (8) where T = 2t. The equivalences follow by definition of Hamming distance, symmetric difference (7), and SUR (8). In our context, the above relation means LSHk f (w) − LSHk f (w′ ) H ≤ t
⇐⇒
fk f (w) − fk f (w′ ) SUR ≤ 2t
(9)
∥·∥SUR computation from Fnpa : One advantage of using ∥·∥SUR is that we can compute the distance between two vectors contributed by mutually untrusting parties without explicitly revealing the vectors to each other. The process is as follows. Let v⃗1 = MX (⃗ w) and v⃗2 = MX (⃗ w′ ) be two vectors contributed by C and S, respectively. They sample random polynomials $ $ r1 (x) ← F[x] and r2 (x) ← F[x] respectively, of degree δ. Then, they locally compute r⃗1 ← ⟨r1 (x)⟩ x∈X and r⃗2 ← ⟨r2 (x)⟩ x∈X . Finally, using calls to Fnpa , they compute r⃗2 × v⃗1 + r⃗1 × v⃗2 . Then, v⃗1 − (⃗ r2 × v⃗1 + r⃗1 × v⃗2 ) SUR = v⃗2 − (⃗ r2 × v⃗1 + r⃗1 × v⃗2 ) SUR = v⃗1 − v⃗2 SUR
(w.h.p.)
(10)
(10) is due to the fact that r1 (x) and r2 (x) are random polynomials, and so with overwhelming probability, they do not share common roots with
pv⃗1 (x) and pv⃗2 (x) that interpolate v⃗1 and v⃗2 , respectively. Thus, gcd(pv⃗1 (x), c(x)) = gcd(pv⃗2 (x), c(x)) = gcd(pv⃗1 (x), pv⃗2 (x)) with high probability, where c(x) ← r2 (x) · pv⃗1 (x) + pv⃗1 (x) · r1 (x). We prove this in App. B. Crucially, the value of θ ∈ (δ, 2δ + 1) can be set as a function of δ and T such that if ⃗v − ⃗v′ SUR ≤ T , ⃗ ), otherwise no information is then S learns ⃗v (and w ⃗ to the server [29]. Intuitively, the revealed about w idea is that with less than θ ≤ 2δ + 1 points, it is not possible to uniquely define and interpolate the polynomial r2 (x) · ew⃗ (x) + r1 (x) · ew⃗ ′ (x) and thus r⃗1 , r⃗2 , unless ew⃗ (x) and ew⃗ ′ (x) share 2(δ − T ) roots. Protocol: The protocol ΠTC realizing FTC is presented in App. C.2. Intuitively, the protocol is an adaptation of the fuzzy PSI protocol of Chakraborti et al. [29], and checks the Hamming distance between Csnd ’s input and the embeddings in the blocklist by computing the ∥·∥SUR distance. Specifically, recall that one of the outputs of ΠEM is p⃗1 = P⟨⃗κ1 ,⃗κ2 ⟩ ( fk f (w)) = ⃗κ1 × fk f (w) + ⃗κ2 . For each element l in S’s blocklist, the protocol computes r⃗1 × fk f (w) + r⃗2 × fk f (l) using a series of calls to Fnpa . Then, using (10) the protocol computes fk f (w) − fk f (l) SUR , which allows it to check LSHk f (w) − LSHk f (l) H > t due to (9). We set θ ∈ (δ, 2δ + 1) using the parameters suggested in [29] such that if LSHk f (w) − LSHk f (l) H > t, then S learns no information about the Hamming distance. If the distance check is satisfied, the protocol proceeds to computing the authentication token ⃗γ ← P−1 ( p⃗ ) + P−1⃗ ( p⃗2 ). Observe that ⃗γ is a linear com⃗P 1 k1 k2P bination of two vectors in Fθ , and recall from Sec. 4 that P (and so P−1 ) is a random linear combination of its input. Therefore, ⃗y is interactively computed by Csnd and S from p⃗1 and p⃗2 using calls to Fnpa , ensuring that S does not learn P−1⃗ ( p⃗1 ) or P−1⃗ ( p⃗2 ). k1P
k2P
Theorem 6.2. There is a secure protocol realizing FTC with O(nθ) communication and compute costs, assuming that there are secure protocols realizing Fnpa and Fole .
6.3. Implicit Check ⃗ and a nonce After receiving the file w, the mask m nonce, the client Crcv forwards nonce to S. nonce allows the server to identify the authentication token ⃗γ for the file, the embedding key k f , and the mask ⃗s. Crcv recomputes fk f (w) and H(w, fk f (w), k f , m ⃗ ) after obtaining k f from S. Then, Crcv and S invoke Fole , to compute ⃗γ, which is output to S (see Fig. 4b). Finally, Crcv learns whether ⃗γ was previously stored at S, which implies w was checked. The full protocol is described in App. C.3. Theorem 6.3. There is a protocol realizing FIC with
Csnd
S
ΠEM
⃗ w, m p⃗1 = Pk1⃗P ( fk f (w))
⃗ P = ⟨κ⃗1 , κ⃗2 ⟩, k f , k1
Reusable Garbled Circuit
⃗ P = ⟨κ⃗1 ′ , κ⃗2 ′ ⟩, ⃗s k2
= κ⃗1 × fk f (w) + κ⃗2 , p⃗2 = Pk2⃗P (⃗s × h∗ ) = κ⃗1 ′ × (⃗s × h∗ ) + κ⃗2 ′
p⃗1 , r⃗1
ΠTC ⃗ P , r⃗1 ′ l⃗1 , k1
Fnpa r⃗1 ′ × fk f (w) + r⃗1 × l⃗1
... p⃗1 , r⃗n
Test: ∀i ∈ [1, n] fk f (w) − ⃗li > 2t p⃗2 ,
r⃗n ′ × fk f (w) + r⃗n × l⃗n
⃗i i=1 r
Pn
⃗i i=1 r
Pn
nonce
⃗ P , r⃗n ′ l⃗n , k1
Fnpa
′
× fk f (w) + r⃗i × ⃗li ,
⃗ P , k2 ⃗ P , ⃗s ⃗i ′ , k1 i=1 r
Pn
Fnpa
⃗γ = fk f (w) + ⃗s × h∗ Store ⟨nonce, k f , ⃗s, ⃗γ⟩ ⃗ , w, nonce to Crcv Send m
(a) Explicit check Crcv
S
ΠIC fk f (w), h∗
⃗s, ⃗γ
Fole fk f (w) + ⃗s × h∗
(b) Implicit check
Figure 4: High-level description of Half Moon instan⃗ )) tiation (h∗ ← H(w, fk f (w), k f , m
7. Evaluation We implemented the Half Moon-based malware detection6 in C++11. We benchmarked these implementations on a Ubuntu 22.04 machine with 12 cores and 32GB of RAM as the server, and multiple machines that are each equipped with 4 cores and 16GB of RAM as the clients. We used the emptoolkit [9] for OT and garbled circuit operations, and CRGC for reusable garbled circuits. We used the NTL [10] library for finite field arithmetic. The operations were performed in a 128-bit prime-order field. We implemented Ghosh et al.’s OLE [48] and Ghosh et al.’s PSI [46] as building blocks for Half Moon. Our construction works for any metrics that can be embedded into Hamming distance; see App. C.
7.1. Dataset As discussed in Sec. 3, our Half Moon-based malware detection can be applied to email attachments for ransomware checking. We used the Enron dataset [56]
O(θ) communication and compute costs, assuming
that there is a secure protocol realizing Fole .
6. https://github.com/zxinyuan/Half-Moon-Cookie
1
CDF
0.8 0.6 0.4 0.2 0
All attachments Executables 100
101 102 103 File size (kB, log scale)
104
Figure 5: Email attachment size distribution for collecting the general email attachment size distribution. In Fig. 5, we show the cumulative distribution function (CDF) calculated from 133,127 files in https: //trec-legal.umiacs.umd.edu/corpora/trec/legal10/, including files uncompressed from .zip archives. We ignored files with size less than 500 B. The average size of an attachment was 193.6 kB in the Enron dataset, while the median was 98.8 kB. We separated out the executables (files with extensions .exe, .dll, etc.), which had a mean size of 13.7 kB and a median of 3.8 kB. We conducted our experiments based on such statistics. For the malware blocklist, we used the Ember dataset [52], embedding the 16,356,790 malware instances to clusters of different radii.
7.2. Explicit check We start in Sec. 7.2.1 by comparing our explicit check protocol when implemented using the common malware hashes. Then, we turn to measuring throughput of our explicit check protocol in Sec. 7.2.2. 7.2.1. Choosing a hash function Unlike cryptographic hashes, malware hashes (e.g., locality sensitive hashes, context triggered piecewise hashes) can be used as file identifiers that can be compared for estimating file similarity. TLSH [70], ssdeep [58], sdhash [76] are the most common options and are used by VirusTotal and VirusShare. We refer readers to the original works on fuzzy hashing for detailed evaluations of embedding accuracy and similarity detection performance. In general, the accuracy of these fuzzy hashes can be tuned by adjusting the threshold parameter that determines when two digests are considered similar. Half Moon makes black-box use of the hash function and the cost does not depend on the specific threshold value used to classify matches; the computational and communication costs of our scheme remain independent of this parameter choice. Thus, practitioners may select the threshold that best fits their accuracyperformance tradeoff without affecting the efficiency of Half Moon. We first illustrate in Table 1 the utility of our optimizations described in Sec. 6.1.2 that leverage reusable garbled circuits (RGCs) to implement these hash functions in the Embed-and-Map protocol (ΠEM ). This table compares the communication volumes and response times of ΠEM , where response
time is measured at Csnd , starting when it invokes ΠEM and finishing it when it completes that invocation with a lightly loaded S. For each hash function, the table compares cases when the hash function implementation does not (✗) or does (✓) leverage the RGC optimization described in Sec. 6.1.2. (In the case it does not, regular garbled circuits are used, instead.) The size of w was 5 kB, which is about the median size of an email attachment executable. hash
RGCs
Comm. (MB)
Response Time (s)
TLSH
✗ ✓
6.8e4 6.0e1
1.0e3 4.8e0
ssdeep
✗ ✓
5.5e3 5.3e1
2.0e2 5.4e0
sdhash
✗ ✓
5.8e4 1.3e2
9.7e2 2.4e1
Table 1: Embed-and-map (ΠEM ) costs with (✓) and without (✗) reusable garbled circuits (RGCs), with w of size 5 kB As shown in Table 1, for all three hash functions, our RGC optimization reduces communication volume of ΠEM by over two orders of magnitude and response time by at least one order of magnitude. Note that the no-RGC costs shown in Table 1 serve as a very conservative lower bound for an implementation of a full explicit check using a monolithic, conventional garbled circuit. Comparing across hash functions, TLSH provides the fastest response time and ssdeep provides the lowest communication volume. The response time for ΠEM using sdhash (implemented using RGCs) is about 4× that using ssdeep, and the response time using sdhash is 5× more than that using TLSH. Using ssdeep or TLSH results in similar communication volumes, though sdhash induces ∼ 2× more communication. While ssdeep yields a comparably efficient implementation of ΠEM , unfortunately it embeds the digest to edit distance, which is not directly compatible with our Half Moon design. As a result, to use ssdeep for an explicit check, its edit-distance embedding is further embedded into Hamming distance within ΠEM . We do so through edit-sensitive parsing [35], which embeds edit-distance to L1 distance and is then compatible with Chakraborti et al. [29]. This extra embedding step results in an additional 1.23 s in client response time and 4.46 MB in total communication in ΠEM . Moreover, the embedding vector size must be increased to compensate for the approximation introduced by the edit-sensitive parsing, in order to preserve the accuracy of ssdeep, which results in greater cost in the Test-and-Commit protocol implementation (ΠTC ). This extra cost causes the total explicit check response time using ssdeep to exceed the response time using TLSH by a more substantial margin. This can be seen by comparing Table 2a and Table 2b, which show the response times as measured by Csnd for a full explicit check, for various sizes of w and L.
size of w (kB)
|L| 1e2 5e2 1e3 5e3 1e4 5e0 44.7 169.0 319.4 1548.4 3112.9 1e1 61.8 186.9 336.7 1566.6 3129.8 1e2 337.7 456.0 606.7 1839.3 3399.6 2e2 631.8 756.5 904.7 2136.7 3709.7 1e3 3033.2 3160.7 3319.0 4547.6 6100.7
size of w (kB)
(b) ssdeep |L| 1e2 5e2 1e3 5e3 1e4 5e0 45.5 77.3 114.2 421.7 812.7 1e1 101.1 132.0 170.0 477.2 868.3 1e2 658.1 683.7 714.9 1031.5 1420.2 2e2 1253.7 1282.4 1324.5 1631.1 2026.3 1e3 6056.7 6084.5 6121.2 6428.2 6819.4
(c) sdhash
Table 2: Explicit check response time (s) when instantiated with different fuzzy hashes We also tested using sdhash, which transforms w to a Bloom filter whose size scales linearly with w. This expansion significantly increases the communication and computation required during FTC , ultimately slowing overall performance. As such, TLSH outperforms both ssdeep and sdhash in the the overall explicit check for all parameter settings we tested (Table 2a vs. Table 2b vs. Table 2c). Therefore, we pick TLSH for the rest of our Half Moon protocol benchmarking below. 7.2.2. Explicit check throughput To measure the throughput of the explicit check in our Half Moon design, we conducted tests wherein we loaded the server S with increasingly many concurrent client requests until it saturated. Fig. 6 shows the results of these tests. The workload on the server is shown on the x-axis, representing the number of client requests issued concurrently to the server. The y-axis reports the response time per client request, averaged over all clients’ invocations. The black solid line in both plots show the Csnd response time with input size of 10 kB and |L| = 100. Response time remains low and grows slowly with few concurrent client requests, with a single-client request completing in 19.11 s. However, as the concurrency level increases, response time reaches a noticeable inflection point around 250 simultaneous requests. At this load, the average response time spikes, suggesting that the server reached a saturation threshold beyond which queuing and resource contention dominate system performance. The red solid line represents the same functionality in a monolithic garbled circuit. It takes 247 s for a single client to finish the task, while the performance significantly degrades at around 5
avg. response time (s)
(a) TLSH
avg. response time (s)
size of w (kB)
|L| 1e2 5e2 1e3 5e3 1e4 5e0 14.2 44.9 82.7 391.1 781.1 1e1 19.2 49.9 87.7 396.5 786.2 1e2 110.8 138.3 177.8 485.1 876.2 2e2 207.8 240.2 282.5 586.5 978.3 1e3 1012.8 1040.2 1078.3 1387.7 1773.4
1,000
500
0 0
200 400 clients
(a) w is 10 kB. |L| = 1e2 (—); 1e3 (– –); or 1e4 (· ·).
1,000
500
0 0
200 400 clients
(b) |L| = 1e2. w is 1e1 (—); 1e2 (– –); or 2e2 (· ·) kB.
Figure 6: Explicit check throughput. Red line (—) is the same parameter sizes as the black line (—) but with the explicit check functionality implemented in a monolithic garbled circuit. clients. In Fig. 6a, we show results of Half Moon when varying the size of the blocklist, |L|. We observe that the overall throughput degrades more quickly as the number of entries increases, because a larger blocklist directly increases the communication cost between Csnd and S, leading to greater network overhead and earlier saturation. As a result, the turning point, where latency begins to rise sharply, occurs at lower concurrency levels when the L is large. When |L| = 1,000, the saturation threshold is at around 80 clients, while it is at around 20 clients with |L| = 10,000. In Fig. 6b, we vary the Csnd input size. In contrast, the impact on throughput is substantially smaller. Due to the reusable garbled circuit technique described in Sec. 6.1.2, the server-side workload remains independent of the input size, and only the client-side local circuit computation scales with the input length. Therefore, while latency does increase gradually with larger inputs, the shape of the throughput curve remains largely consistent, and the turning point does not shift significantly.
7.3. Implicit check As discussed in Sec. 2, the design of Half Moon is closely related to the functionality provided by an asymmetric fuzzy PSI. In particular, a fuzzy PSI enables one party to learn only the existence of approximate matches between its set and another party’s input under a given distance metric. We compare implicit check to a one-shot fuzzy PSI instantiation for two important reasons. First, implicit check amortizes the cost of private matching by avoiding recomputing proximity against the blocklist for every subsequent check where the same client input must be validated multiple times. Second, implicit check provides resilience against TOCTOU attacks. In a naive fuzzy PSI-based approach, the proximity check and the subsequent use of the result are decoupled; unless it is performed at every use. Therefore, we use asymmetric fuzzy PSI as a natural baseline, as it captures the same level of functionality and security of implicit check. We compare to Chakraborti et al. [29] and Blass
and Noubir [23] since they are also Hammingdistance-based designs and support sets of asymmetric sizes. The TLSH embedding vector is of length 35 bytes, so Chakraborti et al. [29] outperformed Blass and Noubir [23] as its cost is independent of the vector length. We also report the result from Rindal and Schoppmann [75], the state-of-the-art semi-honest exact PSI, which compares against Ublk instead of the embeddings L. As ΠIC requires only a few Fole executions for reconstructing the token and then performs an exact match over the token, it significantly outperforms either a fuzzy PSI or an exact PSI by at least two orders of magnitude in response time and three orders of magnitude in communication volume. Note also that the cost of ΠIC does not depend on the blocklist size.
Implicit check (ΠIC ) Chakraborti et al. [29] Blass and Noubir [23] Rindal and Schoppmann [75]
Comm. (MB)
Response Time (s)
7.2e−3 3.4e1 2.0e3 6.3e2
1.9e−1 1.6e2 2.6e3 6.1e1
Table 3: Implicit check cost comparison on w of size 100 kB
8. Conclusion This paper presents Half-Moon Cookie, which enables a client to determine if its item approximately matches any item of a server’s blocklist, without requiring the client to disclose its item to the server or the server to disclose its blocklist to the client. If the client’s item passes this check, the server is provided a hiding and binding token to that item to store on its allowlist until the blocklist is updated, so that future clients can more efficiently confirm that the item they received was checked against the latest blocklist. We apply Half Moon to malware defense, wherein a sending client performs the (relatively expensive) blocklist check before sending an executable, permitting receiving clients to perform only the (relatively inexpensive) allowlist check before using the executable, enabling them to efficiently avoid TOCTOU attacks. Through judicious protocol construction, Half Moon scales efficiently in the sizes of both the item to be checked and the blocklist.
References [1]
[2]
“Customer advisory: An attack, leveraging spam email, Teams, SharePoint, and OneDrive, potentially linked to the ransomware group Sangria Tempest,” https://www.deepwatch.com/labs/spamemail-attach-teams-sharepoint-and-onedrivepotentially-linked-to-the-ransomware-groupsangria-tempest/, 2024. “EasyList,” https://easylist.to, 2016.
[3]
“Image hash list,” https://www.iwf.org.uk/ourtechnology/our-services/image-hash-list/. [4] “NCMEC, Google and image hashing technology,” https://safety.google/stories/hashmatching-to-help-ncmec/. [5] “Don’t route or peer lists (DROP),” https://www. spamhaus.org/blocklists/do-not-route-or-peer/. [6] “Don’t panic. Protect your network,” https:// www.team-cymru.com/bogon-networks. [7] “Black and white cookie,” https://en.wikipedia. org/wiki/Black and white cookie, 8 Sep. 2025. [8] “CWE-367: Time-of-check time-of-use (TOCTOU) race condition,” https://cwe.mitre.org/ data/definitions/367.html, 2006. [9] “emp-toolkit,” https://github.com/emp-toolkit. [10] “NTL: A library for doing number theory,” https://libntl.org. [11] “Internet x.509 public key infrastructure certificate and certificate revocation list (CRL) profile,” https://datatracker.ietf.org/doc/html/ rfc5280, 2008. [12] “Simple mail transfer protocol,” https://datatracker.ietf.org/doc/html/rfc5321, 2008. [13] “Message submission for mail,” https://datatracker.ietf.org/doc/html/rfc6409, 2011. [14] N. Agrawal, J. Bell, A. Gascón, and M. J. Kusner, “MPC-friendly commitments for publicly verifiable covert security,” in ACM Conference on Computer and Communications Security, 2021. [15] S. Agrawal, “Stronger security for reusable garbled circuits, general definitions and attacks,” in Advances in Cryptology – CRYPTO, 2017. [16] S. Angel, E. Ioannidis, E. Margolin, S. Setty, and J. Woods, “Reef: fast succinct non-interactive zero-knowledge regex proofs,” in USENIX Security Symposium, 2024. [17] C. Barnum, D. Heath, V. Kolesnikov, and R. Ostrovsky, “Adaptive garbled circuits and garbled RAM from non-programmable random oracles,” https://eprint.iacr.org/2023/1527, 2023. [18] C. Baum, “On garbling schemes with and without privacy,” in International Conference on Security and Cryptography for Networks, 2016. [19] M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for designing efficient protocols,” in ACM Conference on Computer and Communications Security, 1993. [20] ——, “Introduction to modern cryptography,” https://web.cs.ucdavis.edu/∼rogaway/classes/ 227/spring05/book/main.pdf, 2004. [21] J. Belotti, “More than DNS: The 14 hour AWS us-east-1 outage,” https://thundergolfer. com/blog/aws-us-east-1-outage-oct20, 26 Oct. 2025. [22] M. Blanton and F. Bayatbabolghani, “Efficient server-aided secure two-party function evaluation with applications to genomic computation,” Proceedings on Privacy Enhancing Technolo-
gies, 2016. [23] E. Blass and G. Noubir, “Assumption-free fuzzy PSI via predicate encryption,” https://eprint.iacr. org/2025/217, 2025. [24] Broadcom, “About the SEP Intensive Protection file reputation service,” https://techdocs.broadcom.com/us/en/symantecsecurity-software/information-security/dataloss-prevention/16-1/about-discovering-andpreventing-data-loss-on-endpoints/aboutthe-sep-intensive-protection-file-reputationservice.html, 4 Sep. 2025. [25] A. Z. Broder, “On the resemblance and containment of documents,” in Compression and Complexity of SEQUENCES, 1997. [26] W. J. Buchanan and H. Ali, “Partial and fully homomorphic matching of IP addresses against blacklists for threat analysis,” arXiv, Tech. Rep., 2025. [27] J. Camenisch and G. M. Zaverucha, “Private intersection of certified sets,” in International Conference on Financial Cryptography and Data Security, 2009. [28] S. K. Cha, I. Moraru, J. Jang, J. Truelove, D. Brumley, and D. G. Andersen, “SplitScreen: Enabling efficient, distributed malware detection,” in 7th USENIX Symposium on Networked System Design and Implementation, Apr. 2010. [29] A. Chakraborti, G. Fanti, and M. K. Reiter, “Distance-aware private set intersection,” in USENIX Security Symposium, 2023. [30] N. Chandran, D. Gupta, and A. Shah, “CircuitPSI with linear complexity via relaxed batch OPPRF,” in Proceedings on Privacy Enhancing Technologies, 2022. [31] I. Chang, K. Sotiraki, W. Chen, M. Kantarcioglu, and R. A. Popa, “HOLMES: A platform for detecting malicious inputs in secure collaborative computation,” in USENIX Security Symposium, 2023. [32] M. S. Charikar, “Similarity estimation techniques from rounding algorithms,” in ACM Symposium on Theory of Computing, May 2002. [33] W. Chongchitmate, S. Lu, and R. Ostrovsky, “Approximate PSI with near-linear communication,” 2024. [Online]. Available: https://eprint.iacr.org/2024/682 [34] Cisco, “File reputation filtering and file analysis,” https://www.cisco.com/c/en/us/td/ docs/security/ces/ces 15-5-3/user guide/b ESA Admin Guide ces 15-5-3/b ESA Admin Guide 12 1 chapter 010001.pdf. [35] G. Cormode and S. Muthukrishnan, “The string edit distance matching problem with moves,” in ACM Symposium on Discrete Algorithms, 2002. [36] H. Corrigan-Gibbs and D. Boneh, “Prio: private, robust, and scalable computation of aggregate statistics,” in USENIX Symposium on Networked System Design and Implementation, 2017. [37] “Child sexual abuse material (CSAM) identification and reporting for U.S. based companies,” https://technologycoalition.org/wp-
content/uploads/CSAM-Identification Reporting R3-1.pdf, 2022. [38] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni, “Locality-sensitive hashing scheme based on p-stable distributions,” in ACM Symposium on Computational Geometry, 2004. [39] “DNS blacklists and whitelists,” https://datatracker.ietf.org/doc/html/rfc5782, 2010. [40] J. Fan, C. Guan, K. Ren, Y. Cui, and C. Qiao, “SPABox: Safeguarding privacy during deep packet inspection at a middlebox,” IEEE/ACM Transactions on Networking, 2017. [41] M. Fischlin, A. Lehmann, T. Ristenpart, T. Shrimpton, M. Stam, and S. Tessaro, “Random oracles with(out) programmability,” in Advances in Cryptology – ASIACRYPT, 2010. [42] S. Garg, M. Hajiabadi, M. Mahmoody, and A. Mohammed, “Limits on the power of garbling techniques for public-key encryption,” in Advances in Cryptology – CRYPTO, 2018. [43] G. Garimella, B. Pinkas, M. Rosulek, N. Trieu, and A. Yanai, “Oblivious key-value stores and amplification for private set intersection,” in Advances in Cryptology – CRYPTO, 2021, p. 395–425. [44] G. Garimella, M. Rosulek, and J. Singh, “Structure-aware private set intersection, with applications to fuzzy matching,” in Advances in Cryptology – CRYPTO, 2022. [45] G. Garimella, B. Goff, and P. Miao, “Computation efficient structure-aware PSI from incremental function secret sharing,” in Advances in Cryptology – CRYPTO, 2024. [46] S. Ghosh and T. Nilges, “An algebraic appproach to maliciously secure private set intersection,” in Advances in Cryptology – EUROCRYPT, 2019. [47] S. Ghosh and M. Simkin, “The communication complexity of threshold private set intersection,” in Advances in Cryptology – CRYPTO, 2019. [48] S. Ghosh, J. B. Nielsen, and T. Nilges, “Maliciously secure oblivious linear function evaluation with constant overhead,” in Advances in Cryptology – ASIACRYPT, 2017. [49] S. Goldwasser, Y. Kalai, R. A. Popa, V. Vaikuntanathan, and N. Zeldovich, “Reusable garbled circuits and succinct functional encryption,” in ACM Symposium on Theory of Computing, 2013, p. 555–564. [50] “Real-time, privacy-preserving url protection,” https://security.googleblog.com/2024/03/blogpost.html, 2024. [51] C. Harth-Kitzerow, G. Carle, F. Fei, A. Luckow, and J. Klepsch, “CRGC – a practical framework for constructing reusable garbled circuits,” in International Conference on Security and Cryptography, 2022. [52] R. J. Joyce, G. Miller, P. Roth, R. Zak, E. Zaresky-Williams, H. Anderson, E. Raff, and J. Holt, “Ember2024 - a benchmark dataset for holistic evaluation of malware classifiers,” in
ACM SIGKDD, 2025. [53] J. Katz, A. J. Malozemoff, and X. Wang, “Efficiently enforcing input validity in secure two-party computation,” 2016. [Online]. Available: https://eprint.iacr.org/2016/184 [54] I. Kim, W. Susilo, J. Baek, J. Kim, and Y. W. Chow, “Pcsf: Privacy-preserving content-based spam filter,” 2023. [55] L. Kissner and D. Song, “Privacy-preserving set operations,” in Advances in Cryptology – CRYPTO, 2005. [56] B. Klimt and Y. Yang, “The enron corpus: A new dataset for email classification research,” in European Conference on Machine Learning, 2004. [57] D. Kogan and H. Corrigan-Gibbs, “Private blocklist lookups with checklist,” in USENIX Security Symposium, 2021. [58] J. Kornblum, “Identifying almost identical files using context triggered piecewise hashing,” 2006. [59] A. Kulshrestha and J. R. Mayer, “Identifying harmful media in end-to-end encrypted communication: Efficient private membership computation,” in USENIX Security Symposium, 2021. [60] C. Lan, J. Sherry, R. Ada Popa, S. Ratnasamy, and Z. Liu, “Embark: Security outsourcing middleboxes to the cloud,” in 13th USENIX Symposium on Networked System Design and Implementation, Mar. 2016. [61] D. Lee, M. Ahn, H. Kwak, J. B. Hong, and H. Kim, “BlindFilter: Privacy-preserving spam email detection using homomorphic encryption,” 2023. [62] L. Li, B. Pal, J. Ali, N. Sullivan, R. Chatterjee, and T. Ristenpart, “Protocols for checking compromised credentials,” in ACM Conference on Computer and Communications Security, 2019. [63] Y. Li, S. C. Sundaramurthy, A. G. Bardas, X. Ou, D. Caragea, X. Hu, and J. Jang, “Experimental study of fuzzy hashing in malware clustering analysis,” in USENIX Conference on Cyber Security Experimentation and Test, 2015. [64] N. Luo, C. Weng, J. Singh, G. Tan, M. Raykova, and R. Piskac, “Privacy-preserving regular expression matching using tnfa,” 2024. [65] “MalwareBazaar,” https://bazaar.abuse.ch. [66] L. Melis, H. J. Asghar, E. De Cristofaro, and M. A. Kaafar, “Private processing of outsourced network functions: Feasibility and constructions,” in ACM International Workshop on Security in Software Defined Networks and Network Function Virtualization, Mar. 2016. [67] Microsoft Defender, “Turn on cloud protection in Microsoft Defender Antivirus,” https://learn.microsoft.com/en-us/defenderendpoint/enable-cloud-protection-microsoftdefender-antivirus, 20 Oct. 2025. [68] Microsoft Threat Intelligence, “File hosting services misused for identity phishing,” https://www.microsoft.com/enus/security/blog/2024/10/08/file-hosting-
services-misused-for-identity-phishing, 2024. [69] J. Oberheide, E. Cooke, and F. Jahanian, “CloudAV: N-version antivirus in the network cloud,” in 17th USENIX Security Symposium, Jul. 2008. [70] J. Oliver, C. Cheng, and Y. Chen, “Tlsh – a locality sensitive hash,” in Cybercrime and Trustworthy Computing Workshop, 2013. [71] B. Pal, M. Islam, M. S. Bohuk, N. Sullivan, L. Valenta, T. Whalen, C. Wood, T. Ristenpart, and R. Chatterjee, “Might i get pwned: A second generation compromised credential checking service,” in USENIX Security Symposium, 2022. [72] M. A. Pathak, M. Sharifi, and B. Raj, “Privacy preserving spam filtering,” arXiv:1102.4021, 2011. [73] “PhotoDNA,” https://www.microsoft.com/en-us/ photodna. [74] “Proofpoint et intelligence,” https: //www.proofpoint.com/sites/default/files/ proofpoint et intelligence ds r5.pdf. [75] P. Rindal and P. Schoppmann, “Vole-psi: Fast oprf and circuit-psi from vector-ole,” in Advances in Cryptology – EUROCRYPT, 2021. [76] V. Roussev, “Data fingerprinting with similarity digests,” in Advances in Digital Forensics, 2010. [77] M. Scannapieco, I. Figotin, E. Bertino, and A. K. Elmagarmid, “Privacy preserving schema and data matching,” in ACM SIGMOD, 2007. [78] “Network reporting,” https://www.shadowserver. org/what-we-do/network-reporting/, 2006. [79] J. Sherry, C. Lan, R. Ada Popa, and S. Ratnasamy, “BlindBox: Deep packet inspection over encrypted traffic,” in ACM SIGCOMM, Aug. 2015. [80] “Spamhaus blocklist (SBL),” https://www. spamhaus.org/blocklists/spamhaus-blocklist/. [81] “Domain blocklist (DBL),” https://www. spamhaus.org/blocklists/domain-blocklist/. [82] “Spamhaus blocklist (sbl),” https: //www.spamhaus.org/faqs/spamhaus-blocklist/. [83] H. Sun, X. Wang, J. Su, and P. Chen, “RScam: Cloud-based anti-malware via reversible sketch,” in 11th International Conference on Security and Privacy in Communication Networks, Oct. 2015. [84] H. Sun, J. Su, X. Wang, R. Chen, Y. Liu, and Q. Hu, “PriMal: Cloud-based privacy-preserving malware detection,” in Australasian Conference on Information Security and Privacy, 2017. [85] “URLhaus,” https://urlhaus.abuse.ch. [86] S. Wang, N. Karunanayake, T. Nguyen, and S. Seneviratne, “Privacy-preserving spam filtering using functional encryption,” arXiv:2012.04163, 2020. [87] X. S. Wang, Y. Huang, Y. Zhao, H. Tang, X. Wang, and D. Bu, “Efficient genome-wide, privacy-preserving similar patient query based on private edit distance,” in ACM Conference on Computer and Communications Security, 2015, pp. 492–503. [88] A. C. Yao, “Protocols for secure computations,”
in IEEE Symposium on Foundations of Computer Science, 1982. [89] ——, “How to generate and exchange secrets,” in IEEE Symposium on Foundations of Computer Science, 1986. [90] C. Zhang, Z. DeStefano, A. Arun, J. Bonneau, P. Grubbs, and M. Walfish, “Zombie: Middleboxes that Don’t snoop,” in USENIX Symposium on Networked System Design and Implementation, 2024. [91] Y. Zhang, M. Blanton, and F. Bayatbabolghani, “Enforcing input correctness via certification in garbled circuit evaluation,” in European Symposium on Research in Computer Security, 2017.
Appendix A. One-Time Pairwise Permutation
Unpredictable-
Theorem. For a random selection of a key ⟨⃗κ1 ,⃗κ2 ⟩ ∈ ⃗ +⃗κ2 is (F \ {0})θ × (F)θ , the function P⟨⃗κ1 ,⃗κ2 ⟩ (⃗ w) = ⃗κ1 × w a one-time pairwise-unpredictable permutation over Fθ . Proof. First note that P is a permutation. For a fixed key k⃗P ← ⟨⃗κ1 ,⃗κ2 ⟩, if there are two vectors v⃗1 ← ⟨v1,1 , . . . , v1,θ ⟩ and v⃗2 ← ⟨v2,1 , . . . , v2,θ ⟩ such that v⃗1 , v⃗2 and P⟨⃗κ1 ,⃗κ2 ⟩ (v⃗1 ) = P⟨⃗κ1 ,⃗κ2 ⟩ (v⃗2 ), then there is at least one k ∈ [1, θ] where v1,k , v2,k but κ1,k · v1,k + κ2,k = κ1,k · v2,k + κ2,k . This leads to a contradiction that F is a field. Also, P is surjective because v −κ v −κ for any vector ⃗v, P−1 (⃗v) = ⟨ 1κ1,12,1 , . . . , θκ1,θ2,θ ⟩ ∈ Fθ . ⟨⃗κ1 ,⃗κ2 ⟩ Note, ⃗κ1 , ⟨0, . . . , 0⟩. it is clear that Now, ⃗ + ⃗κ2 = ⃗v = |F|1θ due to the P P⟨⃗κ1 ,⃗κ2 ⟩ (⃗ w) = ⃗κ1 × w random choice of ⃗κ1 and ⃗κ2 from Fθ . Consider ⃗ ′ ∈ Fθ such that w ⃗ ∆⃗ another arbitrary input w w′ = d ′ ⃗ ∆⃗ where d ∈ [1, θ], i.e., w w is the number of ⃗ and w ⃗ ′ differ. Consider any one dimensions where w such dimension j ∈ [1, θ], and two arbitrary vectors ⃗v, ⃗v′ ∈ F. Then, ⃗ [ j] + κ2, j = v j ∧ κ1, j · w ⃗ ′ [ j] + κ2, j = v′j P κ1, j · w v′j − v j ⃗ = Pκ2, j = v j − κ1, j · w[ j] ∧ κ1, j = ′ ⃗ [ j] − w ⃗ [ j] w 1 = |F \ 0| · |F|
P P⟨⃗κ1 ,⃗κ2 ⟩ (⃗ w) = ⃗v ∧ P⟨⃗κ1 ,⃗κ2 ⟩ (⃗ w′ ) = ⃗v′ !θ−d 1 1 1 = · = ⃗ ∆⃗ w w′ | | |F| |F \ 0|d · |F|θ (|F \ 0| · |F|) By applying Bayes’ theorem, we get the result P(P⟨⃗κ1 ,⃗κ2 ⟩ (⃗ w) = ⃗v | P⟨⃗κ1 ,⃗κ2 ⟩ (⃗ w′ ) = ⃗v′ ) =
1 |F \ 0|d □
Lemma A.1 ([55]). Given two polynomials p1 (x) and p2 (x), and two uniformly random polynomials r1 (x) and r2 (x) of fixed degrees Deg(r1 (x)) ≥ Deg(p2 (x)) and Deg(r2 (x)) ≥ Deg(p1 (x)), the polynomial r3 (x) satisfying the following is a random polynomial. r1 (x) · p1 (x) + r2 (x) · p2 (x) = gcd(p1 (x), p2 (x)) · r3 (x) Proposition A.2. Let v⃗1 , v⃗2 ∈ F2δ+1 . Let r1 (x), r2 (x) ∈ F[x] be random polynomials of fixed degrees Deg(r1 (x)) ≥ Deg(pv⃗1 (x)) and Deg(r2 (x)) ≥ Deg(pv⃗2 (x)). Then, 1 P v⃗1 − v⃗2 SUR , R pv⃗1 (x) + R pv⃗2 (x) − 2 · R p(x) ≤ |F| for p(x) = gcd(pv⃗1 (x), r1 (x)pv⃗2 (x)) 1 P v⃗1 − v⃗2 SUR , R pv⃗1 (x) + R pv⃗2 (x) − 2 · R p(x) ≤ |F| for p(x) = gcd(pv⃗1 (x)r2 (x), pv⃗2 (x)) 1 P v⃗1 − v⃗2 SUR , R pv⃗1 (x) + R pv⃗2 (x) − 2 · R p(x) ≤ |F| for p(x) = gcd(pv⃗1 (x)r2 (x), r1 (x)pv⃗2 (x))
Proof. The proposition follows from the result that given some fixed polynomial p(x) and a random polynomial r(x), we have P gcd(p(x), r(x)) , 1 ≤ 1/ |F| [47]. Due to Lemma A.1, we can compute v⃗1 − v⃗2 SUR from r1 (x) · pv⃗1 (x) + r2 (x) · pv⃗2 (x), knowing either pv⃗1 (x) or pv⃗2 (x), and the degrees of pv⃗1 (x), pv⃗2 (x). This is because gcd(pv⃗1 (x), r1 (x) · pv⃗1 (x) + r2 (x) · pv⃗2 (x)) = gcd(pv⃗1 (x), pv⃗2 (x)) with overwhelming probability. □
Appendix B. Background B.1. CRGC Background
CRGC [51] compiles a Boolean circuit C with garbler input a into an obfuscated circuit C′ and obfuscated The probability reflects the fact that it is always input a′ such that C(a, b) = C′ (a′ , b) for any evaluator possible to produce one pair κ1, j , κ2, j ∈ {F \ 0} × F input b. In other words, C′ does not leak garbler’s to satisfy both equations, and since ⃗κ1 and input to the evaluator while preserving the original ⃗κ2 are selected randomly, any such pair is circuit functionality. In this appendix, we summarize equally likely. Also, for any other dimension the obfuscation techniques and argue about the input ⃗ and w ⃗ ′ differ, i ∈ [1, θ], i , j, where w privacy provided by CRGC. In short, obfuscation pro⃗ [ j] + κ2, j = v j ∧ κ1, j · w ⃗ ′ [ j] + κ2, j = v′j is inP κ1, j · w ceeds via bit flipping and selective gate transforma⃗ [i] + κ2,i = vi ∧ κ1,i · w ⃗ ′ [i] + κ2,i = v′i tions. Gates that admit indistinguishability are placed dependent of P κ1,i · w because each component of ⃗κ1 and ⃗κ2 are in the reusable section, while any remaining gates can selected independently. Thus, we have be handled by a non-reusable, normal garbled circuit.
transformations, g′ is represented by a balanced truth table (XOR/XNOR), or more generally by a passive gate (i.e. a gate that does not introduce new information about the garbler’s input beyond what is already encoded in its input wire labels) modified so as to provide indistinguishability obfuscation. Then g does not leak the garbler’s wire value v to the evaluator under the standard cryptographic assumptions of garbling.
Figure 7: Truth Table for XOR Gates
We start with bit flipping. In CRGC, bit flipping transforms a garbled circuit to be reusable, which is the foundation of Lemma 2. Bit flipping refers to applying a one-time pad over a and all wires in the circuit C to obtain C′ and a′ . Evaluator input b and final output wires do not get flipped. A flipped wire needs to be modified so that the truth table of its child gates maintains the integrity of C. Fig. 7 shows such an example of XOR gates. Note that the truth table of (a) is identical to (b), but the garbler’s input in (a) is flipped while the gate output wire in (b) is flipped. The evaluator cannot distinguish between the two; thus, a is hidden from the evaluator. Similarly, the evaluator cannot tell (c) apart from (d). Concretely, CRGC Lemma 2 shows that flipping inputs/outputs of balanced gates yields pairs of indistinguishable truth tables, so the evaluator has advantage 0 in telling the garbler’s original input bit. Hence each balanced gate provides indistinguishability obfuscation over the garbler’s input. However, bit flipping alone provides privacy only for balanced gates, whose truth tables have symmetric output distributions (i.e. have the same number of 0’s and 1’s). Imbalanced gates do not enjoy this symmetry: even under input flips, the evaluator can still distinguish which inputs yield the gate’s unique outputs. Thus, leakage originating from imbalanced gates may propagate backward toward garbler inputs. To prevent such leakage, CRGC must ensure that every path from a potentially revealing (imbalanced) gate to any garbler input contains at least two balanced gates through intermediary gate transforms. This structural requirement forms the basis of leakage prediction in CRGC frameworks: the library analyzes all paths from imbalanced gates and classifies a garbler input as achieving indistinguishability if and only if every such path contains at least two balanced gates. In Lemma B.1, we argue indistinguishability obfuscation of transformed by CRGC bit flipping and intermediary gate obfuscation. Lemma B.1. Let C′ be the transformed circuit obtained from C by Bit Flipping together with the fixedgate and intermediary-gate transformations. Suppose a gate g lies in the reusable section and, after these
Proof Sketch. Bit Flipping applies a one-time-padstyle mask to garbler wires and all internal wires, and the paper states that under Bit Flipping all balanced gates (XOR/XNOR) achieve indistinguishability obfuscation. In particular, different garbler inputs can yield identical balanced-gate truth tables after flipping, so the evaluator cannot infer the underlying garbler bit by inspection. The paper’s Lemma 2 formalizes this for balanced reusable gates: for XOR/XNOR, u = v′ ⊕ w or u = ¬(v′ ⊕ w) with each wire label masked as v′ = v ⊕ m where $ m ← {0, 1}. Since the evaluator does not know the hidden masks on garbler-side/internal wires, it cannot distinguish the cases v = 0 and v = 1 by inspecting the truth table of g. Hence g does not leak v. Moreover, the fixed-gate and intermediary-gate transformations are specifically used to turn certain level-1 (i.e. gates where one of the input wire corresponds to a garbler’s input wire) or passive gates into balanced/passive forms that provide indistinguishability obfuscation without breaking correctness. Therefore, once a gate has been transformed into such a reusable balanced/passive form, the same indistinguishability argument applies. □ To integrate CRGC into FEM , S first decomposes f into reusable and non-reusable components. This decomposition is guided by whether a subcircuit already satisfies the CRGC non-leakage condition, or can be transformed to do so. To make a circuit compatible with CRGC requirements, S may insert additional XOR layers parameterized by the embedding key k f . The purpose of these inserted balanced gates is to ensure that every path from an output wire back to any garbler input wire contains at least two balanced gates, thereby meeting the structural privacy guarantees required by CRGC. The rest parts that are incompatible with such transforms will be executed via a standard Yao’s garbled circuit. The resulting combination of reusable and non-reusable sections is referred to as a PRGC. In Lemma B.2, we argue such construction of PRGC provides the same level of garbler input privacy as a standard Yao’s garbled circuit. We prove security of FEM instantiation in App. E. Lemma B.2. Let C′ be a PRGC obtained from C such that: 1) Every gate in the reusable section satisfies the reusable-section privacy condition, and in
particular every reusable gate is covered by Lemma B.1 above. 2) Every gate not satisfying that condition is placed in a non-reusable section evaluated with Yao’s garbled-circuit protocol. Then C′ provides the same level of input privacy against a semi-honest evaluator as Yao’s garbledcircuit protocol. Proof Sketch. In Harth-Kitzerow et al. [51], the appendix reduces PRGC input privacy to showing that, in the evaluator’s view, the wire labels in reusable sections are distributed independently of the garbler’s actual input, namely that the relevant wire values satisfy equation (3) in Harth-Kitzerow et al. [51]. Lemmas 1-3 states that all gates in a reusable section are handled by the balanced/passive indistinguishability argument, so the reusable section contributes no information about the garbler input beyond what is already hidden by the masked wire-label distribution. For every gate outside the reusable section, the construction places it in a non-reusable section. Lemma 4 then applies: such a section is evaluated using OT plus Yao garbling, and therefore does not leak v under the security assumptions of Yao’s garbled-circuit protocol. The outputs of each such non-reusable section are either final outputs, which are allowed by functionality, or they re-enter the reusable section at gates that again satisfy equation (3). Therefore, the evaluator’s full view decomposes into: • reusable-section views that are indistinguishable under equation (3), and • non-reusable-section views protected by Yao security. Composing these two kinds of sections yields exactly the PRGC privacy claim stated by the paper: PRGCs do not leak garbler inputs and guarantee the same level of input privacy as Yao’s garbled-circuit protocol. □
B.2. Hamming-distance-aware queries
private
We will use the two-party Hamming-distance-aware query protocol by Chakraborti et al. [29]. Given two ⃗ ∈ {0, 1}δ and w ⃗ ′ ∈ {0, 1}δ , the protocol bit vectors w ′ ⃗ −w ⃗ H ≤ t. If w ⃗ −w ⃗ ′ H > t, then checks whether w ⃗ neither of the parties learn any information about w ⃗ ′ . Here, we will discuss the high level steps, and w which is enough to understand its use in a Half Moon construction. The protocol has two steps: Mapping step: The parties first locally map their ⃗ and w ⃗ ′ , to the metric space respective inputs, w θ (F , ∥·∥SUR ) using the injective map MX : {0, 1}δ → Fθ . MX takes a set X as a parameter, which both parties first agree on. ⃗v ← MX (⃗ w) and ⃗v′ ← MX (⃗ w′ ) are the mapped embeddings. ⃗ −w ⃗′ H ≤ Matching step: To check whether w t, the parties interactively and privately check that
⃗v − ⃗v′ SUR ≤ T = 2t using (6)–(8). As pointed out in ⃗ −w ⃗ ′ H ≤ t is equivalent Chakraborti et al. [29], w ′ to ⃗v − ⃗v SUR ≤ T since MX is injective. For this, the protocol leverages the fact that ∥·∥SUR can be computed using Fnpa due to (10). Crucially, the protocol sets θ ∈ (δ, 2δ + 1) as a function of δ and T such that if ⃗v − ⃗v′ SUR ≤ T , then ⃗ ), otherwise no information the server learns ⃗v (and w ⃗ to the server. Intuitively, the is revealed about w idea is that with less than θ ≤ 2δ + 1 points, it is not possible to uniquely define and interpolate the polynomial r2 (x) · ew⃗ (x) + r1 (x) · ew⃗ ′ (x) and thus r⃗1 , r⃗2 , unless ew⃗ (x) and ew⃗ ′ (x) share 2(δ − T ) roots.
Appendix C. Half-Moon Cookie for Hamming Distance C.1. Embed-and-Map The protocol ΠEM (Fig. 8) realizing FEM perform two tasks: embedding and permutation. S selects keys for both embedding and permutation, produces a garbled circuit with the keys as its inputs, and sends the circuit to Csnd (evaluator). The circuit first embeds Csnd ’s input into Fθ (Step 1). The embedding has to be executed in the garbled circuit as the malicious client is not trusted to honestly embed its inputs. Otherwise, blk a malicious Csnd can set the FARU to 1 through L,T iterating through the input universe. After that, the circuit computes the one-time pairwise-independent permutation P on the mapped input (Step 2). In addition, the circuit also produces a collision-resistant mapping on Csnd ’s input, randomized by both Csnd and S. We explain the necessity of the two blinding ⃗ and ⃗s in the next functionality. factors m Parameters: A keyed one-time pairwise-unpredictable permutation scheme P : KP θ × Fθ → Fθ ; a nonprogrammable random oracle H : {0, 1}∗ → Fθ ; an embedding function f : K f × U → Fθ . ⃗ ∈ Fθ . S’s input Inputs: Csnd ’s input is w ∈ U and m ⃗ P , k2 ⃗ P ∈ KP θ , k f ∈ K f , and ⃗s ∈ Fθ . is a k1 Protocol: S generates a garbled circuit and Csnd executes this circuit as the evaluator. The circuit does the following: ⃗ ← fk f (w) 1) Compute w 2) Output p⃗1 ← Pk1⃗P (⃗ w) and p⃗2 ← Pk2⃗P (⃗s × ⃗ ) to Csnd . H(w, fk f (w), k f , m
Figure 8: ΠEM : Embed-and-Map protocol
C.2. Test-and-Commit The protocol ΠTC (Fig. 9) realizes FTC , where S first locally computes its input set L by mapping each element in Ublk to a vector in Fθ with f . Then, ⃗ − ⃗li the protocol checks w ≤ T for all ⃗li ∈ L SUR (Steps 1–6). S can learn the result from Fnpa (Step 4) ⃗ P , which iff S is able to reverse Csnd ’s input p⃗1 with k1 indicates that the output from ΠEM and the input to ΠTC are consistent.
During commit phase, Csnd and S interactively com⃗ + ⃗ri × ⃗li and ⃗s × pute the summation of ⃗ci ← ⃗ri′ × w ⃗ ) using a series of calls to Fole . They H(w, fk f (w), k f , m start by eliminating ⃗r (Csnd ’s input, in Steps 8–10) ⃗ and ⃗r′ , ⃗l (S’s inputs, in Steps 11–13), without reveal⃗ and ⃗s × H(w, fk f (w), k f , m ⃗ ) individuing either of w ally to S. Csnd and S proceed with computing the ⃗ + ⃗s × H(w, fk f (w), k f , m ⃗) authentication token ⃗γ ← w (Step 12). S locally adds ⟨k f , ⃗s, ⃗γ⟩ to the stored allowlist from the explicit check if blockedL,T ( f (w)) = Ublk k f ⃗ and ⃗s therefore guarantee that i) FALSE (Step 13). m w is hidden from S and S cannot brute force over the input universe on the allowlist entries; ii) Csnd cannot predict/generate the authentication token; iii) the checked input matches the input stored on the S allowlist. Parameters: A set of elements X ← {x1 , . . . , xθ } ⊂ F. Inputs: Csnd ’s input is p⃗1 ← Pk1⃗P (⃗ w) = ⟨p1,1 , . . . , p1,θ ⟩, and p⃗2 ← Pk2⃗P (⃗s × H(w, fk f (w), k f )) = ⟨p2,1 , . . . , p2,θ ⟩ obtained from ΠEM . S’s input is a set L ← { fk f (l) | l ∈ Ublk } ⊂ Fθ of size n derived from ⃗ P , k2 ⃗ P ∈ KP θ Ublk ; a distance threshold T ; and keys k1 ′ ′ ⃗ P = ⟨κ⃗1 , κ⃗2 ⟩ and k2 ⃗ P = ⟨κ⃗1 , κ⃗2 ⟩. where k1 Test Phase 1) For ⃗li = ⟨l⃗i,1 , . . . , l⃗i,θ ⟩ ∈ L, S computes e⃗li (x) by interpolating the set of points {(x1 , l⃗i,1 ), . . . , (xθ , l⃗i,θ )}. 2) Csnd selects n random polynomials r1 (x), . . . , rn (x) of degree δ, and computes ⃗ri ← ⟨ri (x)⟩ x∈X = ⟨ri,1 , . . . , ri,θ ⟩ for i ∈ [n]. 3) S selects n random polynomials r1′ (x), . . . , rn′ (x) of degree δ, and computes ⃗ri′ ← ⟨ri′ (x)⟩ x∈X = ′ ′ ⟨ri,1 , . . . , ri,θ ⟩ for i ∈ [n]. 4) For i ∈ [1, n], S and Csnd call Fnpa : a) Csnd ’s inputs are ⃗ri and Pk1⃗P ( fk f (w)). b) S’s inputs are ⃗ri′ and κ⃗1 × ⃗li . c) S learns ⃗ri′ × Pk1⃗P ( fk f (w)) + ⃗ri × (κ⃗1 × ⃗li ) = ⃗ri′ × (κ⃗1 × fk f (w) + κ⃗2 ) + ⃗ri × (κ⃗1 × ⃗li ) 5) Using κ⃗1 , ⃗ri′ and κ⃗2 , S computes ⃗ci ← ⃗ri′ × fk f (w) + ⃗ri × ⃗li D E = ri′ (x) · ew⃗ (x) + ri (x) · e⃗li (x)
x∈X
.
6) For i ∈ [1, n], S tries to compute gcd(ew⃗ (x), e⃗li (x)) from ⃗ci by interpolating the points [29]. If the interpolation is successful, S sets blockedL,T (⃗ w) = TRUE. Otherwise, it sets blockedL,T (⃗ w) = FALSE. Commit Phase P ′ 7) S computes rc (x) ← ri (x), and r⃗c ← i∈[n]
⟨rc (x)⟩ x∈X . $ ′ ′ 8) S samples t⃗i′ = ⟨ti,1 , . . . , ti,θ ⟩ ← Fθ . For i ∈ [n], k ∈ [θ], Csnd and S call Fole where Csnd ’s input is −ri,k ′ and S’s inputs are l⃗i,k and ti,k . After all the calls, ′ ⃗ ⃗ Csnd learns ti − ⃗ri × li for i ∈ [n]. $
9) S samples ⃗ti = ⟨ti,1 , . . . , ti,θ ⟩ ← Fθ . For i ∈ [n], k ∈ [θ], S and Csnd call Fole , where Csnd ’s input is p2,k , and S’s inputs are rcκ(x′ k ) . After all calls, Csnd 1,k learns (κ⃗1 ′ )−1 × r⃗c × p⃗2 + ⃗ti for i ∈ [n].
10) From the step above, Csnd computes and sends to S ⃗v′ ←
X
t⃗i′ + ⃗ti − ⃗ri × ⃗li + (κ⃗1 ′ )−1 × r⃗c × p⃗2 .
i∈[n]
11) S computes ⃗v ← (
P ⃗′ ti + ⃗ti )+ n· ((κ⃗1 ′ )−1 × r⃗c × κ⃗2 ′ ).
i∈[n]
12) S computes n X 1 −1 ′ ⃗y ← · r⃗c × ⃗ci + ⃗v − ⃗v n i=1 1 = · r⃗c −1 × n n · r⃗c × ( fk f (w) + (κ⃗1 ′ )−1 × p⃗2 − (κ⃗1 ′ )−1 × κ⃗2 ′ ) ⃗ ). = fk f (w) + ⃗s × H(w, fk f (w), k f , m 13) If blockedL,T (⃗ w) = FALSE, S stores ⟨nonce, ⃗γ, k f , ⃗s⟩ and outputs 1 and nonce ← {0, 1}∗ ⃗ . Otherwise, to Csnd . Csnd keeps nonce, w, and m S aborts and Csnd receives a 0.
Figure 9: ΠTC : Test-and-Commit protocol
C.3. Implicit Check The protocol ΠIC (Fig. 9) realizes FIC . Crcv ’s inputs are the re-created outputs of ΠEM , without P, with k f obtained from S (Fig. 3). S may reveal k f to Crcv because k f is randomly chosen for each Csnd and an authentication token ⃗γ for that Crcv will only be stored at S if explicit check goes through. Then, Crcv and S evaluate Fole with the reconstructed inputs and S’s blinding factor ⃗s (Step 3). S will obtain a token ⃗γ′ to be compared to the allowlist (Step 4). Same as ⃗γ, ⃗γ′ hides w′ from S. Crcv learns only a 0/1 output, indicating whether the implicit check is successful or not. Inputs: Crcv ’s input is z⃗1 , z⃗2 ∈ Fθ . S’s input is ⃗s, ⃗γ ∈ Fθ . Protocol 1) Crcv computes ⟨z1,1 , . . . , z1,θ ⟩ ← z⃗1 and ⟨z2,1 , . . . , z2,θ ⟩ ← z⃗2 . 2) S computes ⟨⃗s1 , . . . , ⃗sθ ⟩ ← ⃗s. 3) For k ∈ [1, θ], Crcv and S call Fole . a) Crcv ’s input are z1,k and z2,k . b) S’s input are ⃗sk . c) After all calls, S learns ⃗γ′ ← z⃗1 + ⃗s × z⃗2 . ?
4) S checks whether ⃗γ′ = ⃗γ. If so, S outputs 1 to Crcv ; otherwise, Crcv receives a 0.
Figure 10: ΠIC : Implicit check protocol
Appendix D. Proof of Framework Security In this appendix, we formally prove the framework of Fig. 3 securely realizes the Half Moon design against the adversaries described in Sec. 3.2.3, under the assumption that the constituent functionalities FEM , FTC , FIC are secure. (The proofs of security for these functionalities can be found in App. E.) A
real/ideal proof is compatible in principle; we chose a game-based formulation [20] for clarity and modularity in the current presentation, as it lets us cleanly state each adversary’s goals, and isolate which primitive properties imply which system-level guarantees. We reduce the security of our framework to typical properties of types of function families, which we recount below. Definition 6 (One-time pairwise unpredictability). Let g : K × D → D be a family of permutations, and let A be an algorithm that returns a pair of elements from D. Let Experiment Exptopu g(A) P $
k←K w ← A() x ← gk (w) (w′ , y) ← A(x) if gk (w′ ) = y then return 1 else return 0
$
$
k f ← K f , ⃗s ← Fθ H(·) ⃗ P , k2 ⃗ P , ⃗s)) ⃗ ), (k f , k1 (( p⃗1 , p⃗2 ), ·) ← FEM ((w, m H ⟨ϕ2 , p⃗′1 , p⃗′2 ⟩ ← A2 (·) (ϕ1 , p⃗1 , p⃗2 ) H(·) ⃗′ ⃗′ ⃗ P , k2 ⃗ P )) (b, ⃗γ) ← FTC (( p1 , p2 ), (k1 if ⃗γ = ⊥ then return 0 H(·)
H(·),FIC (·,⃗s)
⃗ ′ ⟩ ← A3 ⟨w′ , m
(ϕ2 , k f )
⃗γ′ ← fk f (w′ ) + ⃗s × H(w′ , fk f (w′ ), k f , m ⃗ ′) ′ ′ if w ∈ Ublk ∧ ⃗γ = ⃗γ then return 1 else return 0 Then, CC AdvCC P,H (A1 , A2 , A3 ) = P ExptP,H (A1 , A2 , A3 ) = 1 CC AdvCC P,H (t, qH , q) = max AdvP,H (A1 , A2 , A3 )
A1 ,A2 ,A3
where the maximum is taken over all adversaries (A1 , A2 , A3 ) running in total time t, with at most qH queries to H, and making at most q oracle queries to FIC (·, ⃗s) from A3 .
Then,
opu
Experiment ExptCC P,H (A1 , A2 , A3 ) ⃗ ⟩ ← AH1 (·) () ⟨ϕ1 , w, m $ $ ⃗ P ← KP θ , k2 ⃗P ← k1 KP θ ,
opu
Advg (A) = P ExptP (A) = 1 opu
opu
Advg (t) = max Advg (A) A
where the maximum is taken over all algorithms A that run in time at most t.
D.1. Security against C D.1.1. In threat model T1 Assuming FEM , FTC , and FIC are secure, then no transcripts are leaked to Csnd and the only information Csnd learns are the outputs. Since L is not involved in the computation of any outputs, it is trivial that no information about Ublk will be leaked to Csnd than the decision (w ∈ Ublk or not) implies in one execution of the explicit check phase. In this threat model, Csnd is malicious and aims to have a token stored at S on some w ∈ Ublk during explicit check and verify at implicit check. As such, the goal of such a Csnd is to cause the following experiment to return 1, where Csnd is denoted as a triple of algorithms (A1 , A2 , A3 ). For each call to the functionalities, each input (output) pairs will be denoted in parenthesis, with the Csnd input (output) as the first item and the S input (output) as the second item.
The key distinctions between the prescribed algorithm in Fig. 3 and ExptCC P,H are that (i) the (malicious) Csnd ⃗ ′ (in A3 ) and p⃗′1 , p⃗′2 (in is permitted to compute w′ , m A2 ), whereas a correct Csnd simply sets w′ ← w, ⃗′ ← m ⃗ , p⃗′1 ← p⃗1 , and p⃗′2 ← p⃗2 ; and (ii) the m malicious Csnd is granted oracle access to FIC (·, ⃗s) to model its repeated attempts at implicit check. Note that we omit nonce in the experiments. An adversarial Csnd may attempt to impersonate an honest Crcv by running the implicit check with S on multiple guessed nonces before relaying any inputs to the real Crcv . It may also collude with multiple Crcv to obtain information stored for other inputs. However, both k f and ⃗s are freshly and independently sampled in every explicit check. Consequently, varying the nonce nonce does not provide Csnd with any additional leverage to probe other entries in the allowlist. The only substantive attack surface is therefore the ability to guess an unknown authentication token ⃗γ by issuing queries to the non-programmable random oracle H. We show that the advantage of a malicious Csnd in compromising a single Half Moon session is negligible; hence, the probability of successfully attacking any aggregate of sessions is also negligible. Proposition D.1. If H is a random oracle, and FEM , FTC , FIC are secure and output correctly, then AdvCC P,H (t, qH , q) blk ≤ FARU + L,T
2 · |F| qH + 1 + |KP | Fθ
for t′ = t + O(1). Proof. Let (A1 , A2 , A3 ) be a Half Moon adversary that runs in time t and makes at most qH queries to H oracle and q queries to FIC oracles.
There are 2 scenarios for w′ from A3 : (i) w′ = w, which means that (malicious) Csnd has a valid authentication token for a blocked input stored at S; (ii) w′ , w, which indicates that Csnd is submitting inconsistent inputs to explicit check and implicit check. We start with (i) w′ = w. First note that ! ′ w = w P ExptCC (A , A , A ) = 1 P,H 1 2 3 ! ¬blockedL,T ( fk f (w)) = P ExptP,H (A1 , A2 , A3 ) = 1 ∧ w ∈ Ublk L,T × P ¬blocked ( fk f (w)) w ∈ Ublk × P(w ∈ Ublk ) ! blockedL,T ( fk f (w)) CC + P ExptP,H (A1 , A2 , A3 ) = 1 ∧ w ∈ Ublk L,T × P blocked ( fk f (w)) w ∈ Ublk × P(w ∈ Ublk ) ≤ P ¬blockedL,T ( fk f (w)) w ∈ Ublk ! blockedL,T ( fk f (w)) + P ExptCC (A , A , A ) = 1 1 2 3 P,H ∧ w ∈ Ublk CC
blk The first term is just FARU , and so for the rest L,T of the proof, we focus on bounding the second term. Recall that ExptCC P,H (A1 , A2 , A3 ) = 1 implies ¬blockedL,T (P−1⃗ ( p⃗′1 )), which implies P−1⃗ ( p⃗′1 ) ,
k1P
k1P
L,T
fk f (w) because blocked ( fk f (w)). A2 wins by producing p⃗′1 and p⃗′2 such that P−1⃗ ( p⃗′1 ) + P−1⃗ ( p⃗′2 ) = k1P k2P fk f (w) + ⃗s × H(w, fk f (w), k f ) ∧ p⃗′1 , p⃗1 ∧ p⃗′2 , p⃗2 . Since k f is kept secret from Csnd during the explicit check, Csnd has to produce p⃗′1 and p⃗′2 by querying P. First, note that A1 gets one invocation to Pk1⃗P (·) and one invocation to Pk2⃗P (·) (both via FEM ) to produce p⃗1 and p⃗2 , respectively, though A2 generates p⃗′1 and p⃗′2 that are passed to P−1⃗ (·) and P−1⃗ (·). Thus, A2 ’s adk1P k2P vantage in producing P−1 ( p⃗′ ) from p⃗1 , p⃗2 is bounded ⃗P k1
1
(t′ ) = 2·|R| by Advopu P |KP | since P is an unpredictable ⃗ P and k2 ⃗ P are chosen function. The keys k1 ⃗ ⃗ independently, and if k2P , k1P , p⃗2 does not provide any information about P−1⃗ ( p⃗′1 ). Due to the random k1P ⃗ P = k1 ⃗ P is |F| . key selection, the probability that k2 |KP | ′ We now consider the case where w , w. In this scenario, a malicious Csnd first stores an authentication token ⃗γ corresponding to a benign input w at the S, and later attempts to find a colliding preimage w′ , where w′ ∈ Ublk . More precisely, the security requirement is that ⃗γ is binding in the sense that it is computationally infeasible to come up with a pair ⃗ ′ such that w′ , w ∧ m ⃗′ , m ⃗ ∧ fk f (w′ ) + ⃗s × w′ , m ′ ′ ′ ⃗ ) = ⃗γ. That is, no efficient adverH(w , fk f (w ), k f , m sary should be able to produce a different input–mask pair that maps to the same authentication token. There are two cases: 1) When fk f (w′ ) , fk f (w), the probability is F1θ | | since ⃗γ is not known and producing such a pair ⃗ ′ is equivalent to guessing ⃗γ over the of w′ , m space Fθ . The probability does not enhance with the number of oracle queries given to either H or FIC .
2) When fk f (w′ ) = fk f (w), it means that there is a collision over the embedding function. As k f is given to an adversarial Csnd , it can enumerate over U to find such a collision with probability 1. Then finding a collision over ⃗γ ⃗ ′ such that is equivalent to finding the pair w′ , m ′ ′ ′ ⃗ ) = H(w, fk f (w), k f , m ⃗ ). As H H(w , fk f (w ), k f , m is a random oracle, such a probability would be qH . |Fθ | Summing up all cases above, gives the result: AdvCC P,H (A1 , A2 , A3 )
! ′ w = w = P ExptCC (A , A , A ) = 1 P,H 1 2 3 ! ′ CC + P ExptP,H (A1 , A2 , A3 ) = 1 w , w blk ≤ FARU + L,T
2 · |F| qH + 1 + |KP | Fθ □
D.2. Security against S We prove security for threat model T2 in this section. Assuming FEM , FTC , and FIC are secure, the method available to S to attack the framework in Fig. 3 is to guess the input w of Csnd . As such, the goal of such a S is to cause the following experiment to return 1, where S is denoted as algorithm (S1 , S2 ). In short, we require that S cannot distinguish Csnd ’s input w when w is not blocked by the framework. Experiment ExptSH (S1 , S2 ) ⃗ P , k2 ⃗ P , k f ⟩ ← SH(·) () ⟨ϕ1 , w0 , w1 , ⃗s, k1 1 L,T if blocked ( fk f (w0 )) ∨ blockedL,T ( fk f (w1 )) return 0 $
$
⃗ ← Fθ , b ← {0, 1} m H(·) ⃗ P , k2 ⃗ P , ⃗s)) ⃗ ), (k f , k1 (( p⃗1 , p⃗2 ), ·) ← FEM ((wb , m H(·) ⃗ P , k2 ⃗ P )) (1, ⃗γ) ← FTC (( p⃗1 , p⃗2 ), (k1 ⃗) z⃗1 ← fk f (wb ), z⃗2 ← H(wb , fk f (wb ), k f , m H(·),FIC ((z⃗1 ,z⃗2 ),·) ′ b ← S2 (ϕ1 , ⃗γ) if b′ = b then return 1 else return 0 Then, AdvS (S1 , S2 ) = P ExptSH (S1 , S2 ) = 1 AdvS (t, q) = max AdvS (S1 , S2 ) S1 ,S2
where the maximum is taken over all adversaries (S1 , S2 ) running in total time t, with at most qH queries to H, and at most q oracle queries to FIC ((⃗ z1 , z⃗2 ), ·) from S2 . To win the experiment ExptSH , S2 needs to successfully guess b, meaning that it distinguishes the input from the protocol transcripts. S1 selects w0 and w1 from U according to an application-specific distribution that need not be uniform. But both have to be not blocked since the functionality we design implies
that the server learns {⃗l ∈ L : d fk f (w) ≤ T } when blockedL,T ( fk f (w)). Proposition D.2. If H is a random oracle and FEM , FTC , FIC are secure and output correctly, then AdvSH (t, qH , q) ≤
1 qH + 2 Fθ
for t′ = t + O(1). Proof. First recall that (S1 , S2 ) receives no output from FEM and so does not learn p⃗1 or p⃗2 individually. FTC outputs to server only ⃗γ = P−1⃗ ( p⃗1 ) + P−1⃗ ( p⃗2 ) = k1P k2P ⃗ ). H is a random oracle fk f (w) + ⃗s × H(w, fk f (w), k f , m that maps {0, 1}∗ into Fθ , where F is a finite field. ⃗γ ∈ Fθ is a vector of field elements, so the addition is a linear combination in the finite field, which is a secure one-time-pad with perfect secrecy. ⃗γ carries no ⃗ is kept secret information about w or fk f (w) since m from S. No matter the properties of H, the (S1 , S2 ) adversary can win the above experiment with probability ⃗ ′) at least qFHθ , simply by invoking H(w, fk f (w′ ), k f , m | | ⃗ ∈ Fθ . and guessing elements w of U and the secret m Prop. D.2 says that if H is a random oracle, then this is the best that (S1 , S2 ) can do. As such, the probability the adversary succeeds is as stated in the proposition. The experiment ExptS accounts for S maliciously trying to learn w. However, we do not claim this because doing so would require FEM , FTC , FIC to be maliciously secure and they are not in our implementation due to efficiency reasons. In other words, through instantiating FEM , FTC , FIC with maliciously secure primitives, Half Moon can be secure against a deviating S trying to learn Csnd and Crcv ’s inputs. □
Theorem. Assuming that there are protocols that securely realize Fole and Fnpa , ΠTC securely realized FTC against a semi-honest server S, and a malicious client Csnd in the (Fole , Fnpa )-hybrid model. Proof. We will show that there is a polynomial time simulator that simulates Csnd ’s and S’s views. ⃗P ← When S is corrupt: The simulator obtains k1 ′ ′ ′ ⃗ ⟨⃗κ1 ,⃗κ2 ⟩ and k2P ← ⟨κ⃗1 , κ⃗2 ⟩, and r1 (x), . . . , rn′ (x) from S’s random tape. Let ⃗κ1 ← ⟨κ1,1 , . . . , κ1,θ ⟩ and ′ ′ ⃗κ2 ← ⟨κ2,1 , . . . , κ2,θ ⟩. Also, let κ⃗1 ′ ← ⟨κ1,1 , . . . , κ1,θ ⟩ ′ ′ ′ and κ⃗2 ← ⟨κ2,1 , . . . , κ2,θ ⟩. For i ∈ [1, n], the simulator obtains ⃗li ∈ L from S’s input tape; Recall S is assumed to be semihonest. Let ⃗li = ⟨l⃗i,1 , . . . , l⃗i,θ ⟩ and let e⃗li (x) be the polynomial obtained by interpolating the points {(x1 , l⃗i,1 ), . . . , (xθ , l⃗i,θ )}. First consider the case where S’s output tape has gcd(ew (x), e⃗li (x)) for i ∈ [1, n]. There are two cases here 1) For j , i: When S’s output tape does not have gcd(ew (x), e⃗l j (x)), then the degree of gcd(ew (x), e⃗l j (x)) < δ − T/2. In this case, the simulator sets Sw ← {r1 , . . . , rδ }, $ where r1 , . . . , rδ Q← F, and the polynomial ew (x) ← (x − s). The simulator s∈Sw
Appendix E. Full Proofs of Sec. 6 In this appendix, we prove our instantiation of the framework. Theorem E.1 ([29]). Let F be a finite field of order q. Fix polynomials p1 (x) and p2 (x) of degree δ, and an arbitrary set of points X ← {x1 , . . . , xθ }. Let r(x) and r′ (x) be random Q polynomials of degree ≥ δ. Also, let p′ (x) ← (x − xi ). Then, when $
xi ←F
Deg(gcd(p1 (x), p2 (x))) < δ − T2 and θ = 2δ − T2 + 2,
X
Proof. The entire functionality is implemented in a garbled circuit construction that is generated by the semi-honest S. The party Csnd playing the role of the evaluator is malicious, however it does not get outputs from the circuit unless it correctly evaluates it. Assuming that there is a construction realizing FGC with a semi-honest garbler and a malicious evaluator, ΠEM can be proved to be secure in the FGC -hybrid model. □
|P ⟨r(xk ) · p1 (xk ) + r′ (xk ) · p2 (xk )⟩θk=1 = Y
Y←Fθ
1 − P ⟨r(xk ) · p1 (xk ) + r′ (xk ) · p′ (xk )⟩θk=1 = Y | ≤ |F| (11) Theorem. Assuming that there is a protocol that securely realizes a garbled circuit, ΠEM securely realizes FEM against a semi-honest server S, and a malicious client Csnd .
simulates Fnpa returning evaluations of ⟨κ1,k · r′j (xk ) · ew (xk ) + r j (xk ) · e⃗l j (xk ) + r′j (xk ) · κ2,k ⟩θk=1 to S, where r j (x) is a random polynomial of degree δ. The simulation is indistinguishable from the real protocol execution: r j (x) is sampled from the same distribution as r j (x), and from Theorem E.1, D Eθ r′j (xk ) · ew (xk ) + r j (xk ) · e⃗l j (xk ) k=1 is indistinguishableE from D θ ′ r j (xk ) · ew (xk ) + r j (xk ) · e⃗l j (xk ) . k=1 2) For j = i: When S’s output tape has gcd(ew (x), e⃗l j (x)), let Sw∩⃗l j be the set of the roots of gcd(ew (x), e⃗l j (x)) and Sw∩⃗l j = d. Then, the simulator computes a set Sw ← {r1 , . . . , rδ−d } ∪ Sw∩⃗l j where r1 , . . . , rδ−d < Sw∩⃗l j . The simulaQ tor sets ew (x) ← (x − s). The simulator s∈Sw
of ⟨κ1,k · simulates Fnpa returning evaluations r′j (xk ) · ew (xk ) + r j (xk ) · e⃗l j (xk ) + r′j (xk ) · κ2,k ⟩θk=1 to S, where r j (x) is a random polynomial of degree δ. Let r′j (x) · ew (x) + r j (x) · e⃗l j (x) = gcd(ew (x), e⃗l j (x)) · R(x) and r′j (x) ·
ew (x) + r j (x) · e⃗l j (x) = gcd(ew (x), e⃗l j (x)) · R(x) Since r′j (x), r j (x) and r j (x) are all random polynomials, due to Lemma A.1, R(x) and R(x) are both random polynomials of the same degree, and are therefore indistinguishable. Thus, r′j (x) · ew (x) + r j (x) · e⃗l j (x) is indistinguishable from r′j (x) · ew (x) + r j (x) · e⃗l j (x), and consequently the simulation is indistinguishable from the real execution. In the case where there is no ⃗li where S’s output tape has gcd(ew (x), e⃗li (x)), the simulator follows case (1) for all i ∈ [1, n]. In the commit phase, the simulator implements the $ random oracle, and sets ⟨h1 , . . . , hθ ⟩ ← Fθ . The simulator computes ⟨p2,1 , . . . , p2,θ ⟩ ← Pk2⃗P (⟨h1 , . . . , hθ ⟩), ⃗ P from the random tape where the simulator gets k2 of S. The simulator simulates the calls to Fole in Steps 8–9 with inputs ri (xk ) and p2,k respectively. The simulator does not need to simulate an output to S. n P Then, for Step 10 the simulator returns ⃗v′ ← ⟨ ti,k + i=1
′ ti,k −ri (x)·e⃗li (xk )+ rcκ(x′ k ) ·p2,k ⟩θk=1 to S. ⃗v′ is indistinguish1,k able from ⃗v′ as ri (x) is identically distributed to ri (x), and ⟨h1 , . . . , hθ ⟩ is indistinguishable from ⟨h1 , . . . , hθ ⟩ assuming that H(·) is a random oracle.
When Csnd is corrupt: We will prove the protocol secure in the (Fole , Fnpa )-hybrid model. The simulator does the following 1) During Step 4 of ΠTC , the simulator obtains A’s inputs ⟨ri (xk )⟩θk=1 and p⃗′1 . The simulator simulates Fnpa with Csnd ’s inputs. There is no output to A from this step. 2) In Step 8, the simulator gets ri (xk )∗ from A’s input to Fole in for i ∈ [1, n], k ∈ [1, θ]. If ri (xk )∗ = ri (xk ) (obtained earlier), then the simulator sends ri (xk ) to Fole , obtains outi,k from Fole , and simulates Fole returning outi,k to Csnd . $
Otherwise, the simulator sets outi,k ← F and simulates Fole returning outi,k to Csnd . The simulator outputs whatever A outputs. 3) In Step 9, the simulator gets p2,1 ′ , . . . , p2,θ ′ as inputs to Fole . The simulator simulates returning the output of Fole to Csnd , and outputs whatever A outputs. 4) The simulator gets ⃗v′ from A in Step 10. The simulator checks whether ⃗v′ has been correctly computed as the sum of the values returned to Csnd in the previous steps. If so, the simulator sets p⃗2 ′′ ← p⃗2 ′ . Otherwise, for each j ∈ [1, θ] where ⃗v′j has not been correctly com$
puted, p2, j ′′ ← F. 5) The simulator sends to FTC the inputs p⃗′1 and p⃗2 ′′ . The functionality returns ⃗γ or ⊥. If the output of FTC is ⊥, then send 0 to Csnd . Otherwise, send 1 to Csnd . Output whatever A outputs. The simulation is indistinguishable from the real execution of the protocol. In Step 2, outi,k and outi,k are indistinguishable. This is because in the real execution
$
$
′ ′ of ΠTC , outi,k = ti,k −ri (xk )·e⃗li (xk ) ← F, when ti,k ← F, $
which is indistinguishable from outi,k ← F. In Step 3,, the simulator simply simulates Fole using A’s input and thus follows the protocol exactly. In Step 5, first note that the ideal functionality outputs ≤ T , which equivalent to ⊥ when fk f (w) − ⃗l SUR checking that the degree of gcd(ew (x), e⃗l (x)) ≥ δ − T2 . On the other hand, the simulation outputs ⊥ when the degree of c(x) ← gcd(ew (x), ri′ (x)·ew (x)+ri (x)·e⃗l (x)) ≥ δ − T2 . From Prop. A.2, we have P fk f (w) − ⃗l
SUR
, 2 · δ − Deg(c(x)) ≤ 1/ |F|
Thus, with overwhelming probability, the output of the simulation to Csnd and the real protocol execution are identical. Next, note that when ⃗v′ has been correctly computed, ⃗′ ⃗′ the simulator provides p1 and p2 to FTC , which −1 ⃗′ −1 ⃗′ returns ⃗γ ← P ⃗ p1 + P ⃗ p2 . In the real exek1P k2P cution, ⃗γ is identically computed. When A provides inconsistent value of ⃗v′ , either due to the fact that ⃗v′ is not correctly computed as a sum of the results returned before to Csnd , or because ri (xk )∗ , ri (xk ) for some k, i, then the simulator sends to FTC p⃗2 ′′ , p⃗′2 . Let p⃗2 ′′ and p⃗′2 differ in the j-th component. Then, P−1 ( p⃗′ )+ P−1⃗ ( p⃗′2 ) and P−1⃗ ( p⃗′1 )+ P−1⃗ ( p⃗2 ′′ ) also differ ⃗P 1 k1 k2P k1P k2P in the j-component, and the value of the j-th compo′′ nent of P−1⃗ ( p⃗2 ) is uniformly random to Csnd . Thus, k2P the value ⃗γ in the real protocol is indistinguishable from the output of the simulation. □ Theorem. Assuming that there is a protocol to securely realize Fole , ΠIC securely realizes FIC against a semi-honest server S and a malicious client Csnd . Proof. We will show that there is a polynomial time simulator that indistinguishably simulates S’s and Csnd ’s views of the protocol in the ideal world simulation. When S is corrupt: It is straightforward to simulate S’s view when interacting with Fole . Specifically, for each k ∈ [1, θ], the simulator simulates Fole with S’s input ⃗sk (which it gets from S’s input tape), and $ outputs a value rk ← F. The simulation is indistinguishable from the protocol execution if Fole can be simulated since S’s output, ⃗γ, in the real protocol execution is identically distributed to the simulated output assuming that H(·) is a random oracle. When Csnd is corrupt: In the protocol, Csnd receives 1 from S when the output of Fole is equal to ⃗γ, otherwise it receives 0. Since ⃗γ = fk f (w) + ⃗s × H(w, fk f (w), k f , m ⃗ ) is uniformly distributed in Fθ , the probability that for some z⃗1 , fk f (w′ ) and z⃗2 , ⃗ ), z⃗1 +⃗s×z⃗2 = ⃗γ is ≤ 1/ |F|. Therefore, H(w, fk f (w), k f , m with overwhelming probability, when Csnd provides incorrect inputs to Fole in the real protocol execution, the output to Csnd in the real protocol execution is 0.
In the ideal world, the simulator obtains the inputs z⃗1 and z⃗2 to Fole , and sends these values to FIC . The output to Csnd is identically distributed in the real world and the ideal world. Thus, Csnd ’s view in the simulation is indistinguishable assuming that there is a simulator that can simulate Fole against a malicious sender. □