Private set operators are functions over private inputs that multiple parties can jointly evaluate while revealing only the prescribed output. Two such operators are intersection and join-and-compute, realized respectively by private set intersection (PSI), outputting the intersection of two sets, and private join and compute (PJC), outputting aggregates such as cardinality, sum, and inner product over matching records. Classical PSI and PJC target one-shot two-party settings where each party holds its full input. Real deployments rarely fit this model: servers maintain persistent datasets reused across many clients, and inputs are often split across multiple data owners. Existing protocols fall short: they lack cross-execution consistency, require per-execution server reprocessing, or incur substantial overhead for distributed inputs.

This thesis develops efficient and provably secure protocols for private set operators in practical client-server settings, through three schemes together with new cryptographic primitives:

(1) Inspired by password-checkup applications, we study client-output PSI in which the server publishes a one-time, linear-size encoding of its set, after which each client executes PSI with the server at cost linear only in its own set, with simulation-based security against malicious adversaries. A key ingredient is an efficient oblivious verifiable unpredictable function (OVUF).

(2) We introduce committed vector oblivious linear evaluation (C-VOLE), which generates VOLE correlations on a pre-committed vector and serves as a unifying tool for zero-knowledge proofs of committed values and actively secure multi-party computation. Built on a tailored LPN-based commitment, our matching C-VOLE protocols exploit the commitment structure to minimize the cost of binding the committed vector to the VOLE correlation, and efficiently instantiate a maliciously secure server-output PSI protocol.

(3) Beyond intersection, we study computation over matching records from distributed datasets, motivated by applications such as privacy-preserving ad conversion measurement. We propose the first efficient approximate PJC protocol with communication sublinear in the input size. Its core is a new adaptation of the Alon-Matias-Szegedy (AMS) sketch, redesigned for efficient evaluation under fully homomorphic encryption via structured randomness.