2022/04/05 by Chen, Justin Y., Narayanan, Shyam, Xu, Yinzhan
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2204.02335
We revisit the problem of privately releasing the all-pairs shortest path distances of a weighted undirected graph up to low additive error, which was first studied by Sealfon [Sea16]. In this paper, we improve significantly on Sealfon's results, both for arbitrary weighted graphs and for bounded-weight graphs on n nodes. Specifically, we provide an approximate-DP algorithm that outputs all-pairs shortest path distances up to maximum additive error O(√(n)), and a pure-DP algorithm that outputs all pairs shortest path distances up to maximum additive error O(n2/3) (where we ignore dependencies on ε, δ). This improves over the previous best result of O(n) additive error for both approximate-DP and pure-DP [Sea16], and partially resolves an open question posed by Sealfon [Sea16, Sea20]. We also show that if the graph is promised to have reasonably bounded weights, one can improve the error further to roughly n√(2)-1+o(1) in the approximate-DP setting and roughly n(√(17)-3)/2 + o(1) in the pure-DP setting. Previously, it was only known how to obtain O(n1/2) additive error in the approximate-DP setting and O(n2/3) additive error in the pure-DP setting for bounded-weight graphs [Sea16].