2024/11/08 by Jui‐Ting Hu, Hu, Jerry Yao-Chieh, Han Liu +6
Computer Science · Mathematics · #Artificial Intelligence (cs.AI) #Complexity and Algorithms in Graphs #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · pdf · doi:10.48550/arxiv.2411.05750
openalex publication_date 2024/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a database of bit strings A1,…,Am∈ \0,1\n, a fundamental data structure task is to estimate the distances between a given query B∈ \0,1\n with all the strings in the database. In addition, one might further want to ensure the integrity of the database by releasing these distance statistics in a secure manner. In this work, we propose differentially private (DP) data structures for this type of tasks, with a focus on Hamming and edit distance. On top of the strong privacy guarantees, our data structures are also time- and space-efficient. In particular, our data structure is ε-DP against any sequence of queries of arbitrary length, and for any query B such that the maximum distance to any string in the database is at most k, we output m distance estimates. Moreover, - For Hamming distance, our data structure answers any query in \widetilde O(mk+n) time and each estimate deviates from the true distance by at most \widetilde O(k/eε/log k); - For edit distance, our data structure answers any query in \widetilde O(mk2+n) time and each estimate deviates from the true distance by at most \widetilde O(k/eε/(log k log n)). For moderate k, both data structures support sublinear query operations. We obtain these results via a novel adaptation of the randomized response technique as a bit flipping procedure, applied to the sketched strings.