SEEK: Secure and Efficient Encrypted Keyword Search For Privacy-Preserving Messaging Protocols Soumyadyuti Ghosh
Michail Maniatakos
Center for Cyber Security New York University Abu Dhabi Abu Dhabi, United Arab Emirates [email protected]
Center for Cyber Security New York University Abu Dhabi Abu Dhabi, United Arab Emirates [email protected]
arXiv:2609.18459v1 [cs.CR] 16 Sep 2026
Abstract Encrypted communication protects sensitive user data but can facilitate harmful or unlawful exchanges, creating a trade-off between detecting dangerous messages and preserving end-user privacy. To address this, we propose SEEK, a practical and efficient encrypted keyword-search protocol for privacy-preserving messaging that combines homomorphic encryption with secure two-party computation (2PC). SEEK first partitions messages into ciphertext fragments with the minimum sufficient overlap, then homomorphically correlates them using encrypted keyword trapdoors. For long messages, this design can reduce sender-side encryption and upload overhead by up to two orders of magnitude over state-of-the-art baselines. It supports ASCII case-insensitive matching with one fixed-size encrypted trapdoor and one homomorphic multiplication per fragment, yielding up to 5.47× faster correlation computation than the strongest fragmentation-based baselines. SEEK then invokes 2PC-based selected decoding, blinded zero testing, and secure aggregation, revealing only the keyword presence-or-absence bit while hiding the keyword, its length, message contents, match counts, and locations. SEEK achieves 100% accuracy under case variations that result in exact-matching failures, without requiring additional trapdoors or online communication. We further realize SEEK as an end-to-end web and cross-platform mobile application. Prototype evaluation on a weekly messaging history yields an online computation time of 1.92 s per search, demonstrating the practical feasibility and efficiency of SEEK.
CCS Concepts • Security and privacy → Privacy-preserving protocols.
Keywords Privacy-preserving Keyword Search, E2EE Messaging, Homomorphic Encryption, Secure Two-Party Computation (2PC).
1
Introduction
In the modern digital world, users regularly exchange highly sensitive personal, corporate, and governmental information through Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. Conference’17, Washington, DC, USA © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-x-xxxx-xxxx-x/YYYY/MM https://doi.org/10.1145/nnnnnnn.nnnnnnn
cloud-serviced messaging platforms that store private conversations beyond the direct control of their users. Without cryptographic protection, these communications can be exposed to untrustworthy cloud service providers (CSPs), compromising user privacy at scale. Consequently, End-to-End Encryption (E2EE) has become a de facto requirement for secure messaging, ensuring that only the sender and recipient can read messages, while CSP handles only encrypted data, thus substantially reducing associated privacy concerns. ■ Motivation. While preserving the confidentiality of private communications remains essential, lawfully authorized investigations increasingly require targeted searches of retained messages for evidence of misconduct or crime. Searchability Paradox. Retrospective access to communications can have substantial investigative value in serious crime cases. Infiltrations of encrypted criminal platforms such as EncroChat and Operation Trojan Shield enabled authorities to analyze messages related to drugs, weapons, money laundering, violence, and corruption, leading to large-scale arrests and asset seizures [31, 55, 73]. EncroChat litigation also produced legal rulings, with UK courts admitting evidence obtained under a targeted equipment-interference warrant and the Court of Justice of the European Union addressing the cross-border transmission and use of such evidence under European Investigation Orders [23, 28]. Legal process can likewise compel disclosure when a provider retains readable message content, as occurred in the Nebraska Facebook/Messenger investigation [37]. However, approaches built on provider-side plaintext access, broad endpoint-side scanning, or reusable exceptional-access capabilities threaten to transform targeted investigations into scalable surveillance infrastructure, creating substantial risks to privacy, security, accountability, mission creep, and civil liberties [1, 2, 19]. Access-Control Paradox. The tension surrounding E2EE has further intensified due to ongoing governmental and regulatory initiatives across jurisdictions aimed at weakening, bypassing, or reversing robust encryption standards. In the United Kingdom, authorities reportedly sought access to Apple users’ encrypted cloud data, prompting Apple to withdraw Advanced Data Protection for new UK users [63, 64]. European Union negotiations over the proposed CSA Regulation continue to consider whether detection orders should extend to E2EE interpersonal communications [30, 65], while Australia’s Assistance and Access framework enables agencies to seek provider assistance when encryption or other technical barriers impede lawful investigations [6, 60]. The removal of opt-in E2EE for private messages by Instagram, along with reports regarding Apple’s operations in China, further demonstrates how the availability of encryption, data storage practices, and infrastructure
Conference’17, July 2017, Washington, DC, USA
Soumyadyuti Ghosh and Michail Maniatakos
of the keyword. Fig. 1 illustrates the foundational SEEK architecture and its associated workflow.
1.1
Figure 1: Fundamental SEEK Protocol Architecture.
control can shift in response to safety, content moderation, law enforcement, or local compliance requirements [57, 72]. Conversely, providers and E2EE services have resisted demands to weaken or bypass encryption, as illustrated by the Facebook Messenger wiretap dispute and WhatsApp’s traceability challenge in India [24, 27, 62]. These divergent responses demonstrate why the technical interface matters: major providers typically require valid legal process before disclosing stored content, transparency reporting reveals the scale of such requests, and data-minimization measures limit what providers retain and can disclose [5, 50, 70]. Cryptographic Middle Ground. Together, these competing imperatives motivate the central design question: In legally authorized investigations, should access require bulk disclosure of decrypted messages, or be limited to scoped cryptographic queries over encrypted data? We pursue the latter approach by constraining authorized access through the technical interface rather than goodwill or general plaintext disclosure. Our aim is therefore to offer a narrower cryptographic middle ground: a trade-off that can satisfy legitimate law-enforcement needs for targeted message probing while cryptographically preventing mass-scale surveillance of the encrypted corpus. ☛ Design Objectives. Realizing this middle ground requires a search interface that does not depend on endpoint cooperation. Our design objectives differ from traditional victim-initiated abusereporting mechanisms for E2EE messaging and message-frankingbased protocols, in which a cooperative recipient reports an abusive message together with its cryptographic evidence [36, 41]. In contrast, the proposed setting considers users who may intentionally exchange harmful or unlawful messages and fall within the scope of investigation, so neither can be expected to initiate a voluntary abuse report. In a realistic deployment, users communicate via E2EE while CSP stores the encrypted messages. An authorized pattern provider (PP) encodes a harmful or relevant keyword as an encrypted trapdoor and submits it to the CSP, which executes a privacy-preserving search protocol over the encrypted corpus. The CSP learns neither the plaintext messages, queried keyword, nor the search outcome, while PP learns only the presence or absence
Related Work
Encrypted search over private data spans several domains. Below, we briefly describe each approach and its limitations. 1 Indexed and Tokenized Search. Index-based searchable encryption (SE) enables conjunctive queries, updates, access control, multi-user sharing, and forward or backward privacy over encrypted indexes. However, it typically matches only indexed keywords and returns document identifiers [21, 39, 46, 47, 49, 52]. Consequently, retrospective arbitrary-substring search requires relevant substrings to be indexed or represented using specialized structures. Encrypted suffix-tree constructions facilitate such searches with linear-size ciphertexts, but they require three communication rounds, reveal prescribed access patterns, and return occurrence indices [22]. Moreover, practical query-reconstruction attacks exploit the scheme-specific leakage profiles of prominent substringSSE schemes [38]. Encrypted deep packet inspection (DPI) systems such as BlindBox and BlindIDS tokenize network traffic to enable encrypted equality matching [18, 69]. Supporting variable-length patterns necessitates either scheme-specific tokenization or query decomposition. In contrast, SEST enables arbitrary-length matching using shiftable trapdoors and bilinear-pairing tests, but discloses match locations [26]. Consequently, retrospective arbitrary search with only a presence bit requires modified search representations, private aggregation, or result obfuscation. 2 Fragmentation-Based Encrypted Search. A distinct line of research divides streams into fixed-size encrypted fragments and introduces overlap or auxiliary boundary instances to preserve cross-boundary matches [10, 13, 14]. These approaches employ either bilinear-pairing constructions [10, 13] or functional-encryption (FE) primitives [14]. In the latter approach, fragmentation avoids position-dependent key material that would otherwise grow linearly with stream length, but the native functionality returns match positions rather than a hidden aggregate. Pairing-based matching also requires computationally costly bilinear-pairing evaluations across the tested instances. Pattern privacy remains limited because [13] does not target pattern-hiding trapdoors, while [10] protects patterns from the CSP only under a high min-entropy assumption. These limitations position homomorphic encryption (HE) as a complementary design choice for privacy-preserving pattern/keyword search in the encrypted domain. 3 Homomorphic Matching. Prior HE-based constructions employ several distinct techniques. Unlike the pairing and FE-based schemes that generate overlapping boundary instances [10, 13, 14], the HE design of [11] uploads non-overlapping fragments and forms adjacent pairs online for cross-boundary matches. Its casesensitive exact path uses one trapdoor ciphertext, whereas caseinsensitive wildcard matching uses two. Excluding pair formation, this variant requires two ciphertext–ciphertext (ct–ct) multiplications, two ciphertext–plaintext (ct–pt) multiplications, and two additions or subtractions per evaluation. While the fragment-length bound in [11] leaves at least half of each uploaded ciphertext’s packing width unused, the constant-depth BGV construction [12] packs overlapping chunks across slots and applies randomized equality.
SEEK: Secure and Efficient Encrypted Keyword Search For Privacy-Preserving Messaging Protocols
Table 1: Qualitative comparison of representative encrypted pattern/keyword-matching approaches with SEEK. Approach
Any Any Single Dynamic HE ASCII Exact No Hide Private KW PL TD History Evaluation CI match ASP PL presence
Encrypted Search Paradigms SE [21, 46, 47, 52] ✗ part. ✓ part. DPI [18, 69] ✓ ✗ part. part. SEST [26] ✓ ✓ ✓ ✓ Pairing/FE[10, 13, 14] ✓ ✓ dep. ✓ Homomorphic String Search Constructions CipherMatch [42] ✓ ✓ ✗ ✗ RLWE Frag. [11] ✓ ✓ 1/2 ✓ BGV Search [12] ✓ ✓ ✓ part. TFHE Search [54] ✓ ✓ ✗ ✗ CKKS Search [68] ✓ ✓ ✓ ✗
— — — —
✗ ✗ ✗ ✗
✓ ✓ ✓ ✓
✗ part. ✗ part.
✗ ✗ ✗ ✗
✗ ✗ ✗ ✗
Add-only 2CC+2CP HomEQ PBS/CMux Poly.+rot.
✗ ✓ ✗ ✗ ✗
✓ ✓ rand. ✓ approx.
✓ ✓ ✓ ✓ ✓
✗ ✗ ✗ ✓a ✗
✗ ✗ ✗ ✗ part.b
✓
1CC
✓
✓
✓
✓
✓
SEEK (Section 4)
✓
✓
✓
KW: Keyword; PL: Pattern Length; TD: Trapdoor; CI: Case-Insensitive; ASP: CSP Access/Search Pattern Leakage; CC/CP: ct–ct/ct–pt Multiplication; HomEQ: Homomorphic Equality; PBS: Programmable Bootstrapping. part./dep.: Partial/ModelDependent. Any KW, Any PL, and Single TD denote post-encryption query choice, length variation without corpus reprocessing, and one fixed-size encrypted trapdoor, respectively. Dynamic history means incremental encrypted ingestion with cross-boundary completeness. Private presence means only one party (e.g., PP) learns corpus-wide presence bit. HE Evaluation lists dominant query-dependent homomorphic core operations (e.g., correlation score). For [11], 1/2 is the exact/CI TD count and wildcard costs exclude pair formation. rand./approx. denote randomized/approximate equality. a Hidden within a public padded bound. b Native only for one slot-bounded target. Longer histories require fragmentation and aggregation.
However, its representation and evaluation process disclose the private query length, and matching remains pattern-length dependent through repeated equality circuits involving multiple multiplications, rotations, and Frobenius maps. Its randomized equality also has a one-sided false-positive probability that accumulates across tested positions. These two constructions further expose richer outputs to the decryptor, namely per-offset correlation scores and locations in [11] and occurrence locations and counts in [12]. CipherMatch [42] instead reduces arithmetic cost by packing multiple bits per BFV coefficient and performing addition-only exact equality with shifted encrypted queries. This approach requires multiple query ciphertexts, and its query-dependent shifts can reveal the query length unless padded. Moreover, the TFHE-based search [54] performs binary search over an encrypted suffix array constructed from the complete plaintext, preventing direct support for independently encrypted, incrementally arriving messages. Its proposed encoding uses four LWE ciphertexts per character, while bootstrapping and encrypted lookups scale with the padded pattern length, increasing runtime and memory. CKKS-based comparison [68] instead examines every candidate alignment using rotations and approximate polynomial binarization. It explicitly reveals the pattern length, while near matches can cause false positives unless higher-degree, deeper circuits are used, increasing runtime and memory. Slot-bounded targets also require fragmentation and aggregation for longer histories. Except for the wildcard path of [11], these schemes lack native case-insensitive matching, while corpus-wide presence-only release can require further query padding, boundary-aware fragmentation, cross-ciphertext aggregation, result obfuscation, or private aggregation. We retain [11] as the primary quantitative baseline and compare the remaining HE constructions qualitatively in Appendix B.
Conference’17, July 2017, Washington, DC, USA
☛ Our Contributions. We present SEEK, a privacy-preserving keyword-search protocol for practical E2EE messaging systems. Table 1 qualitatively compares prior encrypted search paradigms against SEEK in our E2EE messaging system. We summarize our contributions below: (1) We introduce a byte-aligned fragmentation strategy that combines minimal sufficient overlap with full-width homomorphic packing, reducing the fragment count by up to two orders of magnitude relative to prior designs [10, 11] and thereby lowering the CSP-side ciphertext footprint, encryption, and communication overheads. (2) We design SEEK, an ASCII case-insensitive keyword-search protocol using a single fixed-size encrypted trapdoor (unlike [11, 42]), and compute the complete within-fragment correlation vector using a single query-dependent homomorphic multiplication per fragment (unlike [11]). To obtain the final search results, PP and CSP jointly perform privacy-preserving selected decoding, zero testing, and secure aggregation, revealing only the presence-or-absence bit to PP while CSP receives no result and neither party learns match counts, locations, or correlation scores. (3) We prove the correctness of SEEK and establish its privacy against semi-honest adversaries under standard real/ideal-world simulation paradigm. We further analyze the feasibility of exhaustive repeated query attacks against SEEK. (4) We implement SEEK using Microsoft SEAL and integrate it into E2EE web/mobile applications through a modified nodeseal backend. Across 10,000 encrypted searches over SAMSum messaging corpus scaled up to an estimated five-year history [34], SEEK achieves 100% observed accuracy and up to a 5.47× correlation-computation speedup over the evaluated wildcard baseline configuration of [11].
2 Preliminaries 2.1 BFV Homomorphic Encryption We build SEEK’s encrypted-matching core on the Brakerski–Fan– Vercauteren (BFV) leveled homomorphic-encryption (HE) scheme [15, 33], whose security is based on the Ring-Learning-with-Errors (RLWE) assumption. An approved BFV parameter set params fixes the polynomial-modulus degree 𝑁 , a prime plaintext modulus Îℓ𝑄 −1 𝑡, and an RNS ciphertext-modulus chain 𝑄 = ℓ=0 𝑞 ℓ . These parameters define the plaintext ring 𝑅𝑡 = Z𝑡 [𝑋 ]/(𝑋 𝑁 + 1) and the ciphertext ring 𝑅𝑄 = Z𝑄 [𝑋 ]/(𝑋 𝑁 + 1). Key generation produces (pk, sk, rlk) ← KeyGen(params), where pk and sk are the public and secret keys and rlk is the relinearization key, used to relinearize a homomorphic product ciphertext into the standard form 𝑐 = (𝑐 0, 𝑐 1 ) ∈ 𝑅𝑞2 at an active RNS modulus level 𝑞 | 𝑄. Our privacy analysis uses the adaptive multi-message IND-CPA model for HE, in which the adversary receives all published evaluation material, including rlk [3]. Encryption and decryption are denoted by 𝑐 ← Encpk (𝑚) and 𝑚 ← Decsk (𝑐), while homomorphic evaluation uses ct-ct operations Evaladd and Evalmult and ct-pt operations Evaladd-plain and Evalmult-plain . For any modulus 𝑟 , let can𝑟 (𝑎) ∈ {0, . . . , 𝑟 − 1} denote the canonical integer representative of 𝑎 ∈ Z𝑟 . For any odd modulus 𝑟 , let ctr𝑟 (𝑎) ∈ {−(𝑟 − 1)/2, . . . , (𝑟 − 1)/2} denote its centered integer representative, and
Conference’17, July 2017, Washington, DC, USA
[·] 𝑡 denote reduction modulo 𝑡. We define coefficient-wise BFV decoding as DecCoeff𝑞,𝑡 (𝑎) = [⌊(𝑡/𝑞) ctr𝑞 (𝑎)⌉] 𝑡 . For a relinearized ciphertext 𝑐 = (𝑐 0, 𝑐 1 ), decryption first forms the noisy plaintext 𝑣 = 𝑐 0 +𝑐 1 sk (mod 𝑞) and applies DecCoeff𝑞,𝑡 independently to its coefficients. In particular, a coefficient encoding 𝑚𝑖 ∈ Z𝑡 is recovered correctly whenever |(𝑡/𝑞) ctr𝑞 (𝑣𝑖 ) − ctr𝑡 (𝑚𝑖 )| < 1/2. For an odd active modulus 𝑄 ′ | 𝑄, the public operation ModSwitch𝑄→𝑄 ′ reduces a ciphertext to the active modulus 𝑄 ′ while preserving its decoded plaintext whenever the BFV correctness condition remains satisfied. Because SEEK uses signed-coefficient arithmetic, elements of Z𝑡 are interpreted through their centered representatives: for example, −1 is encoded as 𝑡 − 1. Our deployment settings require a prime plaintext modulus 𝑡, satisfying 𝑡 ≡ 1 (mod 2𝑁 ), so that Z𝑡 is a field and SEEK supports NTT-compatible arithmetic.
2.2
Secure Two-Party Computation (2PC)
■ Beaver Multiplication. For modulus 𝑟 and 𝑥 ∈ Z𝑟 , we write ⟨𝑥⟩𝑟 = (𝑥 1, 𝑥 2 ) for an additive sharing satisfying 𝑥 = 𝑥 1 + 𝑥 2 (mod 𝑟 ). When 𝑟 = 𝑡, we omit the subscript and write ⟨𝑥⟩. To multiply shares ⟨𝑥⟩ and ⟨𝑦⟩ over Z𝑡 , the parties consume a fresh Beaver triple (⟨𝑢⟩, ⟨𝑣⟩, ⟨𝑤⟩) satisfying 𝑤 = 𝑢𝑣 (mod 𝑡) [9]. In the online phase, the parties reconstruct only the masked differences 𝑑 = 𝑥 − 𝑢 and 𝑓 = 𝑦 − 𝑣 and compute 𝑧 1 = 𝑤 1 + 𝑑 𝑣 1 + 𝑓 𝑢 1 + 𝑑 𝑓 (mod 𝑡) and 𝑧 2 = 𝑤 2 + 𝑑 𝑣 2 + 𝑓 𝑢 2 (mod 𝑡), yielding 𝑧 1 + 𝑧 2 = 𝑥𝑦 (mod 𝑡). Because 𝑢 and 𝑣 are uniform and remain secret-shared, the opened values 𝑑 and 𝑓 reveal no information about 𝑥 or 𝑦 in the semi-honest model. Fresh arithmetic triples over the prime field Z𝑡 can be generated by standard finite-field preprocessing [44]. ■ Oblivious Linear Evaluation (OLE). In an OLE over Z𝑡 , a sender holding (𝑎, 𝑏) and a receiver holding 𝑥 securely compute 𝑎𝑥 + 𝑏 (mod 𝑡) for the receiver, without revealing 𝑥 to the sender or anything beyond the output about (𝑎, 𝑏) to the receiver [8]. SEEK invokes one OLE instance per retained coefficient to generate the correlated zero-test tokens, with all instances evaluated as one offline batch. Section 4.5 defines their distribution, while Appendix C specifies the exact sender and receiver inputs, correctness invariant, and batching. ■ Boolean Sharing and Mixed-Domain Conversion. For a bit 𝑏 ∈ {0, 1}, we write J𝑏KB = (𝑏 1, 𝑏 2 ) for a Boolean XOR sharing satisfying 𝑏 = 𝑏 1 ⊕ 𝑏 2 . For a bitstring, this notation is applied componentwise. We use a standard semi-honest GMW protocol to evaluate Boolean circuits over these shares [25, 35]: XOR gates are evaluated locally, whereas each AND gate consumes a fresh Boolean multiplication triple (J𝑎KB, J𝑏KB, J𝑐KB ) satisfying 𝑐 = 𝑎 ∧ 𝑏. To convert Boolean outputs into arithmetic shares over Z𝑡 , the parties use daBits (J𝜌KB, ⟨𝜌⟩), in which the same random bit 𝜌 is represented in both domains [29, 66]. All Boolean triples and daBits used in an execution are fresh, independent, and consumed once.
3
Protocol Architecture and Threat Model
Our E2EE messaging and privacy-preserving keyword-search system comprises four primary entities: a sender (S), a receiver (R), a cloud service provider (CSP), and a pattern provider (PP), as illustrated in Fig. 1. Each party performs a distinct role in the SEEK protocol. We outline these roles and trust assumptions associated with each entity as follows.
Soumyadyuti Ghosh and Michail Maniatakos
● Sender (S). The sender encodes, fragments, and encrypts each message once using R’s public key before uploading the resulting ciphertext fragments to CSP. Although S and R may cooperatively exchange harmful or unlawful content, they remain compliant with the protocol. Semantic evasion through code words or out-of-band pre-encryption before the protocol encoding and HE layers remains outside the literal keyword-search guarantee, as receiver-initiated abuse-reporting protocols likewise address reported plaintext rather than deliberately concealed semantics [36, 41]. ● Receiver (R). Each receiver generates the BFV keys as in Section 2.1, retains the full secret key locally, publishes the corresponding public and evaluation keys, and decrypts the ciphertext fragments forwarded by CSP. These fragments are retained by CSP for search, making the delivered ciphertexts the sole searchable representation and eliminating the need for a separate upload. Because R possesses the full secret key, it has the capability to decrypt the encrypted correlations produced by SEEK. Returning these correlations to an implicated R would reveal query-related scores and locations, allowing it to suppress or misreport the search result. Consequently, both endpoints remain outside the online search process, while PP and CSP each hold additive shares of R’s full secret key and use them to generate their respective local selected-decoding shares. The privacy-motivated R is assumed not to disclose its key or collude with either PP or CSP, as such actions would fundamentally compromise its own message privacy. Nevertheless, it is essential to validate the functional consistency of the key artifacts and additive shares supplied by R, as inconsistencies could lead to missed detections or biased search outcomes. SEEK therefore performs randomized functional-validation checks during registration and before the search pipeline, as detailed in Section 4.8, thereby supporting correct and unbiased subsequent search outcomes. ● Pattern Provider (PP). For an authorized query, PP encodes the keyword as an encrypted trapdoor and submits it to CSP. After CSP computes the encrypted correlations, PP uses its secret-key share for selected decoding and jointly performs zero testing and secure aggregation with CSP. Only the presence-or-absence bit is revealed to PP. Beyond its query, it learns no plaintext, match count, location, or correlation score. Locations are withheld as repeated single-character queries (e.g., a–z) could reveal sufficient positional structure to reconstruct substantial message content. Although presence-only disclosure still allows dictionary inference through repeated queries, Section 7.2 demonstrates the practical infeasibility of such exhaustive repeated-query attacks. ● Cloud Service Provider (CSP). Upon receiving the trapdoor, CSP computes correlations over the stored ciphertext fragments and uses its secret-key share to generate its local selected-decoding contribution. In SEEK, CSP and PP are modeled as static, noncolluding, semi-honest adversaries that adhere to the protocol while attempting to infer information from their individual views. The non-collusion assumption models the organizational separation and potentially divergent incentives between an investigator or authorizing body and the messaging provider, as illustrated by the Facebook Messenger wiretap dispute and WhatsApp’s traceability challenge in India [24, 27, 62]. Under this model, CSP observes its local setup state, ciphertexts, trapdoors, intermediate values, and public metadata but learns no additional information about the plaintext messages, query, its length, or the result.
SEEK: Secure and Efficient Encrypted Keyword Search For Privacy-Preserving Messaging Protocols
SEEK targets efficient encrypted messaging and privacy-preserving keyword search, while message authentication, integrity, replay protection, ratcheting, and post-compromise security must be provided by a complementary messaging security layer that adheres to standard key evolution and lifecycle practices [7, 61]. Setup artifacts are subject to deployment-defined rotation, with retained historical shares enabling retrospective search. Legal approval, query admission, signed audit and transparency records [45, 56], and per-authorization budgets [20, 43] function as external controls. An authorized query therefore refers to a search approved by the appropriate legal authority and admitted under these controls.
SEEK: Privacy-Preserving Encrypted Messaging and Keyword Search Protocol
4
■ Overview. In this section, we present SEEK, a privacy-preserving case-insensitive keyword-search protocol for E2EE messaging systems. In SEEK, the sender S encodes each message into overlapping fragments, encrypts, and uploads them to CSP (Section 4.2). The PP then submits a single encrypted trapdoor (Section 4.3), which CSP evaluates against the query-independently preprocessed fragments to obtain encrypted correlation polynomials (Section 4.4). After publicly removing overlap-induced duplicate positions, PP and CSP privately encode the match targets (Section 4.5), decode only the retained coefficients into additive shares (Section 4.6), transform them into blinded zero-test values (Section 4.7), and aggregate them using the Beaver-multiplication protocol (Section 2.2). Only one presence-or-absence bit is revealed to PP, while CSP learns no search result. Fig. 2 illustrates the E2E SEEK workflow using a running example.
4.1
Cryptographic Setup Phase
For each key-lifecycle epoch 𝑒, SEEK first selects the BFV parameters params𝑒 = (𝑁 , 𝑄, 𝑡). During the setup phase, R generates (pk𝑅,𝑒 , sk𝑅,𝑒 , rlk𝑅,𝑒 ) ← KeyGen(params𝑒 ), as defined in Section 2.1. These parameters and keys are reused for all uploads and authorized searches within the epoch and replaced only upon deliberate rotation. The receiver R retains sk𝑅,𝑒 for E2EE message decryption, distributes (params𝑒 , pk𝑅,𝑒 ) to S, and (params𝑒 , pk𝑅,𝑒 , rlk𝑅,𝑒 ) PP to PP and CSP. Afterwards, PP samples sk𝑅,𝑒 ← 𝑅𝑄 uniformly and CSP PP sends it to R, who derives sk𝑅,𝑒 = sk𝑅,𝑒 − sk𝑅,𝑒 (mod 𝑄) and sends this share to CSP (Step 1 of Fig. 2). The resulting 2-out-of-2 additive shares reconstruct sk𝑅,𝑒 , while each is marginally uniform and statistically independent of the fixed BFV key tuple. By the RNS representation of Section 2.1, the same additive sharing relation holds independently coefficient-wise in every modulus limb and remains valid after both parties restrict their shares to any reduced modulus level 𝑄 ′ | 𝑄. Thus, for a relinearized ciphertext 𝑐 = (𝑐 0, 𝑐 1 ) ∈ 𝑅𝑞2 at 𝑞 ∈ {𝑄, 𝑄 ′ }: 𝑐 0 + 𝑐 1 sk𝑅,𝑒 =
PP 𝑐 1 sk𝑅,𝑒 | {z } PP-side decryption
+
CSP (𝑐 0 + 𝑐 1 sk𝑅,𝑒 ) | {z }
(mod 𝑞)
CSP-side decryption
This additive decomposition follows the multiparty BFV paradigm [53]. PP and CSP locally compute their decryption-phase contributions from its secret-key share and supplies them as private inputs to the
Conference’17, July 2017, Washington, DC, USA
selected-decoding functionality of Section 4.6, realized using 2PC primitives of Section 2.2.
4.2
Fragmentation and Encryption
Let Σ denote the messaging alphabet, and 𝜙 : Σ → {0, 1}8 be a fixed public 8-bit encoding. A plaintext message sent from S to R is represented as 𝑀S→R and encoded as the bitstream mS→R = 𝜙 (𝑀S→R ) ∈ {0, 1}𝐿 . For a public byte-aligned maximum pattern length 𝐿max ∈ 8N with 8 ≤ 𝐿max ≤ 𝑁 , SEEK partitions the bitstream into zero-padded length-𝑁 fragments using the minimal sufficient overlap of 𝐿max − 8 bits. Accordingly, the fragment step size is defined as stride = 𝑁 − 𝐿max + 8, and the number of fragments is J = max{1, ⌈(𝐿−(𝐿max −8))/(𝑁 −𝐿max +8)⌉}. The overlap 𝐿max −8 is the minimal sufficient overlap that guarantees containment of every byte-aligned encoded-keyword window with 𝐿𝑃 ∈ 8N and 𝐿𝑃 ≤ 𝐿max (see Lemma 5.1). For each fragment index 𝑗 ∈ {0, . . . , J − 1}, the starting offset is defined as: off 𝑗 = 𝑗 · stride and the logical fragment length 𝑇 𝑗 = min{𝑁 , 𝐿 − off 𝑗 }. The corresponding padded fragment coefficients 𝑏𝑖( 𝑗 ) are defined as of Eq. 1 and the resulting coefficient-encoded plaintext polynomial is computed as: 𝑚 𝑗 (𝑋 ) = Í𝑁 −1 ( 𝑗 ) 𝑖 𝑖=0 𝑏𝑖 𝑋 ∈ 𝑅𝑡 . 𝑏𝑖( 𝑗 ) = 1[𝑖 < 𝑇 𝑗 ] mS→R [off 𝑗 + 𝑖], for 0 ≤ 𝑖 < 𝑁
(1)
The sender then computes 𝑐 𝑀,𝑗 ← Encpk𝑅,𝑒 (𝑚 𝑗 (𝑋 )) and uploads 𝑐 𝑀,𝑗 with the public metadata ( 𝑗, off 𝑗 ,𝑇 𝑗 ) to CSP. ■ Preprocessing at CSP. To reduce online latency, CSP transforms 0/1-encoded ciphertexts into a {±1, 0} representation as a one-time query-independent preprocessing step. For each fragment Í𝑇 𝑗 −1 𝑖 𝑗, CSP constructs a public plaintext mask mask 𝑗 (𝑋 ) = 𝑖=0 𝑋 , whose coefficients are 1 in positions [0,𝑇 𝑗 − 1] and 0 elsewhere. The affine map 𝑏 ↦→ 1 − 2𝑏 is evaluated homomorphically on the stored ciphertext as follows. ±1 𝑐 𝑀,𝑗 ← Evaladd-plain (Evalmult-plain (𝑐 𝑀,𝑗 , −2), mask 𝑗 (𝑋 ))
(2)
±1 maps message bits By construction, the resulting ciphertext 𝑐 𝑀,𝑗 0/1 ↦→ +1/−1, and positions outside the logical fragment map to 0. This preprocessing requires only ct–pt multiplications and additions per fragment, and can be performed asynchronously once before any search evaluation. ☛ Running Example. Steps 2-4 of Fig. 2 illustrate fragmentation using message “Meet GO now”. With 𝐿 = 88, 𝑁 = 32, and 𝐿max = 16, the 24-bit stride produces 4 overlapping fragments with one-byte overlap, and the bits encoding “GO” are fully contained in 𝐹 1 , while final fragment is padded to 𝑁 bits.
4.3
Case-Insensitive Trapdoor Generation
Capitalization differences are common in messaging and can cause false negatives under exact case-sensitive search. Accordingly, the exact-equality variants in [11, 42] fail to match variants such as security, Security, and SECURITY using a single query. Although the wildcard mechanism in [11] supports case-insensitive matching, it requires two trapdoor ciphertexts and, including adjacent-pair construction, two ct–ct multiplications, three ct–pt multiplications, and three ciphertext additions/subtractions per pair. SEEK instead realizes case-insensitive matching using one signed-correlation trapdoor ciphertext and one query-dependent ct–ct multiplication
Conference’17, July 2017, Washington, DC, USA
Soumyadyuti Ghosh and Michail Maniatakos
Figure 2: End-to-end overview of SEEK with a running example under illustrative parameter settings. per fragment. For every authorized search, PP decides on a secret keyword 𝑃 of length ℓ𝑃 and encodes it as p = 𝜙 (𝑃) ∈ {0, 1}𝐿𝑃 , where 𝐿𝑃 = 8ℓ𝑃 ≤ 𝐿max ≤ 𝑁 and 𝑡 > 4𝐿max + 2. Let AASCII = {A, . . . , Z, a, . . . , z} represent the ASCII alphabetic characters. Because uppercase and lowercase ASCII letters differ only at the 6th LSB bit position 𝑘 case (e.g., 𝜙 (A) = 01000001 vs. 𝜙 (a) = 01100001), the pattern provider masks only this case bit for alphabetic characters while keeping non-alphabetic characters fully constrained. For each character position 𝑟 ∈ {0, . . . , ℓ𝑃 − 1} and bit position 𝑘 ∈ {0, . . . , 7}, the flattened bit index is 𝑖 = 8𝑟 + 𝑘. PP assigns 𝛾𝑖 = 0 when 𝑃 [𝑟 ] ∈ AASCII and 𝑘 = 𝑘 case , and sets 𝛾𝑖 = 1 otherwise. It then computes the signed query coefficients 𝑦𝑖 = 𝛾𝑖 (1 − 2p[𝑖]) ∈ {−1, 0, +1}. Let 𝐴𝑃 = |{𝑟 : 𝑃 [𝑟 ] ∈ AASCII }| denote the number of alphabetic characters in 𝑃. After ignoring one case bit per letter, the number of constrained query bits is 𝐿fix = 𝐿𝑃 − 𝐴𝑃 = 7ℓ𝑃 , when 𝑃 consists entirely of ASCII letters. PP then forms the reversed Í𝐿𝑃 −1 polynomial 𝑃CI (𝑋 ) = 𝑖=0 𝑦e𝑖 𝑋 𝐿𝑃 −1−𝑖 ∈ 𝑅𝑡 , where 𝑦e𝑖 is the representative of 𝑦𝑖 in Z𝑡 (Section 2.1). The reversal causes the aligned signed-bit products of each candidate window to accumulate in one correlation coefficient [74, 75]. Finally, PP computes the trapdoor 𝑐 𝑃 ← Encpk𝑅,𝑒 (𝑃CI (𝑋 )) and sends it to CSP. Coefficients beyond the encoded query are zero, so every trapdoor occupies one fixed-size ciphertext regardless of 𝐿𝑃 . ☛ Running Example. Step 5 of Fig. 2 encodes “go” as a reversed signed trapdoor. Ignoring two ASCII case bits gives 𝐿fix = 14, enabling the trapdoor to match “GO”.
4.4
Encrypted Correlation Computation
±1 For each trapdoor 𝑐 𝑃 and preprocessed ciphertext fragment 𝑐 𝑀,𝑗 from Eq. 2, where 𝑗 ∈ {0, . . . , J − 1}, CSP computes the encrypted correlation, relinearizes it using rlk𝑅,𝑒 , and switches it to the reduced
coefficient modulus 𝑄 ′ (refer Section 2.1): ±1 b 𝑐 corr,𝑗 ← Evalmult (𝑐 𝑀,𝑗 , 𝑐𝑃 )
(3)
𝑄′ 𝑐 corr,𝑗 ← ModSwitch𝑄→𝑄 ′ (Relinrlk𝑅,𝑒 (b 𝑐 corr,𝑗 ))
(4)
The chosen 𝑄 ′ ensures coefficient-wise BFV decoding correctness for every message, query, and result. A complete byte-aligned candidate window in fragment 𝑗 begins at 𝑠 0 satisfying 0 ≤ 𝑠 0 ≤ 𝑇 𝑗 − 𝐿𝑃 and (off 𝑗 + 𝑠 0 ) mod 8 = 0. Because 𝑃CI (𝑋 ) reverses the query polynomial, its correlation score occurs at 𝑠 = 𝑠 0 + 𝐿𝑃 − 1. We denote ) the candidate window by Win 𝑗,𝑠0 = (𝑏𝑠(0𝑗 ) , . . . , 𝑏𝑠(0𝑗+𝐿 ) and define 𝑃 −1 𝐿 𝑃 the Hamming distance between a, b ∈ {0, 1} as Ham𝛾 (a, b) = Í𝐿𝑃 −1 𝑖=0 𝛾𝑖 (a[𝑖] ⊕ b[𝑖]). Since 𝑠 ≥ 𝐿𝑃 − 1 and the unreduced polynomial product has degree at most 𝑁 + 𝐿𝑃 − 2, no term of degree 𝑠 + 𝑁 exists. Therefore, reduction modulo 𝑋 𝑁 + 1 introduces no negacyclic contribution at coefficient 𝑠. Its plaintext correlation value is represented as: 𝑧 𝑗 [𝑠] =
𝐿∑︁ 𝑃 −1
) 𝑦𝑖 (1 − 2𝑏𝑠(0𝑗+𝑖 ) = 𝐿fix − 2Ham𝛾 (Win 𝑗,𝑠0 , p)
(5)
𝑖=0
Thus, 𝑧 𝑗 [𝑠] = 𝐿fix iff the candidate window matches 𝑃 under the case-insensitive predicate. Coefficients with 𝑠 < 𝐿𝑃 − 1 represent no complete window and may contain negacyclic wraparound, while those outside the logical fragment length 𝑇 𝑗 correspond to no message position. Because 𝐿𝑃 is private, retained early coefficients are not removed using it and instead they receive private dummy targets as in Section 4.5. ■ Overlap-Duplicate Pruning. Fragment overlap guarantees completewindow coverage for byte-aligned candidates, but creates duplicate positions across adjacent correlation polynomials. After modulus switching, CSP removes these duplicates. Since coefficient 𝑠 of fragment 𝑗 corresponds to absolute window-end position off 𝑗 + 𝑠, the
SEEK: Secure and Efficient Encrypted Keyword Search For Privacy-Preserving Messaging Protocols
parties retain: I = {𝜉 = ( 𝑗, 𝑠) : 0 ≤ 𝑗 < J, 0 ≤ 𝑠 < 𝑇 𝑗 , off 𝑗 + 𝑠 ≡ 7 (mod 8), | {z } byte-aligned end position
𝑗 = 0 ∨ 𝑠 ≥ 𝐿max − 1 } | {z }
(6)
exclude repeated overlap positions
The congruence condition retains byte-aligned absolute end positions, while the final condition removes the initial overlap of each later fragment because those positions occur in its predecessor. Because I depends only on public geometry and 𝐿max , it reveals neither the query nor the result. For each fragment contributing to 𝑄′ 𝑄′ I, CSP retains 𝑐 0,𝑗 and sends (𝑐 1,𝑗 , 𝑗, off 𝑗 ,𝑇 𝑗 , 𝑒) to PP. This allows PP to form its local decryption shares for every retained coefficient 𝑄′ CSP but not to decode independently, since 𝑐 0,𝑗 and sk𝑅,𝑒 remain with CSP. ☛ Running Example. Steps 6–8 of Fig. 2 show the resulting correlation and public pruning. In 𝐹 1 , the match beginning at relative bit offset 16 produces score 𝐿fix = 14 at coefficient 𝑠 = 31. Because the overlap causes absolute window-end position 31 to appear in both 𝐹 1 and 𝐹 2 , pruning removes the duplicate from 𝐹 2 and retains the occurrence from 𝐹 1 .
Conference’17, July 2017, Washington, DC, USA
execution, 𝛼 𝜉PP also masks the selected-decoding output, enabling Section 4.7 to convert shares of 𝑥 𝜉 into shares of 𝛽𝜉 𝑥 𝜉 . Because token allocation depends only on the public set I, the 𝐾 = |I| independent OLE instances are evaluated as one offline batch [8]. Appendix C specifies the batch binding and one-time lifecycle. ☛ Running Example. Step 8 of Fig. 2 compares each retained coefficient with a hidden target: 14 = 𝐿fix for complete candidates and the dummy target 𝐿max + 1 = 17 for early partial-overlap coefficients. Thus, the coefficient aligned with “GO” in 𝐹 1 yields a zero difference, while early coefficients remain nonzero, hiding target selection and match location.
4.6
Privacy-Preserving Selected Decoding
For each retained index 𝜉 = ( 𝑗, 𝑠), the parties derive additive shares of 𝑥 𝜉 = 𝑧 𝑗 [𝑠] − 𝜃 𝜉 (mod 𝑡) while ensuring that neither reconstructs 𝑧 𝑗 [𝑠] or 𝑥 𝜉 , 𝜃 𝜉 remains hidden from CSP, and both local BFV decryption-phase contributions remain private. PP masks 𝜃 𝜉 using the fresh token mask 𝛼 𝜉PP from Section 4.5 by setting 𝑎𝜉 = −𝜃 𝜉 −𝛼 𝜉PP (mod 𝑡). Following the multiparty-BFV paradigm [53], the parties locally compute: 𝑄′
4.5
Private Zero-Target Encoding and Offline Zero-Test Tokens
After overlap pruning, SEEK retains public coefficient indices I, but the private length 𝐿𝑃 determines which coefficients represent complete query windows. To hide this distinction from CSP, PP privately assigns a target 𝜃 𝜉 to each 𝜉 = ( 𝑗, 𝑠) ∈ I and defines the corresponding zero-test input 𝑥 𝜉 as: ( 𝐿fix, 𝑠 ≥ 𝐿𝑃 − 1 𝜃𝜉 = and 𝑥 𝜉 = 𝑧 𝑗 [𝑠] − 𝜃 𝜉 (mod 𝑡) 𝐿max + 1,𝑠 < 𝐿𝑃 − 1 For complete candidates, 𝑥 𝜉 = 0 exactly when the candidate matches 𝑃 under the case-insensitive predicate. If 𝑠 < 𝐿𝑃 − 1, the coefficient cannot represent a complete private query window with |𝑧 𝑗 [𝑠]| ≤ 𝐿fix ≤ 𝐿max , so the dummy target 𝐿max + 1 cannot yield zero under the no-wrap condition (Lemma 5.3). As neither 𝜃 𝜉 nor 𝑥 𝜉 is disclosed, CSP learns neither 𝐿𝑃 nor which retained coefficients represent complete windows. To determine whether any 𝑥 𝜉 = 0 without reconstructing individual values, SEEK constructs one fresh one-sided zero-test token per 𝜉 ∈ I using the OLE primitive of Section 2.2 [8]. In inputindependent preprocessing, PP and CSP sample: PP : 𝛼 𝜉PP ← Z𝑡 , CSP : 𝛼 𝜉CSP, 𝜇𝜉CSP ← Z𝑡 , 𝛽𝜉 ← Z𝑡∗ For each 𝜉, CSP is the OLE sender with (𝑎𝜉OLE, 𝑏 𝜉OLE ) = (𝛽𝜉 , 𝛽𝜉 𝛼 𝜉CSP − 𝜇𝜉CSP ), while PP is the receiver with 𝑥 𝜉OLE = 𝛼 𝜉PP . The OLE returns only 𝜇𝜉PP to PP, such that: 𝜇𝜉PP = 𝑎𝜉OLE𝑥 𝜉OLE + 𝑏 𝜉OLE = 𝛽𝜉 𝛼 𝜉PP + 𝛼 𝜉CSP − 𝜇𝜉CSP Thus, PP holds (𝛼 𝜉PP, 𝜇𝜉PP ), and CSP holds (𝛼 𝜉CSP, 𝜇𝜉CSP, 𝛽𝜉 ). The token’s base values are sampled freshly and independently across candidates and executions and independently of the corpus, query, result, and other preprocessing instances, and components within a token are correlated only by this invariant. In the same
PP 𝑝 𝜉PP = [𝑐 1,𝑗 (sk𝑅,𝑒 mod 𝑄 ′ )] 𝑠 𝑄′
(mod 𝑄 ′ )
𝑄′
CSP 𝑝 𝜉CSP = [𝑐 0,𝑗 + 𝑐 1,𝑗 (sk𝑅,𝑒 mod 𝑄 ′ )] 𝑠
(mod 𝑄 ′ )
■ Batched selected-decoding functionality. For public moduli 𝑞,𝑡 𝑞, 𝑡, and public index set I, the functionality FSD receives (𝑝 𝜉PP, 𝑎𝜉 ) from PP and 𝑝 𝜉CSP from CSP and computes: 𝑣 𝜉 = 𝑝 𝜉PP + 𝑝 𝜉CSP
(mod 𝑞), ∀ 𝜉 ∈ I (7)
𝑤 𝜉 = DecCoeff𝑞,𝑡 (𝑣 𝜉 ) + 𝑎𝜉
(mod 𝑡), ∀ 𝜉 ∈ I
It returns only (𝑤 𝜉 )𝜉 ∈ I to CSP, revealing neither 𝑣 𝜉 nor the other party’s local contribution. For 𝑞 = 𝑄 ′ , we suppress the fixed modpre uli (𝑄 ′, 𝑡) from the notation. Let Π SD and Πon SD denote the 2PC joint-mask preprocessing and online selected-decoding protocols, respectively, which jointly realize FSD . Appendix C gives their concrete composition using standard GMW and mixed-domain conversion primitives [25, 29, 35, 66], following the MPC thresholdFHE decryption paradigm of [76], and proves its correctness and semi-honest security under the stated preprocessing assumptions. Under BFV decoding correctness at 𝑄 ′ , DecCoeff𝑄 ′ ,𝑡 (𝑣 𝜉 ) = 𝑧 𝑗 [𝑠] (mod 𝑡). Hence, the value returned to CSP satisfies: 𝑤 𝜉 = DecCoeff𝑄 ′ ,𝑡 (𝑣 𝜉 ) + 𝑎𝜉 = 𝑥 𝜉 − 𝛼 𝜉PP
(mod 𝑡)
(8)
Therefore, the assignments 𝑥 𝜉PP = 𝛼 𝜉PP and 𝑥 𝜉CSP = 𝑤 𝜉 satisfy 𝑥 𝜉PP + 𝑥 𝜉CSP = 𝑥 𝜉 (mod 𝑡). Because 𝛼 𝜉PP is fresh, uniform, hidden from CSP, and consumed once, 𝑤 𝜉 is uniform from CSP’s view for every 𝑥 𝜉 . Thus, neither party reconstructs an individual correlation coefficient or zero-test input, and all indices in I can be processed as one parallel batch. ☛ Running Example. Step 9 of Fig. 2 converts the selected correlation coefficient into additive shares of its hidden target difference. Here, 61 + 132 = 193 ≡ 0 (mod 193), while neither PP nor CSP reconstructs the coefficient individually.
Conference’17, July 2017, Washington, DC, USA
4.7
Soumyadyuti Ghosh and Michail Maniatakos
One-Sided Zero Testing and Aggregation
After selected decoding, PP and CSP hold additive shares 𝑥 𝜉PP = 𝛼 𝜉PP and 𝑥 𝜉CSP = 𝑤 𝜉 of each hidden zero-test input 𝑥 𝜉 . For every 𝜉 ∈ I, they consume its fresh offline token and set 𝑦𝜉PP = 𝜇𝜉PP and 𝑦𝜉CSP = 𝜇𝜉CSP + 𝛽𝜉 (𝑥 𝜉CSP − 𝛼 𝜉CSP ) (mod 𝑡). The token invariant from Section 4.5 gives 𝑦𝜉PP + 𝑦𝜉CSP = 𝛽𝜉 𝑥 𝜉 (mod 𝑡). Because each fresh 𝛽𝜉 ∈ Z𝑡∗ is nonzero and known only to CSP, the shared value 𝑦𝜉 is zero exactly when 𝑥 𝜉 is zero, without revealing the individual outcome. For 𝐾 = |I|, if 𝐾 = 0, the parties set 𝑌 = 1 and skip multiplication. Otherwise, they multiply the shares ⟨𝑦𝜉 ⟩ using a balanced binary tree, consuming 𝐾 − 1 fresh triples and ⌈log2 𝐾⌉ online rounds, producing additive shares of: 𝑌 =
Ö 𝜉∈I
𝑦𝜉 =
Ö 𝜉∈I
𝛽𝜉
Ö
𝑥𝜉
(mod 𝑡)
(9)
𝜉∈I
Only 𝑌 is reconstructed to PP, which outputs present = 1[𝑌 = 0]. Since Z𝑡 is a field and every 𝛽𝜉 ≠ 0, 𝑌 = 0 iff some retained candidate has 𝑥 𝜉 = 0, equivalently, a keyword match exists. Lemma 6.3 establishes the distribution of 𝑌 conditioned on PP’s preceding view. Hence, aggregation reveals no match count, score, or location beyond the prescribed leakage, and presence bit, while CSP receives no result. ☛Running Example. Steps 10–11 of Fig. 2 blind each target difference with a fresh nonzero scalar and aggregate the results. For (143, 0, 61), the product is zero, so PP receives present = 1 without learning which factor caused the match.
4.8
Functional Setup Validation
After completing the epoch setup described in Section 4.1 and before enabling search, PP and CSP freeze their public artifacts, the active modulus 𝑄 ′ , and local secret-key shares. Employing a collisionresistant hash over canonical, domain-separated encodings, the parties agree on the sender-visible digest 𝑑𝑒S = H(receiverID ∥ 𝑒 ∥ params𝑒 ∥ 𝐿max ∥ pk𝑅,𝑒 ) and the full digest setupDigest𝑒 = H(𝑑𝑒S ∥ rlk𝑅,𝑒 ∥ 𝑄 ′ ), aborting the protocol upon disagreement. Only after this state is fixed do the parties independently sample and exchange 𝜂 PP, 𝜂 CSP ← {0, 1}𝜆 and derive seedval = 𝜂 PP ⊕ 𝜂 CSP . A secure pseudorandom generator and bounded sampler expand the seed into 𝜅 tuples (𝑚 𝜈 , 𝑎 𝜈 , 𝑏 𝜈 , 𝑢 𝜈 ) that are computationally indistinguishable from independent samples, where 𝑚 𝜈 , 𝑎 𝜈 , 𝑏 𝜈 ∈ 𝑅𝑡 are prescribed sparse or dense test polynomials, and 𝑢 𝜈 ∈ {0, . . . , 𝑁 − 1}. For each tuple, PP uses fresh randomness to encrypt (𝑚 𝜈 , 𝑎 𝜈 , 𝑏 𝜈 ) under pk𝑅,𝑒 as (𝑐 𝜈 , 𝑐 𝑎𝜈 , 𝑐 𝑏𝜈 ). CSP computes 𝑐 𝜈 = ModSwitch𝑄→𝑄 ′ (𝑐 𝜈 ) and 𝑑 𝜈 = ModSwitch𝑄→𝑄 ′ (Relinrlk𝑅,𝑒 (Evalmult (𝑐 𝑎𝜈 , 𝑐 𝑏𝜈 ))). The protocol then invokes selected decoding from Section 4.6, followed by one-sided zero testing from Section 4.7, on two singleton instances targeting 𝑚 𝜈 [𝑢 𝜈 ] in 𝑐 𝜈 and (𝑎 𝜈 𝑏 𝜈 ) [𝑢 𝜈 ] in 𝑑 𝜈 . All 2𝜅 instances utilize fresh validation-only selected-decoding preprocessing and one-time zero-test tokens. PP reconstructs the blinded singleton outputs, converts them into zero-test bits, and transmits authenticated copies to CSP. The setup is accepted only if all 2𝜅 bits equal one. Otherwise, R’s epoch setup is rejected and
flagged, and search remains disabled. By the functional correctness of selected decoding and singleton zero testing, all 2𝜅 knownanswer checks return one for a consistent frozen setup (Lemmas 5.4 and 5.5). Passing these checks validates the functional consistency of the frozen BFV artifacts and additive secret-key shares across joint decryption, multiplication, relinearization, modulus switching, selected decoding, and singleton zero testing. The componentlevel correctness results in Lemmas 5.1–5.5 and Theorem 5.6 establish that, for an accepted, consistent setup satisfying the theorem’s conditions, these operations compose into a functionally correct post-setup SEEK search. Upon acceptance, the parties define 𝜒𝑒 = (receiverID, 𝑒, 𝑑𝑒S, setupDigest𝑒 , seedval, 𝜅), compute 𝜏𝑒 = H(𝜒𝑒 ), and issue cert𝑒 = (𝜒𝑒 , SigPP (𝜏𝑒 ), SigCSP (𝜏𝑒 )) under an EUFCMA-secure signature scheme. Before encryption, S recomputes 𝑑𝑒S from the sender-visible setup and verifies the certificate fields and both signatures. Each authenticated upload includes (receiverID, 𝑒, setupDigest𝑒 ), and CSP forwards and searches only ciphertexts matching its active validated setup. Each party stores cert𝑒 together with its frozen local state, including its secret-key share, and refuses to use the certificate if that state changes. Any modification requires fresh validation and certification. Thus, a valid certificate binds every upload and search to one frozen, functionally validated setup, preventing wrong artifact execution and preserving the correctness of subsequent SEEK searches.
5
Correctness Analysis of SEEK
In this section, we present the component-level correctness lemmas and the E2E correctness theorem for SEEK. Full detailed and technical proofs are deferred to Appendix D. Lemma 5.1 (Fragment Coverage and Unique Retention): Under the fixed encoding, let 𝐿𝑃 , 𝐿max, 𝑁 ∈ 8N with 𝐿𝑃 ≤ 𝐿max ≤ 𝑁 . With the minimal sufficient overlap 𝐿max − 8, every complete byte-aligned length-𝐿𝑃 window is fully contained in at least one fragment. Moreover, the pruning set I of Eq. 6 retains the absolute window-end position exactly once. Lemma 5.2 (Correlation Semantics): For every complete byte-aligned candidate window Win 𝑗,𝑠0 whose correlation score occurs at 𝑠 = 𝑠 0 + 𝐿𝑃 − 1, the plaintext coefficient satisfies Eq. 5. Consequently, 𝑧 𝑗 [𝑠] = 𝐿fix if and only if the candidate matches 𝑃 under the ASCII case-insensitive predicate. Lemma 5.3 (No Wraparound and Target Soundness): For every 𝜉 = ( 𝑗, 𝑠) ∈ I, the correlation satisfies |𝑧 𝑗 [𝑠]| ≤ 𝐿fix ≤ 𝐿max . If 𝑠 ≥ 𝐿𝑃 − 1, then 𝑥 𝜉 = 𝑧 𝑗 [𝑠] −𝐿fix ∈ [−2𝐿fix, 0] and equals zero exactly for a complete case-insensitive match. Otherwise, the dummy target 𝐿max + 1 gives 𝑥 𝜉 ∈ [−(2𝐿max + 1), −1]. Therefore, if 𝑡 > 4𝐿max + 2, both ranges lie within the centered representatives of Z𝑡 , so neither an incomplete nor a nonmatching complete candidate becomes zero modulo 𝑡. Lemma 5.4 (Selected-Decoding Correctness): The preprocessing pre and online selected-decoding protocols Π SD and Π on SD jointly realize FSD with functional correctness. For every 𝜉 ∈ I, PP receives nothing, while CSP receives 𝑤 𝜉 (Eq. 7). Lemma 5.5 (Aggregate Correctness): By Lemma 5.4 and Eq. 8, selected decoding yields additive shares of every 𝑥 𝜉 , while zero-test
SEEK: Secure and Efficient Encrypted Keyword Search For Privacy-Preserving Messaging Protocols
conversion yields additive shares of 𝛽𝜉 𝑥 𝜉 : 𝑥 𝜉PP + 𝑥 𝜉CSP = 𝑥 𝜉
(mod 𝑡), 𝑦𝜉PP + 𝑦𝜉CSP = 𝛽𝜉 𝑥 𝜉
(mod 𝑡)
If I ≠ ∅, the Beaver tree reconstructs the aggregate in Eq. 9. If I = ∅, the tree is skipped and the empty product is defined as 𝑌 = 1. In either case, 𝑌 = 0 ⇐⇒ ∃ 𝜉 ∈ I : 𝑥 𝜉 = 0. Theorem 5.6 (End-to-End Correctness of SEEK). Let 𝑀S→R denote an 𝐿-bit encoded message history. For SEEK and BFV parameters 𝐿𝑃 , 𝐿max, 𝑁 ∈ 8N, 𝐿𝑃 ≤ 𝐿max ≤ 𝑁 , prime 𝑡 > 4𝐿max + 2, and correct BFV decoding at 𝑄 ′ , SEEK satisfies: present = 1 ⇐⇒ ∃ 𝑀S→R, ∃ 𝑢 ∈ {0, 8, . . . , 𝐿 − 𝐿𝑃 } : Ham𝛾 ((mS→R [𝑢], . . . , mS→R [𝑢 + 𝐿𝑃 − 1]), p) = 0
(10)
Therefore, SEEK produces neither false positives nor false negatives for byte-aligned case-insensitive keyword search.
6
Security Analysis of SEEK
We analyze SEEK in the standard real-world/ideal-world simulation paradigm under the threat model of Section 3. Before keyword search, receiver-provided artifacts undergo the functional setup validation of Section 4.8 and any test failure rejects the setup and flags R accordingly. The analysis therefore conditions on an accepted and consistent setup as specified in Section 4.1. Full proofs are deferred to Appendix E. ■ Prescribed Leakage. The prescribed leakage includes the BFV public parameters (𝑁 , 𝑡, 𝑄, 𝑄 ′ ), public BFV keys, 𝐿max , and public corpus geometry, which includes message and fragment counts and identifiers, fragment offsets and lengths, and the retained-candidate count 𝐾 = |I|. For CSP, the leakage excludes the query-dependent values 𝑃, 𝐿𝑃 , 𝛾, 𝐿fix , and the search result. For PP, 𝑃 and 𝐿𝑃 are ideal inputs and beyond those inputs and the final presence bit, PP learns no plaintext message, correlation coefficient, match count, or location. Definition 6.1 (Ideal Functionality). Ideal functionality FSEEK is initialized with retained plaintext messages and public corpus geometry. Upon receiving keyword 𝑃 from PP, it computes present ∈ {0, 1} according to Eq. 10. It releases only present to PP, no search result to CSP or R, and otherwise only the prescribed leakage. Repeated admitted queries release the corresponding presence-bit sequence only to PP. Lemma 6.2 (Selected-Decoding Privacy): Under the semi-honestpre secure 2PC and preprocessing primitives of Section 2.2, Π SD and Πon SD securely realize FSD against a static semi-honest adversary corrupting at most one of PP and CSP. 0 denote a Lemma 6.3 (Presence-Only Aggregate Leakage): Let 𝑉PP corrupted PP’s complete view in the input-independent preprocessinghybrid model after invoking FSD and immediately before the Beaver product tree, using fresh, independent zero-test tokens as specified in 0 , public 𝐾, and present = 1[𝑌 = 0], Section 4.5. Conditioned on 𝑉PP the aggregate satisfies:
1, 𝐾 = 0 (necessarily present = 0) 𝑌 ∼ 0, 𝐾 ≥ 1 and present = 1 𝑈 (Z∗ ), 𝐾 ≥ 1 and present = 0 𝑡
Conference’17, July 2017, Washington, DC, USA
Here 𝑈 (Z𝑡∗ ) is uniform over the nonzero field elements. For 𝐾 = 0, the aggregation transcript is empty and 𝑌 = 1 is fixed by the protocol definition. For 𝐾 ≥ 1, semi-honest security of Beaver product [9] makes the aggregation transcript and 𝑌 computationally simulatable 0 , 𝐾, and present. from 𝑉PP Theorem 6.4 (Semi-Honest Privacy of SEEK). Under the adaptive multi-message IND-CPA security of BFV, the semi-honest security of batched OLE [8], and the component guarantees of Lemmas 6.2 and 6.3, the post-setup execution of SEEK, including the encrypted pre corpus, the concrete Π SD and Πon SD protocols, and all subsequent search phases, securely realizes FSEEK with the prescribed leakage against a static semi-honest adversary corrupting at most one of PP and CSP. The corrupted party’s view is simulatable from its local setup state, ideal input/output, and prescribed leakage. Consequently, beyond its query and prescribed leakage, PP learns only present bit, while CSP receives no search result. This guarantee extends to any polynomially bounded and potentially adaptive sequence of authorized queries, provided each execution employs fresh independent one-time preprocessing: the information leakage is limited to the ideal presence-bit sequence and its logical implications.
7
Experimental Evaluation
We evaluate SEEK across three complementary dimensions. We first microbenchmark the computation and communication costs of individual protocol stages. We then measure E2E latency using web and mobile application prototypes. Finally, we assess the feasibility of repeated presence-only queries. ■ Implementation and Baseline. We implement SEEK and the fragmentation-based baseline [11] using Microsoft SEAL [67] and instantiate all protocol roles (S/R/PP/CSP) to isolate protocol design costs from runtime heterogeneity. All microbenchmarks are executed single-threaded on a machine with two 64-core AMD EPYC processors, 2 TB of DDR4 memory, and Ubuntu 22.04.5 LTS. Both schemes use the same parameter grid: 𝑁 ∈ {212, 213, 214, 215 } and 𝐿max ∈ {128, 256, 512, 1024, 2048}. Each configuration uses a 20-bit prime plaintext modulus satisfying 𝑡 ≡ 1 (mod 2𝑁 ) and 𝑡 > 4𝐿max + 2, together with a ciphertext-modulus chain providing at least 128-bit classical security [3]. Appendix F reports the full implementation parameterization (𝑁 , 𝑡, 𝑄, 𝑄 ′, 𝑞 ℓ ) and BFV noisebudget stress test. We select [11] as our primary baseline because its RLWE-based fragmentation design closely matches our construction and E2EE messaging setting, compared to other HE-based techniques (Appendix B). ■ Datasets and Keywords. SEEK is evaluated on the SAMSum messenger-style dataset, comprising 173,717 messages with approximately 1.5M words between 4,416 distinct users. We use a common parameter setting across all users, which makes the total cost of searching individual conversations comparable to that of searching the entire corpus. This approach demonstrates SEEK’s scalability with increasing message volume. Since SAMSum lacks timestamps, we assign interpretive workload durations using populationaverage estimates of 54.15 messages per user per day and 14.31 words per message [48, 58, 59]. Under this mapping, the complete corpus represents approximately five years of messaging, while 1K and 25K words correspond to about one day and one month, respectively. We evaluate ten increasing workloads spanning these scales
Conference’17, July 2017, Washington, DC, USA
under 500 patterns averaging 16 bytes, evenly divided between present and absent queries. Present patterns are sampled from SAMSum, while absent patterns are drawn from a frequency-ranked WordFreq/SUBTLEX-US universe of 248,266 keywords [17, 71]. Section 7.2 uses this universe to analyze the operational cost of repeated queries. ■ End-to-End Web and Mobile Prototype. To measure E2E latency and deployment feasibility on commodity devices, we build a web and cross-platform mobile application with S, R, PP, and CSP deployed as distinct networked endpoints. We use a modified node-seal backend [4] supporting the coefficient-domain plaintext construction required by SEEK but unavailable in the standard bindings. We run the mobile client on a OnePlus 11R with 8 GB RAM and 256 GB storage. We provide detailed implementation, demonstrations, and interface discussion in Appendix A.
7.1
Protocol Microbenchmarks and Scalability
■ Correctness. Across all 20 (𝑁 , 𝐿max ) pairs, we execute 10,000 encrypted searches: 5000 positive and 5000 negative. SEEK produces no false positives or false negatives, achieving 100% precision, recall, F1 score, and accuracy. By contrast, the exact-match protocol of [11] maintains 100% precision but achieves only 60% recall, 75% F1 score, and 80% accuracy because case variations cause 2000 false negatives. Its wildcard extension supports equivalent ASCII case-insensitive matching but requires a two-ciphertext trapdoor, compared with one ciphertext for SEEK. Thus, SEEK handles capitalization using negligible local case-mask construction, without additional trapdoor variants or online communication. ■ Fragmentation, Encryption, and Trapdoor Generation. Fig. 3 reports fragmentation, overlap, and encrypted-ingestion overhead for the 1.5M-word (five-year) workload. Across the four 𝑁 values, SEEK averages 173.7K fragments at every 𝐿max , while the baseline decreases from 558.8K at 𝐿max = 128 to 210.5K at 512 and 174.0K at 2048. At 𝐿max = 128 and 512, SEEK reduces mean fragment count and encrypted upload by 3.22× and 1.21×. Across all 20 pairs, it reduces the mean fragment count from 288.7K to 173.7K and upload/storage from 713.64 to 429.44 GiB, a 39.82% reduction. Increasing 𝑁 removes only the 15 excess fragments at 𝑁 = 4096 but expands SEEK’s mean footprint from 21.23 GiB to 1272.36 GiB at 𝑁 = 32768, favoring the smallest secure degree satisfying the computation and correctness bounds. At the practical (𝑁 , 𝐿max ) = (4096, 512) pair, SEEK and the baseline require 173,732 and 210,535 fragments, occupy 21.23 and 25.73 GiB, and complete fragmentation and encryption in 198.27 and 230.13 s, respectively. This corresponds to 1.14 ms per message for SEEK. At (4096, 128), the sender costs are 1.12 and 3.44 ms per message. Overlap-induced repetition shows an even larger gap. Averaged over 𝑁 , SEEK and the baseline process 56.3 bytes and 3.57 MiB at 𝐿max = 128 (66,516× reduction), and 236.3 bytes and 352.6 KiB at 𝐿max = 512 (1,528× reduction). Their grid-wide averages are 368.3 bytes and 1.10 MiB, giving a 3,129× reduction. At 𝑁 = 4096, SEEK/baseline trapdoors occupy 128.11/256.22 KiB and take 15.99/29.70 ms to construct, approximately halving both costs without penalizing smaller policyadequate values of 𝐿max . Long documents amplify the fragmentation advantage even more. For 𝑁 = 4096/8192/16384/32768, 1K/10Kword documents at 𝐿max = 512 require 84/839 baseline blocks but
Soumyadyuti Ghosh and Michail Maniatakos
only 12/120, 6/56, 3/27, and 2/14 SEEK fragments, yielding 7–42× and 6.99–59.93× reductions. At 𝐿max = 128, the baseline requires 335/3,353 blocks, compared with 11/108, 6/54, 3/27, and 2/14 for SEEK, yielding 30.45–167.5× and 31.05–239.5× reductions. Because the construction of [11] couples its base-fragment length to the maximum supported pattern length, our primary comparison uses the common 𝐿max . Even when the baseline alone is overprovisioned from 512 bits to its maximum 𝑁 /2, its 1K/10K-word counts of 21/210, 11/105, 6/53, and 3/27 remain 1.50–2.00× and 1.75–1.96× those of SEEK at 𝐿max = 512. This bound already supports four times the average pattern length. However, larger values only increase overlap, reduce stride, and generate more fragments for long messages. ■ Correlation Computation. Fig. 41 compares SEEK’s encrypted correlation overhead with the baseline’s online adjacent-pair reconstruction and case-insensitive wildcard correlation cost across all histories and 20 (𝑁 , 𝐿max ) pairs. Following [11], adjacent-pair overlaps are reconstructed online for each query. Precomputing and storing them would increase storage by up to 2× while saving only the 0.18% median time spent on reconstruction. SEEK is faster in all 200 observations, achieving median and maximum speedups of 1.99× and 5.47×, with a 4.52× median at 𝐿max = 128. Including preprocessing yields a 1.95× speedup because preprocessing contributes only 1.54% of the combined cost. Computation grows approximately linearly with retained history. From 1K to 1.5M words, the median over 𝐿max increases from 0.382/0.784 to 670.3/1,352.6 s for SEEK/baseline at 𝑁 = 4096, and from 37.45/69.15 s to 65.71/119.17 ks at 𝑁 = 32768. For fixed 𝑁 and history, SEEK’s median max–min ratio across the five 𝐿max values is only 1.03×, compared with up to 2.9× for the baseline. This advantage follows from fewer instances and lighter arithmetic. SEEK uses one ct–ct multiplication per fragment, while each baseline wildcard variant’s core correlation uses two ct–ct multiplications, two ct–pt multiplications, and two additions/ciphertext subtractions, with adjacent-pair reconstruction adding one monomial ct–pt multiplication and one ciphertext addition. ■ Online Cost Analysis and Scalability. Fig. 5 reports average per-query costs across all message histories and (𝑁 , 𝐿max ) pairs. Computation begins once the encrypted trapdoor, preprocessed corpus, and fresh preprocessing material are available and ends when PP constructs present. Communication includes trapdoor delivery and all subsequent PP–CSP exchanges. Across all (𝑁 , 𝐿max ) pairs, daily, monthly, and five-year histories require 0.408–42.46 s and 3.74–32.97 MiB, 12.41 s–1.29 ks and 107.49–778.96 MiB, and 715.50 s–74.50 ks and 6.05–43.44 GiB, respectively. From one month to five years, computation increases by 57.64–57.65× and communication by 57.10–57.62×, closely tracking message growth and confirming near-linear scalability. The bottom panel identifies 𝑁 as the principal performance determinant. For the five-year history, increasing 𝑁 from 4096 to 32768 raises median computation over 𝐿max from 727.43 s to 73.19 ks, a 100.6× increase, and communication from 6.05 to 43.44 GiB, a 7.18× increase. At fixed 𝑁 , varying 𝐿max changes computation by at most 1.05× and leaves communication unchanged because overlap pruning limits selected decoding and aggregation to unique byte-aligned positions. Across all 200 searches, 1 Here and subsequently, costs increase with 𝑁 , history size, or query count, as appli-
cable (Figs. 4–7), enabling distinction without varying markers.
SEEK: Secure and Efficient Encrypted Keyword Search For Privacy-Preserving Messaging Protocols
Conference’17, July 2017, Washington, DC, USA
Figure 3: Fragmentation, encrypted-upload, and overlap overheads of SEEK and [11] for the ≈ 1.5M-word message corpus (five year history). Values indexed by 𝐿max are averaged over all 𝑁 and the 𝑁 -indexed upload is averaged over all 𝐿max .
Figure 4: Query-wise average correlation cost of SEEK and overlap construction with correlation cost of [11].
correlation multiplication, relinearization, and modulus switching account for 97.0% of computation, while reduced-𝑐 1 transfer and GMW openings account for 96.6% of communication. Consequently, 𝑁 = 4096 is the practical sweet spot whenever its decoding and correctness conditions hold. For 𝐿max = 256, 512, and 1024, it requires only 0.408–0.424 s, 12.41–12.90 s, and 715.50–743.65 s for daily, monthly, and five-year histories, with corresponding communication of 3.74 MiB, 107.49 MiB, and 6.05 GiB. ■ Offline Cost Analysis. Fig. 6 reports the one-time main BFV pre setup and fresh per-query ΠSD costs, assuming Boolean triples and daBits are available. The setup includes BFV context and key generation, additive secret-key sharing, serialization, and key/share distribution. Its cost increases from 12.518 ms and 1.501 MiB at 𝑁 = 4096 to 1.053 s and 272.008 MiB at 𝑁 = 32,768 and is amortized over the key-lifecycle period. At the practical (𝑁 , 𝐿max ) = (4096, 512) pre setting, ΠSD requires 0.562 ms and 0.365 MiB for the daily history, 14.460 ms and 9.138 MiB for the monthly history, and 0.817 s and 530.340 MiB for the five-year history. The complete fresh per-query bundle for joint-mask preprocessing, selected decoding, zero testing, and aggregation contains 𝐾 (8ℓ𝑄 + 2) Boolean triples, 3𝐾 daBits, 𝐾 − 1 arithmetic Beaver triples, and 𝐾 scalar OLEs [8, 9, 25, 29, 66]. Under a state-of-the-art 128-bit semi-honest generation model using batches of 107 and an amortized rate of 0.118 communicated bits per random oblivious transfer [16], generating this bundle is projected
Figure 5: Computation and communication costs of SEEK with increasing message history and across all (𝑁 , 𝐿max ) pairs.
to communicate 1.666 MiB, 41.745 MiB, and 2.366 GiB for the daily, monthly, and five-year histories, respectively. Since these resources depend only on public 𝐾 and the BFV parameters, rather than the corpus, keyword, or result, they can be batch-generated before query arrival. ☛ Example. At (4096, 512), with preprocessing available, the fiveyear online search from trapdoor delivery to final present bit requires 743.65 s and 6.05 GiB, or 13.26 min with serialized computation and ideal 1 Gbps transmission. Even the largest evaluated corpus, 1.243 TiB at (32768, 2048), is searched online in approximately 20.39 h, demonstrating SEEK’s feasibility at substantially larger scales.
Conference’17, July 2017, Washington, DC, USA
Soumyadyuti Ghosh and Michail Maniatakos
Figure 6: One-time BFV setup and fresh per-query selecteddecoding preprocessing overheads of SEEK at 𝐿max = 512. Figure 7: Repeated-Query Overhead.
7.2
Repeated-Query Attack Analysis
Fig. 7 demonstrates the conservative lower-bound costs for repeatedquery abuse over one-month and five-year SAMSum histories [34], considering only the online correlation-to-presence pipeline under the practical (𝑁 , 𝐿max ) = (4096, 128) configuration. Following the fixed, target-independent external WordFreq/SUBTLEX-US frequency ranking [17, 71], the first 1334/1290, 4655/4521, and 21,537/20,145 queries cover at least 70%, 80%, and 90% of word occurrences in the one-month/five-year histories, respectively. The complete 248,266-query sweep reaches only 92.50%/92.57% coverage. These evaluator-side oracle measurements overstate actual disclosure because each query reveals only one history-wide substringpresence bit without counts, message identity, position, or order. Consequently, even 90% occurrence coverage neither recovers 90% of the plaintext nor provides sufficient structure to reconstruct conversations. At WhatsApp scale [51], applying a 5K-query sweep, which exceeds both 80% thresholds, to three billion five-year histories is projected to require 346.5 million compute-years and 97.4 ZB. Even one platform-wide query requires 69,300 compute-years and 19.5 EB, taking approximately 36 weeks with 105 perfectly balanced workers. Within one week, this cluster can process at most approximately 83 million user-keyword evaluations, equivalent to one keyword over 83 million users or 5K keywords over only 16,600 users, before communication further reduces this bound. An attacker must therefore trade keyword breadth against population and history length. Narrow targeted probing remains feasible, but platform-scale reconstruction is computationally and communicationally infeasible.
7.3
End-to-End Prototype Evaluation
We evaluate the complete SEEK application prototype under (4096, 512) using a one-week history of approximately 5K words represented by 91 fragments. The complete setup and functional validation (𝜅 = 4) takes 24.62 s on the web client and 24.81 s on mobile, with 6.37 MB of communication, indicating that server-side PP–CSP operations dominate. Message packing and BFV encryption cost approximately 0.4 ms per word on the web client and 4 ms per word on mobile. Fresh input-independent preprocessing requires 67.76 s of computation in the current serialized implementation, with 36.1 s incurred by PP and 31.66 s by CSP. Computation is dominated by Boolean-triple generation (49.91 s) and base OT (12.15 s), while preprocessing exchanges 622.72 MB of payload, primarily for Boolean
triples (549.38 MB) and arithmetic Beaver triples (46.31 MB), corresponding to an ideal serialization time of 4.98 s over a 1 Gbps link. SEEK additionally exchanges 15.84 MB across corpus processing and online 2PC (11.65 MB). A fresh execution including preprocessing therefore corresponds to 5.11 s of communication time at 1 Gbps. With input-independent preprocessing off the query path, trapdoor encryption, encrypted ±1 mapping, and correlation-to-bit reconstruction require 1.59 ms, 8.51 ms, and 1.91 s, respectively. The latter includes 319.8 ms for homomorphic multiplication, 626.4 ms for joint-mask processing, and 631.3 ms for selected decoding. Overall, the query-time cryptographic pipeline requires 1.92 s, demonstrating practical E2E encrypted messaging and privacy-preserving search across web and commodity mobile devices.
8
Conclusion
We presented SEEK, a privacy-preserving keyword-search protocol that combines minimum-sufficient byte-aligned fragmentation, packed BFV correlation, and 2PC-based selected decoding, blinded zero testing, and secure aggregation. It supports ASCII caseinsensitive search using one fixed-size encrypted trapdoor and one query-dependent homomorphic multiplication per fragment, releasing only a corpus-wide presence bit to PP. We established search correctness and post-setup privacy against a static semi-honest adversary under the stated assumptions. SEEK achieved 100% observed accuracy, reduced mean fragment overhead by 39.82%, and provided maximum correlation speedup of 5.47× over the wildcard baseline. Our web/mobile prototype and scalability analysis further demonstrate practical and efficient presence-only search over retained encrypted messages.
References [1] Harold Abelson, Ross Anderson, Steven M Bellovin, Josh Benaloh, Matt Blaze, Jon Callas, Whitfield Diffie, Susan Landau, Peter G Neumann, Ronald L Rivest, et al. 2024. Bugs in our pockets: the risks of client-side scanning. Journal of Cybersecurity 10, 1 (2024), tyad020. [2] Harold Abelson, Ross Anderson, Steven M. Bellovin, Josh Benaloh, Matt Blaze, Whitfield Diffie, John Gilmore, Matthew Green, Susan Landau, Peter G. Neumann, Ronald L. Rivest, Jeffrey I. Schiller, Bruce Schneier, Michael A. Specter, and Daniel J. Weitzner. 2015. Keys under doormats: mandating insecurity by requiring government access to all data and communications. Journal of Cybersecurity 1, 1 (09 2015), 69–79. doi:10.1093/cybsec/tyv009 [3] Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, et al. 2022. Homomorphic encryption standard. In Protecting privacy through homomorphic
SEEK: Secure and Efficient Encrypted Keyword Search For Privacy-Preserving Messaging Protocols
encryption. Springer, 31–62. [4] Nick Angelou. 2025. node-seal: Homomorphic Encryption for TypeScript or JavaScript - Microsoft SEAL. https://github.com/s0l0ist/node-seal/tree/main. [5] Apple. 2025. Legal Process Guidelines: Government and Law Enforcement within the United States. https://www.apple.com/legal/privacy/law-enforcementguidelines-us.pdf. [6] Australian Department of Home Affairs. 2023. The Assistance and Access Act 2018. https://www.homeaf fairs.gov.au/about- us/our- portfolios/nationalsecurity/lawful-access-telecommunications/data-encryption. [7] Richard Barnes, Benjamin Beurdouche, Raphael Robert, Jon Millican, Emad Omara, and Katriel Cohn-Gordon. 2023. RFC 9420: The Messaging Layer Security (MLS) Protocol. https://www.rfc-editor.org/rfc/rfc9420. RFC 9420. [8] Carsten Baum, Daniel Escudero, Alberto Pedrouzo-Ulloa, Peter Scholl, and Juan Ramón Troncoso-Pastoriza. 2022. Efficient protocols for oblivious linear function evaluation from ring-LWE. Journal of Computer Security 30, 1 (2022), 39–78. [9] Donald Beaver. 1991. Efficient multiparty protocols using circuit randomization. In Annual international cryptology conference. Springer, 420–432. [10] Anis Bkakria, Nora Cuppens, and Frédéric Cuppens. 2020. Privacy-preserving pattern matching on encrypted data. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 191–220. [11] Anis Bkakria and Malika Izabachène. 2024. Efficient post-quantum pattern matching on encrypted data. IACR Communications in Cryptology 1, 2 (2024). [12] Charlotte Bonte and Ilia Iliashenko. 2020. Homomorphic string search with constant multiplicative depth. In Proceedings of the 2020 ACM SIGSAC Conference on Cloud Computing Security Workshop. 105–117. [13] Elie Bouscatié, Guilhem Castagnos, and Olivier Sanders. 2021. Public key encryption with flexible pattern matching. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 342–370. [14] Élie Bouscatié, Guilhem Castagnos, and Olivier Sanders. 2023. Pattern matching in encrypted stream from inner product encryption. In IACR International Conference on Public-Key Cryptography. Springer, 774–801. [15] Zvika Brakerski. 2012. Fully homomorphic encryption without modulus switching from classical GapSVP. In Annual cryptology conference. Springer, 868–886. [16] Andreas Brüggemann, Robin Hundt, Thomas Schneider, Ajith Suresh, and Hossein Yalame. 2023. FLUTE: fast and secure lookup table evaluations. In 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 515–533. [17] Marc Brysbaert and Boris New. 2009. Moving beyond Kučera and Francis: A critical evaluation of current word frequency norms and the introduction of a new and improved word frequency measure for American English. Behavior research methods 41, 4 (2009), 977–990. [18] Sébastien Canard, Aïda Diop, Nizar Kheir, Marie Paindavoine, and Mohamed Sabt. 2017. BlindIDS: Market-compliant and privacy-friendly intrusion detection system over encrypted traffic. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security. 561–574. [19] Ran Canetti and Gabriel Kaptchuk. 2021. The Broken Promise of Apple’s Announced Forbidden-photo Reporting System – And How To Fix It. https: //www.bu.edu/riscs/2021/08/10/apple-csam/. [20] David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. 2015. Leakageabuse attacks against searchable encryption. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security. 668–679. [21] Javad Ghareh Chamani, Dimitrios Papadopoulos, Mohammadamin Karbasforushan, and Ioannis Demertzis. 2022. Dynamic searchable encryption with optimal search in the presence of deletions. In 31st USENIX Security Symposium (USENIX Security 22). 2425–2442. [22] Melissa Chase and Emily Shen. 2015. Substring-searchable symmetric encryption. Proceedings on Privacy Enhancing Technologies (2015). [23] Court of Justice of the European Union. 2024. Judgment of the Court in Case C-670/22, M.N. (EncroChat). https://eur-lex.europa.eu/legal-content/EN/TXT/? uri=CELEX:62022CJ0670_RES. [24] Tech Crunch. 2018. US Government Loses Bid to Force Facebook to Wiretap Messenger Calls. https://techcrunch.com/2018/09/28/us-government-loses-bidto-force-facebook-to-wiretap-messenger-calls/. [25] Daniel Demmler, Thomas Schneider, and Michael Zohner. 2015. ABY-A framework for efficient mixed-protocol secure two-party computation.. In Ndss. [26] Nicolas Desmoulins, Pierre-Alain Fouque, Cristina Onete, and Olivier Sanders. 2018. Pattern matching on encrypted streams. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 121–148. [27] Electronic Frontier Foundation. 2018. EFF, ACLU v. DOJ – Facebook Messenger Unsealing. https://www.ef f.org/cases/ef f-aclu-v-doj-facebook-messengerunsealing?language=en. [28] England and Wales Court of Appeal, Criminal Division. 2021. A, B, D and C v. Regina, [2021] EWCA Crim 128. https://www.judiciary.uk/judgments/a-b-d-c-vregina/. [29] Daniel Escudero, Satrajit Ghosh, Marcel Keller, Rahul Rachuri, and Peter Scholl. 2020. Improved primitives for MPC over mixed arithmetic-binary circuits. In Annual international cryptology conference. Springer, 823–852.
Conference’17, July 2017, Washington, DC, USA
[30] European Commission. 2022. Proposal for a Regulation laying down rules to prevent and combat child sexual abuse. https://eur- lex.europa.eu/legalcontent/EN/TXT/?uri=celex%3A52022PC0209. [31] Europol. 2023. Dismantling encrypted criminal EncroChat communications leads to over 6,500 arrests and close to EUR 900 million seized. https://www.europo l.europa.eu/media-press/newsroom/news/dismantling-encrypted-criminalencrochat-communications-leads-to-over-6-500-arrests-and-close-to-eur900-million-seized [32] Expo. 2025. Expo: An open-source framework for making universal native apps with React. https://github.com/expo/expo. [33] Junfeng Fan and Frederik Vercauteren. 2012. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive (2012). [34] Bogdan Gliwa, Iwona Mochol, Maciej Biesek, and Aleksander Wawer. 2019. SAMSum Corpus: A Human-annotated Dialogue Dataset for Abstractive Summarization. CoRR abs/1911.12237 (2019). arXiv:1911.12237 http://arxiv.org/abs/ 1911.12237 [35] Oded Goldreich, Silvio Micali, and Avi Wigderson. 2019. How to play any mental game, or a completeness theorem for protocols with honest majority. In Providing sound foundations for cryptography: on the work of Shafi Goldwasser and Silvio Micali. 307–328. [36] Paul Grubbs, Jiahui Lu, and Thomas Ristenpart. 2017. Message Franking via Committing Authenticated Encryption. In Advances in Cryptology – CRYPTO 2017 (Lecture Notes in Computer Science, Vol. 10403). Springer, 66–97. doi:10.1007/9783-319-63697-9_3 [37] The Guardian. 2022. Facebook gave police their private data. Now, this duo face abortion charges. https://www.theguardian.com/us-news/2022/aug/10/facebookuser-data-abortion-nebraska-police. [38] Zichen Gui, Kenneth G Paterson, and Sikhar Patranabis. 2024. Analyze Your Leakage! Security Analysis of Encryption Schemes for Substring Search. Cryptology ePrint Archive (2024). [39] Zichen Gui, Kenneth G Paterson, Sikhar Patranabis, and Bogdan Warinschi. 2024. SWiSSSE: System-wide security for searchable symmetric encryption. Proceedings on Privacy Enhancing Technologies (2024). [40] Yu Ishimaki, Hiroki Imabayashi, and Hayato Yamana. 2017. Private substring search on homomorphically encrypted data. In 2017 IEEE International Conference on Smart Computing (SMARTCOMP). IEEE, 1–6. [41] Rawane Issa, Nicolas Alhaddad, and Mayank Varia. 2022. Hecate: Abuse reporting in secure messengers with sealed sender. In 31st USENIX Security Symposium (USENIX Security 22). 2335–2352. [42] Mayank Kabra, Rakesh Nadig, Harshita Gupta, Rahul Bera, Manos Frouzakis, Vamanan Arulchelvan, Yu Liang, Haiyu Mao, Mohammad Sadrosadati, and Onur Mutlu. 2025. CIPHERMATCH: Accelerating Homomorphic Encryption-Based String Matching via Memory-Efficient Data Packing and In-Flash Processing. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2. 111–130. [43] Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O’neill. 2016. Generic attacks on secure outsourced databases. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 1329–1340. [44] Marcel Keller, Emmanuela Orsini, and Peter Scholl. 2016. MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 830–842. [45] Ben Laurie, Eran Messeri, and Rob Stradling. 2021. RFC 9162: Certificate Transparency Version 2.0. https://www.rfc-editor.org/rfc/rfc9162. [46] Tung Le, Rouzbeh Behnia, Jorge Guajardo, and Thang Hoang. 2024. { MUSES } : Efficient { Multi-User } Searchable Encrypted Database. In 33rd USENIX Security Symposium (USENIX Security 24). 2581–2598. [47] Dongli Liu, Wei Wang, Peng Xu, Laurence T Yang, Bo Luo, and Kaitai Liang. 2024. { d-DSE } : Distinct Dynamic Searchable Encryption Resisting Volume Leakage in Encrypted Databases. In 33rd USENIX Security Symposium (USENIX Security 24). 2563–2580. [48] Fiona Lyddy, Francesca Farina, James Hanney, Lynn Farrell, and Niamh Kelly O’Neill. 2014. An analysis of language in university students’ text messages. Journal of Computer-Mediated Communication 19, 3 (2014), 546–561. [49] Long Meng, Liqun Chen, Yangguang Tian, Mark Manulis, and Suhui Liu. 2024. { FEASE } : Fast and Expressive Asymmetric Searchable Encryption. In 33rd USENIX Security Symposium (USENIX Security 24). 2545–2562. [50] Meta. 2026. Information for law enforcement authorities. https://www.meta.c om/safety/communities/law/guidelines/. [51] Meta. 2026. It’s Time to Reserve Your WhatsApp Username. https://about.fb.c om/news/2026/06/its-time-to-reserve-your-whatsapp-username/. Accessed July 30, 2026. [52] Priyanka Mondal, Javad Ghareh Chamani, Ioannis Demertzis, and Dimitrios Papadopoulos. 2024. { I/O-Efficient } dynamic searchable encryption meets forward & backward privacy. In 33rd USENIX Security Symposium (USENIX Security 24). 2527–2544.
Conference’17, July 2017, Washington, DC, USA
[53] Christian Mouchet, Juan Troncoso-Pastoriza, Jean-Philippe Bossuat, and JeanPierre Hubaux. 2021. Multiparty homomorphic encryption from ring-learningwith-errors. Proceedings on Privacy Enhancing Technologies 2021, 4 (2021), 291– 311. [54] Shintaro Narisada, Hiroki Okada, Takashi Nishide, and Kazuhide Fukushima. 2026. Efficient Homomorphic String Search via TFHE. Pragmatic Cybersecurity 1, 2 (2026), 13. doi:10.53941/pc.2026.100013 [55] National Crime Agency. 2020. NCA and police smash thousands of criminal conspiracies after infiltration of encrypted communication platform in UK’s biggest ever law enforcement operation. https://www.nationalcrimeagency.gov. uk/news/operation-venetic. [56] National Institute of Standards and Technology. 2020. Security and Privacy Controls for Information Systems and Organizations. https://csrc.nist.gov/pubs /sp/800/53/r5/upd1/final. [57] Jack Nicas, Raymond Zhong, and Daisuke Wakabayashi. 2021. Censorship, Surveillance and Profits: A Hard Bargain for Apple in China. https://www.nyti mes.com/2021/05/17/technology/apple-china-censorship-data.html. The New York Times. [58] Ofcom. 2023. WhatsAppening in the World of Online Communications? Ofcom research report. https://www.ofcom.org.uk/internet-based-services/technolog y/whatsappening-in-the-world-of-online-communications [59] Office for National Statistics. 2024. Population Estimates for the UK, England, Wales, Scotland, and Northern Ireland: Mid-2022. https://www.ons.gov.uk/peopl epopulationandcommunity/populationandmigration/populationestimates/bul letins/annualmidyearpopulationestimates/mid2022 [60] Parliament of Australia. 2018. Telecommunications and Other Legislation Amendment (Assistance and Access) Bill 2018. https://www.aph.gov.au/Parliamentary _Business/Bills_Legislation/Bills_Search_Results/Result?bId=r6195. [61] Trevor Perrin, Moxie Marlinspike, and Rolfe Schmidt. 2025. The Double Ratchet Algorithm. https://signal.org/docs/specifications/doubleratchet/. accessed July 30, 2026. [62] Rest of World. 2024. WhatsApp gives India an ultimatum on encryption. https: //restofworld.org/2024/exporter-whatsapp-encryption-india/. [63] Reuters. 2025. Apple pulls data protection feature in UK amid government demands. https://www.reuters.com/technology/apple-removing-end-to-endcloud-encryption-feature-uk-bloomberg-news-reports-2025-02-21/. [64] Reuters. 2025. UK orders Apple to open up users’ encrypted cloud data, report says. https://www.reuters.com/world/uk/uk-asks-apple-let-it-spy-usersencrypted-accounts-washington-post-reports-2025-02-07/. [65] Reuters. 2026. EU fails to extend rules on child abuse content detection by online platforms. https://www.reuters.com/legal/litigation/eu-fails-extend-rules-childabuse-content-detection-by-online-platforms-2026-03-16/. [66] Dragos Rotaru and Tim Wood. 2019. Marbled circuits: Mixing arithmetic and boolean circuits with active security. In International Conference on Cryptology in India. Springer, 227–249. [67] SEAL 2023. Microsoft SEAL (release 4.1). https://github.com/Microsoft/SEAL. Microsoft Research, Redmond, WA.. [68] Iñaki Seco-Aguirre, Cristina Regueiro, Julen Bernabé-Rodríguez, and Eduardo Jacob. 2026. Extending homomorphic algorithms for encrypted text comparison. Scientific Reports (2026). https://doi.org/10.1038/s41598-026-48255-2 [69] Justine Sherry, Chang Lan, Raluca Ada Popa, and Sylvia Ratnasamy. 2015. Blindbox: Deep packet inspection over encrypted traffic. In Proceedings of the 2015 ACM conference on special interest group on data communication. 213–226. [70] Signal Messenger. 2026. Government Requests. https://signal.org/bigbrother/. [71] Robyn Speer. 2022. rspeer/wordfreq: v3.0. doi:10.5281/zenodo.7199437 [72] The Guardian. 2026. Instagram to remove end-to-end encryption for private messages in May. https://www.theguardian.com/technology/2026/mar/18/instagramto-remove-end-to-end-encryption-for-private-messages-in-may [73] US Department of Justice. 2021. FBI’s Encrypted Phone Platform Infiltrated Hundreds of Criminal Syndicates, Resulting in Massive Worldwide Takedown. https://www.justice.gov/usao- sdca/pr/fbi- s- encrypted- phone- platforminfiltrated-hundreds-criminal-syndicates-result-massive. [74] Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, and Takeshi Koshiba. 2013. Practical Packing Method in Somewhat Homomorphic Encryption. In Data Privacy Management and Autonomous Spontaneous Security 8th International Workshop, DPM 2013, and 6th International Workshop, SETOP 2013, Egham, UK, September 12-13, 2013, Revised Selected Papers (Lecture Notes in Computer Science, Vol. 8247), Joaquín García-Alfaro, Georgios V. Lioudakis, Nora Cuppens-Boulahia, Simon N. Foley, and William M. Fitzgerald (Eds.). Springer, 34–50. doi:10.1007/978-3-642-54568-9_3 [75] Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, and Takeshi Koshiba. 2013. Secure pattern matching using somewhat homomorphic encryption. In Proceedings of the 2013 ACM workshop on Cloud computing security workshop. 65–76. [76] Guy Zyskind, Doron Zarchy, Max Leibovich, and Chris Peikert. 2025. HighThroughput Universally Composable Threshold FHE Decryption. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security. 2339–2353.
Soumyadyuti Ghosh and Michail Maniatakos
A
Prototype SEEK Application Details
■ Prototype Implementation. To quantify end-to-end latency on commodity devices and validate deployability within an encryptedmessaging workflow, a proof-of-concept web and cross-platform mobile application was developed for the SEEK protocol. The prototype consists of four logical components: (i) a combined Chat/Registration layer for authentication, receiver setup, certified public-key distribution, and encrypted-message communication; (ii) a PP service for trapdoor generation, search coordination, and final-result reconstruction; (iii) a CSP service for encrypted storage and search evaluation; and (iv) sender/receiver endpoints implemented as web and mobile messaging clients. The React web client utilizes a bundled node-seal backend [4], which exposes the coefficient-domain BFV plaintext operations required by SEEK through WebAssembly. The cross-platform mobile client is built in React Native using Expo SDK [32]. Since React Native does not execute WebAssembly directly, the mobile client invokes the same embedded SEAL WASM stack inside a hidden WebView via a structured message-passing interface. Both clients verify the receiver’s certified public key, encrypt outgoing message fragments locally, and decrypt received messages exclusively at the endpoint. The PP and CSP components are implemented as Python services using FastAPI, with core cryptographic operations executed by native helpers built on Microsoft SEAL. The components communicate through authenticated REST APIs, and Socket.IO supports real-time messaging. For each authorized search, PP pins the selected directed corpus and generates a fixed-size encrypted trapdoor, while CSP applies the encrypted transformation 𝑚 ↦→ 1 − 2𝑚, evaluates BFV correlation, performs relinearization and modulus switching, and retains its local BFV shares. The parties directly generate fresh Boolean multiplication triples [25], doubly authenticated bits (daBits) [29, 66], scalar oblivious linear evaluation (OLE) zero-test tokens [8], and arithmetic Beaver multiplication triples using RSA-based oblivious transfers (OTs) and extensions. These resources support joint-mask GMW, selected decoding with daBits, scalar-OLE zero testing, and balanced Beaver product aggregation. Only the final product-tree root is reconstructed at PP and mapped to a single presence bit, whereas no match position, count, correlation score, or matching-message identity is revealed, and CSP receives no result. The four components communicate as distinct networked roles within a containerized local deployment with different endpoints, and the unified client architecture supports both iOS and Android. ■ Interfaces and Workflow. Fig. 8 and Fig. 9 illustrate the authentication, encrypted messaging, and authorized search interfaces. Fig. 10 displays the search outputs and setup diagnostics. Upon successful registration, a receiver epoch is automatically provisioned and validated, enabling the client to access the chat interface. Each outgoing message is independently fragmented and encrypted locally using the receiver’s certified BFV public key, transmitted via Chat services to CSP, and decrypted and reassembled exclusively by the receiver. As a result, searches do not span message boundaries. In Fig. 9, the PP operator selects a sender S, a receiver R, and an ASCII case-insensitive keyword. The direction S → R refers solely to the ordered history of messages sent from S to R within the selected receiver epoch, excluding the reverse history. PP submits a single fixed-size encrypted trapdoor for this history, after which the
SEEK: Secure and Efficient Encrypted Keyword Search For Privacy-Preserving Messaging Protocols
(a) Login Interface.
(b) Registration Interface.
(c) Chat Interface.
Figure 8: Client interfaces for login, registration, and encrypted messaging.
(a) Successful Search. (b) Unsuccessful Search.
Conference’17, July 2017, Washington, DC, USA
Figure 9: Search Interface: Requires a directed message history of targeted end users, and an ASCII case-insensitive keyword.
(c) Functional validation of the end users’ setup artifacts, as described in Section 4.8.
Figure 10: SEEK application outputs for keyword-presence search and functional validation of end-user setup artifacts. scheme in [10] requires 𝜙 ≥ 2(𝐿max − 1) and generates 𝜂 base fragments along with 𝜂 − 1 boundary fragments, resulting in a total of 2𝜂 − 1 logical fragments. In the padded two-grid instantiation, these fragments form two length-𝜙 grids offset by 𝜙/2. The RLWE refinement [11] uploads only the 𝜂 non-overlapping base ciphertexts. Its matching algorithm constructs 𝜂 − 1 adjacent-pair ciphertexts, and applies packed Hamming-distance matching to each pair. In contrast, under its fixed 8-bit encoding and byte-aligned fragmentation, SEEK fragments each message independently and employs the minimal sufficient overlap 𝐿max − 8. For a message of length 𝐿𝑖 , B Comparison with Prior Encrypted Schemes it stores J𝑖 ciphertext fragments, defined as follows (refer Section This appendix expands upon Section 1.1 by evaluating SEEK in 4.2): J𝑖 = max{1, ⌈(𝐿𝑖 − 𝐿max + 8)/(𝑁 − 𝐿max + 8)⌉} Therefore, for comparison with representative HE-based pattern and keywordmessages with lengths 𝐿1, . . . , 𝐿𝑀 , the total number of fragments is Í𝑀 matching constructions. The fragmentation-based RLWE scheme [11] given by J = 𝑖=1 J𝑖 . is identified as the closest construction-level baseline to SEEK, en☛ Example. Consider a message with 𝐿 = 131072 and 𝐿max = abling direct comparison of fragmentation and operation counts. 512. For [11], our comparison uses 𝜙 = 𝐿max = 512, so 𝜂 = 256: Other constructions, such as CipherMatch [42], constant-depth scheme [11] uploads 256 base ciphertexts and evaluates 255 adjacentBGV [12], BWT-based FHE substring search [40], suffix-array TFHE [54], pair instances. For the padded instantiation of [10], let 𝜙 = 2𝐿 max = and CKKS-based comparison [68], utilize distinct encodings, evalu1024, so 𝜂 = 128 and the scheme materializes 2𝜂 − 1 = 255 logation models, correctness regimes, and output interfaces. Therefore, ical fragments. SEEK uses J = 37 for 𝑁 = 4096 and J = 5 for their suitability for SEEK’s incremental messaging history, role𝑁 = 215 . Relative to [11], this reduces the stored-ciphertext count by separated, presence-only setting is assessed qualitatively rather 6.92× and 51.2×, respectively, and the per-query matching-instance than through direct runtime comparison. count by 6.89× and 51×. Relative to [10], the corresponding logicalFragmentation-based RLWE matching [11] extends the boundaryfragment-footprint reductions are 6.89× and 51×. coverage strategy introduced in [10]. Here, 𝜙 represents the basefragment length, and 𝜂 = ⌈𝐿/𝜙⌉ for a message of length 𝐿. The
online search is conducted with CSP without receiver involvement. As depicted in Fig. 10a and Fig. 10b, the only corpus-dependent output is the bit present ∈ {0, 1}, shown as Keyword present or Keyword not present. No match count, location, or correlation score is revealed, and CSP obtains no result. Finally, Fig. 10c presents an optional diagnostic for rerunning the PP-CSP validation of an active receiver setup.
Conference’17, July 2017, Washington, DC, USA
As specified in [11], forming each adjacent-pair ciphertext uses one ct-pt multiplication by the public monomial and one ciphertext addition. Its normal match algorithm then uses one ct-ct multiplication, two ct-pt polynomial multiplications, and two ciphertext additions/subtractions per pair. The published wildcard match used in our case-insensitive comparison (Section 7.1) has a core of two ct–ct multiplications, two ct–pt multiplications, including the public scalar-by-2 multiplication, and two ciphertext additions/subtractions per pair. Including adjacent-pair construction, the complete evaluated wildcard path therefore performs two ct–ct multiplications, three ct–pt multiplications, and three ciphertext additions/subtractions per pair. This wildcard extension can realize the same ASCII case-insensitive predicate. The distinction of SEEK is therefore not the predicate itself, but its combined construction using one trapdoor ciphertext, one query-dependent ct-ct multiplication per stored fragment, fewer evaluated instances, and presence-only aggregation. Adding a presence-only output layer to [11] can align its leakage with SEEK, but does not reduce its per-query adjacent-pair evaluations. CipherMatch [42] addresses client-server exact binary string matching by packing 𝑏 bits per BFV plaintext coefficient, complementing and replicating the query, encrypting multiple left-shifted query polynomials, and adding each variant to every encrypted database block. A matching 𝑏-bit chunk produces the all-ones value 2𝑏 − 1. Let 𝑆 (𝐿𝑃 ) represent the number of shifted variants and 𝐵 the number of encrypted database blocks, where 𝐵 = ⌈𝐿/(𝑁𝑏)⌉ for a single 𝐿-bit sequence. The matching core uploads 𝑆 (𝐿𝑃 ) query ciphertexts once and reuses them across the 𝐵 blocks, resulting in 𝑆 (𝐿𝑃 )𝐵 ciphertext additions at the server. Since [42] specifies only eight variants for its 8-bit example and does not provide a general formula for 𝑆 (𝐿𝑃 ), a query-length-hiding adaptation must pad to a public bound 𝑆 max . This approach requires Θ(𝑆 max ) query ciphertexts and Θ(𝑆 max 𝐵) server additions. Furthermore, [42] does not address matches that cross separately encrypted database polynomials, and its server natively generates and returns exact match locations. Consequently, a presence-only E2EE adaptation necessitates explicit boundary handling and secure result aggregation. In contrast, SEEK employs a single fixed-size encrypted trapdoor and retrieves all within-fragment offsets using one ct-ct multiplication per fragment, thereby avoiding shifted-query amplification. Constant-depth BGV search [12] encodes one character per SIMD slot and represents an 𝑁𝑇 -character text using an (𝑀, 𝑘)-cover, where 𝑘 is the slot count and 𝑀 < 𝑘 is the server-visible patternlength parameter. It stores 𝑟 = ⌈(𝑁𝑇 − 𝑀 + 1)/(𝑘 − 𝑀 + 1)⌉ length-𝑘 chunks with 𝑀 − 1 characters of overlap, ensuring unique coverage of length-𝑀 candidates. The search invokes its randomized HomEQ circuit 𝑟 𝑀 times. Thus, although its multiplicative depth is independent of 𝑀, its operation count remains pattern-length dependent through repeated multiplications, rotations, and Frobenius maps. An unequal candidate is falsely accepted with probability 𝑡 −𝑑 , giving whole-search correctness of at least (1 − 𝑡 −𝑑 )𝑟 (𝑘 −𝑀+1) . Its wildcard extension adds one ct-ct multiplication per equality evaluation but does not natively implement ASCII case-insensitive matching. The compressed output preserves all occurrence locations for client decryption. Although the server can derive a new cover from existing ciphertexts, this requires additional selections,
Soumyadyuti Ghosh and Michail Maniatakos
rotations, and additions. The construction provides neither a lengthhiding fixed-bound execution nor canonical pruning of duplicate shorter-pattern candidates. In contrast, SEEK fixes fragmentation and public pruning using 𝐿max , privately masks candidates incomplete for the hidden 𝐿𝑃 , and releases only a corpus-wide presence-or-absence bit. The private substring search of [40] evaluates encrypted substring queries over encrypted data using SIMD batching and a BWTbased representation. However, this construction does not specify mechanisms for updating independently encrypted, incrementally arriving messages or for supporting a role-separated, corpus-wide presence-only interface. Supporting SEEK’s setting would therefore require rebuilding or updating the BWT representation, or maintaining separate structures and privately aggregating their outputs. Moreover, TFHE-based search [54] replaces exhaustive alignment testing with homomorphic binary search over an encrypted suffix array. Prior to encryption, the data owner pads the entire text, constructs its suffix array in plaintext, and encrypts both the text and the decomposed suffix-array tables. Considering the padded pattern and text as 𝑃e and 𝑇e, CMux-tree lookups and bootstrapped lexicographic comparisons achieve 𝑂 (|𝑃e| log |𝑇e|) matching complexity while concealing the actual lengths within publicly known padded bounds. Similarly, the construction specifies no dynamic index-update procedure, so incrementally arriving messages would require rebuilding/updating the suffix array, or maintaining separate indexes and aggregating their outputs. Its query contains one LWE ciphertext per encoded pattern character. Under the proposed extension, each character expands into four encoded characters and therefore four query ciphertexts, resulting in increased runtime and memory use. The native output is one encrypted matching position or nothing, rather than role-separated corpus-wide presence bit. SEEK instead directly supports incrementally encrypted histories, native case-insensitive matching, and one fixed-size trapdoor ciphertext. CKKS-based comparison [68] packs an ASCII-encoded target and a replicated, zero-padded pattern into CKKS slots. The evaluator receives the target bound 𝑛, pattern length 𝐿𝑃 , and padding metadata in the clear, then examines the resulting 𝑛 − 𝐿𝑃 + 1 alignments using rotations. Across these alignments, two stages of Chebyshevpolynomial approximation implement absolute-value and nonzero testing, after which a balanced multiplication tree produces an encrypted containment value intended to be zero for presence and one for absence. Because this predicate is approximate, near-ASCII mismatches can produce values undesirably close to zero and increase false-positive risk. Increasing the polynomial degree and multiplicative depth improves the distinguishability but raises runtime and memory. A single invocation is also limited by the available CKKS slots, so longer or incrementally accumulated histories require additional fragmentation, boundary handling, and crossciphertext aggregation. In contrast, SEEK deterministically evaluates overlap-complete fragments, hides 𝐿𝑃 within public 𝐿max , and releases corpus-wide presence through role-separated two-party computation.
C
Preprocessing and Selected Decoding
This section realizes the ideal selected-decoding preprocessing repre pre lation FSD through ΠSD and, using its outputs, realizes FSD from
SEEK: Secure and Efficient Encrypted Keyword Search For Privacy-Preserving Messaging Protocols
Section 4.6 through Π on SD . The former combines local scaled decomposition, semi-honest GMW, and one daBit conversion per selected coefficient, while the latter uses GMW comparisons and daBit-based Boolean-to-arithmetic conversion [25, 29, 35, 66]. Thus, Boolean triples and daBits are the only standard input-independent resources required within selected decoding. The construction follows the multiparty-BFV paradigm [53] and the masked-opening and private-rounding techniques of MPC threshold-FHE decryption [76]. ■ Scaled Quotient and Remainder. For 𝑢 ∈ Z𝑄 ′ , let 𝑢 + = can𝑄 ′ (𝑢) ∈ {0, . . . , 𝑄 ′ −1} denote its canonical integer representative. We define the scaled quotient 𝑘𝑢 and the scaled remainder 𝜌𝑢 as the quotient and remainder obtained by dividing the integer 𝑡𝑢 + by 𝑄 ′ , such that: 𝑡𝑢 + = 𝑘𝑢 𝑄 ′ +𝜌𝑢 , for 0 ≤ 𝜌𝑢 < 𝑄 ′ . Equivalently, 𝑘𝑢 = ⌊𝑡𝑢 + /𝑄 ′ ⌋ and 𝜌𝑢 = 𝑡𝑢 + − 𝑘𝑢 𝑄 ′ . We denote this quotient-remainder pair by ScaleDiv𝑄 ′ ,𝑡 (𝑢) = (𝑘𝑢 , 𝜌𝑢 ). Since 0 ≤ 𝑢 + < 𝑄 ′ , these values satisfy 0 ≤ 𝑘𝑢 < 𝑡 and 0 ≤ 𝜌𝑢 < 𝑄 ′ . For a nonnegative integer 𝜌 < 𝑄 ′ , the notation J𝜌KB denotes componentwise Boolean XOR shares of its fixed-length binary representation. Let ℓ𝑄 = ⌈log2 𝑄 ′ ⌉, so every 𝜌 ∈ {0, . . . , 𝑄 ′ − 1} has an ℓ𝑄 -bit representation. ■ Two-party Offline Preprocessing. For parameters (𝑄 ′, 𝑡), evpre ery 𝜉 ∈ I, FSD receives 𝑟 𝜉PP, 𝑟 𝜉CSP ∈ Z𝑄 ′ , and computes: 𝑟 𝜉 = 𝑟 𝜉PP + 𝑟 𝜉CSP (mod 𝑄 ′ ), (𝑘𝑟,𝜉 , 𝜌𝑟,𝜉 ) = ScaleDiv𝑄 ′ ,𝑡 (𝑟 𝜉 ) PP ←Z and 𝜌 PP ←{0, 1} indeTo share these outputs, it samples 𝑘𝑟,𝜉 𝑡 𝑟,𝜉,𝑖 CSP and 𝜌 CSP as follows and returns pendently for every bit 𝑖, sets 𝑘𝑟,𝜉 𝑟,𝜉,𝑖 only the local shares. CSP PP CSP PP 𝑘𝑟,𝜉 = 𝑘𝑟,𝜉 − 𝑘𝑟,𝜉 (mod 𝑡), 𝜌𝑟,𝜉,𝑖 = 𝜌𝑟,𝜉,𝑖 ⊕ 𝜌𝑟,𝜉,𝑖
All sampling is independent across components, coefficients, and pre executions. Protocol ΠSD realizes this relation as follows. (1) Each party 𝐴 ∈ {PP, CSP} independently samples 𝑟 𝜉𝐴 ← Z𝑄 ′ and locally computes (𝑘𝜉𝐴 , 𝜌 𝜉𝐴 ) = ScaleDiv𝑄 ′ ,𝑡 (𝑟 𝜉𝐴 ). (2) Using GMW on private ℓ𝑄 -bit values 𝜌 𝜉PP and 𝜌 𝜉CSP , the parties compute Boolean shares of 𝑐 𝜉 and 𝜌𝑟,𝜉 , as: 𝑆𝜉 = 𝜌 𝜉PP + 𝜌 𝜉CSP, 𝑐 𝜉 = 1[𝑆𝜉 ≥ 𝑄 ′ ], 𝜌𝑟,𝜉 = 𝑆𝜉 − 𝑐 𝜉 𝑄 ′ (3) Parties convert only J𝑐 𝜉 KB to arithmetic shares ⟨𝑐 𝜉 ⟩𝑡 using 𝐴 = 𝑘 𝐴 + 𝑐 𝐴 (mod 𝑡). one daBit and locally set 𝑘𝑟,𝜉 𝜉 𝜉 𝐴 , J𝜌 K𝐴 ) and neither party reThe resulting local state is (𝑟 𝜉𝐴 , 𝑘𝑟,𝜉 𝑟,𝜉 B
constructs 𝑟 𝜉 , 𝑐 𝜉 , 𝑘𝑟,𝜉 , or 𝜌𝑟,𝜉 .
pre Lemma C.1 (Correctness and Security of Π SD ): Given fresh, non-
reused Boolean triples and daBits and semi-honest-secure GMW and pre pre Boolean-to-arithmetic conversion, Π SD securely realizes FSD against a static semi-honest adversary corrupting at most one of PP and CSP. Proof. For 𝐴 ∈ {PP, CSP}, let (𝑟 𝜉𝐴 ) + = can𝑄 ′ (𝑟 𝜉𝐴 ). Local decomposition gives 𝑡 (𝑟 𝜉𝐴 ) + = 𝑘𝜉𝐴𝑄 ′ + 𝜌 𝜉𝐴 . Let 𝜔 𝜉 = 1[(𝑟 𝜉PP ) + + (𝑟 𝜉CSP ) + ≥ 𝑄 ′ ] and 𝑟 𝜉+ = can𝑄 ′ (𝑟 𝜉 ) Then 𝑟 𝜉+ = (𝑟 𝜉PP ) + + (𝑟 𝜉CSP ) + −𝜔 𝜉 𝑄 ′ . Because 𝑆𝜉 = 𝑐 𝜉 𝑄 ′ +𝜌𝑟,𝜉 , adding the two local decompositions gives: 𝑡𝑟 𝜉+ = (𝑘𝜉PP + 𝑘𝜉CSP + 𝑐 𝜉 − 𝑡𝜔 𝜉 )𝑄 ′ + 𝜌𝑟,𝜉
Conference’17, July 2017, Washington, DC, USA
Uniqueness of Euclidean division therefore implies: 𝑘𝑟,𝜉 = 𝑘𝜉PP + 𝑘𝜉CSP + 𝑐 𝜉 − 𝑡𝜔 𝜉 ≡ 𝑘𝜉PP + 𝑘𝜉CSP + 𝑐 𝜉
(mod 𝑡)
This is exactly the reconstruction of the arithmetic shares, while the GMW output reconstructs the required 𝜌𝑟,𝜉 . All interactions occur within the GMW circuit, and the daBit-based conversion of 𝑐 𝜉 is local. Mask sampling, scaled decomposition, and quotient-share formation are performed locally. The semi-honest simulators, together with sequential and parallel composition, therefore simulate the batched protocol view. Fresh GMW output masks ensure uniformity of the Boolean remainder shares, while the independent daBit mask guarantees uniformity of the arithmetic quotient shares, resulting pre in the distribution specified by FSD . □ ■ Online Masked Opening and Secure Rounding. Using the pre local state produced by Π SD , for each 𝜉 ∈ I and 𝐴 ∈ {PP, CSP}, the parties compute and reconstruct only: 𝑣¯𝜉𝐴 = 𝑝 𝜉𝐴 + 𝑟 𝜉𝐴
(mod 𝑄 ′ )
𝑣¯𝜉 = 𝑣¯𝜉PP + 𝑣¯𝜉CSP = 𝑣 𝜉 + 𝑟 𝜉
(mod 𝑄 ′ )
(11)
Because 𝑟 𝜉 is uniform, hidden, and used once, the opened value 𝑣¯𝜉 is uniform in Z𝑄 ′ for every fixed 𝑣 𝜉 . Since 𝑣¯𝜉 is public, both parties locally compute (𝑘 𝑣¯,𝜉 , 𝜌 𝑣¯,𝜉 ) = ScaleDiv𝑄 ′ ,𝑡 (𝑣¯𝜉 ). Using the GMW and mixed-domain primitives of Section 2.2, they then privately compute Boolean shares of: 𝑏 𝜉 = 1[𝜌 𝑣¯,𝜉 < 𝜌𝑟,𝜉 ], 𝜌 𝑣,𝜉 = (𝜌 𝑣¯,𝜉 − 𝜌𝑟,𝜉 ) mod 𝑄 ′ ℎ𝜉 = 1[𝜌 𝑣,𝜉 ≥ ⌈𝑄 ′ /2⌉] The bit 𝑏 𝜉 is the borrow in modular subtraction, while ℎ𝜉 implements BFV nearest-integer rounding. Because 𝑄 ′ is odd, the rounding comparison has no tie. Using the two daBits, the parties convert the Boolean shares of 𝑏 𝜉 and ℎ𝜉 into arithmetic shares ⟨𝑏 𝜉 ⟩𝑡 and ⟨ℎ𝜉 ⟩𝑡 . They share the public value 𝑘 𝑣¯,𝜉 as (𝑘 𝑣PP , 𝑘 CSP ) = ¯,𝜉 𝑣¯,𝜉 (𝑘 𝑣¯,𝜉 mod 𝑡, 0) and locally compute: 𝐴 𝐴 𝐴 𝐴 𝑚𝐴 𝜉 = 𝑘 𝑣¯,𝜉 − 𝑘𝑟,𝜉 − 𝑏 𝜉 + ℎ 𝜉
(mod 𝑡)
Finally, PP sends the rebased share reb𝜉 = 𝑚𝜉PP + 𝑎𝜉
(12) (mod 𝑡) to
CSP, which outputs 𝑤 𝜉 as follows: 𝑤 𝜉 = 𝑚𝜉CSP + reb𝜉
(mod 𝑡)
(13)
The protocol gives no designated output to PP and processes all indices independently in one batch. Lemma C.2 (Semi-Honest Security of Selected Decoding): In the pre FSD -hybrid model, for odd 𝑄 ′ and semi-honest-secure GMW comparison and Boolean-to-arithmetic conversion, Π on SD securely realizes FSD against a static semi-honest adversary corrupting at most one party. Proof. For each fixed 𝑣 𝜉 , the honest party’s fresh mask share ensures that 𝑣¯𝜉 = 𝑣 𝜉 + 𝑟 𝜉 (mod 𝑄 ′ ) is uniformly distributed in Z𝑄 ′ . Therefore, the simulator samples 𝑣¯𝜉 uniformly and selects the honest opening share. The GMW and Boolean-to-arithmetic views are simulatable under their assumed semi-honest security. If PP is corrupted, FSD produces no output, and its local values and outgoing rebased share are determined by its input and the simulated subprotocol views. If CSP is corrupted, the simulator receives 𝑤 𝜉 , simulates 𝑚𝜉CSP , and sets reb𝜉 = 𝑤 𝜉 −𝑚𝜉CSP (mod 𝑡). This approach
Conference’17, July 2017, Washington, DC, USA
preserves the real conditional distribution and reconstructs the prescribed 𝑤 𝜉 . Independence across indices and parallel composition together yield the claimed batched realization. □ ■ Separate Zero-Test Token Generation. The zero-test-token construction and its share invariant are defined in Section 4.5. Its 𝐾 = |I| OLE instances are generated batch-wise and independently pre of Π SD . Each batch is bound to (receiverID, 𝑒, 𝑄 ′, 𝑡, I, batchID), delivered before its associated online execution, consumed once, and then erased. The input-independent backend also supplies the fresh Boolean triples and two daBits required to compute 𝑏 𝜉 and ℎ𝜉 , together with the arithmetic triples required by the aggregation tree. ■ Cost Analysis. Let ℓ𝑡 = ⌈log2 𝑡⌉ and 𝐾 = |I|. The following pre counts cover ΠSD , Π on SD , and online Beaver aggregation. Generation of the required OLEs, Boolean triples, daBits, and arithmetic triples is accounted for separately in the evaluation. For each retained copre efficient, the ripple-carry implementation of ΠSD uses 2ℓ𝑄 Boolean ′ AND gates for addition, ℓ𝑄 + 1 for public-𝑄 subtraction, and ℓ𝑄 for conditional reduction. It therefore consumes 4ℓ𝑄 + 1 Boolean triples and one daBit. Since each GMW AND opening transmits two logical bits per party and the daBit conversion reveals one masked bit, this stage transmits 𝐾 (8ℓ𝑄 + 3) logical bits per party. Protocol Πon SD consumes another 4ℓ𝑄 +1 Boolean triples and two daBits per coefficient, bringing the selected-decoding totals to 𝐾 (8ℓ𝑄 + 2) Boolean triples and 3𝐾 daBits. Before fixed-width serialization and batch-wise byte padding, the online stage transmits approximately 𝐾 (9ℓ𝑄 + 4 + ℓ𝑡 ) bits from PP and 𝐾 (9ℓ𝑄 + 4) bits from CSP. These totals include one ℓ𝑄 -bit masked-value share from each party, two bits per party for each of the 4ℓ𝑄 + 1 GMW AND gates, two daBit-opening bits pre per party, and one ℓ𝑡 -bit rebased share from PP. Including ΠSD increases the respective totals to 𝐾 (17ℓ𝑄 + 7 + ℓ𝑡 ) and 𝐾 (17ℓ𝑄 + 7) bits before aggregation. For 𝐾 ≥ 1, the Beaver tree protocol transmits an additional 2(𝐾 − 1)ℓ𝑡 bits per party and one final ℓ𝑡 -bit root share from CSP.
D
Correctness Analysis of SEEK
This appendix contains the proofs of Lemma 5.1, 5.2, 5.3, 5.4, 5.5, and Theorem 5.6, as stated in Section 5. Proof of Lemma 5.1. Consider a message of length 𝐿 and a complete byte-aligned query window beginning at 𝑢 ∈ {0, 8, . . . , 𝐿 − 𝐿𝑃 }. By Section 4.2, fragment 𝑗 begins at off 𝑗 = 𝑗 · stride, where stride = 𝑁 − 𝐿max + 8. We define the relevant fragment index as 𝑗 = min{⌊𝑢/stride⌋, J − 1}. This definition selects the latest available fragment whose starting offset does not exceed 𝑢, and therefore off 𝑗 ≤ 𝑢. We first consider the case in which 𝑗 < J − 1. By definition, the window starts before the next fragment offset, so 𝑢 < off 𝑗 + stride. Since both positions are byte aligned, 𝑢 ≤ off 𝑗 + stride − 8, we have: 𝑢 + 𝐿𝑃 − 1 ≤ 𝑢 + 𝐿max − 1 (as 𝐿𝑃 ≤ 𝐿max ) ≤ off 𝑗 + stride − 8 + 𝐿max − 1 = off 𝑗 + 𝑁 − 1 Thus, the window is contained in fragment 𝑗. If 𝑗 = J − 1, validity of the window and 𝑇 𝑗 = 𝐿 − off 𝑗 give: 𝑢 + 𝐿𝑃 − 1 ≤ 𝐿 − 1 = off 𝑗 + 𝑇 𝑗 − 1
Soumyadyuti Ghosh and Michail Maniatakos
So the final fragment also contains it. The overlap is minimal within the class of byte-aligned fragmentations. Suppose instead that the overlap were 𝑂 < 𝐿max −8, and let two consecutive fragments begin at 𝑎 and 𝑏 = 𝑎 + 𝑁 − 𝑂. A length-𝐿max window beginning at 𝑏 − 8 starts before the second fragment, while its final bit satisfies the following: (𝑏 − 8) + (𝐿max − 1) = 𝑎 + 𝑁 − 1 + (𝐿max − 𝑂 − 8) > 𝑎 + 𝑁 − 1 It therefore extends beyond the first fragment and begins before the second, so no fragment contains it. It remains to prove exact-once retention. Let 𝑒 = 𝑢 + 𝐿𝑃 − 1 be the window’s absolute end position. Because 𝑢 and 𝐿𝑃 are multiples of eight, 𝑒 ≡ 7 (mod 8). Hence, 𝑒 satisfies the byte-alignment condition in Eq. 6. Fragment 0 retains all its eligible byte ends, whereas each fragment 𝑗 > 0 retains those with 𝑠 ≥ 𝐿max − 1. Every fragment preceding another is full, and the definition of J ensures that every noninitial final fragment has 𝑇 𝑗 ≥ 𝐿max . Moreover, the first retained absolute end of any fragment 𝑗 > 0 is: off 𝑗 + 𝐿max − 1 = off 𝑗 −1 + stride + 𝐿max − 1 = off 𝑗 −1 + 𝑁 + 7 This is the next byte-aligned end after the preceding fragment’s last eligible end off 𝑗 −1 + 𝑁 − 1. Thus, the retained byte-end sets are disjoint and consecutive and partition {7, 15, . . . , 𝐿 − 1}. Consequently, 𝑒 has a unique representation 𝑒 = off 𝑗 ★ + 𝑠 ★, for ( 𝑗 ★, 𝑠 ★) ∈ I. If 𝑗 ★ = 0, then 𝑠 ★ = 𝑒 ≥ 𝐿𝑃 − 1. Otherwise, 𝑠 ★ ≥ 𝐿max − 1 ≥ 𝐿𝑃 − 1. Therefore, 𝑠 0★ = 𝑠 ★ − (𝐿𝑃 − 1) ≥ 0, off 𝑗 ★ + 𝑠 0★ = 𝑒 − (𝐿𝑃 − 1) = 𝑢 Since 𝑠 ★ < 𝑇 𝑗 ★ , this unique retained coefficient represents precisely the original complete window beginning at 𝑢. □ Proof of Lemma 5.2. Consider a complete candidate window beginning at relative offset 𝑠 0 in fragment 𝑗. The reversed query polynomial places query coefficient 𝑖 at degree 𝐿𝑃 − 𝑖 − 1. Therefore, the products of the aligned message and query coefficients contribute to output coefficient 𝑠 = 𝑠 0 + 𝐿𝑃 − 1. The unreduced product 𝑢 𝑗 (𝑋 )𝑃CI (𝑋 ) has degree at most 𝑁 + 𝐿𝑃 − 2, where 𝑢 𝑗 (𝑋 ) = Í𝑇 𝑗 −1 (𝑗) 𝑖 𝑖=0 (1 − 2𝑏𝑖 )𝑋 . Since 𝑠 ≥ 𝐿𝑃 − 1, we have 𝑠 + 𝑁 ≥ 𝑁 + 𝐿𝑃 − 1, which exceeds the maximum degree of the unreduced product. Thus, no term of degree 𝑠 + 𝑁 exists, and reduction modulo 𝑋 𝑁 + 1 introduces no negacyclic contribution at coefficient 𝑠. Accordingly, its plaintext value is defined as in Eq. 5. For every constrained position with 𝛾𝑖 = 1, the corresponding signed product is +1 when the two bits agree and −1 when they differ. Positions with 𝛾𝑖 = 0 contribute zero. Let ℎ = Ham𝛾 (Win 𝑗,𝑠0 , p). Among the 𝐿fix constrained positions, exactly ℎ differ and 𝐿fix − ℎ agree. It follows that 𝑧 𝑗 [𝑠] = (𝐿fix −ℎ)−ℎ = 𝐿fix −2ℎ, which is Eq. 5. Therefore, 𝑧 𝑗 [𝑠] = 𝐿fix if and only if ℎ = 0. For an alphabetic query byte, 𝛾𝑖 removes only the bit of numerical weight 32. Uppercase and lowercase encodings of the same ASCII letter differ exactly in this bit, while all other bits remain equal. Hence, ℎ = 0 holds precisely when the candidate matches 𝑃 under the ASCII case-insensitive predicate. □ Proof of Lemma 5.3. Each coefficient of the negacyclic correlation polynomial is a signed sum containing at most one contribution from every constrained query position. Each nonzero
SEEK: Secure and Efficient Encrypted Keyword Search For Privacy-Preserving Messaging Protocols
contribution has magnitude one. Therefore, for every retained coefficient, including coefficients affected by negacyclic reduction, we have |𝑧 𝑗 [𝑠] | ≤ 𝐿fix ≤ 𝐿max . Suppose first that 𝑠 ≥ 𝐿𝑃 − 1, so that 𝜉 = ( 𝑗, 𝑠) represents a complete candidate. By Lemma 5.2 and the real target 𝜃 𝜉 = 𝐿fix , the zero-test value reduces to 𝑥 𝜉 = 𝑧 𝑗 [𝑠] −𝐿fix = −2Ham𝛾 (Win 𝑗,𝑠0 , p). Consequently, 𝑥 𝜉 ∈ [−2𝐿fix, 0] ⊆ [−2𝐿max, 0], and 𝑥 𝜉 = 0 if and only if the candidate is a valid case-insensitive match. Now suppose that 𝑠 < 𝐿𝑃 − 1. The protocol assigns the dummy target 𝜃 𝜉 = 𝐿max +1. Combining this target with −𝐿fix ≤ 𝑧 𝑗 [𝑠] ≤ 𝐿fix provides the following observation: 𝑥 𝜉 = 𝑧 𝑗 [𝑠] − (𝐿max + 1) ∈ [−(𝐿fix + 𝐿max + 1), 𝐿fix − 𝐿max − 1]
product as 𝑌 = 1. Assume henceforth that I ≠ ∅, and fix an arbitrary 𝜉 = ( 𝑗, 𝑠) ∈ I. By the additive BFV secret-key sharing relation and the local definitions in Section 4.6: 𝑄′
𝑄′
𝑄′
𝑄′
PP CSP 𝑝 𝜉PP + 𝑝 𝜉CSP = [𝑐 0,𝑗 + 𝑐 1,𝑗 (sk𝑅,𝑒 + sk𝑅,𝑒 )] 𝑠
= [𝑐 0,𝑗 + 𝑐 1,𝑗 sk𝑅,𝑒 ] 𝑠
(mod 𝑄 ′ )
Thus, 𝑣 𝜉 = 𝑝 𝜉PP + 𝑝 𝜉CSP (mod 𝑄 ′ ) is precisely the selected BFV decryption-phase coefficient. By coefficient-wise BFV correctness at 𝑄 ′ : DecCoeff𝑄 ′ ,𝑡 (𝑣 𝜉 ) = 𝑧 𝑗 [𝑠] (mod 𝑡). By Lemma 5.4, the selecteddecoding protocol returns no designated output to PP and returns to CSP: 𝑤 𝜉 = DecCoeff𝑄 ′ ,𝑡 (𝑣 𝜉 ) + 𝑎𝜉 (mod 𝑡). Substituting 𝑎𝜉 = −𝜃 𝜉 − 𝛼 𝜉PP (mod 𝑡) and 𝑥 𝜉 = 𝑧 𝑗 [𝑠] − 𝜃 𝜉 (mod 𝑡) gives: 𝑤 𝜉 = 𝑧 𝑗 [𝑠] − 𝜃 𝜉 − 𝛼 𝜉PP = 𝑥 𝜉 − 𝛼 𝜉PP
⊆ [−(2𝐿max + 1), −1] Thus, an early coefficient is always nonzero as an integer. Because 𝑡 > 4𝐿max + 2 and 𝑡 is odd, the centered representative range of Z𝑡 contains the complete interval [−(2𝐿max + 1), 2𝐿max + 1]. All correlation and zero-test values considered above therefore have their intended centered representatives modulo 𝑡. In particular, modular reduction cannot map any nonzero incomplete or nonmatching candidate to zero. This proves both no-wrap and target-soundness. □ Proof of Lemma 5.4. Let 𝜉 ∈ I, 𝑣 𝜉+ = can𝑄 ′ (𝑣 𝜉 ), 𝑟 𝜉+ = can𝑄 ′ (𝑟 𝜉 ), and 𝑣¯𝜉+ = can𝑄 ′ (𝑣¯𝜉 ). From Eq. 11, there exists 𝜆𝜉 ∈ {0, 1} such that: 𝑣 𝜉+ = 𝑣¯𝜉+ −𝑟 𝜉+ + 𝜆𝜉 𝑄 ′ By the definitions of scaled quotient, remainder and the borrow bit, we have: 𝑡 𝑣¯𝜉+ = 𝑘 𝑣¯,𝜉 𝑄 ′ + 𝜌 𝑣¯,𝜉 , 𝑡𝑟 𝜉+ = 𝑘𝑟,𝜉 𝑄 ′ + 𝜌𝑟,𝜉 𝜌 𝑣,𝜉 = 𝜌 𝑣¯,𝜉 − 𝜌𝑟,𝜉 + 𝑏 𝜉 𝑄 ′ = 𝜌 𝑣¯,𝜉 − 𝜌𝑟,𝜉 mod 𝑄 ′
Conference’17, July 2017, Washington, DC, USA
(mod 𝑡)
Therefore, the assignments 𝑥 𝜉PP = 𝛼 𝜉PP, 𝑥 𝜉CSP = 𝑤 𝜉 satisfy: 𝑥 𝜉PP + 𝑥 𝜉CSP = 𝑥 𝜉 (mod 𝑡). For token conversion, Section 4.7 defines 𝑦𝜉PP = 𝜇𝜉PP , and 𝑦𝜉CSP = 𝜇𝜉CSP + 𝛽𝜉 (𝑥 𝜉CSP − 𝛼 𝜉CSP ) (mod 𝑡). Using the token invariant from Section 4.5: 𝜇𝜉PP + 𝜇𝜉CSP = 𝛽𝜉 (𝛼 𝜉PP + 𝛼 𝜉CSP ) (mod 𝑡), we obtain the following: 𝑦𝜉PP + 𝑦𝜉CSP = 𝜇𝜉PP + 𝜇𝜉CSP + 𝛽𝜉 (𝑥 𝜉CSP − 𝛼 𝜉CSP ) = 𝛽𝜉 (𝛼 𝜉PP + 𝑥 𝜉CSP ) = 𝛽𝜉 𝑥 𝜉
(mod 𝑡)
Thus, the parties hold additive shares of 𝑦𝜉 = 𝛽𝜉 𝑥 𝜉 (mod 𝑡). Applying correctness of Beaver multiplication [9] inductively at every internal node of the balanced product tree yields Eq. 9: Because 𝑡 is prime, Z𝑡 is a field and because every 𝛽𝜉 ∈ Z𝑡∗ , every multiplier is nonzero. Therefore, Ö 𝑌 = 0 ⇐⇒ 𝑥 𝜉 = 0 ⇐⇒ ∃ 𝜉 ∈ I : 𝑥 𝜉 = 0 𝜉∈I
Therefore 0 ≤ 𝜌 𝑣,𝜉 < 𝑄 ′ . Substituting the two Euclidean decompositions gives the following: 𝑡𝑣 𝜉+ = 𝑘 𝑣¯,𝜉 − 𝑘𝑟,𝜉 − 𝑏 𝜉 + 𝜆𝜉 𝑡 𝑄 ′ + 𝜌 𝑣,𝜉 Since 0 ≤ 𝜌 𝑣,𝜉 < 𝑄 ′ , the definition of ℎ𝜉 shows exactly whether nearest-integer rounding adds one to the quotient. Moreover, replacing the canonical representative 𝑣 𝜉+ by the centered representative ctr𝑄 ′ (𝑣 𝜉 ) changes the scaled value by an integer multiple of 𝑡, which vanishes modulo 𝑡. Therefore, applying the definition of DecCoeff𝑄 ′ ,𝑡 (Section 2.1) yields: DecCoeff𝑄 ′ ,𝑡 (𝑣 𝜉 ) = 𝑘 𝑣¯,𝜉 − 𝑘𝑟,𝜉 − 𝑏 𝜉 + ℎ𝜉
(mod 𝑡)
(14)
By functional correctness of the preprocessing shares, GMW comparisons, and daBit conversions, Eq. 12 therefore satisfies: 𝑚𝜉PP + 𝑚𝜉CSP = DecCoeff𝑄 ′ ,𝑡 (𝑣 𝜉 )
(mod 𝑡)
Combining this equality with Eq. 13 gives 𝑤 𝜉 as: 𝑤 𝜉 = 𝑚𝜉CSP + reb𝜉 = 𝑚𝜉CSP + 𝑚𝜉PP + 𝑎𝜉 = DecCoeff𝑄 ′ ,𝑡 (𝑣 𝜉 ) + 𝑎𝜉
(mod 𝑡)
This is exactly the output prescribed by FSD .
□
Proof of Lemma 5.5. If I = ∅, all per-index claims are vacuous, the Beaver tree is skipped, and the protocol defines the empty
This proves the claim.
□
Proof of Theorem 5.6. We prove the two directions of Eq. 10, e.g., Soundness and Completeness separately. Soundness. Assume present = 1. By the output rule in Section 4.7, this implies 𝑌 = 0. Lemma 5.5 then guarantees the existence of a retained coefficient 𝜉 = ( 𝑗, 𝑠) ∈ I satisfying 𝑥 𝜉 = 0. Lemma 5.3 excludes every early dummy coefficient and every nonmatching complete candidate. Hence, 𝜉 represents a complete candidate whose correlation value is 𝑧 𝑗 [𝑠] = 𝐿fix . Let the absolute starting position of this candidate be 𝑢 = off 𝑗 + 𝑠 − (𝐿𝑃 − 1). Because 𝜉 ∈ I, its absolute end position satisfies off 𝑗 + 𝑠 ≡ 7 (mod 8). Since 𝐿𝑃 − 1 ≡ 7 (mod 8), it follows that 𝑢 ≡ 0 (mod 8). Moreover, completeness of the candidate gives 0 ≤ 𝑢 ≤ 𝐿 − 𝐿𝑃 . By Lemma 5.2, the corresponding message window has restricted Hamming distance zero from p. Therefore, the righthand side of Eq. 10 holds. Completeness. Assume the right-hand side of Eq. 10 holds. Thus, some retained message contains a byte-aligned window beginning at a valid offset 𝑢 whose restricted Hamming distance from p is zero. Lemma 5.1 guarantees that this window is contained in a fragment and that its absolute end position is represented by exactly one retained coefficient 𝜉 ∈ I. Lemma 5.2 then gives 𝑧 𝑗 [𝑠] = 𝐿fix . Because 𝜉 is a complete candidate, its target is 𝜃 𝜉 = 𝐿fix , and hence 𝑥 𝜉 = 0. By Lemma 5.5, this zero is preserved through token conversion
Conference’17, July 2017, Washington, DC, USA
and the aggregate satisfies 𝑌 = 0. The output rule therefore gives present = 1. The soundness and completeness implications establish Eq. 10. If I = ∅, the protocol defines 𝑌 = 1 and hence present = 0. Moreover, by Lemma 5.1, no complete byte-aligned candidate exists in this case. □
E
Detailed Security Proof for SEEK
This appendix proves Lemmas 6.2 and 6.3 and Theorem 6.4 in its stated input-independent preprocessing-hybrid model. Ideal batched OLE and ideal generators provide fresh, independent, nonpre reused Boolean triples, daBits, and arithmetic triples, while Π SD remains a concrete part of SEEK using the ideal Boolean-triple and daBit interfaces. The privacy proof begins after all the functional validation (Section 4.8) tests are passed. The public setup transcript and the corrupted party’s local setup state, including its additive secret-key share, are auxiliary inputs to the simulation. The receiver R does not participate in the online protocol, and the adversary statically corrupts at most one of PP and CSP. Proof of Lemma 6.2. The result follows from Lemma C.1, Lemma 5.4, and Lemma C.2 by sequential composition. □ ■ Simulation Notation. Let 𝐴 ∈ {PP, CSP}. Lemma 6.2 guaran𝐴 for Π pre followed by Π on . It uses the public tees a simulator SSD SD SD information, the corrupted party’s local input and ideal-resource state, and the prescribed FSD output. This output is only (𝑤 𝜉 )𝜉 ∈ I for CSP. The ideal OLE and correlated-resource generators produce no backend transcript. Similarly, semi-honest Beaver-multiplication 𝐴 security guarantees a simulator SProd for the product-tree transcript using the corrupted party’s leaf shares, ideal arithmetic-triple state, and prescribed output [9]. The prescribed output is only 𝑌 for PP. Proof of Lemma 6.3. For each 𝜉 ∈ I, token generation in the ideal batched-OLE hybrid samples 𝛼 𝜉PP, 𝛼 𝜉CSP, 𝜇𝜉CSP ← − Z𝑡 and 𝛽𝜉 ← − Z𝑡∗ independently, and sets 𝜇𝜉PP = 𝛽𝜉 (𝛼 𝜉PP + 𝛼 𝜉CSP ) − 𝜇𝜉CSP (mod 𝑡). Because 𝜇𝜉CSP is uniform, thus for fixed 𝑎, 𝑚 ∈ Z𝑡 and 𝑏 ∈ Z𝑡∗ , we have: Pr[𝜇𝜉PP = 𝑚 | 𝛼 𝜉PP = 𝑎, 𝛽𝜉 = 𝑏] ∑︁ 1 = Pr[𝛼 𝜉CSP = 𝑢, 𝜇𝜉CSP = 𝑏 (𝑎 + 𝑢) − 𝑚] = 𝑡 𝑢 ∈Z 𝑡
Hence the pair (𝛼 𝜉PP, 𝜇𝜉PP ) observed by PP is independent of 𝛽𝜉 . Since tokens are independent across retained indices and selected decoding does not reveal or use a CSP-side token component, con0 leaves (𝛽 ) ∗ 𝐾 ditioning on 𝑉PP 𝜉 𝜉 ∈ I uniformly distributed over (Z𝑡 ) . By Eq. 9, if present = 1, correctness gives 𝑥 𝜉 = 0 for some 𝜉, so 𝑌 = 0. If present = 0 and 𝐾 ≥ 1, every 𝑥 𝜉 is nonzero. Because Z𝑡 is a field and the product of independent uniform elements of Z𝑡∗ is uniform in Z𝑡∗ , the aggregate 𝑌 is uniform in Z𝑡∗ . For 𝐾 = 0, the protocol defines the empty product as 𝑌 = 1. The simulator therefore samples 1, 𝑌e ← 0, 𝑈 (Z∗ ) 𝑡
𝐾 =0 𝐾 ≥ 1 and present = 1 𝐾 ≥ 1 and present = 0
Soumyadyuti Ghosh and Michail Maniatakos
For 𝐾 = 0, the simulator sets 𝑌e = 1 and emits the empty aggregation PP transcript, exactly as the real protocol. Otherwise, it invokes SProd PP e on the local leaf shares (𝜇𝜉 )𝜉 ∈ I and prescribed output 𝑌 . This 0 , 𝐾, and the final simulates the complete aggregation view from 𝑉PP present bit. □ Proof of Theorem 6.4. Let 𝐴 ∈ {PP, CSP} be the corrupted party. The simulator S𝐴 receives its ideal input, local setup state, prescribed leakage, and ideal output. For each query, the ideal preprocessing interfaces supply its OLE-token and local preprocess𝐴 and S 𝐴 ing shares, while SSD simulate the composed selectedProd decoding and aggregation views, respectively. The simulator maintains one persistent dummy corpus for the epoch. Whenever the public leakage identifies a stored fragment 𝑗, it samples one fresh encryption: e 𝑐 𝑀,𝑗 ← − Encpk𝑅,𝑒 (0) and applies the public preprocess±1 . If 𝐴 = CSP, it also sets e ing to obtain e 𝑐 𝑀,𝑗 𝑐𝑃 ← − Encpk𝑅,𝑒 (0) and if 𝐴 = PP, it generates the trapdoor 𝑐 𝑃 from the corrupted party’s query. Considering 𝑐 ★ 𝑐 𝑃 , 𝑐 𝑃 } as the resulting trapdoor, it then 𝑃 ∈ {e computes the correlation, relinearization and modulus switching operations, exactly as in the real protocol: 𝑄′
±1 e 𝑐 corr,𝑗 ← ModSwitch𝑄→𝑄 ′ (Relinrlk𝑅,𝑒 (Evalmult (e 𝑐 𝑀,𝑗 , 𝑐★ 𝑃 )))
By the setup condition in Theorem 6.4, the corrupted party’s additive secret-key share is distributed as prescribed in Section 4.1 and is independent of the complete BFV secret key and published keys. BFV IND-CPA security therefore permits a polynomial-length hybrid replacing the hidden corpus ciphertexts, and for a corrupted CSP the hidden trapdoor, by these dummy encryptions. Public homomorphic evaluation, modulus switching, and local share computation are efficient post-processing and preserve indistinguishability. If 𝐾 = 0, the simulator emits empty selected-decoding, zerotesting, and aggregation transcripts. It sets 𝑌 = 1 for a corrupted PP, and present = 0 follows from the ideal functionality. The following two cases therefore assume 𝐾 ≥ 1. ■ Case 1: Corrupted CSP. For each 𝜉 = ( 𝑗, 𝑠) ∈ I, the simulator computes the corrupted party’s local contribution from the evaluated dummy ciphertext as: ′
′
𝑄 𝑄 CSP 𝑝e𝜉CSP = [e 𝑐 0,𝑗 + e 𝑐 1,𝑗 (sk𝑅,𝑒 mod 𝑄 ′ )] 𝑠
(mod 𝑄 ′ )
By the ideal batched-OLE token distribution, 𝛼 𝜉PP remains hidden and uniform in Z𝑡 . Hence 𝑤 𝜉 = 𝑥 𝜉 − 𝛼 𝜉PP is uniform in Z𝑡 for every fixed 𝑥 𝜉 , and (𝑤 𝜉 )𝜉 ∈ I ≡ 𝑈 (Z𝑡𝐾 ). The simulator samples w e ← Z𝑡𝐾 CSP with (e and invokes SSD 𝑝 𝜉CSP )𝜉 ∈ I as the corrupted CSP’s local selected-decoding input and w e as its prescribed output. Using its local token state from the ideal batched-OLE hybrid, it then computes 𝑦e𝜉CSP as: 𝑦e𝜉CSP = 𝜇𝜉CSP + 𝛽𝜉 (e 𝑤 𝜉 − 𝛼 𝜉CSP )
(mod 𝑡)
CSP on (e It invokes SProd 𝑦𝜉CSP )𝜉 ∈ I with no prescribed output. Thus the simulated CSP view uses neither the plaintext corpus nor the keyword, its length, the search result, or any match value. ■ Case 2: Corrupted PP. The simulator uses the corrupted party’s genuine query to construct the private targets and the genuine trapdoor, evaluates it against the persistent dummy corpus, and
SEEK: Secure and Efficient Encrypted Keyword Search For Privacy-Preserving Messaging Protocols
computes: 𝑄′ PP 𝑝e𝜉PP = [e 𝑐 1,𝑗 (sk𝑅,𝑒 mod 𝑄 ′ )] 𝑠
′
profile, with a globally observed minimum of 8 bits. These results provide implementation-level evidence for the tested stress cases.
(mod 𝑄 )
It sets 𝑎𝜉 = −𝜃 𝜉 − 𝛼 𝜉PP (mod 𝑡) as in the real protocol and inPP with ((e vokes SSD 𝑝 𝜉PP, 𝑎𝜉 ))𝜉 ∈ I as the corrupted PP’s local selecteddecoding inputs and PP receives no designated output. The local zero-test leaf share is 𝑦𝜉PP = 𝜇𝜉PP . Using 𝐾 and the ideal bit present, PP the simulator samples 𝑌e according to Lemma 6.3 and invokes SProd PP e on (𝜇 )𝜉 ∈ I with prescribed output 𝑌 . The simulated party recon𝜉
structs 𝑌e and outputs 1[𝑌e = 0] = present. Here, no individual hit, count, location, or match identity is selected or revealed by the simulator. To justify the construction formally, let 𝐻 0𝐴 denote the real execution in the stated preprocessing-hybrid model. In 𝐻 1𝐴 , the execution pre 𝐴 of Π SD followed by Π on SD is replaced with FSD and its simulator SSD , as justified by Lemma 6.2. For a corrupted CSP, the prescribed output may be sampled as w e ← Z𝑡𝐾 , since 𝑤 𝜉 = 𝑥 𝜉 − 𝛼 𝜉PP is exactly uniform under the ideal batched-OLE distribution and PP receives no designated output. In 𝐻 2𝐴 , the Beaver-tree transcript is replaced 𝐴 , using Lemma 6.3 to sample the output delivered to a corby SProd rupted PP. In 𝐻 3𝐴 , every BFV ciphertext whose plaintext is hidden from 𝐴 is replaced by the corresponding dummy encryption, recompute the public evaluations and local contributions, and regenerate the simulated views using the same prescribed outputs. Thus, View𝐴real ≡ 𝐻 0𝐴 ≈𝑐 𝐻 1𝐴 ≈𝑐 𝐻 2𝐴 ≈𝑐 𝐻 3𝐴 ≡ Viewideal S𝐴 The transitions follow from Lemma 6.2 and the uniform-mask argument, Beaver-product security together with Lemma 6.3, and BFV IND-CPA security under efficient post-processing. For a polynomially bounded, sequentially adaptive sequence of authorized queries over the same fixed retained corpus within same epoch, the simulator retains the same dummy corpus and simulates each query as above using fresh, disjoint, one-time preprocessing. For a corrupted CSP, hidden trapdoors are replaced as they are received. Sequential composition applies because every query consumes fresh independent one-time preprocessing. The only cumulative output is the ideal presence-bit sequence and its logical implications, exactly as stated in Theorem 6.4. □
F
Conference’17, July 2017, Washington, DC, USA
BFV Evaluation Parameters
Table 2 shows the BFV parameter sets used in our evaluation. For each of the 20 (𝑁 , 𝐿max ) profiles, we ran three independent trials, testing a total of 540 adversarial correlation instances. The test cases include both pattern-length extremes 𝐿𝑃 ∈ {8, 𝐿max }, dense all +1 and all −1 inputs, maximum Hamming distance, earliest complete coefficients, fragment boundaries, and cases with the minimum final fragment. Each instance tests signed-fragment preprocessing, ct–ct multiplication and relinearization, every intermediate level of sequential modulus switching, and the direct 𝑄 → 𝑄 ′ path. In 6615 stage-level observations, all 𝑁 coefficients of every decrypted polynomial matched an independent negacyclic-polynomial oracle, every selected coefficient decoded as expected, and every observed noise budget stayed positive. Table 3 gives the minimum remaining BFV invariant noise budget at 𝑄 ′ . Both the sequential and direct modulus-switching paths yielded the same minimum for every
Table 2: BFV parameters used in the evaluation.
𝑁
𝑡
4096 1,032,193 8192 1,032,193 16384 786,433 32768 786,433
𝑄
{𝑞 ℓ }
𝑄′
(bits)
(bits)
(bits)
72 174 389 825
36 + 36 43 + 43 + 44 + 44 3×48 + 5×49 15×55
36 43 48 55
Table 3: Minimum observed remaining BFV invariant noise budget at 𝑄 ′ (bits). 𝑁 \𝐿max
128
256
512
1024
2048
4096 8192 16384 32768
9 15 20 26
9 15 20 26
8 15 20 26
8 15 20 26
9 15 20 26