Source-linked AI summary
SEEK: Secure and Efficient Encrypted Keyword Search For Privacy-Preserving Messaging Protocols
Soumyadyuti Ghosh, Michail Maniatakos
TL;DR
E2EE protects sensitive communications, but authorized investigations may require targeted searches of retained messages. SEEK combines homomorphic matching with 2PC to search encrypted messages, achieving 100% observed accuracy and up to 5.47× correlation speedup over the evaluated wildcard baseline. Its prototype and protocol limit the disclosed search result to a presence bit, while relying on stated assumptions and external controls.
Problem
The paper asks how authorized investigations can search retained E2EE messages without requiring bulk plaintext disclosure or weakening message privacy.
Source: §1 · pp. 1–2Method
SEEK combines minimal-sufficient-overlap fragmentation and packed BFV correlation with 2PC-based selected decoding, zero testing, and secure aggregation.
Source: §1.1 · p. 3, §4.2 · p. 5, §8 · p. 12Results
100% observed accuracy, 39.82% lower mean fragment overhead, and up to 5.47× maximum correlation speedup over the wildcard baseline were reported.
Source: §8 · p. 12Takeaways & Limitations
The protocol releases only a corpus-wide presence bit to PP, and a web/mobile prototype demonstrates SEEK in E2EE messaging applications.
Source: §1.1 · p. 3SEEK does not provide authentication, integrity, replay protection, ratcheting, or post-compromise security, which require a complementary layer.
Source: §3 · p. 5
Abstract
from arXiv · showhide
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.47x 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.
1 Introduction
SEEK addresses the tension between protecting E2EE messages and enabling narrowly scoped, authorized searches without bulk plaintext disclosure. It combines encrypted matching with private result processing, against prior approaches that can expose query or match information.
1 Introduction
- E2EE protects messages from cloud providers, but authorized retrospective searches may be valuable while plaintext access and broad endpoint scanning threaten privacy and civil liberties.The paper frames this as a searchability paradox for retained messages.Source: §1 · p. 1
- Authorized cryptographic queries offer a narrower alternative to bulk disclosure, while avoiding dependence on investigated users voluntarily reporting harmful messages.The design aims to constrain access through the technical interface rather than plaintext disclosure or endpoint cooperation.Source: §1 · p. 2
1.1 Related Work
- Prior encrypted-search approaches can expose match locations or access patterns, require specialized representations, or incur costly matching operations [10, 13, 14, 22, 26].The related-work discussion also identifies query-length leakage and richer outputs in several HE constructions [42].Source: §1.1 · pp. 2–3
- SEEK reduces fragment count by up to two orders of magnitude relative to prior designs through byte-aligned fragmentation with minimal sufficient overlap and full-width homomorphic packing.The stated reductions lower CSP-side ciphertext footprint, encryption, and communication overheads.Source: §1.1 · p. 3
- SEEK uses one fixed-size encrypted trapdoor and one query-dependent homomorphic multiplication per fragment for case-insensitive matching, then reveals only a presence bit to PP.The protocol uses selected decoding, zero testing, and secure aggregation; neither party learns match counts, locations, or correlation scores.Source: §1.1 · p. 3
- 100% observed accuracy across 10,000 encrypted searches, with up to a 5.47× correlation-computation speedup over the evaluated wildcard baseline configuration of.The searches used the SAMSum corpus scaled to an estimated five-year history [34].Source: §1.1 · p. 3
2 Preliminaries
The preliminaries establish the BFV homomorphic-encryption operations used for encrypted matching and the 2PC primitives used for private computation. Together, these provide the cryptographic building blocks for SEEK’s protocol.
2.1 BFV Homomorphic Encryption
- BFV encrypts messages over parameterized plaintext and ciphertext rings and supports homomorphic addition and multiplication, including ciphertext–plaintext operations.The scheme uses public and secret keys plus a relinearization key; decoding recovers encoded coefficients when the stated correctness condition holds.Source: §2.1 · pp. 3–4
2.2 Secure Two-Party Computation (2PC)
- 2PC represents values as additive shares and multiplies them with Beaver triples, opening only masked differences in the online phase.The parties’ shares combine to the product, while the opened differences reveal no information about the inputs in the semi-honest model.Source: §2.2 · p. 4
- The 2PC preliminaries also define OLE for correlated zero-test-token generation and Boolean sharing with GMW gates and daBits for conversion to arithmetic shares.The described triples and daBits are fresh, independent, and consumed once.Source: §2.2 · p. 4
3 Protocol Architecture and Threat Model
SEEK assigns message encryption and storage to the endpoints and CSP, while PP and CSP jointly conduct online searches. Its privacy claims depend on stated trust assumptions and external controls.
3 Protocol Architecture and Threat Model
- The sender encrypts and uploads each message once, while the CSP retains ciphertext fragments as the searchable representation.Randomized validation checks address possible inconsistencies in receiver-supplied key artifacts and shares.Source: §3 · p. 4
- PP submits an encrypted keyword trapdoor and learns only the corpus-wide presence-or-absence bit, not match counts, locations, or correlation scores.CSP computes encrypted correlations and receives no search result.Source: §3 · p. 4
- SEEK models CSP and PP as static, noncolluding, semi-honest adversaries; CSP learns no additional information about message plaintext, query, query length, or result.The endpoints remain outside the online search process, and the receiver is assumed not to disclose its key or collude with either party.Source: §3 · p. 4
- Message authentication, integrity, replay protection, ratcheting, and post-compromise security require a complementary messaging security layer.Legal approval, query admission, audit and transparency records, and per-authorization budgets are external controls, not protocol functions.Source: §3 · p. 5
4 SEEK: Privacy-Preserving Encrypted Messaging and Keyword Search Protocol
SEEK combines homomorphic encryption and 2PC to search encrypted, overlapping message fragments while revealing only a presence bit to the pattern provider. Its pipeline covers setup and fragmentation, case-insensitive correlation, private decoding and aggregation, and functional setup validation.
4.1 Cryptographic Setup Phase
- Within each key-lifecycle epoch, SEEK shares the receiver’s secret key between PP and CSP for joint decryption operations.The receiver retains the full key for message decryption; the additive shares are used in the selected-decoding functionality.Source: §4.1 · p. 5
4.2 Fragmentation and Encryption
- The sender encodes messages as bits and encrypts zero-padded fragments with the minimal sufficient overlap of Lmax − 8 bits.This overlap guarantees containment of byte-aligned keyword windows up to the public maximum pattern length.Source: §4.2 · p. 5
4.3 Case-Insensitive Trapdoor Generation
- SEEK masks only ASCII letters’ case bit and uses one fixed-size signed-correlation trapdoor ciphertext for case-insensitive matching.Its trapdoor uses one query-dependent homomorphic multiplication per fragment.Source: §4.3 · pp. 5–6
4.4 Encrypted Correlation Computation
- Reversed-query correlation scores identify matching complete windows, while public pruning removes duplicate positions caused by fragment overlap.A score of Lfix indicates a case-insensitive match; the retained coefficient set is selected using public geometry, without revealing the query or result.Source: §4.4 · pp. 6–7
4.5 Private Zero-Target Encoding and Offline Zero-Test Tokens
- PP assigns private targets to retained coefficients, using a dummy target for incomplete windows so CSP cannot infer query length or complete-window positions.Fresh, input-independent one-sided zero-test tokens are allocated per retained candidate.Source: §4.5 · p. 7
4.6 Privacy-Preserving Selected Decoding
- Selected decoding converts retained ciphertext coefficients into additive shares without either party reconstructing an individual coefficient or zero-test input.The selected-decoding protocols jointly realize the stated functionality under the paper’s preprocessing assumptions.Source: §4.6 · p. 7
4.7 One-Sided Zero Testing and Aggregation
- The parties blind each target difference and securely aggregate the values, revealing only the presence bit to PP and no result to CSP.The aggregation hides match counts, scores, and locations.Source: §4.7 · p. 8
4.8 Functional Setup Validation
- Functional setup validation checks frozen BFV artifacts and secret-key shares, then binds uploads and searches to the accepted setup with a certificate.A failed check rejects the setup and keeps search disabled; modifications require fresh validation and certification.Source: §4.8 · p. 8
5 Correctness Analysis of SEEK
SEEK’s correctness analysis establishes that, under its stated encoding and BFV parameter conditions, byte-aligned case-insensitive search returns the correct presence result. Component lemmas support the end-to-end claim.
5 Correctness Analysis of SEEK
- With overlap Lmax − 8, every complete byte-aligned keyword window is covered by a fragment, and pruning retains each absolute window end exactly once.Correlation equals Lfix exactly for a complete case-insensitive match.Source: §5 · p. 8
- The no-wraparound target construction prevents incomplete or nonmatching windows from becoming zero modulo t when t > 4Lmax + 2.Selected decoding and aggregate correctness lemmas establish that the final zero test corresponds to whether any retained candidate matches.Source: §5 · pp. 8–9
- SEEK produces neither false positives nor false negatives for byte-aligned case-insensitive keyword search under the theorem’s stated conditions.The theorem assumes the specified BFV parameters and correct decoding at Q′.Source: §5 · p. 9
6 Security Analysis of SEEK
SEEK’s security analysis specifies the leakage available to each party and proves semi-honest privacy under its stated cryptographic and preprocessing assumptions. PP learns the presence-bit sequence, while CSP receives no search result.
6 Security Analysis of SEEK
- The prescribed leakage includes public parameters and corpus geometry; CSP learns neither the query, its length, nor the result, while PP learns only its input and the final presence bit.The ideal functionality releases no search result to CSP or the receiver.Source: §6 · p. 9
- Selected decoding reveals neither party’s private contribution, and the aggregate transcript is simulatable from PP’s prior view, candidate count, and presence bit.The selected-decoding privacy result assumes the semi-honest-secure 2PC and preprocessing primitives specified in the paper.Source: §6 · p. 9
- Under the stated assumptions, SEEK securely realizes its ideal functionality against a static semi-honest adversary corrupting at most one party.The guarantee covers polynomially bounded, potentially adaptive authorized queries when each execution uses fresh independent one-time preprocessing.Source: §6 · p. 9
7 Experimental Evaluation
SEEK is evaluated through protocol microbenchmarks, repeated-query analysis, and web/mobile prototypes. Results show accurate case-insensitive search, reduced costs relative to, and practical presence-only search at the evaluated scales.
7.1 Protocol Microbenchmarks and Scalability
- SEEK achieves 100% precision, recall, F1 score, and accuracy across 10,000 encrypted searches, while exact matching reaches 80% accuracy because of case-variation false negatives.The exact-match protocol has 60% recall and 75% F1; its wildcard extension supports equivalent case-insensitive matching with a two-ciphertext trapdoor, versus one for SEEK.Source: §7.1 · p. 10
- Across all 20 parameter pairs, SEEK reduces mean fragment count from 288.7K to 173.7K and upload/storage from 713.64 to 429.44 GiB, a 39.82% reduction.For the five-year workload, overlap-induced repetition averages 368.3 bytes for SEEK and 1.10 MiB for [11], a 3,129× reduction.Source: §7.1 · p. 10
- For long documents at Lmax = 512, SEEK uses 2–120 fragments versus 12–839 baseline blocks across the reported N and document-length settings.At Lmax = 128, the reported fragment reductions range from 30.45–167.5× for 1K-word documents and 31.05–239.5× for 10K-word documents.Source: §7.1 · p. 10
- SEEK is faster in all 200 correlation observations, with median and maximum speedups of 1.99× and 5.47× over.SEEK uses one ciphertext-ciphertext multiplication per fragment; the baseline wildcard core uses two ciphertext-ciphertext and two ciphertext-plaintext multiplications, plus additions or subtractions.Source: §7.1 · p. 10
- For five-year histories, computation and communication increase by 57.64–57.65× and 57.10–57.62× from one month, closely tracking message growth.Increasing N from 4096 to 32768 raises median five-year computation 100.6× and communication 7.18×; at fixed N, varying Lmax changes computation by at most 1.05× and leaves communication unchanged.Source: §7.1 · pp. 10–11
- At the practical (N, Lmax) = (4096, 512) setting, fresh per-query selected-decoding preprocessing takes 0.817 s and uses 530.340 MiB for a five-year history.A separate one-time BFV setup is amortized over the key-lifecycle period.Source: §7.1 · p. 11
7.2 Repeated-Query Attack Analysis
- A 5K-query sweep covering at least 80% of word occurrences in the evaluated histories would require an estimated 346.5 million compute-years across three billion five-year histories.The analysis treats these evaluator-side oracle measurements as an overestimate of actual disclosure because each query reveals only a history-wide presence bit.Source: §7.2 · p. 12
7.3 End-to-End Prototype Evaluation
- 1.92 s per search is the query-time cryptographic pipeline cost in the prototype, with input-independent preprocessing off the query path.The prototype uses a one-week history of approximately 5K words represented by 91 fragments.Source: §7.3 · p. 12
8 Conclusion
SEEK combines minimum-sufficient byte-aligned fragmentation and packed BFV correlation with 2PC-based decoding, zero testing, and aggregation. Its evaluated results show accurate, efficient presence-only search over retained encrypted messages.
8 Conclusion
- SEEK achieves 100% observed accuracy, reduces mean fragment overhead by 39.82%, and reaches a maximum correlation speedup of 5.47× over the wildcard baseline.The protocol releases only a corpus-wide presence bit to PP, and the paper reports correctness and post-setup privacy against a static semi-honest adversary under stated assumptions.Source: §8 · p. 12
A Prototype SEEK Application Details
The prototype integrates encrypted messaging and authorized search across web and cross-platform mobile clients. Messages are encrypted locally, while the search interface selects a directed history and returns only a presence bit.
Prototype Implementation
- The application separates messaging clients, PP, and CSP into four logical components, with cryptographic operations supported by a modified node-seal backend and native SEAL helpers.The mobile client invokes the embedded SEAL WebAssembly stack inside a hidden WebView; PP and CSP are Python services communicating through authenticated REST APIs.Source: A Prototype SEEK Application Details · p. 14
Interfaces and Workflow
- Outgoing messages are independently fragmented and encrypted locally with the receiver’s certified BFV public key, then decrypted and reassembled only by the receiver.Searches do not span message boundaries.Source: A Prototype SEEK Application Details · p. 14
- PP selects a sender, receiver, and ASCII case-insensitive keyword for the ordered S → R history, excluding reverse-direction messages.PP submits a single fixed-size encrypted trapdoor, and CSP conducts the online search without receiver involvement.Source: A Prototype SEEK Application Details · pp. 14–15
- The only corpus-dependent output is a present-or-absent bit reconstructed at PP; match counts, locations, and correlation scores remain unrevealed, and CSP receives no result.Figure 10 also shows an optional diagnostic for rerunning validation of an active receiver setup.Source: A Prototype SEEK Application Details · p. 15, Figure 10 · p. 15
B Comparison with Prior Encrypted Schemes
The comparison identifies as the closest construction-level baseline and contrasts SEEK with other encrypted matching designs whose encodings, update support, or outputs differ. SEEK combines a fixed-size trapdoor, fewer matching operations, and presence-only aggregation.
Fragmentation-Based RLWE Matching
- For a 131072-bit message at Lmax = 512, SEEK uses 37 fragments at N = 4096 and 5 at N = 2^15, versus 256 base ciphertexts for.The corresponding stored-ciphertext reductions are 6.92× and 51.2×, respectively.Source: B Comparison with Prior Encrypted… · p. 15
- SEEK uses one trapdoor ciphertext and one query-dependent ciphertext-ciphertext multiplication per stored fragment, whereas ’s evaluated wildcard path uses two ciphertext-ciphertext multiplications per adjacent pair.Adding presence-only output to can align its leakage with SEEK but does not reduce its adjacent-pair evaluations.Source: B Comparison with Prior Encrypted… · p. 16
CipherMatch
- CipherMatch [42] uses Θ(Smax) query ciphertexts and Θ(SmaxB) server additions in a query-length-hiding adaptation, and does not address matches across separately encrypted database polynomials.Its native output is exact match locations, so a presence-only E2EE adaptation needs boundary handling and secure result aggregation.Source: B Comparison with Prior Encrypted… · p. 16
Constant-depth BGV Search
- Constant-depth BGV search still has pattern-length-dependent operations through repeated multiplications, rotations, and Frobenius maps, and its compressed output preserves occurrence locations.SEEK instead uses public Lmax for fragmentation and pruning, privately masks incomplete candidates, and releases only a corpus-wide presence-or-absence bit.Source: B Comparison with Prior Encrypted… · p. 16
BWT and Suffix-Array Search
- The BWT-based and suffix-array TFHE approaches do not specify dynamic index-update procedures for incrementally arriving messages, while SEEK directly supports incrementally encrypted histories.The suffix-array method’s native output is one encrypted matching position or nothing, rather than a role-separated corpus-wide presence bit.Source: B Comparison with Prior Encrypted… · p. 16
CKKS-Based Comparison
- CKKS-based comparison uses polynomial approximations whose degree and depth affect runtime and memory, and one invocation is limited by available CKKS slots.SEEK hides pattern length within public Lmax and uses role-separated 2PC for corpus-wide presence.Source: B Comparison with Prior Encrypted… · p. 16
C Preprocessing and Selected Decoding
Selected decoding and secure aggregation let the parties process chosen BFV coefficients while limiting the designated output to the result prescribed by the protocol. The construction uses Boolean triples and daBits for selected decoding and is secure against a static semi-honest adversary corrupting at most one party.
Security and outputs
- Selected decoding securely realizes its functionality against a static semi-honest adversary corrupting at most one party.The protocol gives PP no designated output; CSP receives the per-index output, and all indices are processed in one batch.Source: C Preprocessing and Selected Decoding · p. 17
Preprocessing resources
- The preprocessing relation uses Boolean triples and daBits, while secure aggregation uses arithmetic triples.The resources are generated independently of online execution and accounted for separately in the evaluation.Source: C Preprocessing and Selected Decoding · pp. 17–18
Cost analysis
- Selected decoding consumes K(8ℓ_Q + 2) Boolean triples and 3K daBits across K retained coefficients.Before fixed-width serialization and batch-wise byte padding, the combined preprocessing and online stages transmit K(17ℓ_Q + 7 + ℓ_t) bits from PP and K(17ℓ_Q + 7) bits from CSP.Source: C Preprocessing and Selected Decoding · p. 18
D Correctness Analysis of SEEK
The correctness analysis establishes that SEEK retains each complete byte-aligned candidate window exactly once and that its correlation and zero-testing rules identify precisely the valid case-insensitive matches. The resulting aggregate reports presence exactly when a retained message contains such a match.
Fragmentation correctness
- Minimal sufficient overlap ensures every complete byte-aligned window is contained in a fragment; the retained byte-end sets are disjoint and partition all byte-aligned message ends.The analysis also shows that smaller overlap can leave a maximum-length window contained in no fragment.Source: D Correctness Analysis of SEEK · p. 18
Correlation correctness
- For a complete candidate, the correlation score equals L_fix − 2 times its restricted Hamming distance, so it equals L_fix exactly for an ASCII case-insensitive match.For alphabetic query bytes, the predicate ignores only the bit of numerical weight 32.Source: D Correctness Analysis of SEEK · p. 18
Zero-test correctness
- The zero-test value is zero exactly for a valid case-insensitive match, while incomplete candidates receive dummy targets and remain nonzero after modular reduction.The condition t > 4L_max + 2 ensures the centered representative range covers the relevant values without wraparound.Source: D Correctness Analysis of SEEK · p. 19
Decoding and aggregation
- Each retained coefficient decodes to the corresponding correlation value modulo t, and the selected-decoding and token-conversion steps preserve the zero used by aggregation.The proof relies on coefficient-wise BFV decoding correctness and the selected-decoding output relation.Source: D Correctness Analysis of SEEK · p. 19
End-to-end correctness
- The aggregate output is present exactly when some retained message contains a valid byte-aligned window matching the query under the restricted Hamming-distance predicate.If no complete candidate exists, the aggregate is defined as 1 and the output is present = 0.Source: D Correctness Analysis of SEEK · pp. 19–20
E Detailed Security Proof for SEEK
The proof establishes SEEK’s privacy in the stated preprocessing-hybrid model, including polynomially bounded sequentially adaptive authorized queries over a fixed retained corpus within one epoch. Simulations expose only prescribed outputs, with fresh disjoint one-time preprocessing for each query.
E Detailed Security Proof for SEEK
- The proof assumes input-independent preprocessing and static corruption of at most one of PP and CSP; the receiver does not participate online.The appendix proves the stated lemmas and theorem in this preprocessing-hybrid model.Source: E Detailed Security Proof for SEEK · p. 20
- When a keyword is present, correctness makes the aggregate Y zero; when absent and K≥1, Y is uniform among nonzero field elements.For K=0, the protocol defines the empty product as Y=1.Source: E Detailed Security Proof for SEEK · p. 20
- The simulated views reveal no individual hit, count, location, or match identity, and each party receives only its prescribed ideal output.The prescribed outputs are CSP’s selected-decoding values and PP’s aggregate output.Source: E Detailed Security Proof for SEEK · pp. 20–21
- Security follows through sequential hybrids using selected-decoding and aggregation simulators, uniform-mask arguments, Beaver-product security, and BFV IND-CPA.The ciphertext replacements rely on BFV IND-CPA security under efficient public evaluation and post-processing.Source: E Detailed Security Proof for SEEK · pp. 20–21
- Polynomially bounded sequentially adaptive authorized queries remain simulatable over one fixed retained corpus within an epoch when each query uses fresh disjoint one-time preprocessing.The only cumulative output is the ideal presence-bit sequence and its logical implications.Source: E Detailed Security Proof for SEEK · p. 21
F BFV Evaluation Parameters
The BFV evaluation tested 20 parameter profiles across adversarial correlation cases, and all observed decrypted coefficients and selected decodings matched expectations while noise budgets remained positive.
F BFV Evaluation Parameters
- 540 adversarial correlation instances were tested across 20 (N, Lmax) profiles, with three independent trials per profile.Cases included pattern-length extremes, dense inputs, maximum Hamming distance, fragment boundaries, and minimum final fragments.Source: F BFV Evaluation Parameters · p. 21, Table 2 · p. 21
- Across 6615 stage-level observations, every decrypted polynomial coefficient matched an independent oracle, selected coefficients decoded as expected, and every noise budget stayed positive.The tests covered signed-fragment preprocessing, multiplication and relinearization, and sequential and direct modulus switching.Source: F BFV Evaluation Parameters · p. 21
- 8 bits was the globally observed minimum remaining BFV invariant noise budget at Q′, and both modulus-switching paths yielded the same minimum for every profile.Table 3 reports the minimum observed remaining budget.Source: F BFV Evaluation Parameters · p. 21, Table 3 · p. 21