Pith. sign in

REVIEW 3 major objections 4 minor 85 references

ORQ: Complex Analytics on Private Data with Strong Security Guarantees

T0 review · 3 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2509.10793 v2 pith:STFM6S6E submitted 2025-09-13 cs.CR cs.DB

Eli Baum , Sam Buxbaum , Nitin Mathai , Muhammad Faisal , Vasiliki Kalavri , Mayank Varia , John Liagouris This is my paper · ORCID
classification cs.CRcs.DB
keywords multi-partycomputationobliviousqueryprocessingrelationaljoinssecretsharingTPC-Hjoinaggregationsortingprivacy-preservinganalytics
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [§5.1, Footnote 1, Abstract/Contributions] 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.'
  2. [§2.1, §3.6, Appendix C] 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.
  3. [§5.3, Figure 5 (right)] 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.
minor comments (4)
  1. [Appendix E] 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.
  2. [§5.3, Figure 7 text] 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.
  3. [Appendix C header] 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.
  4. [§3.3, trimming heuristic] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: ORQ's complexity claims are derived from protocol pseudocode and measured end-to-end; the TPC-H substitutions are a benchmark-validity concern, not a circular derivation.

full rationale

No circularity found. ORQ's central asymptotic claims (O(n log n) ops, O(log n) rounds, O(n) memory) are supported by protocol listings (Protocols 1-3, 9-11) and by end-to-end measurements; no parameter is fitted to the target result and no 'prediction' is read back from the fitting data. The load-bearing premise that all 31 collected workloads have result sizes worst-case bounded by input size is an empirical generalization, explicitly grounded in an enumeration of workloads from TPC-H and prior MPC papers, not a definitional equivalence: ORQ's supported class is independently characterized by decomposable aggregation and group-by keys in one input, and the claim that prior queries fall into this class is checked by inspection of the workloads. Prior shuffling and sorting work (Asharov et al., Peceny et al.) is used as a building block with independent cryptographic and implementation support, and the authors' earlier Secrecy system appears as a baseline, not as justification for ORQ's correctness. The disclosed TPC-H substitutions (fixed-point arithmetic replaced by integers and LIKE by equality, Footnote 1 and §5.1) are a benchmark-validity risk: they may change selectivity and workload difficulty, so the 'full TPC-H at SF10' headline is not established exactly as stated. But this is a correctness/evaluation concern, not circularity, because the SF10 numbers are measured end-to-end rather than derived from the assumption that the substitutions preserve difficulty. There is no equation in the paper that reduces to its own inputs, no fitted parameter renamed as a prediction, and no load-bearing self-citation chain. Hence the appropriate circularity score is 0.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claim rests on the query-class restriction (bounded output) and on standard MPC abstractions. The performance claims depend on concrete engineering choices like the trimming heuristic and the quicksort preprocessing bound, which are disclosed as heuristics with derived constants. No new cryptographic entities or trust assumptions are introduced.

free parameters (3)
  • Trimming heuristic threshold = trim when 9m < n lg n lg l for SH-HM
    Section 3.3 and Appendix C.3: a cost-model-derived heuristic chooses when to trim rows after a join. The constants are hand-derived and affect performance, not correctness.
  • Quicksort preprocessing bound = 2n lg n Beaver triples, plus a 10,000-triple buffer for n<2000
    Appendix B.4: chosen so preprocessing is sufficient 99.9% of the time. A probabilistic design constant affecting runtime and memory, not correctness.
  • Input padding width = 32 bits always added
    Appendix B.2: padding guarantees uniqueness and enables permutation extraction. A fixed engineering constant affecting communication and share bitwidth.
assumptions (5)
  • domain assumption MPC primitives (+, x, xor, and) are available as black boxes with their standard security properties.
    Section 2.4 states ORQ operators are protocol-agnostic and inherit the guarantees of the underlying MPC protocols. This is the standard abstraction for MPC systems.
  • domain assumption Revealing comparison results after an oblivious shuffle leaks no information about the data.
    Section 3.2 and Appendix B.1 rely on the shuffle-then-sort paradigm proven in prior work (Hamada et al. [32], Araki et al. [4]). The paper cites these as established results.
  • domain assumption Aggregation functions are decomposable (self-decomposable) so partial evaluation is possible.
    Section 3.5 defines the decomposability requirement, which is necessary for the many-to-many pre-aggregation technique. The supported query class is restricted accordingly.
  • domain assumption The 31 collected workloads are representative of practical relational MPC queries, so the bounded-output observation holds broadly.
    Section 1 bases the central observation on an analysis of 31 TPC-H and prior-work queries. This is an empirical generalization, not a proven theorem; the paper itself lists queries outside the class in Section 2.1.
  • domain assumption Malicious security of the 4-party shuffle groups follows from the INP protocol of Fantastic Four.
    Appendix A.3 relies on the security of the INP resharing protocol from Dalskov et al. [19] to argue that a single corrupted party cannot corrupt both received values.

how reviews work

0 comments
Cite this review

Pith. "Pith review of ORQ: Complex Analytics on Private Data with Strong Security Guarantees." pith.science (2026). https://pith.science/paper/STFM6S6E

@misc{pith2026250910793,
  author       = {Pith},
  title        = {Pith review of: ORQ: Complex Analytics on Private Data with Strong Security Guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/STFM6S6E}},
  note         = {Machine review of arXiv:2509.10793}
}
read the original abstract

We present ORQ, a system that enables collaborative analysis of large private datasets using cryptographically secure multi-party computation (MPC). ORQ protects data against semi-honest or malicious parties and can efficiently evaluate relational queries with multi-way joins and aggregations that have been considered notoriously expensive under MPC. To do so, ORQ eliminates the quadratic cost of secure joins by leveraging the fact that, in practice, the structure of many real queries allows us to join records and apply the aggregations "on the fly" while keeping the result size bounded. On the system side, ORQ contributes generic oblivious operators, a data-parallel vectorized query engine, a communication layer that amortizes MPC network costs, and a dataflow API for expressing relational analytics -- all built from the ground up. We evaluate ORQ in LAN and WAN deployments on a diverse set of workloads, including complex queries with multiple joins and custom aggregations. When compared to state-of-the-art solutions, ORQ significantly reduces MPC execution times and can process one order of magnitude larger datasets. For our most challenging workload, the full TPC-H benchmark, we report results entirely under MPC with Scale Factor 10 -- a scale that had previously been achieved only with information leakage or the use of trusted third parties.

Figures

Figures reproduced from arXiv: 2509.10793 by the authors.

Figure 1
Figure 1. Orq targets the typical outsourced setting that uses a small set of computing parties (whose number depends on the MPC protocol) to support any number of data owners and analysts. of the result only to the designated data analysts. Orq cur￾rently supports three MPC protocols and can be instantiated with semi-honest or malicious security. We describe Orq’s secret-sharing techniques and protocols in §2.3-2.4. Orq is d… view at source ↗
Figure 2
Figure 2. Steps of the basic Orq operator. The input tables are concatenated and sorted to bring valid rows with the same join key 𝐾 (e.g., x and y) next to each other. Values in 𝑂.𝐶 are copied to matching rows from 𝑅. Values in 𝑂.𝐴 are aggregated per key 𝐾 and stored in 𝑂.𝐺. Protocol 3: Join-Aggregation (Join-Agg) Input :Tables 𝐿, 𝑅; keys 𝐾 = {𝐾1, · · · , 𝐾𝑗 }, columns 𝐶 = {𝐶1, · · · ,𝐶𝑘 } to propagate from 𝐿 to 𝑅, an aggreg… view at source ↗
Figure 3
Figure 3. Step-by-step oblivious evaluation of TPC-H Q3 assuming no PK-FK constraints (all input tables have duplicate join keys). 𝑅.Time. In this case, Orq executes Protocol 3 using the equal￾ity predicate(s) that bound the output size and reduces all other predicates in 𝜃 into oblivious filters. 3.5 Supporting aggregations In line 5 of Join-Agg, join is combined with an aggregation in the same oblivious control flow (AggNet… view at source ↗
Figures from the paper (9 more)
Figure 5
Figure 5. Figure 5: Orq query times compared to Secrecy and SecretFlow. Secrecy operates in the outsourced setting without leakage. Secret￾Flow is a peer-to-peer system that offloads operations to the data owners’ trusted compute and leaks the result of the join to parties [PITH_FULL_IMA…
Figure 4
Figure 4. Figure 4: Query execution time (min) at SF1 in LAN (solid) and WAN (hatched). Bars are overlapped, not stacked. TPC-H queries shown on the left and other queries on the right. Q6 times annotated. 4-7 joins each, with Q21 also performing a self-join on the largest input table, Li…
Figure 6
Figure 6. Figure 6: Performance of oblivious sort in SecretFlow and Orq [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: Performance of oblivious radixsort protocols in MP-SPDZ and Orq. We run MP-SPDZ until it crashes or runs out of memory. Comparison on oblivious sort. We now compare Orq’s oblivious radixsort against two publicly available state-of￾the-art implementations. In [PITH_FUL…
Figure 8
Figure 8. Figure 8: Ratio of TPC-H query execution times at SF10 over SF1 for the SH-DM protocol in LAN. The 22 queries are sorted from left to right by increasing SF10 latency [PITH_FULL_IMAGE:figures/full_fig_p013_8.png]
Figure 9
Figure 9. Figure 9: Orq performance at SF10 in WAN. Bars are labeled with the scaling ratio compared to SF1 in the same environment. Q21 is the most expensive query in the TPC-H benchmark across protocols [PITH_FULL_IMAGE:figures/full_fig_p013_9.png]
Figure 10
Figure 10. Figure 10: Scaling Orq’s oblivious sorting protocols to very large inputs. Quicksort scales to larger inputs than radixsort, which has higher time and memory requirements for permutation generation. further and evaluate their performance on even larger in￾puts. We run radixsort …
Figure 11
Figure 11. Figure 11: Comparison of our radixsort protocol with Asharov et al. [5] for (a) ℓ = 32 and (b) ℓ = 64. All data points are the average of 3 runs and are run with 34 threads in the 3-party setting. WAN data points are collected in a WAN environment with 20ms latency. 64-bit radix…
Figure 12
Figure 12. Figure 12: TPC-H query times at SF1 in a geo-distributed WAN deployment, with ratios over times in our symmetric WAN. time to run the entire TPC-H benchmark [PITH_FULL_IMAGE:figures/full_fig_p030_12.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

85 extracted references · 2 canonical work pages

  1. [1]

    Navid Alamati, Guru-Vamsi Policharla, Srinivasan Raghuraman, and Peter Rindal. 2024. Improved Alternating-Moduli PRFs and Post- quantum Signatures. InAdvances in Cryptology – CRYPTO 2024: 44th Annual International Cryptology Conference, CRYPTO 2024, Santa Barbara, CA, USA, August 18–22, 2024, Proceedings, Part VIII(Santa Barbara, CA, USA). Springer-Verlag...

    work page doi:10.1007/978-3-031-68397-8_9 2024

  2. [2]

    Apple and Google. 2021. Exposure Notification Privacy-preserving Analytics (ENPA).https://covid19-static.cdn-apple.com/applications/ covid19/current/static/contact-tracing/pdf/ENPA_White_Paper.pdf. [Online; accessed April 2025]

    2021

  3. [3]

    Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara. 2016. High-Throughput Semi-Honest Secure Three-Party Com- putation with an Honest Majority. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS) (Vienna, Austria). 805–817. doi:10.1145/2976749.2978331

    arXiv 2016

  4. [4]

    Toshinori Araki, Jun Furukawa, Kazuma Ohara, Benny Pinkas, Hanan Rosemarin, and Hikaru Tsuchida. 2021. Secure Graph Analysis at Scale. InProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security(Virtual Event, Republic of Korea)(CCS ’21). Association for Computing Machinery, New York, NY, USA, 610–629. doi:10.1145/3460120.3484560

    arXiv 2021

  5. [6]

    Gilad Asharov, Koki Hamada, Ryo Kikuchi, Ariel Nof, Benny Pinkas, and Junichi Tomida. 2023. Secure Statistical Analysis on Multiple Datasets: Join and Group-By. InProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security(Copenhagen, Denmark)(CCS ’23). Association for Computing Machinery, New York, NY, USA, 3298–3312. doi:10.114...

    arXiv 2023

  6. [7]

    Axel Bacher, Olivier Bodini, Alexandros Hollender, and Jérémie Lum- broso. 2015. Mergeshuffle: a very fast, parallel random permutation algorithm.arXiv preprint 1508.03167(2015)

    arXiv 2015

  7. [8]

    Saikrishna Badrinarayanan, Sourav Das, Gayathri Garimella, Srini- vasan Raghuraman, and Peter Rindal. 2022. Secret-Shared Joins with Multiplicity from Aggregation Trees. InProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security(Los Angeles, CA, USA)(CCS ’22). Association for Computing Machinery, New York, NY, USA, 209–222. do...

    arXiv 2022

  8. [9]

    Kenneth E. Batcher. 1968. Sorting Networks and Their Applications. In American Federation of Information Processing Societies: AFIPS Confer- ence Proceedings: 1968 Spring Joint Computer Conference, Atlantic City, NJ, USA, 30 April - 2 May 1968. 307–314. doi:10.1145/1468075.1468121

    arXiv 1968

Show all 85 references
  1. [10]

    Kho, and Jennie Rogers

    Johes Bater, Gregory Elliott, Craig Eggen, Satyender Goel, Abel N. Kho, and Jennie Rogers. 2017. SMCQL: Secure Query Processing for Private Data Networks.Proc. VLDB Endow.10, 6 (2017), 673–684. doi:10.14778/3055330.3055334

    2017

  2. [11]

    Johes Bater, Xi He, William Ehrich, Ashwin Machanavajjhala, and Jennie Rogers. 2018. Shrinkwrap: efficient sql query processing in differentially private data federations.Proceedings of the VLDB En- dowment12, 3 (2018), 307–320

    2018

  3. [12]

    Johes Bater, Yongjoo Park, Xi He, Xiao Wang, and Jennie Rogers. 2020. SAQE: practical privacy-preserving approximate query processing for data federations.Proceedings of the VLDB Endowment13, 12 (2020), 2691–2705

    2020

  4. [13]

    Laura Blackstone, Seny Kamara, and Tarik Moataz. 2020. Revisiting Leakage Abuse Attacks. InNDSS. The Internet Society

    2020

  5. [14]

    Marina Blanton and Everaldo Aguiar. 2012. Private and oblivious set and multiset operations. InAsiaCCS. ACM, 40–41

    2012

  6. [15]

    Dan Bogdanov, Liina Kamm, Baldur Kubo, Reimo Rebane, Ville Sokk, and Riivo Talviste. 2016. Students and Taxes: a Privacy- Preserving Study Using Secure Computation.Proceedings on Orq: Complex Analytics on Private Data with Strong Security Guarantees Privacy Enhancing Technolog...

    2016

  7. [16]

    Dan Bogdanov, Sven Laur, and Riivo Talviste. 2014. A Practical Anal- ysis of Oblivious Sorting Algorithms for Secure Multi-party Computa- tion. InSecure IT Systems, Karin Bernsmed and Simone Fischer-Hübner (Eds.). Springer International Publishing, Cham, 59–74

    2014

  8. [17]

    Boston Women’s Workforce Council. 2024. Data Privacy: Ensuring Secure and Private Data Analysis. https://thebwwc.org/mpc

    2024

  9. [18]

    Henry Corrigan-Gibbs and Dan Boneh. 2017. Prio: Private, Robust, and Scalable Computation of Aggregate Statistics. InProceedings of the 14 th USENIX Symposium on Networked Systems Design and Im- plementation (NSDI). USENIX Association, Boston, Massachusetts, USA, 259–282.https...

    2017

  10. [19]

    Anders P. K. Dalskov, Daniel Escudero, and Marcel Keller. 2021. Fan- tastic Four: Honest-Majority Four-Party Secure Computation With Malicious Security. InUSENIX Security Symposium. USENIX Associa- tion, 2183–2200

    2021

  11. [20]

    Ivan Damgård and Jesper Buus Nielsen. 2003. Universally Compos- able Efficient Multiparty Computation from Threshold Homomorphic Encryption. InCRYPTO (Lecture Notes in Computer Science, Vol. 2729). Springer, 247–264

    2003

  12. [21]

    Emma Dauterman, Mayank Rathee, Raluca Ada Popa, and Ion Stoica

  13. [22]

    Gonzalez, and Ion Stoica

    Ankur Dave, Chester Leung, Raluca Ada Popa, Joseph E. Gonzalez, and Ion Stoica. 2020. Oblivious coopetitive analytics using hardware enclaves. InEuroSys. ACM, 39:1–39:17

    2020

  14. [23]

    Daniel Demmler, Thomas Schneider, and Michael Zohner

  15. [24]

    Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, et al. 2019. The design and operation of{CloudLab}. In 2019 USENIX annual technical conference (USENIX ATC 19). 1–14

    2019

  16. [25]

    Daniel Escudero, Satrajit Ghosh, Marcel Keller, Rahul Rachuri, and Pe- ter Scholl. 2020. Improved Primitives for MPC over Mixed Arithmetic- Binary Circuits. InCRYPTO (2) (Lecture Notes in Computer Science, Vol. 12171). Springer, 823–852

    2020

  17. [26]

    Muhammad Faisal, Jerry Zhang, John Liagouris, Vasiliki Kalavri, and Mayank Varia. 2023. TVA: A multi-party computation system for secure and expressive time series analytics. In32nd USENIX Security Symposium (USENIX Security 23). USENIX Association, Anaheim, CA, 5395–5412.http...

    2023

  18. [27]

    Wenjing Fang, Shunde Cao, Guojin Hua, Junming Ma, Yongqiang Yu, Qunshan Huang, Jun Feng, Jin Tan, Xiaopeng Zan, Pu Duan, et al. 2024. SecretFlow-SCQL: A Secure Collaborative Query Platform.Proceedings of the VLDB Endowment17, 12 (2024), 3987–4000

    2024

  19. [28]

    1938.Statistical Tables for Biological, Agricultural and Medical Research

    Ronald Aylmer Fisher and Frank Yates. 1938.Statistical Tables for Biological, Agricultural and Medical Research. Oliver and Boyd

    1938

  20. [29]

    Goodrich

    Michael T. Goodrich. 2011. Data-oblivious external-memory algo- rithms for the compaction, selection, and sorting of outsourced data. InSPAA. ACM, 379–388

    2011

  21. [30]

    J. Gray, A. Bosworth, A. Lyaman, and H. Pirahesh. 1996. Data cube: a relational aggregation operator generalizing GROUP-BY, CROSS-TAB, and SUB-TOTALS. InProceedings of the Twelfth International Confer- ence on Data Engineering. 152–159. doi:10.1109/ICDE.1996.492099

    1996

  22. [31]

    Pa- terson

    Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, and Kenneth G. Pa- terson. 2018. Pump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries. InCCS. ACM, 315–331

    2018

  23. [32]

    Koki Hamada, Ryo Kikuchi, Dai Ikarashi, Koji Chida, and Katsumi Takahashi. 2012. Practically Efficient Multi-party Sorting Protocols from Comparison Sort Algorithms. InICISC (Lecture Notes in Computer Science, Vol. 7839). Springer, 202–216

    2012

  24. [33]

    Feng Han, Lan Zhang, Hanwen Feng, Weiran Liu, and Xiangyang Li. 2022. Scape: Scalable Collaborative Analytics System on Private Database with Malicious Security. In2022 IEEE 38th International Con- ference on Data Engineering (ICDE). 1740–1753. doi:10.1109/ICDE53745. 2022.00176

    2022

  25. [34]

    W Daniel Hillis and Guy L Steele Jr. 1986. Data parallel algorithms. Commun. ACM29, 12 (1986), 1170–1183

    1986

  26. [35]

    Paulo Jesus, Carlos Baquero, and Paulo Sérgio Almeida. 2014. A survey of distributed data aggregation algorithms.IEEE Communications Surveys & Tutorials17, 1 (2014), 381–404

    2014

  27. [36]

    Joglekar, Rohan Puttagunta, and Christopher Ré

    Manas R. Joglekar, Rohan Puttagunta, and Christopher Ré. 2016. AJAR: Aggregations and Joins over Annotated Relations. InProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, Tova...

    2016

  28. [37]

    Kristján Valur Jónsson, Gunnar Kreitz, and Misbah Uddin. 2011. Secure multi-party sorting and applications. InProceedings of the 9 th Inter- national Conference on Applied Cryptography and Network Security (ACNS)(Nerja (Malaga), Spain)

    2011

  29. [38]

    Seny Kamara, Abdelkarim Kati, Tarik Moataz, Jamie DeMaria, Andrew Park, and Amos Treiber. 2024. MAPLE: MArkov Process Leakage attacks on Encrypted Search.Proc. Priv. Enhancing Technol.2024, 1 (2024), 430–446

    2024

  30. [39]

    Seny Kamara, Abdelkarim Kati, Tarik Moataz, Thomas Schneider, Amos Treiber, and Michael Yonli. 2022. SoK: Cryptanalysis of En- crypted Search with LEAKER - A framework for LEakage AttacK Evaluation on Real-world data. InEuroS&P. IEEE, 90–108

    2022

  31. [40]

    Darya Kaviani, Sijun Tan, Pravein Govindan Kannan, and Raluca Ada Poda. 2024. Flock: A Framework for Deploying On-Demand Dis- tributed Trust. InUSENIX Symposium on Operating Systems Design and Implementation

    2024

  32. [41]

    Gunawi, Cody Hammock, Joe Mambretti, Alexander Barnes, François Halbach, Alex Rocha, and Joe Stubbs

    Kate Keahey, Jason Anderson, Zhuo Zhen, Pierre Riteau, Paul Ruth, Dan Stanzione, Mert Cevik, Jacob Colleran, Haryadi S. Gunawi, Cody Hammock, Joe Mambretti, Alexander Barnes, François Halbach, Alex Rocha, and Joe Stubbs. 2020. Lessons Learned from the Chameleon Testbed. InProc...

    2020

  33. [42]

    Marcel Keller. 2020. MP-SPDZ: A versatile framework for multi-party computation. InProceedings of the 2020 ACM SIGSAC conference on computer and communications security. 1575–1590

    2020

  34. [43]

    Knott, S

    B. Knott, S. Venkataraman, A.Y. Hannun, S. Sengupta, M. Ibrahim, and L.J.P. van der Maaten. 2020. CrypTen: Secure Multi-Party Computation Meets Machine Learning. InProceedings of the NeurIPS Workshop on Privacy-Preserving Machine Learning

    2020

  35. [44]

    Simeon Krastnikov, Florian Kerschbaum, and Douglas Stebila. 2020. Efficient Oblivious Database Joins.Proc. VLDB Endow.13, 11 (2020), 2132–2145.http://www.vldb.org/pvldb/vol13/p2132-krastnikov.pdf

    2020

  36. [45]

    John Liagouris, Vasiliki Kalavri, Muhammad Faisal, and Mayank Varia

  37. [46]

    The libsodium Community. 2025. libsodium: A modern, portable, easy to use crypto library.https://libsodium.org/. [Online; accessed September 2025]. Baum, Buxbaum, Mathai, Faisal, Kalavri, Varia and Liagouris

    2025

  38. [47]

    Yehuda Lindell. 2020. Secure multiparty computation.Commun. ACM 64, 1 (dec 2020), 86–96. doi:10.1145/3387108

    2020 doi

  39. [48]

    Fukang Liu, Takanori Isobe, and Willi Meier. 2021. Cryptanalysis of Full LowMC and LowMC-M with Algebraic Techniques. InAd- vances in Cryptology – CRYPTO 2021: 41st Annual International Cryp- tology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part ...

    2021 doi

  40. [49]

    2005.Arithmetic and logic in computer systems

    Mi Lu. 2005.Arithmetic and logic in computer systems. John Wiley & Sons

    2005

  41. [50]

    Qiyao Luo, Yilei Wang, Wei Dong, and Ke Yi. 2024. Secure Query Processing with Linear Complexity.arXiv preprint 2403.13492(2024). arXiv:2403.13492 [cs.CR]https://arxiv.org/abs/2403.13492

    2024 arXiv

  42. [51]

    Junming Ma, Yancheng Zheng, Jun Feng, Derun Zhao, Haoqi Wu, Wenjing Fang, Jin Tan, Chaofan Yu, Benyu Zhang, and Lei Wang

  43. [52]

    Madden, Michael J

    Samuel R. Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. 2005. TinyDB: an acquisitional query processing system for sensor networks.ACM Trans. Database Syst.30, 1 (March 2005), 122–173. doi:10.1145/1061318.1061322

    2005

  44. [53]

    Apostolos Mavrogiannakis, Xian Wang, Ioannis Demertzis, Dimitrios Papadopoulos, and Minos Garofalakis. 2025. OBLIVIATOR: Oblivious Parallel Joins and other Operators in Shared Memory Environments. Cryptology ePrint Archive, Paper 2025/183.https://eprint.iacr.org/ 2025/183

    2025

  45. [54]

    McDiarmid and R.B

    C.J.H. McDiarmid and R.B. Hayward. 1996. Large Deviations for Quicksort.J. Algorithms21, 3 (Nov. 1996), 476–507. doi:10.1006/jagm. 1996.0055

    1996

  46. [55]

    Payman Mohassel, Peter Rindal, and Mike Rosulek. 2020. Fast Database Joins and PSI for Secret Shared Data. InProceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security(Virtual Event, USA)(CCS ’20). Association for Computing Machinery, New York, NY, U...

    2020

  47. [56]

    In2023 USENIX Annual Technical Conference (USENIX ATC 23)

    SecretFlow-SPU: A Performant and User-Friendly Framework for Privacy-Preserving Machine Learning. In2023 USENIX Annual Technical Conference (USENIX ATC 23). USENIX Association, Boston, MA, 17–33.https://www.usenix.org/conference/atc23/presentation/ ma

  48. [57]

    Muhammad Naveed, Seny Kamara, and Charles V. Wright. 2015. In- ference Attacks on Property-Preserving Encrypted Databases. InPro- ceedings of the 22nd ACM SIGSAC Conference on Computer and Com- munications Security (CCS ’15). 644–655. doi:10.1145/2810103.2813651

    2015

  49. [58]

    Thomas Neumann and Viktor Leis. 2024. A Critique of Modern SQL and a Proposal Towards a Simple and Expressive Query Language. In14th Conference on Innovative Data Systems Research, CIDR 2024, Chaminade, HI, USA, January 14-17, 2024. www.cidrdb.org.https: //www.cidrdb.org/cidr2...

    2024

  50. [59]

    Christopher Olston, Benjamin Reed, Adam Silberstein, and Utkarsh Sri- vastava. 2008. Automatic optimization of parallel dataflow programs. InUSENIX 2008 Annual Technical Conference(Boston, Massachusetts) (ATC’08). USENIX Association, USA, 267–273

    2008

  51. [60]

    Stanislav Peceny, Srinivasan Raghuraman, Peter Rindal, and Harshal Shah. 2024. Efficient Permutation Correlations and Batched Random Access for Two-Party Computation. Cryptology ePrint Archive, Paper 2024/547.https://eprint.iacr.org/2024/547

    2024

  52. [61]

    Mozilla. 2019. Next steps in privacy-preserving telemetry with Prio.https://blog.mozilla.org/security/2019/06/06/next-steps-in- privacy-preserving-telemetry-with-prio/. [Online; accessed Sep- tember 2025]

    2019

  53. [62]

    Rishabh Poddar, Sukrit Kalra, Avishay Yanai, Ryan Deng, Raluca Ada Popa, and Joseph M Hellerstein. 2021. Senate: A Maliciously-Secure MPC Platform for Collaborative Analytics. In30th USENIX Secu- rity Symposium (USENIX Security 21). USENIX Association, Van- couver, B.C.https:/...

    2021

  54. [63]

    Mayank Rathee, Yuwen Zhang, Henry Corrigan-Gibbs, and Raluca Ada Popa. 2024. Private Analytics via Streaming, Sketching, and Silently Verifiable Proofs. In2024 IEEE Symposium on Security and Privacy (SP). IEEE Computer Society, 194–194

    2024

  55. [64]

    Last access: September 2024

    Peter Rindal and Lance Roy. Last access: September 2024. libOTe: an efficient, portable, and easy to use Oblivious Transfer Library. https://github.com/osu-crypto/libOTe

    2024

  56. [65]

    Adi Shamir. 1979. How to Share a Secret.Commun. ACM22, 11 (Nov. 1979), 612–613. doi:10.1145/359168.359176

    1979

  57. [66]

    Xinyu Peng, Feng Han, Li Peng, Weiran Liu, Zheng Yan, Kai Kang, Xinyuan Zhang, Guoxing Wei, Jianling Sun, and Jinfei Liu. 2024. MapComp: A Secure View-based Collaborative Analytics Frame- work for Join-Group-Aggregation.arXiv preprint 2408.01246(2024). arXiv:2408.01246 [cs.CR]...

    2024

  58. [67]

    Transaction Processing Performance Council. 2024. TPC-H Bench- mark Specification. https://www.tpc.org/tpch/. [Online; accessed September 2024]

    2024

  59. [68]

    Transaction Processing Performance Council. 2024. TPC-H Bench- mark Specification (Query Definitions).https://www.tpc.org/TPC_ Documents_Current_Versions/pdf/TPC-H_v3.0.1.pdf. [Online; ac- cessed September 2024]

    2024

  60. [69]

    United Nations Global Working Group (GWG) Task Team on Privacy Preserving Techniques. 2023. Case study repository.https://unstats. un.org/wiki/display/UGTTOPPT/Case+study+repository

    2023

  61. [70]

    Nikolaj Volgushev, Malte Schwarzkopf, Ben Getchell, Mayank Varia, Andrei Lapets, and Azer Bestavros. 2019. Conclave: secure multi-party computation on big data. InProceedings of the Fourteenth EuroSys Conference 2019, Dresden, Germany, March 25-28, 2019, George Candea, Robbert...

    2019

  62. [71]

    SQLite. 2025. SQLite SQL database engine. https://sqlite.org/. [Online; accessed September 2025]

    2025

  63. [72]

    Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. InVLDB, Vol. 81. 82–94

    1981

  64. [73]

    Yuan Yu, Pradeep Kumar Gunda, and Michael Isard. 2009. Distributed aggregation for data-parallel computing: interfaces and implemen- tations. InProceedings of the ACM SIGOPS 22nd Symposium on Op- erating Systems Principles(Big Sky, Montana, USA)(SOSP ’09). As- sociation for Co...

    2009

  65. [74]

    Xin, Patrick Wendell, Tathagata Das, Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shiv- aram Venkataraman, Michael J

    Matei Zaharia, Reynold S. Xin, Patrick Wendell, Tathagata Das, Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shiv- aram Venkataraman, Michael J. Franklin, Ali Ghodsi, Joseph Gonzalez, Scott Shenker, and Ion Stoica. 2016. Apache Spark: a unified en- gine for big data...

    2016 doi

  66. [75]

    Wenhao Zhang, Xiaojie Guo, Kang Yang, Ruiyu Zhu, Yu Yu, and Xiao Wang. 2024. Efficient Actively Secure DPF and RAM-based 2PC with One-Bit Leakage. InIEEE Symposium on Security and Privacy, SP 2024, San Francisco, CA, USA, May 19-23, 2024. IEEE, 561–577. doi:10.1109/ SP54263.2024.00205

    2024

  67. [76]

    2021.Secure Yannakakis: Join-Aggregate Queries over Private Data

    Yilei Wang and Ke Yi. 2021.Secure Yannakakis: Join-Aggregate Queries over Private Data. Association for Computing Machinery, New York, NY, USA, 1969–1981.https://doi.org/10.1145/3448016.3452808

    2021

  68. [81]

    Beekman, Raluca Ada Popa, Joseph E

    Wenting Zheng, Ankur Dave, Jethro G. Beekman, Raluca Ada Popa, Joseph E. Gonzalez, and Ion Stoica. 2017. Opaque: An Oblivious and Encrypted Distributed Analytics Platform. InProceedings of the 14 th USENIX Symposium on Networked Systems Design and Implementation (NSDI). Boston...

    2017

  69. [82]

    As a result, the size of a shuffle group is greater than𝑇 , which is why this approach is limited to the honest-majority setting

    Each shuffle group can collectively hold a sharing of the input data. As a result, the size of a shuffle group is greater than𝑇 , which is why this approach is limited to the honest-majority setting

  70. [83]

    primary keys

    There must exist at least one shuffle group containing no corrupted parties, so that the composed permuta- tion𝜋is unknown to the adversary. Using the Fantastic Four protocol as a concrete example [19], here is a set of shuffle groups in the semi-honest setting: G={{𝑃 0,𝑃 1},{...

  71. [84]

    The aggregation keys are the same as the join keys

  72. [85]

    No aggregation key is also an aggregation output

  73. [86]

    primary key

    No aggregation input is also an aggregation output for a different aggregation. The intuition behind this theorem is that the conditions preclude any interaction between individual aggregations, so they can be evaluated in parallel: calling AggNet(𝑓 1,...) , Orq: Complex Analy...

  74. [2015]

    In22nd Annual Network and Distributed System Security Symposium, NDSS 2015, San Diego, California, USA, February 8-11, 2015

    ABY - A Framework for Efficient Mixed-Protocol Se- cure Two-Party Computation. In22nd Annual Network and Distributed System Security Symposium, NDSS 2015, San Diego, California, USA, February 8-11, 2015. The Internet Society. https://www.ndss-symposium.org/ndss2015/aby---frame...

    2015

  75. [2022]

    In2022 IEEE Symposium on Security and Privacy (SP)

    Waldo: A Private Time-Series Database from Function Secret Sharing. In2022 IEEE Symposium on Security and Privacy (SP). 2450–

  76. [2023]

    In20th USENIX Symposium on Networked Systems Design and Imple- mentation (NSDI 23)

    SECRECY: Secure collaborative analytics in untrusted clouds. In20th USENIX Symposium on Networked Systems Design and Imple- mentation (NSDI 23). USENIX Association, Boston, MA, 1031–1056. https://www.usenix.org/conference/nsdi23/presentation/liagouris

  77. [2468]

    doi:10.1109/SP46214.2022.9833611

    2022

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.