Unleashing the power of the ellipsis: Improving the accuracy of the sparse vector technique (SVT) with exponential noise

The sparse vector technique (SVT) is a fundamental tool in differential privacy, disclosing only one bit per query. Previous conservative privacy analyses overestimated privacy risk, leading to excessive injection of Laplacian/Gaussian noise. The paper proposes a new privacy analysis that accounts for SVT's low-information nature, broadens the applicable noise types, and determines that exponential noise is optimal among all evaluated noises; combined with threshold correction and a follow-up strategy, evaluation metrics improve by up to 50%.