Aspects of the current subject matter are directed to performing privacy-preserving analytics over sensitive data without sharing plaintext data. According to an aspect, a system includes at least one data processor and at least one memory storing instructions which, when executed by the at least one data processor, result in operations including: receiving, from each of a plurality of clients, a utility score and a partial noise value; performing, based on the received utility scores and the partial noise values, a secure multi-party computation of a privacy-preserving statistic, the performing of the secure multi-party computation of the privacy-preserving statistic further comprising determining a noisy utility score for each data value in a domain of output values and selecting a highest noise utility score from the determined noisy utilities scores; and providing, based on the selected highest utility score, an output value for the privacy-preserving statistic.