Private Queries with Sigma-Counting
Jun Gao, Jie Ding · 2025
Read Private Queries with Sigma-Counting by Jun Gao, Jie Ding (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07018.txt.
Introduction
Jun Gao and Jie Ding present sigma-counting in a 2025 paper on answering counting queries without exposing private data. Many applications ask a database how many items fall inside a range of values that a client picks. If a program answers many such queries, its answers can leak facts about single people in the data.
One common defence adds random noise to each answer, spending from a fixed privacy budget over time. That can cap how many queries are allowed and can blur accuracy. Answers can also break the ordering that nested queries should keep. Sigma-counting instead builds on sigma-algebra, the mathematics of set collections. The authors show their design can sharpen accuracy a great deal while still holding the promised privacy level, even under very many queries.
Catalog record
| CREATOR | Jun Gao, Jie Ding |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-07018
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Private Queries with Sigma-Counting Jun Gao, Jie Ding Abstract Many data applications involve counting queries, where a client specifies a feasible range of variables and a database returns the corresponding item counts. A program that produces the counts of different queries often risks leaking sensitive individual-level information. A popular approach to enhance data privacy is to return a noisy version of the actual count. It is typically achieved by adding independent noise to each query and then control the total privacy budget within a period. This approach may be limited in the number of queries and output accuracy in practice. Also, the returned counts do not maintain the total order for nested queries, an important feature in many applications. This work presents the design and analysis of a new method, sigma-counting, that addresses these challenges. Sigma-counting uses the notion of sigma-algebra to construct privacy-preserving counting queries. We show that the proposed concepts and methods can significantly improve output accuracy while maintaining a desired privacy level in the presence of massive queries to the same data. We also discuss how the technique can be applied to address large and time-varying datasets. I Introduction In a growing number of machine learning applications, clients will query the counts of items satisfying particular constraints from a database. Common examples are counting of user clicks in recommendation systems ( Ricci et al. 2011 ) , digital marketing ( Krishna 1995 ) , and nowcasting ( Youn and Cho 2016 ) . Specifically, in the digital marketing business, a commercial client may query the count of potential users in a particular area from a third-party database; in urban planning, a client may query the count of a cohort of residents from a government database. These counting queries are often realized by putting particular criteria on the available variables. Examples are ‘individuals who live in city A,’ ‘users who log in more than three times a day and who are above 30,’ and ‘residents whose salary are more than $5k and who own at least one car.’ However, counting queries are calculated from cohorts of individuals, and it inevitably leaks some individual-level information. For example, whether a particular person has been to a local clinic may be sensitive information but may be revealed by an adversary, who sends a large number of queries to the clinic. Because there is a risk of leaking an individual’s sensitive information, we need a privacy-preserving technique to manage the counting queries. A popular and intuitive method to enhance data privacy is to add independent noise to each query’s actual count. Depending on the type of noise to add, there are different privacy mechanisms such as the Gaussian or Laplacian mechanisms. Under a suitable data privacy framework, trade-offs between the privacy and noise level can be rigorously quantified. We will base our analysis on the framework of differential privacy (DP) ( Dwork et al. 2006b ; Dwork 2011 ) , a notion particularly suitable for database queries. It quantifies privacy leakage by a privacy parameter \varepsilon that bounds the likelihood ratio of the perturbed output under two databases differing in a single row. A smaller value of \varepsilon indicates better privacy. We will take the Laplacian mechanism as an example. To achieve \varepsilon privacy leakage, we need the noise scale to be proportional to 1/\varepsilon . When there are k separate queries to the same database, differential privacy’s composition property ensures that the overall privacy leakage is k\varepsilon ( McSherry 2009 ) . For many governmental or commercial entities that provide database services, it is critical to improve the response accuracy and number of allowed queries simultaneously. However, in most practical applications, a database manager will need to pre-specify the total privacy budget (at least within a period). The budget is an upper bound of privacy leakage (e.g., the above k\varepsilon ). Once the privacy leakage goes beyond the budget, the database will no longer respond. This directly leads to trade-offs between the number of allowed queries and the accuracy of each response. In practice, however, there is usually a massive number of queries to the same database. To maintain a fixed privacy budget, the database manager needs to impose a considerable amount of noise on each query response, which hinders the output accuracy. Moreover, another critical yet often overlooked issue is that the returned counts do not maintain the total order for nested queries. The total order means that if two queries, corresponding to sub-databases A_{1} and A_{2} , satisfy A_{1}\subset A_{2} , it holds that N(A_{1})\leq N(A_{2}) . Here N(\cdot) denotes the returned count. Maintaining total order is crucial in many real-life applications, e.g., data publishing by the U.S. Bureau of Labor Statistics ( Groshen 2015 ) , recommendation systems ( Ricci et al. 2011 ) , and various downstream machine learning based on ordinal data ( Oh et al. 2015 ) . I-A Contributions We identify two critical challenges of generating privacy-preserving counting responses, namely the ‘budget excess’ and ‘non-monotonic counts’. Then, we present the design and analysis of a new method, sigma-counting, that addresses the challenges above. Sigma-counting uses the notion of sigma-algebra to construct privacy-preserving counting queries to a database. It enjoys the following properties: 1) High utility in the presence of a large number of queries, and 2) Monotonicity, meaning that the returned count of a subset A_{2} will not be smaller than that of a larger subset A_{1} ( A_{1}\subseteq A_{2} ). Sigma-counting fully utilizes the nature of database structure: many queries are overlapping, and many sub-databases are repetitively included in the queries. We show that the proposed novel concepts and methods can significantly improve output accuracy while achieving the same privacy level. On the other hand, given the same privacy budget and output accuracy, sigma-counting can respond to many more queries than existing methods. We also extend the proposed method to handle databases with a large number of attributes or time-varying entries. I-B Related work A popular framework of evaluating data privacy is through differential privacy (DP) ( Dwork et al. 2006b ; Dwork 2011 ) , a cryptographically motivated definition of privacy that has been studied over the past decade across different fields ( Chaudhuri et al. 2011 ; Sarwate and Chaudhuri 2013 ; Dong et al. 2019 ; Neunhoeffer et al. 2020 ; Vietri et al. 2020 ) . DP measures privacy leakage by bounding the likelihood ratio of the output of an algorithm under two databases differing in any single individual. DP is statistical database privacy, which is particularly suitable for privatizing individual identity in a database. Unlike database privacy, there is the notion of local privacy that aims to protect privacy during the data collection stage, without trusted database management. Examples are local differential privacy ( Evfimievski et al. 2003 ; Dwork et al. 2006b ; Kasiviswanathan et al. 2011 ) , secure multi-party computing ( Yao 1982 ; Chaum et al. 1988 ) and homomorphic encryption ( Gentry 2009 ; Armknecht et al. 2015 ) . Our work focuses on the database privacy scenario. It involves three parties: data owner (often an individual) who provides sensitive data, database (a trusted third-party) who manages data collected from their owners), and