{"id":"7b916488-66e4-4758-a990-df6a1fe19efe","arxiv_id":"2412.09259","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"A functional encryption scheme for set intersection with non-monotonic access control is constructed and analyzed, but the write-up has critical specification and proof gaps.","lead":"This paper proposes a multi-client functional encryption scheme for private set intersection that adds non-monotonic access control policies, aimed at federated learning. It intends to let an aggregator compute set intersections between clients only when their attribute sets match the aggregator's policy.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The security proof silently sets a_k=b_k and Setup never publishes r; as written, the scheme is not instantiable and Theorem 1 is unproven.","rationale":"The reader's weakest_assumption identified both the missing r in Setup and the unjustified a_k = b_k identification in the proof. My independent reading confirms these are the most load-bearing issues. Without r, the Enc algorithm cannot be executed from the published parameters, so the scheme is not implementable as written. More importantly, the security proof's simulator never accounts for the independent a_k exponents: the proof programs H(Tag*) as g^a and constructs all client-side components and functional keys using only b_k, which forces a_k = b_k. Since Setup deliberately separates a_k and b_k, this is not a cosmetic simplification; it changes the distribution of client keys and functional keys, and no reduction is supplied that handles the original distribution. Consequently, Theorem 1 does not establish the claimed P-IND security of the scheme in Figures 2-5. These concerns are not stylistic or consensus-based; they are internal inconsistencies in the submitted construction and proof. The verdict REJECT is therefore appropriate, and my stress-test does not change it.","tokens_in":23450,"tokens_out":8953,"duration_ms":93436,"concrete_test":"Replay the Phase-1 and Challenge steps of Theorem 1 with a_k and b_k sampled independently as in Figure 2, and attempt to generate a valid sk_f,3 = ghat^{r * b_w / (a_w + a_v)} and challenge component ct1_{nu*,delta} = H(...)^{a_{nu*}} using only the tuple D from Definition 2. If the only successful derivation requires a_k = b_k or otherwise changes the key distribution, the proof of the described scheme fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is a formally proven, instantiable MCFE-SI-NAS scheme. Two load-bearing gaps undermine this claim. First, in Figure 2, Setup outputs pp without any exponent r, yet Enc (Figure 4) and KeyGen (Figure 3) both use r through terms like u0^r, h1^r, and ghat^r. The sentence 'Let ghat^r, u0^r, h1^r be public' appears only inside the KeyGen figure, after encryption already requires r; clients cannot run Enc with the published pp. Second, the security proof does not simulate the actual key distribution. Setup samples independent a_k, b_k for each client, and real functional keys are sk_f,1 = ghat^{a_w * dot_r}, sk_f,2 = ghat^{a_v * dot_r}, sk_f,3 = ghat^{r * b_w / (a_w + a_v)}. The simulator, however, chooses only b_1,...,b_N and constructs sk_f,1 = ghat^{b_w * c_{w,v}}, sk_f,2 = ghat^{b_v * c_{w,v}}, sk_f,3 = (ghat^{1/(b_w + b_v)})^{tilde_b_w * r}. Matching these expressions forces a_w = b_w, a_v = b_v, and tilde_b_w = b_w. No argument shows that setting a_k = b_k is without loss of generality or that the two key distributions are equivalent. Therefore Theorem 1's reduction proves security for a different scheme than the one in Figures 2-5, so the paper's central claim that the described scheme is formally secure is not supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a multi-client functional encryption scheme for set intersection with non-monotonic access structures (MCFE-SI-NAS), intended for federated learning. The scheme is described by four algorithms (Setup, KeyGen, Enc, Dec) in Figures 2-5, with correctness equations in Section 3 and a claimed security proof (Theorem 1) in the random oracle model under assumptions from Lee [20] and a variant of q-DBDHE. The authors also report an implementation and efficiency measurements. The central claim is that this is the first MCFE-SI scheme supporting non-monotonic (AND, OR, NOT, threshold) policies, with formal security proof.","tokens_in":23724,"tokens_out":4279,"duration_ms":42430,"significance":"If the construction were correct and instantiable, the contribution would be meaningful: it extends MCFE for set intersection to support non-monotonic access structures, which existing MCFE-SI schemes do not. The use of labels to resist mix-and-match attacks and the independent, non-interactive client encryption are also attractive properties for federated learning. However, the manuscript as written contains load-bearing gaps that prevent the central claim from being accepted: the Setup algorithm does not produce a global exponent r that both Enc and KeyGen rely on, and the security proof simulates a different key distribution than the real scheme. These are not merely presentation issues; they undermine both the instantiation and the proof of Theorem 1. The paper also provides an implementation, but no code or reproducible benchmarks are included, so the efficiency results cannot be independently verified.","major_comments":[{"comment":"The Setup algorithm in Figure 2 outputs pp = (G, Ghat, GT, e, p, g, ghat, e(g,ghat)^tilde_alpha, Hvec, Uvec, H, N) and msk = (tilde_alpha, a_1..a_N, b_1..b_N), but it does not generate or publish a global exponent r. Figure 3 (KeyGen) then says \"Let ghat^r, u0^r, h1^r be public,\" and Figure 4 (Enc) computes c_t2,k = (u0^r * prod u_i^{y_i})^{s_k}, c_t3,k = (h1^{r*y1} * prod h_i^{y_i})^{s_k}, and c_t(0)_{k,eta} = M_{k,eta} * e(g,ghat)^{tilde_alpha s_k} * e(H(M_{k,eta} * Tag), ghat^r)^{b_k}, all of which require ghat^r, u0^r, and h1^r. As written, clients cannot run Enc with the published pp, and if r were chosen independently inside KeyGen or Enc, the correctness equations in Section 3 would not hold because the pairing products would not cancel. The scheme is therefore not instantiable as specified.","section":"Figures 2, 3, and 4"},{"comment":"The simulator answers f=(w,v) queries with sk_f,1 = ghat^{b_w c_{w,v}}, sk_f,2 = ghat^{b_v c_{w,v}}, and sk_f,3 = (ghat^{1/(b_w+b_v)})^{tilde_b_w r}. The real KeyGen in Figure 3 produces sk_f,1 = ghat^{a_w * dot_r}, sk_f,2 = ghat^{a_v * dot_r}, and sk_f,3 = ghat^{r*b_w/(a_w+a_v)}. Matching the first two components forces a_w = b_w and a_v = b_v, and matching the third component then forces tilde_b_w = b_w. No argument is given that setting a_k = b_k is without loss of generality, and the proof does not simulate the actual distribution of a_k and b_k chosen in Setup. Consequently, Theorem 1 establishes security for a different scheme from the one presented in Figures 2-5, so the paper's central claim that the described scheme is P-IND secure is not supported.","section":"Section 4, Phase-1 function key queries"},{"comment":"The same a_k = b_k mismatch appears in the challenge ciphertext simulation. For k < rho, in the case (M*_{k,eta,mu} in E*_k) and (M*_{k,eta,mu} = M*_{rho,eta,mu}), the simulator sets ct(1)_{k,eta} = g^{a b_i} and e(H(M*_{k,eta,mu} * Tag*), ghat^r)^{b_k} = e(g^a, ghat^r)^{b_k}. But in the real Enc, ct(1)_{k,eta} = H(M_{k,eta} * Tag)^{a_k}, which would require a_k = b_k to match the simulated value. This reinforces the previous point: the simulated ciphertexts are not distributed as in the real scheme unless the independent a_k, b_k from Setup are artificially equated.","section":"Section 4, Challenge phase"}],"minor_comments":[{"comment":"The advantage expressions contain malformed formatting: \"|||Pr[...]=1||| <= epsilon(lambda)\" should be an absolute value, and the double bars are likely meant to denote absolute value but are displayed incorrectly. Please fix the notation in all three definitions.","section":"Section 2.2, Definitions 2-4"},{"comment":"There are many typos and LaTeX errors, including \"simulatior\" (Section 4), \"clssified\" (Section 4), \"massage sets\" (Section 2.6), and \"interaction\" for \"intersection\" in the introduction. A careful proofreading pass is needed.","section":"Throughout"},{"comment":"The correctness equations are unnumbered and several steps mix elements from G and Ghat in what appears to be a single expression, for example in the negated-attribute derivation. This makes the correctness argument harder to verify; please rewrite with clear group membership and equation numbers.","section":"Section 3, Correctness"},{"comment":"The table uses \"#\" for the access structure of the related MCFE-SI schemes [19,21,20,31]. This symbol is not defined; presumably it means that no access control is supported, but it should be stated explicitly.","section":"Table 1"},{"comment":"The implementation section reports average running times over five runs but gives no standard deviation, no hardware/software details beyond the laptop model, and no code or artifact link. The efficiency analysis would be more credible with at least a confidence interval or a description of the test methodology.","section":"Section 5"}],"recommendation":"reject","confidential_remarks":"The paper has two load-bearing flaws: Setup omits the global exponent r that Enc and KeyGen require, making the scheme non-instantiable, and the security proof silently changes the key distribution by equating a_k and b_k. Both issues are central to the claimed contribution of a formally proven MCFE-SI-NAS scheme. While the missing r might be fixable by adding it to Setup, the security proof's mismatch is a fundamental gap that would require either a new reduction or a substantially revised scheme. As written, the paper cannot be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the new combination is real — MCFE for set intersection with non-monotonic access policies hasn't appeared before, and the authors are right that non-monotonic policies are useful for FL access control. The definition/security model and the construction idea are a reasonable starting point. But the written scheme cannot be instantiated and Theorem 1 does not prove what it claims.\n\nThe instantiation problem is in Figure 2: Setup outputs pp without any exponent r, yet Enc (Figure 4) needs u0^r, h1^r, and ghat^r, and KeyGen uses r too. The only appearance of r in parameters is the throwaway parenthetical “Let ghat^r, u0^r, h1^r be public” inside the KeyGen figure — after encryption already needs them. A client given pp cannot run Enc. That alone is fatal to the paper as written.\n\nThe proof has a second load-bearing gap. Real client keys are independent pairs (a_k, b_k); real functional keys are ghat^{a_w·r}, ghat^{a_v·r}, ghat^{r·b_w/(a_w+a_v)}. The simulator, however, picks only b_1,...,b_N and produces sk_f,1 = ghat^{b_w·c_{w,v}}, sk_f,2 = ghat^{b_v·c_{w,v}}, sk_f,3 = (ghat^{1/(b_w+b_v)})^{tilde_b_w·r}. Matching those expressions forces a_w=b_w and a_v=b_v, and there is no argument that this is without loss of generality. The reduction in Theorem 1 therefore establishes security for a different scheme than the one in Figures 2–5. The claim of a formal security proof is unsupported.\n\nSecondary issues: the paper is littered with typos, and the efficiency section reports absolute timings without comparing to any baseline, so the “efficiency analysis” doesn’t tell us much. Those are minor next to the two above.\n\nCredit where due: the combination is new, the security model is a sensible adaptation of existing definitions, and the high-level approach (LSSS plus non-monotonic ABE techniques on top of Lee’s MCFE-SI) is plausible. The paper is not nonsense; it is an unfinished draft. A serious author could fix Setup, either justify a_k=b_k or redo the simulation, and resubmit.\n\nMy recommendation: I would not accept this. I would still send it to a scrutineer rather than desk-reject, because the core combination is new and the flaws are concrete enough that one referee report can put the authors on the path to a correct scheme. But as it stands, the central claim — an instantiable, formally proven MCFE-SI-NAS scheme — is not supported.","headline":"New combination, broken write-up: Setup omits the r that Enc and KeyGen need, and the proof silently sets a_k=b_k; not acceptable as is, but a major revision could salvage the idea.","tokens_in":24287,"tokens_out":3682,"would_cite":false,"duration_ms":34769,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proposes a multi-client functional encryption scheme for set intersection in which non-monotonic access policies let an aggregator compute an intersection only when its attributes satisfy the policy.","keywords":["functional encryption","set intersection","access control","federated learning","non-monotonic access structure","multi-client functional encryption","bilinear pairing","ciphertext label"],"falsifier":"Follow Section 3 exactly: Setup never produces $r$, while KeyGen and Enc both require $r$, so an exact implementation cannot run without inventing an additional parameter; if different parties choose their own $r$, the central pairing equations no longer cancel and decryption outputs garbage.","tokens_in":23200,"feed_emoji":"🔐","tokens_out":14150,"duration_ms":119271,"temperature":0.7,"pith_summary":"The paper sets out to add non-monotonic access control to multi-client functional encryption for set intersection, a tool aimed at federated learning. In the proposed MCFE-SI-NAS scheme, each client encrypts its set independently under a shared label, and an aggregator can compute the intersection of two clients' plaintext sets only when the attribute set attached to the ciphertexts satisfies the aggregator's policy. The policies are non-monotonic, so they can contain AND, OR, NOT, and threshold gates, which earlier MCFE-SI schemes with access control could not express. The construction works over asymmetric prime-order pairings, resists mix-and-match attacks via labels, and is claimed to be passively secure (P-IND) in the random oracle model under the paper's stated assumptions.","feed_headline":"Set-intersection encryption now supports NOT-gate policies","feed_subtitle":"In federated learning, clients encrypt independently and an aggregator learns only the allowed set intersection.","key_machinery":"The mechanism that carries the argument is label-bound ciphertext indexing over an asymmetric prime-order bilinear map $e: G \\times \\hat{G} \\to G_T$. Each plaintext element is hashed together with the label $\\mathit{Tag}$, and the resulting hash is raised to the client's own exponent $a_k$; equal elements from two clients produce equal pairing values when tested against the function-key components $\\hat{g}^{a_w \\dot{r}}$ and $\\hat{g}^{a_v \\dot{r}}$. Access control is layered on through a non-monotonic structure $\\tilde{\\mathbb{A}} = \\mathrm{NM}(\\mathbb{A})$ implemented with a linear secret-sharing scheme: non-negated attributes are encoded through the vector $u_0^{r}\\prod_{i=1}^{d} u_i^{y_i}$ and negated attributes through a companion encoding $h_1^{r y_1}\\prod_{i=2}^{d} h_i^{y_i}$, where $Y = (y_1,\\ldots,y_d)$ is the coefficient vector of the polynomial $P_S[X] = \\prod_{j\\in S}(X-j)$ built from the ciphertext attribute set $S$. The decryption procedure cancels these policy factors with the key shares $\\lambda_i$ and reconstruction coefficients $\\pi_i$, leaving exactly $M_{w,\\eta}\\cdot e(H(M_{w,\\eta}\\cdot\\mathit{Tag}), \\hat{g}^r)^{b_w}$, from which the indexing equation removes the residual $b_w$ term.","core_discovery":"The central discovery is a recipe for making set-intersection functional encryption policy-aware without giving up non-interactive client encryption. Concretely, the paper constructs a scheme in which client $k$ encrypts each element $M_{k,\\eta}$ under its own key $(a_k,b_k)$ and the shared label $\\mathit{Tag}$, producing $ct^{(0)}_{k,\\eta} = M_{k,\\eta} \\cdot e(g,\\hat{g})^{\\tilde{\\alpha} s_k} \\cdot e(H(M_{k,\\eta}\\cdot \\mathit{Tag}), \\hat{g}^{r})^{b_k}$ and $ct^{(1)}_{k,\\eta} = H(M_{k,\\eta}\\cdot \\mathit{Tag})^{a_k}$. A decryption key for $f=(w,v)$ and policy $\\tilde{\\mathbb{A}}$ contains $\\hat{g}^{a_w \\dot{r}}$, $\\hat{g}^{a_v \\dot{r}}$, $\\hat{g}^{r b_w/(a_w+a_v)}$, plus policy components that cancel when the ciphertext attribute set satisfies $\\tilde{\\mathbb{A}}$. The same-label check $e(ct^{(1)}_{w,\\eta}, \\hat{g}^{a_v \\dot{r}}) = e(ct^{(1)}_{v,\\eta}, \\hat{g}^{a_w \\dot{r}})$ identifies equal elements, and the final division recovers $M_{w,\\eta}$ exactly. The paper proves P-IND security in the random oracle model under the assumptions in [20] and a variant of the $q$-DBDHE assumption.","pith_inferences":["The paper leaves implicit that the same label-bound indexing equation could be reused to expose coarser statistics, such as intersection cardinality or union size, without changing the pairing structure.","Not addressed in the paper: decentralizing key generation would require a new model and proof, because the security argument assumes one fully trusted authority that knows every client key.","A natural extension is to lift the passive P-IND notion to static or adaptive corruption; the provided proof does not cover corrupted clients.","The paper's measured encryption cost grows linearly with the number of clients and elements, so precomputation or batched exponentiation would be the first place to make the scheme practical for federated learning."],"forward_implications":["An aggregator whose attributes satisfy the policy can compute the intersection of any two clients' plaintext sets and provably learns nothing else about the sets.","Labels bind all ciphertexts of one run, so ciphertexts from different runs cannot be spliced to compute unintended intersections.","Non-monotonic policies make rules expressible that monotonic-only schemes cannot, such as a history-department aggregator that is explicitly barred from biology-department data.","Clients encrypt once and never interact, which fits federated learning settings where clients may come online only briefly.","Under the P-IND security notion, an adversary that queries only unauthorized policies cannot distinguish which of two challenge message tuples was encrypted."],"supporting_citations":[{"why":"Supplies the original two-client and multi-client functional encryption for set intersection that this work extends with access control.","marker":"[19]"},{"why":"Provides the complexity assumptions and ciphertext-indexing techniques used in the construction and proof.","marker":"[20]"},{"why":"Gives the concrete asymmetric bilinear-group MCFE-SI scheme whose label and indexing design the construction follows.","marker":"[21]"},{"why":"Defines the passive and static indistinguishability security notions that the paper's P-IND model adopts.","marker":"[31]"},{"why":"Introduces the duplicate-and-compress technique for adding fine-grained access control to multi-client functional encryption, which underlies the policy layer.","marker":"[27]"},{"why":"Provides the linear-independence proposition used in the security proof to simulate policy keys for unauthorized access structures.","marker":"[16]"},{"why":"Source of the q-DBDHE assumption whose asymmetric variant is used in the security proof.","marker":"[34]"}],"fun_headline_variants":["Non-monotonic access control for encrypted set intersection","Federated set intersection now supports NOT-gate policies","Multi-client encryption for set intersection with NOT gates","Encrypted set intersection with flexible access policies"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The scheme assumes a single random value $r$ is known to the key-issuing authority and to every client during encryption, but the Setup algorithm never samples $r$ or places it in the public parameters; the security proof additionally assumes two per-client secret values can be set equal without changing the key distribution.","fun_headline_variants_meta":{"raw":{"variants":["Non-monotonic access control for encrypted set intersection","Federated set intersection now supports NOT-gate policies","Multi-client encryption for set intersection with NOT gates","Encrypted set intersection with flexible access policies"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000597,"raw_usage":{"total_tokens":2855,"prompt_tokens":1068,"completion_tokens":1787,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":684,"completion_tokens_details":{"reasoning_tokens":1726}},"tokens_in":684,"tokens_out":1787,"duration_ms":13469,"temperature":1.0,"reasoning_tokens":1726,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:06:09.650906+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Follow Section 3 exactly: Setup never produces $r$, while KeyGen and Enc both require $r$, so an exact implementation cannot run without inventing an additional parameter; if different parties choose their own $r$, the central pairing equations no longer cancel and decryption outputs garbage.","supporting_citations":[{"cited_title":"Two- client and multi-client functional encryption for set intersection, in: Jang-Jaccard, J., Guo, F","cited_arxiv_id":null,"evidence_quote":"Supplies the original two-client and multi-client functional encryption for set intersection that this work extends with access control."},{"cited_title":"Decentralized multi-client functional encryption for set intersection with improved efficiency","cited_arxiv_id":null,"evidence_quote":"Provides the complexity assumptions and ciphertext-indexing techniques used in the construction and proof."},{"cited_title":"Functional encryption for set intersection in themulti-clientsetting","cited_arxiv_id":null,"evidence_quote":"Gives the concrete asymmetric bilinear-group MCFE-SI scheme whose label and indexing design the construction follows."},{"cited_title":"Flexible multi-client functional encryption for set intersection","cited_arxiv_id":null,"evidence_quote":"Defines the passive and static indistinguishability security notions that the paper's P-IND model adopts."},{"cited_title":"Multi-client func- tional encryption with fine-grained access control, in: Agrawal, S., Lin, D","cited_arxiv_id":null,"evidence_quote":"Introduces the duplicate-and-compress technique for adding fine-grained access control to multi-client functional encryption, which underlies the policy layer."},{"cited_title":"Attribute-based encryption for fine-grained access control of encrypted data, in: CCS 2006, Association for Computing Machinery, New York, NY, USA","cited_arxiv_id":null,"evidence_quote":"Provides the linear-independence proposition used in the security proof to simulate policy keys for unauthorized access structures."},{"cited_title":"Hierarchical identity-based inner product functional encryption","cited_arxiv_id":null,"evidence_quote":"Source of the q-DBDHE assumption whose asymmetric variant is used in the security proof."}],"review_version":1}