{"id":"5663ff5f-d7c3-4378-b9a0-eff48897e4b4","arxiv_id":"1908.02784","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The authors propose MRSM SAN, a multi-owner encrypted search scheme that pads pseudo-keywords via a GAN, builds a maximum-likelihood search tree, and clusters indexes into a forest for dynamic updates.","lead":"The paper designs a searchable encryption system that lets multiple owners share encrypted cloud data while users can still search it, using a GAN-style tuner to balance search accuracy and privacy, a probability-sorted index tree, and a distributed index forest. A generalist might read it to see how machine learning is being stitched onto encrypted search, though the key claims rest on tuned parameters rather than verified guarantees.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"MLSB-Tree's O(log N) efficiency claim is asserted, not derived; it depends on an unanalyzed match between random-training queries and actual queries, so the paper's central low-overhead search claim is unsupported.","rationale":"The reader's weakest_assumption identifies exactly the right point: the scheme's efficiency claim rests on an unproven probabilistic-learning heuristic for MLSB-Tree construction. The paper itself concedes in the Fig. 5b caption that the convergence to O(log N) is asymptotic in the number of random searches, but no formal analysis or reproducible experiment establishes this. The security components are largely inherited from ASPE, so the novel and load-bearing part is the claimed near-logarithmic search complexity. Since the reader already assigned CONDITIONAL, this stress-test does not change the verdict; it sharpens the condition by specifying a concrete computational test that would settle whether the O(log N) claim actually holds.","tokens_in":10605,"tokens_out":4920,"duration_ms":59054,"concrete_test":"Implement Algorithms 4 and 6 on the IEEE Xplore corpus used in the paper. For R = 10, 100, 1000, and 10,000 random training queries, build the MLSB-Tree, then evaluate on a disjoint set of 1000 held-out user queries drawn from the same distribution and also from a different distribution. Measure median and 95th percentile of GDFS visited nodes and wall-clock time for N = 500, 2000, 8000, and 20000 documents. If median visited nodes does not stay within a small constant factor of log2 N as N grows, or if held-out or distribution-shifted queries degrade toward O(N), the O(log N) convergence claim is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing concern is the unsupported O(log N) efficiency claim. In Algorithm 4, the MLSB-Tree is built by computing relevance scores of index vectors against randomly generated query vectors, sorting the leaves by those scores, and then constructing a balanced tree bottom-up with the greedy method from [16]. The paper's own Fig. 5b caption states that 'the closer the number of random searches is to infinity, the higher the search efficiency of obtained index tree, this makes the computational complexity of search can converge to O(log N).' That is an assertion, not a derivation. Search (Algorithm 6) prunes nodes using the score of the actual query against a moving top-k threshold, yet the tree structure is fixed after training on random queries. Pruning behavior for a real query therefore depends on whether real queries come from the same distribution as the random training queries; no such distributional assumption is stated, and no argument shows that GDFS visits only O(log N) nodes when the tree is grouped by a different query distribution. If this probabilistic-learning heuristic fails on ordinary user queries, the headline claim of near-logarithmic search complexity and low search overhead collapses, even though the ASPE encryption remains correct. The experiments measure wall-clock time on one dataset and do not report visited-node counts or a formal guarantee.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes MRSM SAN, a multi-owner searchable symmetric encryption (SSE) scheme that combines three mechanisms: (i) a searching adversarial network (SAN) to determine the pseudo-keyword padding distribution, claimed to reach an optimal trade-off between query precision and privacy; (ii) a maximum likelihood search balanced tree (MLSB-Tree) built by sorting index vectors according to relevance scores computed with randomly generated queries, claimed to bring search complexity close to O(log N); and (iii) a balanced index forest (BIF) that partitions the index into clusters to support dynamic updates and distributed search. The encryption core uses the standard asymmetric scalar-product-preserving encryption (ASPE) technique for secure inner-product computation. The abstract claims query precision above 95%, adequate privacy protection, and low computational, communication, and storage overhead. The paper provides algorithms, security arguments delegated to prior work, and experiments on a 20,000-document IEEE Xplore dataset.","tokens_in":10936,"tokens_out":3015,"duration_ms":36970,"significance":"If the efficiency and precision claims were rigorously supported, the paper would be a genuinely useful contribution to multi-owner SSE, addressing a practical gap: simultaneous precision, privacy, and dynamic maintenance. The ASPE-based encrypted inner-product algebra appears standard and is a solid foundation. The paper also makes an honest attempt to test the scheme empirically and reports concrete numbers. However, the central claims are currently supported by heuristic assertions and evaluation practices that are circular in places, rather than by formal analysis or robust experiments. The O(log N) search complexity is not derived, the 'optimal game equilibrium' is computed by tuning three sigma parameters on the evaluation data, and the security analysis is largely copied from prior works without adaptation to the multi-owner, multi-partition setting. These issues are load-bearing because they underpin the abstract's headline assertions. The paper's contribution is therefore interesting but not yet substantiated to the standard required by a journal publication.","major_comments":[{"comment":"The central efficiency claim that MLSB-Tree search complexity converges to O(log N) is asserted, not derived. Algorithm 4 builds the tree by computing relevance scores of index vectors against randomly generated query vectors, sorting the leaves, and then constructing a balanced tree bottom-up with the greedy method from [16]. The paper's own Fig. 5b caption states that 'the closer the number of random searches is to infinity, the higher the search efficiency of obtained index tree, this makes the computational complexity of search can converge to O(log N)' — that is a heuristic belief, not a proof. The GDFS algorithm (Algorithm 6) prunes using the score of the actual query against a moving threshold, but the tree structure is fixed by training on random queries; no distributional assumption links the training queries to real user queries, and no argument shows that GDFS visits only O(log N) nodes for queries outside the training distribution. The experiments report wall-clock time for 1000 random queries but do not report visited-node counts or any worst-case/node-count analysis. This concern is load-bearing because the 'low overhead on computation' claim and the 'near O(log N)' statement in the abstract rest on this unproven heuristic. Please provide either a formal analysis of the tree construction and search pruning, or substantially weaken the efficiency claim to match what is actually demonstrated.","section":"§2.3, Algorithm 4; Fig. 5b caption; §4"},{"comment":"The claimed 'optimal game equilibrium' and the 95% precision result are obtained by fitting the parameters sigma1, sigma2, sigma3 on the evaluation data. The paper defines an objective function f(x,y) = (1/95)x^2 + (1/80)y^2, where 95% and 80% are chosen as benchmarks, and then searches over sigma to maximize f on the same dataset for which the precision numbers are reported. This makes the precision claim circular and does not establish that the scheme will maintain 'query precision above 95%' on unseen data. No held-out validation set, cross-validation, or confidence intervals are reported. Since the abstract's 'query precision above 95%' is a central selling point, the evaluation protocol must be corrected: report precision on a test set not used for tuning, or provide a parametric analysis showing the claimed precision is not simply an artifact of selecting the best sigma on the test data.","section":"§3, 'Optimal Pseudo-keyword Padding' (Fig. 3) and §2.4"},{"comment":"The security analysis is delegated to prior works rather than established for this scheme. The text states that 'ASPE approach [15] is widely used ... and its security has been proven' and then refers to [16] and [1] for keyword privacy and unlinkability. However, the proposed scheme introduces several new elements not covered by those prior proofs: the SAN-based pseudo-keyword distribution, the segmentation of the dictionary into s sub-dictionaries, the MLSB-Tree ordering that leaks ranking scores to the server, and the multi-owner KDO weight model. No formal security definition (e.g., indistinguishability against chosen-keyword attacks, or a known-background model simulation) is given for this combined construction, and the one algebraic argument in the section (the central-limit-theorem approximation for sum_{epsilon_i}) is a heuristic about score distributions, not a proof of privacy. Because 'adequate privacy protection' is a headline claim, this gap needs to be addressed, either by providing a rigorous security proof for the full MRSM SAN scheme or by clearly stating the exact security guarantees inherited from which prior work under which assumptions.","section":"§2.4 'Security Analysis' and §2.2 'Setup'"},{"comment":"The experimental evaluation of search efficiency is conducted under the same random-query distribution used to build the MLSB-Tree. The paper reports that the tree is trained on randomly generated query vectors, and the experiments also use 1000 random queries. This is circular with respect to the claim that the learned ordering matches real query traffic. The paper does not measure the sensitivity of the reported 21.72% and 17.69% improvements to the choice of query distribution, nor does it report the number of nodes visited by GDFS, which would be the directly relevant quantity for assessing whether the O(log N) behavior actually occurs. Please add experiments with realistic query distributions distinct from the training distribution, report node-visit counts and their variance, and provide a theoretical or empirical bound on search cost as a function of N and k.","section":"§3, 'Search Efficiency of MLSB-Tree' and Fig. 4/5"}],"minor_comments":[{"comment":"The abstract states 'maintains query precision above 95%' as a categorical claim, but the experiments show 93% precision at sigma3=0.12 (Fig. 3a). The claim should be qualified to reflect the parameter-dependent behavior.","section":"Abstract and §4"},{"comment":"The line reads 'return Encrypted Encrypted BIF ~F = {...}'; the word 'Encrypted' is duplicated. Please fix the typo.","section":"Algorithm 5, line 12"},{"comment":"The text contains several language issues, e.g., 'only realized the linean search efficiency' (should be 'linear'), 'builded' (should be 'built'), and 'the closer the number of random searches is to infinity' (awkward phrasing). A thorough language edit is recommended.","section":"§1, Related Work"},{"comment":"The notation is dense and partly undefined: for example, the symbol 'sum epsilon_i' is not clearly tied to the actual padding vectors, and the role of alpha_i in the range [0,1] is not explained in the algebra. Please clarify the notation and make the derivation self-contained.","section":"§2.4, 'Keyword privacy'"},{"comment":"The caption for Fig. 3(b) is a run-on sentence that also contains an explanatory note about sigma in the caption; this material should be moved to the main text or presented more clearly.","section":"§3, Fig. 3 caption"}],"recommendation":"major_revision","confidential_remarks":"The manuscript cites several works by the same research group (refs 17, 18, 19, and the preliminary version [2]) as the basis for security claims and the SAN design. The authors should be asked to disclose the exact relationship between [2] and the current submission, and to clarify which parts of the security argument are original versus inherited. There is also a fit concern: the paper is positioned as a cryptographic scheme, but the efficiency argument is largely heuristic and the security analysis is deferred; the journal may prefer to see either a formal security proof or a clearly empirical systems contribution. These concerns are not grounds for rejection by themselves, but they should be addressed in the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a concrete engineering extension of ASPE-based multi-owner SSE, but the two headline numbers—near-log search and above-95% precision—are not backed by the evidence in the paper. The O(log N) claim is a heuristic stated in the Fig. 5b caption, and the precision result comes from choosing sigma values to hit a benchmark defined by the same 95/80 numbers.\n\nWhat is actually new: the combination of adversarial-network-style pseudo-keyword padding, the MLSB-Tree built by sorting index vectors on random-query relevance scores, and the balanced index forest for updates. These are real algorithmic constructions, and the experiments against EDMRS and MKRS-MO show credible wall-clock improvements on a 20,000-paper dataset. That part is useful and should be reproducible.\n\nThe soft spots are where the claims outrun the evidence. First, the central efficiency claim is an assertion: the paper says search complexity \"can converge to O(log N)\" as the number of random training queries goes to infinity, but gives no distributional link between random training queries and real queries, no analysis of the greedy bottom-up tree construction, and no visited-node counts in the experiments. If pruning fails for ordinary queries, the low-overhead claim collapses, even though the ASPE math remains correct. Second, the precision/privacy equilibrium is obtained by scanning sigma over [0.01, 0.2] and picking values that maximize f(x,y)=x^2/95 + y^2/80. Since f is defined in terms of the 95% and 80% benchmarks, this is fitting, not a genuine adversarial equilibrium. The GAN description is decorative; no actual training is shown. Third, the security analysis leans almost entirely on prior ASPE proofs and the group's own earlier padding papers, so the incremental security contribution is not independently established.\n\nWho this is for: readers in applied SSE who want a concrete attempt at multi-owner dynamics and sparse high-dimensional indexes. It is not foundational, but the algorithms are specific enough that a serious referee can engage with them. I would send it out, but my expectation is that the central efficiency claim needs either a formal argument or much stronger empirical evidence—visited-node counts, error bars, and a proper train/test split for the sigma tuning—before publication.\n\nRecommendation: accept for peer review, but brace the authors for a request to substantially rework the validation of the headline claims.","headline":"Plausible engineering combination, but the O(log N) search claim is asserted rather than derived and the 95% precision is tuned, so the headline results need serious revision before they hold up.","tokens_in":11409,"tokens_out":2383,"would_cite":false,"duration_ms":26319,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P20","68P25","94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims a multi-owner encrypted-search scheme that keeps query precision above 95 percent, brings search cost close to $\\mathcal{O}(\\log N)$ with a probability-learned balanced tree, and cuts dynamic update overhead by splitting…","keywords":["searchable symmetric encryption","multi-owner model","multi-keyword ranked search","adversarial networks","pseudo-keyword padding","maximum likelihood search tree","balanced index forest","encrypted cloud search"],"falsifier":"Build synthetic document sets of increasing size, construct MLSB-Tree with an increasing number of random query samples, and measure the average number of tree nodes visited per real query; if the node count does not approach a logarithmic curve and instead grows linearly with $N$, the central search-efficiency claim is false. A second check is to rerun the precision/privacy experiments on an independent dataset and see whether the reported 95 percent precision and roughly 80 percent rank privacy at the chosen $\\sigma$ values reproduce.","tokens_in":10428,"feed_emoji":"🔐","tokens_out":4096,"duration_ms":51080,"temperature":0.7,"pith_summary":"The paper is trying to show that searchable symmetric encryption can serve multiple data owners without sacrificing precision, privacy, speed, or updatability at once. Its scheme, MRSM SAN, pads encrypted index vectors with pseudo-keywords chosen by an adversarial learning game so that a curious cloud server cannot easily tell real from padded data, while query precision stays above 95 percent. It then builds a maximum likelihood search balanced tree by sorting index vectors according to scores from many random queries, pushing search complexity close to $\\mathcal{O}(\\log N)$. A balanced index forest partitions the tree so that adding or updating a document only touches one small index tree rather than the whole collection. If the efficiency claims hold, the scheme would be a practical step toward deploying dynamic encrypted search in real multi-owner cloud storage.","feed_headline":"Encrypted search gets near-log N speed and stays precise","feed_subtitle":"A multi-owner scheme uses adversarial padding and a probability-learned tree to keep precision above 95 percent while cutting update costs.","key_machinery":"The load-bearing objects are three. First, the searching adversarial network: a searcher network generates search results from random noise while a discriminator network tries to tell accurate search results from padded ones, and the minimax equilibrium of this game sets the probability distribution for pseudo-keyword padding, balancing precision against privacy. Second, the maximum likelihood search balanced tree (MLSB-Tree): index vectors are sorted by scores computed against random query vectors, then assembled into a balanced tree by a bottom-up greedy strategy, with the intent that frequently searched vectors sit near the top and search converges to $\\mathcal{O}(\\log N)$ as the number of random queries grows. Third, the balanced index forest (BIF): fast clustering partitions all indexes into $s$ groups, each with its own sub-dictionary and balanced tree, so dynamic maintenance, communication, and storage overhead scale with one partition rather than the whole index set.","core_discovery":"The central claim is that the three longstanding goals of multi-owner SSE, precise ranked search, strong query and keyword privacy, and cheap dynamic updates, can be achieved simultaneously by coupling three mechanisms. Adversarial learning selects the noise distribution for pseudo-keyword padding, reaching a measured equilibrium (for example, query precision 98/97/93 percent with rank-privacy 78/79/84 percent at specific noise variances) where padded and unpadded searches are hard to distinguish. A maximum likelihood search balanced tree, built by sorting index vectors by their relevance scores against randomly generated query vectors and then constructing a balanced tree bottom-up with a greedy method, is claimed to make search approach binary-search efficiency, with measured speedups of 21.72 percent over EDMRS and 17.69 percent over MKRS-MO. The balanced index forest then reduces the dynamic update cost from about $2\\mathcal{O}(\\log N)$ to $(2/s)\\mathcal{O}(\\log(N/s))$ for $s$ index partitions, and the paper projects over 100-fold search efficiency gains on very large, sparse datasets.","pith_inferences":["The $\\mathcal{O}(\\log N)$ convergence claim is distribution-dependent: the tree is trained on random queries, so if real users' queries are highly skewed or shift over time, the learned leaf ordering may no longer match search popularity and the practical speedup could degrade toward linear search.","The adversarial padding equilibrium is found empirically; a natural extension would be to prove a formal indistinguishability bound for the padded index distribution, or to apply the same minimax training to choose other parameters such as the number of pseudo-keywords per partition.","The balanced index forest's advantage is amplified by data sparsity, since sparse vectors make similarity scores near zero and make a single global tree inefficient; in dense, small datasets the clustering overhead might outweigh the search gain.","Because the scheme relies on ASPE-style inner-product encryption, its security inherits the same limitations of that approach; a concrete follow-up could test whether the learned padding distribution leaks information through the distribution of non-zero similarity scores."],"forward_implications":["Query precision above 95 percent and rank privacy around 80 percent can coexist under a tuned pseudo-keyword padding distribution, addressing the precision-privacy trade-off that earlier ranked-search schemes left open.","Search on encrypted indexes can approach $\\mathcal{O}(\\log N)$ complexity even when the index tree is built once and reused, rather than requiring a fully ordered structure that is expensive to maintain.","Dynamic updates cost only $(2/s)\\mathcal{O}(\\log(N/s))$ instead of $2\\mathcal{O}(\\log N)$, making frequent insertions and deletions feasible in a multi-owner setting.","On large, sparse datasets with many owners, the projected efficiency ratio between a single tree and an $s$-partition forest grows to about $\\eta = s\\log N/(\\log N - \\log s)$, exceeding 100 when $N=20000$ and $s=80$.","The same adversarial-learning equilibrium can be tuned by adjusting noise variance $\\sigma$ per index partition, giving system operators a concrete knob for trading query precision against privacy strength."],"supporting_citations":[{"why":"Defines the MRSE baseline, the known-background threat model, and the precision/privacy evaluation metrics this paper adopts.","marker":"[1]"},{"why":"Supplies the generative adversarial minimax framework that the searching adversarial networks are modeled on.","marker":"[4]"},{"why":"Provides the multi-owner ranked-search baseline and the KDO weight model used to generate weighted indexes.","marker":"[6]"},{"why":"Gives the standard balanced-tree search complexity argument that underlies the claimed $\\mathcal{O}(\\log N)$ target.","marker":"[7]"},{"why":"Provides the ASPE encryption technique used to encrypt index vectors and trapdoors while preserving inner-product scores.","marker":"[15]"},{"why":"Contributes the EDMRS balanced-tree construction, greedy depth-first search, and dynamic maintenance baseline that MLSB-Tree and BIF extend.","marker":"[16]"},{"why":"Motivates pseudo-keyword padding as a defense against access-pattern leakage and supports the security rationale for optimal padding.","marker":"[19]"}],"fun_headline_variants":["Adversarial networks make encrypted multi-owner search fast and precise","Multi-owner encrypted search: 95% precision, near-log speed","Adversarial padding balances privacy and precision in encrypted search","Near-log N encrypted search stays above 95% precise"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The efficiency claim rests on an unproved heuristic: sorting index vectors by relevance scores from many random queries and then building a balanced tree bottom-up with a greedy method makes search complexity converge to $\\mathcal{O}(\\log N)$, and this convergence is not formally analyzed.","fun_headline_variants_meta":{"raw":{"variants":["Adversarial networks make encrypted multi-owner search fast and precise","Multi-owner encrypted search: 95% precision, near-log speed","Adversarial padding balances privacy and precision in encrypted search","Near-log N encrypted search stays above 95% precise"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000808,"raw_usage":{"total_tokens":3541,"prompt_tokens":936,"completion_tokens":2605,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":552,"completion_tokens_details":{"reasoning_tokens":2533}},"tokens_in":552,"tokens_out":2605,"duration_ms":19496,"temperature":1.0,"reasoning_tokens":2533,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:34:01.509793+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build synthetic document sets of increasing size, construct MLSB-Tree with an increasing number of random query samples, and measure the average number of tree nodes visited per real query; if the node count does not approach a logarithmic curve and instead grows linearly with $N$, the central search-efficiency claim is false. A second check is to rerun the precision/privacy experiments on an independent dataset and see whether the reported 95 percent precision and roughly 80 percent rank privacy at the chosen $\\sigma$ values reproduce.","supporting_citations":[{"cited_title":"IEEE TPDS 25(1), 222–233 (2014) 12 Kai Chen et al","cited_arxiv_id":null,"evidence_quote":"Defines the MRSE baseline, the known-background threat model, and the precision/privacy evaluation metrics this paper adopts."},{"cited_title":"Addison- Wesley (1998)","cited_arxiv_id":null,"evidence_quote":"Gives the standard balanced-tree search complexity argument that underlies the claimed $\\mathcal{O}(\\log N)$ target."},{"cited_title":"IEEE TPDS 27(2), 340–352 (2016)","cited_arxiv_id":null,"evidence_quote":"Contributes the EDMRS balanced-tree construction, greedy depth-first search, and dynamic maintenance baseline that MLSB-Tree and BIF extend."},{"cited_title":"In: IEEE INFOCOM 2019","cited_arxiv_id":null,"evidence_quote":"Motivates pseudo-keyword padding as a defense against access-pattern leakage and supports the security rationale for optimal padding."}],"review_version":1}