{"id":"f39da22e-69d4-44ea-935d-20a34c512545","arxiv_id":"2509.10793","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"ORQ evaluates multi-way join-aggregation workloads fully obliviously under MPC in O(n log n) time, reporting the first full TPC-H SF10 run under MPC without leakage or trusted compute.","lead":"ORQ is a new system that runs relational database queries, including multi-way joins and aggregations, entirely under secure multi-party computation, so organizations can analyze pooled private data without exposing it and without trusting a third party. It reports executing the full TPC-H benchmark at Scale Factor 10 fully under MPC, a scale previously reached only with information leakage or trusted parties.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"TPC-H 'full benchmark' claim rests on disclosed substitutions that are not validated; SF10 headline should be qualified until fixed-point and LIKE variants are measured.","rationale":"The reader's weakest_assumption focuses primarily on the empirical bounded-output premise derived from 31 workloads. I agree that this is a structural limitation, but it is explicitly scoped: the paper states the supported class and discloses the O(n^2) fallback for queries outside it, so the core algorithmic claim remains coherent even if the empirical universality is not a theorem. The more directly load-bearing concern for the paper's headline result is the TPC-H fidelity issue. Section 5.1 and footnote 1 admit that fixed-point arithmetic and substring operations are unsupported, yet the abstract and contributions call the benchmark 'the full TPC-H benchmark' and the SF10 result is the signature scalability claim. Replacing floats with integers and LIKE with equality is a deliberate approximation; without a sensitivity analysis, the SF10 timing and scaling ratios may not reflect actual TPC-H workload difficulty. This does not invalidate the join-aggregation operator or the O(n log n) asymptotic claims, but it should keep the verdict conditional until the substitutions are quantified. Because the reader already issued CONDITIONAL, my concern does not change the verdict.","tokens_in":44702,"tokens_out":26657,"duration_ms":356423,"concrete_test":"Identify the six TPC-H queries whose dataflow scripts differ from the TPC-H spec due to the substitutions described in §5.1. Re-run those queries under SH-HM at SF1 in ORQ with (a) fixed-point arithmetic implemented via scaled integers with explicit rounding and (b) an oblivious substring match implemented as character-level equality/comparison. Compare outputs against a SQLite TPC-H reference and record time/bandwidth against the substituted variants. If any output diverges from the reference, or if the substituted variant is more than 20% faster on these queries, restate the SF10 claim as 'TPC-H with disclosed substitutions' rather than 'full TPC-H'.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Footnote 1 and §5.1 disclose that ORQ does not yet support fixed-point arithmetic or substring operations, so the 'complete TPC-H benchmark' at SF10 is actually run with integers replacing floats and equality replacing LIKE in six queries. The abstract and contributions nevertheless call this 'full TPC-H' and use SF10 as the headline evidence of scalability. This is load-bearing because the substitutions change both result semantics and workload difficulty: fixed-point multiply/divide with rounding and substring predicates are more expensive than the substituted operators and can alter selectivity, group cardinalities, and the SF1-to-SF10 scaling ratio. The paper provides no equivalence or sensitivity analysis. If the SF10 numbers were obtained only with these substitutions, the claim 'full TPC-H under MPC at SF10' is not established as stated. This concern targets the evaluation claim, not the core join-aggregation mechanism, which is supported by detailed protocol descriptions, correctness arguments, and released open-source code.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"ORQ is a C++ system for oblivious relational query processing in the outsourced MPC setting. It contributes a composite sort-based join-aggregation operator, protocol-agnostic oblivious sorting and shuffling primitives, a vectorized and parallel runtime, and support for three MPC protocols (semi-honest 2PC, semi-honest 3PC, malicious 4PC). The headline claim is the first fully oblivious MPC evaluation of the complete TPC-H benchmark at Scale Factor 10, with asymptotic cost O(n log n) operations, O(log n) rounds, and O(n) memory for queries involving one-to-many joins or many-to-many joins with decomposable aggregation. The paper includes operator-level correctness and security arguments in Appendix C, extensive LAN/WAN experiments against Secrecy, SecretFlow, and MP-SPDZ, and open-source code. The evaluation, however, relies on disclosed substitutions—integers for floating-point values and equality for LIKE predicates in six queries—that affect the strength of the headline TPC-H claim.","tokens_in":44902,"tokens_out":9425,"duration_ms":98552,"significance":"If the results hold, ORQ is a significant contribution to private analytics: it demonstrates that a broad class of join-aggregation workloads can be executed obliviously in MPC at scales previously associated with leakage or trusted compute. The protocol-agnostic operator stack, the unified join-aggregation control flow, and the released implementation are valuable and reproducible contributions. The asymptotic improvements over prior oblivious joins (avoiding O(n^2) intermediate results) are well motivated and supported by detailed protocol descriptions and experiments. However, the strongest advertised result—'full TPC-H benchmark' at SF10—is undermined by the disclosed semantic substitutions, and the paper's general complexity claim for a class of acyclic conjunctive queries is broader than what is formally proven. These issues are addressable, but they affect the paper's central evaluation and contribution claims.","major_comments":[{"comment":"The claim 'full TPC-H benchmark' at SF10 is not supported as stated. The paper replaces floating-point (in TPC-H, fixed-point) arithmetic with integers and replaces six LIKE 'Y%' predicates with equality. These substitutions are not semantics-preserving: fixed-point rounding and prefix-match selectivity affect aggregation outputs, group cardinalities, and the SF1-to-SF10 scaling ratio. No equivalence proof, differential analysis, or sensitivity study is provided. Since the abstract and contributions use 'full TPC-H' and 'SF10' as headline evidence of scalability, the paper should either run the unmodified TPC-H queries (at least at SF1, and for the six queries at SF10) or explicitly qualify all claims to 'TPC-H with integer arithmetic and equality predicates.'","section":"§5.1, Footnote 1, Abstract/Contributions"},{"comment":"The paper asserts a general complexity guarantee for all acyclic conjunctive queries satisfying conditions (i) or (ii). However, the correctness proofs in Appendix C are for the individual Join-Agg protocol and AggNet, and the multi-query composition is only demonstrated on examples (Figure 3 and the Secure Yannakakis query). There is no theorem stating that any query in the claimed class can be compiled to O(n log n) operations, O(log n) rounds, and O(n) memory. The Section 1 observation about 31 workloads is empirical evidence about a sample, not a completeness proof. Please either provide a formal statement with a proof or reduction, or restrict the claim in the abstract and contributions to the collected workloads and the classes explicitly demonstrated.","section":"§2.1, §3.6, Appendix C"},{"comment":"The comparison with SecretFlow grants both systems access to data owners' trusted compute. Since ORQ's target setting is outsourced MPC with no TCB, it is unclear what ORQ actually performs in trusted compute in this comparison and whether the reported 1.1–1.5x speedups on join queries S3–S5 reflect ORQ's intended deployment. Please clarify the exact role of trusted compute in ORQ's configuration and, if the comparison is meant to show that ORQ is competitive even when given the same advantageous setting, state that explicitly in the text.","section":"§5.3, Figure 5 (right)"}],"minor_comments":[{"comment":"The text says 'two of the fastest (Q11, Q21), the median (Q12), and the two slowest (Q8, Q21)'—Q21 appears twice and is elsewhere described as the most expensive query. Likely a typo for Q9 or Q22; please correct.","section":"Appendix E"},{"comment":"The sentence 'up to 2^22 elements with SH-DM, 2^25 with SH-DM, and 2^20 with Mal-HM' repeats SH-DM; the second occurrence should presumably be SH-HM, consistent with Table 11.","section":"§5.3, Figure 7 text"},{"comment":"The paper states that appendices are 'not included in the peer-review process,' yet the correctness proofs for the main operator are located there. If this is a submission version, please include the appendices in the peer-review material or move the central correctness argument into the main text.","section":"Appendix C header"},{"comment":"The trimming heuristic is described with a specific formula ('9m < n lg n lg l') for one protocol, but the derivation in Appendix C.3 uses different approximations. Please align the main-text formula with the appendix analysis for reproducibility.","section":"§3.3, trimming heuristic"}],"recommendation":"major_revision","confidential_remarks":"This is a strong systems/security paper with a substantial implementation and an honest evaluation in most respects. The main risk is the overstatement of the TPC-H result: the abstract and contributions present 'full TPC-H at SF10' as a first, while the actual runs substitute integer arithmetic for fixed-point and equality for LIKE. This is disclosed in the setup, but the headline claims are not qualified. I believe the authors can address this either by running the unmodified variants or by rewording the claims. The second issue—the gap between the stated query-class guarantee and the provided operator-level proofs—is also important for a venue that values formal claims. I recommend major revision rather than reject: the core operator and evaluation are sound, and the issues are fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"ORQ is a real step forward and deserves serious refereeing. The central mechanism — a composite join-aggregation operator that pre-aggregates many-to-many joins so the Cartesian product never materializes — is genuinely new in the fully oblivious MPC setting. The paper argues it carefully: detailed protocols, correctness proofs in the appendix, and an open-source implementation that runs across three MPC threat models (two semi-honest, one malicious). The evaluation is extensive: TPC-H-sized workloads, up to 2^29 rows sorted, and large constant-factor wins over Secrecy, SecretFlow, and MP-SPDZ. The asymptotic claim — O(n log n) operations, O(log n) rounds, O(n) memory for a defined class of acyclic join-aggregate queries — holds up on my reading.\n\nThe real soft spot is the TPC-H headline. The abstract and contributions say 'full TPC-H' and 'complete TPC-H benchmark' at SF10, but footnote 1 and §5.1 disclose that fixed-point arithmetic and substring operations are not supported; six queries substitute integers for floats and equality for LIKE. Those substitutions aren't workload-neutral: fixed-point multiply/divide with rounding and substring predicates are strictly harder in MPC and can shift selectivity and group cardinalities. So the SF10 results are real, but the 'full TPC-H' claim is stronger than what was run. This is a revision issue, not a flaw in the mechanism — the substitutions don't touch the security or the asymptotic story — but the authors should qualify the abstract and either measure the substituted variants' sensitivity or run the real operators.\n\nTwo smaller notes. The bounded-output premise ('results whose size is worst-case bounded by the input size') is an empirical generalization over 31 workloads, not a theorem over the stated class. For a systems paper that's an acceptable scoping device — §2.1 defines the class explicitly and honestly lists what falls out (cyclic queries, aggregation keys spanning tables → O(n²) fallback) — but the paper could be clearer that this is workload-driven, not proven. And the main query figures report point estimates with no variance; a range would help.\n\nWho this is for: anyone building oblivious analytics in MPC or enclaves, and anyone who wants a realistic sense of where secure relational query processing stands. It should go to peer review; the fixes needed are about honest presentation, not the core result.","headline":"Genuinely new join-aggregation mechanism with a strong evaluation; the 'full TPC-H' headline overstates what was run until the disclosed float/LIKE substitutions are qualified.","tokens_in":45412,"tokens_out":5113,"would_cite":true,"duration_ms":49479,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"ORQ claims that practical private-data analytics under MPC can run at sorting cost instead of quadratic join cost, and backs it by running all 22 TPC-H queries at Scale Factor 10 with no leakage and no trusted compute.","keywords":["multi-party computation","oblivious query processing","relational joins","secret sharing","TPC-H","join aggregation","oblivious sorting","privacy-preserving analytics"],"falsifier":"Measure ORQ's end-to-end time for a complex supported query such as TPC-H Q21 at Scale Factors 1, 10, and 100; if per-row cost grows faster than O(n log n), the sorting-cost claim fails. Alternatively, scan the 31 collected workloads for any query whose true worst-case output is not bounded by a constant multiple of its largest input; one counterexample would sink the bounded-output premise.","tokens_in":44585,"feed_emoji":"🔐","tokens_out":6649,"duration_ms":71485,"temperature":0.7,"pith_summary":"ORQ tries to establish that the quadratic cost that has made secure relational joins expensive under multi-party computation (MPC) is not inherent for the queries people actually run. The paper's key claim is that every query in the 31 workloads it collected, including multi-way joins on duplicate keys, has a worst-case output size bounded by the input size. Exploiting that, ORQ evaluates acyclic join-aggregation queries at sorting cost: O(n log n) operations, O(log n) rounds, and O(n) memory, fully obliviously. If correct, collaborative analytics on large private datasets can run in minutes at scales that previously required either leaking join sizes or trusting a third party; the paper demonstrates this by running all 22 TPC-H queries at Scale Factor 10 entirely under MPC.","feed_headline":"TPC-H scale 10 runs end-to-end under MPC","feed_subtitle":"ORQ fuses joins with aggregation so large private queries cost about the same as sorting.","key_machinery":"The load-bearing object is the composite join-aggregation operator: it concatenates two secret-shared tables, sorts them on (validity, join key, origin-table id) using an oblivious table sort, marks group boundaries with an oblivious distinct step, and then runs a Hillis-Steele-style aggregation network that copies values from the left input and applies decomposable aggregation functions in O(log n) rounds. A secret-shared validity column marks dummy and invalidated rows, so true result sizes remain hidden throughout. The same operator is adapted to inner, outer, semi-, anti-, and equality-theta joins, and it composes with itself to form arbitrary acyclic pipelines.","core_discovery":"ORQ's central claim is that oblivious relational analytics in the outsourced MPC setting can be made tractable for a broad class of practical queries by fusing joins with aggregation and relying on the observation that real queries' result sizes are worst-case bounded by their input size. The supported class covers acyclic conjunctive queries with one-to-many joins, or many-to-many joins when a decomposable aggregation is applied and group-by keys live in a single input table. For those queries, ORQ never materializes the Cartesian product: it pre-aggregates one side to make join keys unique, joins with the fused operator, then post-aggregates. The paper supports this with 31 collected workl","pith_inferences":["If the bounded-output regularity holds beyond the 31 collected workloads, the fast path likely covers most real acyclic analytics—but each new workload should be checked, since the paper offers no theorem over the full supported class.","The same fused join-aggregation control flow maps directly onto trusted-hardware analytics, where it would remove the need to leak intermediate result sizes; this is an extension the paper mentions but does not implement.","ORQ's iterative quicksort and permutation-extraction routines are protocol-agnostic, so they may transfer to other MPC backends or plaintext oblivious runtimes, though the paper does not demonstrate that transfer.","A natural hardening is a query compiler that statically checks acyclicity and aggregation-key placement before admitting a query to the fast path; without it, an unsupported query silently falls back to the O(n^2) join."],"forward_implications":["All 22 TPC-H queries—not a subset—run to completion under ORQ at Scale Factor 10 without information leakage and without trusted compute.","Within the supported query class, per-query cost is O(n log n) operations, O(log n) rounds, and O(n) memory, matching the cost of sorting the input rather than the prior quadratic join barrier.","ORQ supports inner, outer, semi-, anti-, and equality-theta joins, plus group-by and user-defined decomposable aggregations, in one oblivious operator.","Oblivious sorting under ORQ scales to 2^29 rows (about 537 million) in its fastest protocol, and the operators work under three threat models including malicious security."],"fun_headline_variants":["ORQ runs TPC-H scale 10 fully under MPC","No trusted third party: ORQ does TPC-H scale 10 in MPC","ORQ: Secure joins without quadratic blowup","Fusing joins and aggregation for private analytics"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The central claim rests on the empirical observation that all 31 collected workloads have worst-case output size bounded by input size—supported by example, not proved for the whole supported class—and the TPC-H evaluation assumes that replacing floats with integers and LIKE with equality preserves workload difficulty.","fun_headline_variants_meta":{"raw":{"variants":["ORQ runs TPC-H scale 10 fully under MPC","No trusted third party: ORQ does TPC-H scale 10 in MPC","ORQ: Secure joins without quadratic blowup","Fusing joins and aggregation for private analytics"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000725,"raw_usage":{"total_tokens":3092,"prompt_tokens":754,"completion_tokens":2338,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":498,"completion_tokens_details":{"reasoning_tokens":2270}},"tokens_in":498,"tokens_out":2338,"duration_ms":18154,"temperature":1.0,"reasoning_tokens":2270,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T17:34:47.893019+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure ORQ's end-to-end time for a complex supported query such as TPC-H Q21 at Scale Factors 1, 10, and 100; if per-row cost grows faster than O(n log n), the sorting-cost claim fails. Alternatively, scan the 31 collected workloads for any query whose true worst-case output is not bounded by a constant multiple of its largest input; one counterexample would sink the bounded-output premise.","supporting_citations":[],"review_version":1}