Lucas Piske

Private histogram computation is a fundamental building block for many data analytics tasks, enabling frequency analysis without revealing individual inputs. Existing protocols achieving robustness against malicious clients and servers typically require three servers with limited adversarial tolerance, restricting practicality. In this work, we present Paras, the first two-server protocol for private histogram computation that achieves robustness against collusion between a malicious server and arbitrarily many malicious clients. Paras builds upon distributed point function-based approaches and introduces novel consistency checks leveraging vector oblivious linear evaluation (VOLE) to enforce both input correctness and output integrity. To realize these checks, we design two new cryptographic primitives: (1) aBV, an authenticated bit verification protocol that ensures VOLE committed shares correspond to valid bits, and (2) adIPA, an authenticated double inner product argument that enables secure consistency checks across two different VOLE sessions. These primitives may be of independent interest for other secure computation tasks. We show that Paras is highly efficient and scalable: clients incur minimal cost independent of domain size, while servers achieve low per-client runtime, communication, and storage even at scale. For example, with 8192 clients over a domain of 128 inputs, each server requires only 14 ms runtime and 24 KB communication per client.

We present unconditionally perfectly secure protocols in the semi-honest setting for several functionalities: (1) private elementwise equality; (2) private bitwise integer comparison; and (3) bit-decomposition. These protocols are built upon a new concept called Shared Oblivious Transfer (Shared OT). Shared OT extends the one-out-of-N String OT by replacing strings with integers modulo M and allowing additive secret-sharing of all inputs and outputs. These extensions can be implemented by simple local computations without incurring additional OT invocations. We believe our Shared OT may be of independent interest. Our protocols demonstrate the best round, communication, and computational complexities compared to all other protocols secure in a similar setting. Moreover, all of our protocols involve either 2 or 3 rounds.