dataesr/scientific-paragraphs-categorization huggingface dataset:
The second squaring is inherent: even if we wanted to approximate p on a single value, we would still need to approximate p within , which requires Ω( 2 ) queries. (See Lemma E. 1 in Appendix E. ) In contrast, the first squaring ultimately comes from the fact that p is quadratic. We can avoid it if we use a linear function to approximate record values: this is exactly what happens in the ApproxValue algorithm. Pseudo-code of the ApproxValue algorithm is provided in Algorithm 2. The first step is to identify a record whose (symmetric) value is as close as possible to N/4. Hypothesis h 1 implies a suitable record exists. We call the resulting record the anchor record. Because its value is close enough to N/4, identifying such a record does not incur the quadratic cost of the function p as in the previous section, because that cost only occurs near the extremum of the function at (N + 1)/2.
However, this limited use of p does not incur a new square factor. In the end, we obtain the following result. Algorithm 2 Approximate database reconstruction algorithm. ApproxValue(Q): Input: Set of queries Q. Output: Function est-val approximating val. 1: Q ← |Q| 2: for each record r do 3: c(r) ← |{q ∈ Q : r ∈ q}| 4: v(r) ← arg min k |c(r)/Q -p(k)| 5: end for 6: r A ← arg min r | v(r) -N/4| Anchor record 7: v A ← v(r A ) Est. anchor value 8: for each record r do 9: c (r) ← |{q ∈ Q : r A , r ∈ q}| 10: w L ← arg min k∈[1, v A ] |d( v A , k) -c (r)/Q| 11: w R ← arg min k∈[ v A ,N ] |d( v A , k) -c (r)/Q| 12: if c(r)/Q < (p( w L ) + p( w R ))/2 then 13: est-val(r) ← w L 14: else 15: est-val(r) ← w R 16: end if 17: end for Theorem 4. 2. Let < 1/4. Assume the database under attack satisfies hypothesis h 1.
Experimental Results The ApproxValue attack achieves -ADR within O( -2 log -1 ) queries (for any given constant probability of success η < 1). We experimentally evaluate the tightness of this bound for a fixed number of records, R, and various numbers of possible values, N , so that we generate both dense and sparse databases. Record values are sampled uniformly at random, so hypothesis h 1 was satisfied with high probability. Our results are averaged over 500 databases, each with 500 randomly sampled queries. For the attack to succeed, the difference |est-val(r) -val(r)| should be at most N for records at least N away from the endpoints. The records whose values are near the endpoints may have been placed on the wrong side of N/2 relative to the anchor record. The bottom group of lines in Figure  2  shows, after every 10 queries, the maximum symmetric value of such misclassified records.
In Section 5. 4, we experimentally evaluate the bounds. In Section 5. 5 we show how the attack can be extended to recover approximate record values, rather than just their order, and present experimental results. Remark. Taking a step back, we note that what range query leakage reveals by itself is the order of records. For sparse databases, numerical information on values can be recovered when some form of additional frequency information is available to the adversary: such information can be the query distribution (as in Section 4), or an approximation of the database distribution (as in Section 5. 5).
The ApproxOrder Attack We now present the ApproxOrder algorithm, which targets sacrificial -AOR. Pseudo-code is given in Algorithm 3. The pseudo-code uses the following notation: if S is a node of a PQ-tree T , then the leaves of S are defined as the leaves of the subtree rooted at S, and denoted leaf(S); and root(T ) denotes the root of T. The idea is to first build the PQ-tree induced by the query access pattern leakage. The algorithm then locates the deepest node T in the tree such that the leaves below T contain a strict majority of all records. The algorithm returns as its output the set A i of leaves below each child C i of T , in the order of the children of T. Thus, the order between two records is learned by the adversary iff they appear below distinct children of T , and the order between the two records matches the order of the children of T below which they appear.
Analytically, our main result is as follows. The theorem assumes hypotheses h 2 and h 3 , which will be presented below, and a uniform query distribution. Theorem 5. 1. Let < 1/4. Assume the database under attack satisfies h 2 and h 3. Then after O 1 log 1 + 1 log 1 δ. queries, ApproxOrder achieves sacrificial -AOR with probability of success at least 1 -δ. The proof of Theorem 5. 1 is given in Appendix D. For any fixed constant probability of success, the algorithm succeeds using only O( -1 log -1 ) queries. As a direct corollary (setting = 1/N ), the Algorithm 3 The ApproxOrder Attack for sacrificial -AOR. ApproxOrder(Q): Input: Set of queries Q. Output: Disjoint subsets of records A 1 ,. , A k. 1: T ← PQ-tree built from Q. 2: T ← FindNodeT(T , root(T )) 3: C 1 ,. , C k ← children of T (in order) 4: return leaf(C 1 ),.
Moreover, the existence of the aforementioned queries inducing the partition is implied by an -net, so that ultimately the query complexity required for those queries to exist is directly derived from the -net theorem of VC theory. The result does require some assumptions about the existence of records having certain values in the database, namely hypotheses h 2 and h 3. Hypothesis h 2 requires that there exist two records with values a and b such that a, b ∈ [N/4, 3N/4], and ba ≥ N/3 (what really matters for the proof to go through is that a, b should be Ω(N ) away from 1, N and each other); and additionally that there exist at least three records with values within [ N, N +1-N ] that are more than N away from each other (note that a and b can be two of these values). Hypothesis h 3 requires that a strict majority of all records have a value within [ N, N + 1 -N ], and that no range of length N contains the values of a (strict) majority of all records.
On the face of it, h 2 and h 3 seem like they are restrictive in that they make several requirements on the database. But those requirements are quite mild. Both hypotheses essentially ask that the database should not be too concentrated over a few values. We have not encountered a real-world dataset that failed to satisfy those requirements. Further, only h 2 is actually required for the T node to exist and leak sacrificial -approximate order as claimed. The only point of hypothesis h 3 , which is more demanding, is to ensure that that node is the deepest node covering a majority of records, so that it can be easily located. But that is a theoretical concern: in our experiments, the desired T node was usually in the first two levels of the tree. Thus, the practically relevant hypothesis is h 2 , which only requires that the database should not be entirely concentrated near the endpoints.
In Appendix E. 2, we prove that the query complexity of our algorithm is optimal within a constant factor. More precisely, any (unbounded) adversary achieving sacrificial -AOR for all databases must require Ω( -1 log -1 ) queries. N = 10000 N = 100000 -1 log -1 -1 log -1 ApproxOrder experimental results R = 1000, compared to theoretical -net bound.
Experimental Results Assuming uniform queries, the ApproxOrder attack succeeds within O( -1 log -1 ) queries (for any given constant probability of success η < 1). We experimentally evaluate the tightness of this bound for a fixed number of records R, and various numbers of possible values, N , so that we generate both dense and sparse databases. Record values are sampled uniformly at random, so hypotheses h 2 and h 3 were satisfied with high probability. Our results are averaged over 500 databases, each with 500 randomly sampled queries. We measured the results after every 10 queries, and therefore sometimes needed a heuristic to identify a likely candidate for the Q node when the number of queries is very small. When the root node was not a Q node, our experiments chose the first child Q node that contained at least a third of the records.
We consider now another more realistic distribution on queries, namely fixed-width range queries. Such queries are widespread in practice: for example, the industrystandard TPC-H contains six explicit fixed-width range queries. For a given number of possible values N and width W ≤ N , there are N + 1 -W such ranges: [1, W ], [2, W + 1],. , [N + 1 -W, N ]. We experimentally evaluate how well the ApproxOrder attack performs for a dataset of R = 1000 records, N = 10000 possible values, and range queries of different widths. The results are in Figure  4. Unlike the case of uniform range queries, the limiting factor here in attaining -AOR is initially the too-high symmetric values of the sacrificed records. For small range widths (relative to the domain size, N ), these results are to be expected: when only a few queries have been observed, the total number of possible values that have matched any query so far is limited, and thus the maximum symmetric value of a record that is not in a bucket may be high.
From AOR to ADR We now show how our approximate ordering attack can be combined with a model of the database distribution π (commonly called an auxiliary distribution) to mount powerful -ADR attacks. That is, we leverage our approximate ordering attack above to achieve approximate database recovery. Our attack is somewhat reminiscent of the LMP auxiliary distribution attack, with two major differences: (1) it does not require the additional rank leakage used by LMP, and (2) we can study its performance analytically. We implemented the resulting -ADR attack and conducted experiments with several datasets representative of practical use cases of encrypted databases. As in the analysis of approximate order reconstruction, we will assume here that the query distribution is uniform only to make the exposition simpler-no part of our attack requires queries to be uniformly distributed.
Our attack takes as input the output of any algorithm achieving -AOR. It also takes a model of the database distribution π (which needs only to approximate the true database distribution), the query distribution π q , and the domain size N. It outputs an estimate for the underlying value of every record in the database. The pseudocode for the attack is given in Algorithm 4. Attack intuition. Briefly, the attack uses the observation that, for every disjoint subset of records A i (i ∈ [1,. , k]) given by -AOR, some information about the ranks of the records (i. e. their positions in a sorted list of all records) in the subset is revealed. Because each sacrificed record could be before A 1 or after A k the exact ranks are unknown, but lower and upper bounds can be computed. There are three main questions to answer in building an attack from this observation.
(1) How should the attack orient the A i ? (2) How many sacrificed records should go before A 1 ? (3) How should record values be estimated? We now describe our attack and how it resolves these three questions. The first step, record rank estimation orients the A i (question 1), estimates the number of sacrificed records less than A 1 (question 2), and produces an estimate of the range of ranks for each group. The second step, partition estimation, uses order statistics to estimate a range of values (i. e. a partition of [N ]) for each range of ranks obtained in the previous step. The third step, database estimation, estimates a value for the records in each group given the estimated partition (question 3). Record rank estimation. To recap, record rank estimation must (1) orient the A i s, (2) guess the number of sacrificed records less than A 1 , the first sorted group, and (3) estimate a range of ranks for each A i.
Our attack uses a heuristic for orienting the A i (this is function OrientSubsets in Algorithm 4): first, measure the proportion of records above and below the middle group. Call these quantities pa and pb , respectively. Then, compute the probability of a database value falling above (p a ) and below (p b ) the value N/2. If pa > pb and p a > p b , keep that orientation, else choose the other one. Though quite naive, below we will see this heuristic generally works well for real data distributions. To guess the number of sacrificed records below the first sorted group (EstimateRank in Algorithm 4), we use a more principled approach. Observe that the sacrificed records are exactly those with values either lower than the value of the smallest left query endpoint (call this value min ) or higher than the value of the largest right endpoint (call this r max ).
Database estimation. This is the simplest step-the previous step outputs a partition Experiment setup and data. We implemented Algorithm 4 in Python 2. 7 and ran all our experiments on an Ubuntu 16. 04 desktop with an Intel Core i7-6700 CPU, clocked at 3. 4GHz. We used an Algorithm 4 Recovering values from approximate order. Input: T 0 , R,π,π q ,N. Output: [x 1 , x 2 ,. , x R ] (∀i,x i ∈ [N ] ). 1: T ← OrientSubsets(T 0 ) 2: B ← GetBuckets(T ) 3: e ← GetEnds(T ) 4: r0 ← EstimateRank(e, π q , π) 5: for all b i ∈ B do 6: r i ← r i-1 + |b i | 7: ep i ← arg max k∈[N ] Pr X (r i ) = k 8: med b i ← RangeMedian(π, ep i-1 , ep i ) 9: for all ind ∈ b i do 10: cand[ind] = med b i 11: end for 12: end for 13: return cand existing C++ implementation  [Gro11]  of the PQ-tree data structure and used SWIG  [swi18]  to call it from Python.
We evaluate the attack on two datasets. The first is a database of registered pilots from the US government Federal Aviation Administration (FAA) [faa17]. It contains the ZIP code of residence for over 61,000 pilots nationwide. ZIP codes are five-decimal-digit numbers. The most significant digits reveal increasingly precise information about location-for example, the first three digits identify a neighborhood in large cities. For more information see  [Wik18]. For this experiment we use US Census data about ZIP code population as an auxiliary model of the distribution. Though there are some high-probability ZIP codes, the distribution is overall fairly uniform. Further, the FAA ZIP codes are not well-modeled by the census data -their statistical distance is about 0. 51. The second is a database of California (CA) state public employee salaries from 2016.
Salary data is sensitive both for cultural reasons and because of the possibility of blackmail. The database contains over 248,000 numbers between 0 and 762,000 US dollars. Most are salaries (i. e. at least 25,000 US dollars), but a sizeable fraction are in the low hundreds of dollars. We did not remove the low dollar amounts (as doing so could bias experiments in our favor) but we did truncate the few outliers over 500,000 US dollars. We used a database of around 120,000 New York (NY) state public employee salaries from the same year as auxiliary data for this experiment. Both NY and CA salary datasets are roughly Gaussian with means 73,000 and 67,000 respectively. Their statistical distance is about 0. 19. Rather than use the full CA salary database, in this experiment we subsampled random databases of 10,000 salaries and averaged the results to better understand how the attack performs on smaller databases.
Results and discussion. Our attacks will measure accuracy as percent error, that is, if the true value of a record is u and the attack guesses v, (for u, v ∈ [N ] the error for that record is |u -v|/N. The baseline guessing attack for this accuracy measure is predicting the median of the database distribution for every record. Figure  5  shows the results of the ZIP code experiment averaged over 20 randomlygenerated transcripts and the salary experiments averaged over 10 randomly subsampled databases each with 10 randomly-generated transcripts. We also show the baseline guessing accuracy. The variance was low in all our experiments with 25 or more queries. With only ten queries, the variance for the 75th percentile error is quite high, which we intuitively expect-with so few queries many groups of records will be large.
) The attack on ZIP codes performed extremely well. With only ten queries, we are able to guess the first digit correctly for over half the records on average. Concretely, about half the database records would have their state of residence partially revealed with only ten queries. With only one hundred queries, we recover the first two digits (or a small window with only a few possibilities) for a majority of the records in the database. For the attack on salaries, the accuracy of the baseline guessing attack is artificially low because of the skew of the distribution-the max value (which we use as the denominator to compute percent error) is much larger than all but a tiny fraction of salaries. Thus, the baseline guessing attack having 5% error translates to 25,000 USD, but most salaries are within 25,000 USD of the median, so baseline guessing performs very poorly on most salaries.
To see that the triangle inequality holds, observe that for any i, j, and k, any query in ∆(C i , C j ) is in ∆(C i , C k ) or ∆(C k , C j ). This allows us to generalize the use of -nets in ApproxOrder to arbitrary query classes. If the adversary observes a set of queries that is an -net for the symmetric difference concept space, then it must be the case that for any subset S of records with identical access pattern, the underlying values V of those records satisfy diam γ (V ) def = max i,j∈V γ π (i, j) ≤. Thus, if we simply group together records that have the same access pattern, then the existence of an -net provides an upper bound on the distance (with respect to the measure γ) of records in the same group. Essentially, access pattern leakage from any query class reveals a kind of approximate equality between the underlying values of the records in the database.
This approximate equality depends both on the query class and the query distribution. For range queries, we used this approximate equality to build the ApproxOrder attack and reveal a great deal of information with few queries. However, closeness in the metric γ may not be practically interesting for all query classes and distributions: for example, access pattern leakage from the "query class" which is sampled uniformly at random from 2 [N ] is unlikely to reveal anything interesting. Nevertheless, for many query classes used in practice, closeness in this distance metric can lead to serious privacy breaches. For example, for prefix queries, two values being close in this metric implies they have a common prefix. We will show a simple attack that allows an adversary to reveal which records in the database are approximately equal according to the distance metric γ π.
Prefix and Suffix Queries Next, we show how to instantiate the approximate equality attack for a practically relevant query class. For a set Σ ≤ of all strings with length ≤ from some alphabet Σ, define a prefix query q to be a string in the set ∪ j=1 Σ j. In text search, prefix queries are usually indicated by a trailing asterisk "*". For any element j ∈ Σ ≤ , define the predicate q(j) to be 1 if either q = j or q is a prefix of j, and 0 otherwise. As an example, take the database {cat, carbon}. A prefix query "c*" on these two values would return both, but "carb*" would return only the second one. Although prefix queries are technically a subset of range queries, there are three crucial differences which obviate the use of previous attacks on range queries: prefix queries do not reveal order, they cannot overlap without one query being contained in the other, and the number of queries matching any fixed string is constant.
Further, if the adversary has a model of the database distribution, it can use frequency analysis to learn the characters of each record, one at a time (reminiscent of the climax of the science-fiction movie WarGames). A WarGames attack on prefix search. Most modern text and web search systems support prefix queries on unstructured data  [es18] , and they are ubiquitous in software-as-a-service (SaaS) products like Salesforce, ServiceNow, and Dropbox [sal18, sno18, dro18]. A common [dro18, sal18] design pattern for these systems is to send a prefix query for every character the user types in the search bar. Since users may find their desired result without finishing their query, the distribution of queries is heavily biased towards shorter prefixes. Our attack in this setting is simple. First, the adversary runs the approximate equality attack described above, obtaining a partition of the records in the database.
This same analysis can be iterated for the rest of the characters. Experiments. We implemented the attack using last name data from the Fraternal Order of Police (FOP) database dump, posted online in 2016. It contains the personal information of over 600,000 law enforcement officers in the United States. For auxiliary data, we used public US Census statistics  [Bur16]  on last name frequencies. We also ran the attack on the FAA ZIP code dataset from the experiments in Section 5. 5, but it performed quite poorly, primarily due to the auxiliary data being a poor model of the ZIP code distribution. In 9 out of 10 trials with only 500 prefix queries sampled according to the distribution described above, we were able to partition the records into groups with at least a one-character prefix in common.
Let γ(i, j) def = Pr πq [ ∆(C i , C j ) ] be the distance metric induced on [N ] by Q and π q. Consider any algorithm that takes as input a database of size R with elements in [N ], together with the access pattern leakage of m queries sampled from π q , and outputs an approximation DB such that γ(DB[i], DB [i]) ≤ for all i ∈ [1,. , R], with probability of success at least 1 -δ (over the choices of queries from π q ). Then m is in Ω( d + 1 log 1 δ ). This result is a direct application of PAC learning theory: an algorithm that takes any database as input and outputs a DB satisfying the stated condition is a PAC learner for the concept space C defined in the theorem statement. We can thus apply a general lower bound  [EHKV89]  on the sample complexity of PAC learning to conclude that m must be in Ω( d + 1 log 1 δ ).
With a smaller number of queries m, there will be, with probability at least δ, two values in [N ] whose distance γ is strictly greater than , but which every query given to the algorithm accessed in the same way. This result is not easy to interpret, so we briefly reflect on its implications. First, it holds even if the adversary knows the exact query distribution and database distribution. Next, note that the same lower bound holds for the existence of an -net: if the queries fail to form an -net for the metric γ, then some records that are more than apart in γ cannot be separated based on access pattern. Since any approximate attack should be able to distinguish such records, in some sense this approximate equality attack is a minimal approximate attack. For example, consider both our sacrifical -ADR and -AOR attacks from Sections 4 and 5.
Conclusions This work initiates the application of learning theory to attacks on encrypted databases which leak access patterns. Our learning-theoretic viewpoint lets us build and analyze approximate reconstruction attacks which are both nearly-optimal in query complexity and effective on real data. We believe this work represents an exciting first step towards building a cohesive theory of security in the presence of access pattern leakage. Towards this, we recommend two main research directions for future work to pursue: first, extend our attacks to other query types of practical importance like edit distance, wildcard, and substring queries. Second, study and apply other results from learning theory, such as active or online learning, to access pattern leakage attacks and defenses. increased, essentially by a factor (at most) two.