2025/06/25 by Quentin Hillebrand, Hillebrand, Quentin, Vorapong Suppakitpaisarn +3
Computer Science · #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2506.20234
openalex publication_date 2025/06/25 · openalex created_date 2025/10/09 · openalex updated_date 2026/07/28
In this work, we propose a differentially private algorithm for publishing matrices aggregated from sparse vectors. These matrices include social network adjacency matrices, user-item interaction matrices in recommendation systems, and single nucleotide polymorphisms (SNPs) in DNA data. Traditionally, differential privacy in vector collection relies on randomized response, but this approach incurs high communication costs. Specifically, for a matrix with N users, n columns, and m nonzero elements, conventional methods require Ω(n × N) communication, making them impractical for large-scale data. Our algorithm significantly reduces this cost to O(ε m), where ε is the privacy budget. Notably, this is even lower than the non-private case, which requires Ω(m log n) communication. Moreover, as the privacy budget decreases, communication cost further reduces, enabling better privacy with improved efficiency. We theoretically prove that our method yields results identical to those of randomized response, and experimental evaluations confirm its effectiveness in terms of accuracy, communication efficiency, and computational complexity.