We propose protocols for query evaluation under the secure multi-party computation model. Our first result is theoretical, which provides circuit constructions for evaluating conjunctive queries under degree constraints, with polylogarithmic depth and size matching the polymatroid bound up to polylogarithmic factors. These circuits yield protocols against any adversary. Our second result is a practical protocol for free-connex join-aggregate query evaluation under secure two-party computation model against semi-honest adversary. This protocol is instance optimal up to one logarithm factor, and greatly outperforms the best previous result in all experiments. Our third result is also a practical protocol. It evaluates any join-aggregate query on foreign-key acyclic schema under secure two...[ Read more ]

We propose protocols for query evaluation under the secure multi-party computation model. Our first result is theoretical, which provides circuit constructions for evaluating conjunctive queries under degree constraints, with polylogarithmic depth and size matching the polymatroid bound up to polylogarithmic factors. These circuits yield protocols against any adversary. Our second result is a practical protocol for free-connex join-aggregate query evaluation under secure two-party computation model against semi-honest adversary. This protocol is instance optimal up to one logarithm factor, and greatly outperforms the best previous result in all experiments. Our third result is also a practical protocol. It evaluates any join-aggregate query on foreign-key acyclic schema under secure two-party computation model against semi-honest adversary. The complexity of the protocol is linear to the input size, which is also instance optimal.