dataesr/scientific-paragraphs-categorization huggingface dataset:
We show that the problem of reconstructing encrypted databases from access pattern leakage is closely related to statistical learning theory. This new viewpoint enables us to develop broader attacks that are supported by streamlined performance analyses. As an introduction to this viewpoint, we first present a general reduction from reconstruction with known queries to PAC learning. Then, we directly address the problem of -approximate database reconstruction ( -ADR) from range query leakage, giving attacks whose query cost scales only with the relative error , and is independent of the size of the database, or the number N of possible values of data items. This already goes significantly beyond the state of the art for such attacks, as represented by Kellaris et al. (ACM CCS 2016) and Lacharité et al.
(IEEE S&P 2018). We also study the new problem of -approximate order reconstruction ( -AOR), where the adversary is tasked with reconstructing the order of records, except for records whose values are approximately equal. We show that as few as O( -1 log -1 ) uniformly random range queries suffice. Our analysis relies on an application of learning theory to PQ-trees, special data structures tuned to compactly record certain ordering constraints. We then show that when an auxiliary distribution is available, -AOR can be enhanced to achieve -ADR; using real data, we show that devastatingly small numbers of queries are needed to attain very accurate database reconstruction. Finally, we generalize from ranges to consider what learning theory tells us about the impact of access pattern leakage for other classes of queries, focusing on prefix and suffix queries.
Introduction This article concerns the analysis of leakage from encrypted databases. The latter are cryptographic techniques that allow a client to outsource a database to an untrusted server while maintaining the ability to make queries on the data. Fuller et al. [FVY + 17] give a comprehensive survey of this area. All known techniques represent a trade-off between security and efficiency, with various forms of leakage being intrinsic to these approaches. For example, without taking special precautions such as using oblivious memory techniques, the access pattern, that is, the set of records returned in response to queries, leaks to the server. While in many cases, formal security proofs are able to establish that nothing more than the access pattern leaks to the adversarial server, there still remains the question: what is the practical impact of this leakage? A more refined version of the question is: If an encrypted database supports a certain class of queries, but leaks the access pattern, then how damaging is that leakage as a function of the number of queries? The setting of this article is one in which only access pattern is leaked to an adversarial server.
Access pattern leakage is inherent to nearly all practical constructions of encrypted databases, and the survey by Fuller et al. [FVY + 17] overviews a plethora of schemes to which such attacks apply. In the particular case of range queries, all known practical solutions leak this information  [LMP18]. Nevertheless, the above question is currently answered using ad hoc cryptanalysis, requiring cumbersome and laborious analyses to establish the impact of leakage as a function of the number of queries. The central aim of our work is to transform this situation by bringing statistical learning theory to bear on the problem.
Database Reconstruction: State of the Art Range queries are fundamental to the operation of databases, and have rightfully received significant attention in the attack literature. The state of the art for attacks based on leakage from range queries is represented by the work of Kellaris-Kollios-Nissim-O'Neill (KKNO)  [KKNO16]  and Lacharité-Minaud-Paterson (LMP)  [LMP18]. KKNO gave attacks showing that O(N 4 log N ) queries suffice to achieve Full Database Reconstruction (FDR), that is, to reconstruct the exact value for every record. Here, N is the number of different possible values, which we assume without loss of generality come from the interval [1, N ]. For dense data, where every possible value is in at least one record, this was improved to O(N 2 log N ) queries by KKNO and then to O(N log N ) queries by LMP.
All of these results assume the query distribution is uniform on ranges (though for the results in the dense setting, this assumption is needed only to facilitate analysis and not for the algorithms to succeed). A typical value of N might be, say, 125 for data pertaining to age in years, making even an O(N 4 log N ) attack potentially worrisome. But for many data types, N can be much larger -think of discrete data such as numerical zip codes, timestamps, or salary data. For large N , especially when the data is sparse rather than dense (as is typically the case), FDR is much too expensive (KKNO proved a general lower bound of Ω(N 4 ) on the number of range queries needed), and really too strong an attack goal. For this reason, LMP introduced the notion of -Approximate Database Reconstruction ( -ADR), where the adversary's goal is to find the value of every record up to an (additive) error of N rather than exactly.
Overview of Our Contributions None of the aforementioned attacks exploiting range query leakage is fully satisfactory: FDR is too expensive for large N , while the only ADR algorithm we have (from LMP's work  [LMP18] ) relies on a density assumption and its query cost still scales with N. This presents a potentially misleading picture of the impact of leakage for range queries, one which may lead to underestimating the potential damage. Additionally, leakage from other kinds of queries has received little attention; nor have other attack settings of practical importance such as known-query attacks. In this work, we show how statistical learning theory effectively addresses the problem of database reconstruction, yielding new results across a range of settings. A common thread through all of our results is the analysis of concept spaces over the set of all queries.
The results we apply from learning theory rely on the VC dimension of the concept space, intuitively a measure of how complex it is. (See Section 2 for a short primer on statistical learning theory. ) PAC learning and known-query attacks. In Section 3, we show that database reconstruction given a set of known queries can be recast as an instance of Probably Approximately Correct (PAC) learning, and standard results from that field can predict how many queries are needed to achieve reconstruction. We present this reduction to PAC learning as an introduction to how we view database reconstruction as a learning problem, as well as an illustration of the power of this viewpoint. While the attack model here is rather powerful, it is considered realistic in some recent literature [ZKP16, GSB + 17, GMN + 16]; our analysis largely resolves the question of how damaging such attacks can be.
Indeed, our algorithm can be seen as generalizing the ideas of KKNO to the ADR setting, and making it scale-free. In Section 4. 3, we introduce our second attack, the ApproxValue algorithm, which achieves sacrificial -ADR using only O( -2 log -1 ) uniformly random queries, but under the additional, mild requirement that the database contains a record whose value is in the range [0. 2N, 0. 3N ] (or its reflection). Setting = 1/N in our algorithm again yields a FDR algorithm with complexity O(N 2 log N ) that works whether data is sparse or dense, assuming only a single favorably-located record. Our proof techniques for both attacks are rooted in learning theory, using VC dimension and the concept of -samples. Both attacks also come with general lower bounds showing that they are optimal in the number of queries needed within a logarithmic factor.
However, they do require that the database is dense, whereas we wish to investigate this question in the general setting. Sacrificial -AOR. In Section 5, we introduce the attack target of sacrificial -Approximate Order Reconstruction (sacrificial -AOR). This asks that the order of all records should be recovered, except for records that are within N of each other (which the algorithm groups), and the sacrificed records whose values are within N of 1 or N. Thus, save for sacrificed values, sacrificial -AOR reveals the order of any two records as soon as they are at least N apart. As our main result in Section 5, we introduce the ApproxOrder algorithm, which takes as input the access pattern leakage of some range queries, builds a PQ-tree, and extracts from it approximate order information. The algorithm does not use any knowledge on the query distribution.
In particular, it does not require uniformly random queries, nor even i. i. d. queries. If, for the sake of analyzing the algorithm, we assume a uniform query distribution, ApproxOrder achieves sacrificial -AOR after only O( -1 log -1 ) queries. Once again, our analysis relies on learning theory, more specifically the concept of an -net, and shows that the attack is scale-free. We also prove that the query complexity of our algorithm is optimal within a constant factor. For = 1/N , -AOR yields exact order reconstruction for all records. If the database is dense, then recovering order directly implies recovering values, so we obtain full database reconstruction in O(N log N ) queries, recovering as a special case the main result of LMP. The ApproxOrder algorithm is not merely theoretical, but highly practical.
There is no barrier (such as an i. i. d. query assumption) to running it on real data. Our experiments in Section 5. 4 show that the attack behaves as predicted by the theory. As an example, for N = 10 6 , after only 500 queries, the attack is able to fully order records, except for records whose difference in value is less than 2% of the support size. From -AOR to -ADR. A crucial question remains: what are the implications of the AOR attack? That is, what does learning approximate order reveal to the attacker? It is well known that leaking record order is highly damaging, if only because it can be closely correlated to record values using an auxiliary distribution [NKW15, GSB + 17]. In fact, the severe implications of order leakage is one of the main motivations behind the development of second-generation encrypted databases schemes that attempt to hide that leakage, as argued in  [LMP18].
To concretize that point, in Section 5. 5 we present an attack showing how approximate database values can be reconstructed from approximate order information: we extend our sacrificial -AOR attack to a sacrificial -ADR attack using an auxiliary model of the database distribution. (As per  [NKW15, LMP18] , such distributions are often available. ) We conduct experiments with real datasets of US ZIP codes and public sector salaries in Section 5. 5. The resulting sacrificial -ADR attack is effective: with only 50 queries, we can learn the first two digits of a ZIP code (often identifying a city) for a majority of records in the target database. With 100 queries on salaries, we can predict a majority of salaries to within 10000 USD. The table in Figure  1  compares our different attacks on range queries.
Beyond range queries. As illustration of the power of the viewpoint we have taken, in Section 6, we generalize approximate reconstruction to other query classes and analyze the resulting attacks using tools from learning theory. Using generalization error as a metric γ on the values in the database, we show that all query classes with finite VC dimension reveal the distance (in γ) between the underlying values of records, which allows an attacker to group records whose values are close. Further, we show how to use an -net to precisely analyze how many queries are needed to guarantee all groups of records have small diameter according to γ. We construct, analyze, and evaluate the first reconstruction attack on prefix queries. We conclude the section with a general lower bound, via a reduction to PAC learning, relating the query class's VC dimension, attack accuracy, and number of queries needed for any reconstruction attack using access pattern leakage.
Related Work Dautrich Jr. and Ravishankar  [JR13]  introduced the use of PQ-trees in revealing the order of records in a database with access pattern leakage. They experimentally measured, in some special cases, how quickly the number of orders contained in the tree decreases as more queries are gathered. We use also use PQ-trees for revealing order from range queries, but otherwise our aims are distinct from theirs-their paper focuses primarily on heuristic measures of security after some ordering information is revealed. Kellaris et al. (KKNO)  [KKNO16]  described the first exact reconstruction attack on range queries with access pattern leakage; Lacharité et al. (LMP)  [LMP18]  improved the results of KKNO in the dense setting, obtaining an O(N log N ) exact reconstruction attack; see Section 1.
Attack Goal Data density Proposed attack Generic lower bound Source KKNO FDR any O(N 4 log N ) Ω(N 4 ) [KKNO16] KKNO FDR dense O(N 2 log N ) - [KKNO16] LMP FDR dense N log N + O(N ) 1 2 N log N -O(N ) [LMP18] LMP -ADR dense 5 4 N log -1 + O(N ) N log -1 -O(N ) [LMP18] GeneralizedKKNO sacrificial -ADR any O( -4 log -1 ) Ω( -4 ) Section 4. 2 ApproxValue sacrificial -ADR any * O( -2 log -1 ) Ω( -2 ) Section 4. 3 ApproxOrder sacrificial -AOR any * O( -1 log -1 ) Ω( -1 log -1 ) Section 5 Figure  1 : Comparison of database reconstruction attacks that use access pattern leakage from range queries chosen uniformly at random. N is the number of possible plaintext values. All attacks are up to global reflection. Generic lower bounds are for any attack targeting the same goal under the same assumptions.
PAC Learning and Database Reconstruction Attacks In this section, we begin exploring the connection between learning theory and database reconstruction attacks. Concretely, we demonstrate a connection between approximate database reconstruction and "Probably Approximately Correct" (PAC) learning  [Val84]  in the setting where the attacker has access pattern leakage from some known queries. For a brief introduction to PAC learning, see Section 2. 4. Reconstruction via PAC learning. The attack setting we consider here is one in which an attacker has observed the access pattern leakage from a number of known queries drawn i. i. d. from a fixed query distribution (which the adversary does not need to know). The assumption of known queries is somewhat stronger than has been considered previously in this literature; however, some recent works have argued that it is realistic [GSB + 17, GMN + 16] on the grounds that the adversary is able to make some queries or has compromised an honest user.
A crucial question is the relationship between the number of known queries and the amount of information the adversary can learn about the database itself, cf. Section 1. We will see that this question is largely resolved via a simple reduction to PAC learning in the known query setting. We can think of a database DB with R records having values in [N ] as being a vector of length R with values in [N ]; the value of record j is DB[j]. We construct a concept space C = (Q, C) as follows. The points in the ground set are the possible queries q ∈ Q. We write q(i) = 1 when value i ∈ [N ] matches query q. We set C i = {q ∈ Q | q(i) = 1}. We then define C = {C i : i ∈ [N ]}. With this set-up, we have the following result. Theorem 3. 1. Let Q be a class of queries and C = (Q, C) be the concept space constructed as above.
Let π q be any distribution over Q. Let d be the VC dimension of C, and assume d is finite. Then, there is an adversary such that for any database DB, given as input m ∈ O( d log d δ ) queries sampled from π q and their access pattern leakage on DB, the adversary outputs a database DB such that Pr πq [ q(DB[j]) = q(DB [j]) ] ≤ holds simultaneously for all j ∈ [R], with probability at least 1 -Rδ. This theorem requires some explanation. In the statement, we chose to use the generalization error Pr πq [ q(DB[j]) = q(DB [j]) ] as the accuracy measure. This is intended to surface the core points without adding unnecessary detail, but it may also make the result hard to interpret. Section 6 studies in more detail how generalization error relates to traditional notions of attack accuracy. The proof proceeds via a natural reduction to PAC learning.
The adversary gets as input m known queries along with their access pattern leakage (i. e. which records match the query) for each of the R records in the database. The core observation is that the access pattern is a binary classification of each database element; further, each database value is a concept in C. This means that the task of reconstructing each database element can be seen as R PAC learning experiments for the concept space C defined above. The adversary simply runs the PAC learner from Theorem 2. 7 R times, invoking it once for each record j. For each invocation, the adversary gives the learner as input the m queries and their access patterns (i. e. the 0/1 labellings) for record j. Each time the learner is run, it outputs a hypothesis H ind ∈ C corresponding to an element of  [N ].
Extensions. The above result can be extended in several ways. First, a symmetric and nearly identical result can be proven about query reconstruction attacks in the presence of known records. Such a result would proceed as above except flipping the role of the queries and values in the concept space. An interesting extension of the above result (and its twin for known database elements) is a setting where the adversary has both known and unknown queries (or database elements). One question which our PAC learning approach can address is how much information the adversary learns about the unknown information elements by PAC learning with its known information. Some authors have argued recently that the even stronger setting of chosen query attacks is a realistic threat model for encrypted databases.
With chosen queries, the corresponding learning setting is not PAC learning, but active learning  [DL]. Active learning is similar to PAC learning except the learner can adaptively query an oracle which labels points in X according to the unknown concept. Interestingly, both the folklore binary-search attack on order-revealing encryption and the Zhang et al. [ZKP16]  document-injection attack can be viewed as active learning algorithms. We note that lower bounds on the sample complexity of PAC learning can be used to prove that certain kinds of security guarantees hold even in the presence of some known or chosen queries (or database elements). In Section 6 we state and prove one such result which does not assume any records or queries are known to the adversary. Closing remark. In the encrypted database literature, it has become apparent that known-and chosen-query attacks are damaging.
Sacrificial Approximate Database Reconstruction In this section, we turn to range queries, and introduce sacrificial -approximate database reconstruction (sacrificial -ADR). Sacrificial -ADR asks to successfully recover the value of every record in the database within N , for some target precision , save for records whose value lies within N of 1 or N. The term -approximate means that reconstruction is within an error of N , as in  [LMP18]. The term sacrificial means the attack "sacrifices" records whose value lies within N of the endpoints. We explain the need for this and provide a full definition in Section 4. 1. The rest of the section presents two results. In Section 4. 2, we extend KKNO's database reconstruction attack  [KKNO16]  to sacrificial -ADR. A direct application of the -sample theorem from learning theory shows the dependency on N vanishes: the required number of queries becomes O( -4 log -1 ), making the attack scale-free.
In Section 4. 3, we introduce a new algorithm, ApproxValue, for sacrificial -ADR with a mild additional hypothesis h 1 : the database contains at least one record whose value lies in [0. 2N, 0. 3N ] ∪ [0. 7N, 0. 8N ]. Under this hypothesis, ApproxValue achieves sacrificial -ADR within only O( -2 log -1 ) queries. The analysis also uses the -sample theorem, but is somewhat more involved. This attack shows the pathological nature of KKNO's lower bounds on query complexity for FDR. An experimental validation in Section 4. 4 supports the analysis, and shows that the constants in the O notation are empirically very small. As noted in the introduction, the previous two results also imply full database reconstruction within O(N 4 log N ) queries in general, and O(N 2 log N ) when h 1 is satisfied.
Definition of Sacrificial -ADR We now formally define sacrificial -approximate database reconstruction (sacrificial -ADR). Let > 0 be the desired precision. Let est-val(r) denote the value predicted by the algorithm for record r. Sacrificial -ADR is said to succeed iff one of the following two events occur: 1. For every record r such that N ≤ val(r) ≤ N + 1 -N , |est-val(r) -val(r)| < N. 2. For every record r such that N ≤ val(r) ≤ N + 1 -N , |est-val(r) -(N + 1 -val(r))| < N. The fact that reconstruction is only possible up to reflection is inherent to this setting, as seen in  [KKNO16, LMP18]. It is required that for all values (except those within N of the extrema), either the estimated value is within N of the correct value, or its reflection. But whichever case it is holds simultaneously for all values.
In other words, only one bit of information is missing globally regarding the reflection symmetry. Note that setting = 1/N yields full database reconstruction (FDR), i. e. exact value reconstruction for all records. Finally, we come to explaining why our attack needs to be sacrificial. Sacrificing values that are close to 1 and N is inherent to a scale-free attack under a uniform query assumption. Intuitively, these values are harder to recover because fewer range queries touch them. The probability of hitting records with values 1 and N with a uniform range query is 2/(N + 1) = O(1/N ). This remains true for any record whose value is within O(1) of 1 or N : hitting one of these records requires Ω(N ) queries. If they are not hit, then it is impossible for the algorithm to differentiate them or determine which records are on the same side of N/2-reflection symmetry cannot be determined globally for those values.
The ApproxValue Attack Next we introduce the ApproxValue algorithm, which achieves sacrificial -ADR within O( -2 log -1 ) queries, saving roughly a square root factor over the generalization of KKNO's algorithm presented above. In particular, setting = 1/N yields full database reconstruction within O(N 2 log N ) queries, significantly improving on KKNO's original O(N 4 log N ) bound. This comes at the cost of the attack requiring a mild hypothesis about the database. The hypothesis h 1 asks that there exist at least one record in the database with a value in [0. 2N, 0. 3N ] ∪ [0. 7N, 0. 8N ]. The constants here are for concreteness; others would work as well. The record does not need to be known to the adversary, it suffices that it exist in the database. We note that an hypothesis such as h 1 is necessary to achieve a query complexity of O( -2 log -1 ): in Appendix E, we prove that any algorithm achieving sacrificial -ADR in full generality requires Ω( -4 ) queries.
With h 1 we prove a similar lower bound of Ω( -2 ), so ApproxValue is optimal in data within a logarithmic factor. We believe that O( -2 ) (resp. N 2 ) better captures the actual cost of -ADR (resp. full reconstruction) on a real database, assuming a uniform query distribution: the O( -4 ) cost of the original attack was because the bound had to account for pathological cases where h 1 is not satisfied. Such databases have all records concentrated around 1, N/2 and N. None of the real datasets used in our experiments had this property. Next we explain how we gain a square factor over the previous attack, which required O( -4 log -1 ) queries. Above we saw that the main 4 term comes as a result of being squared twice: first, to move from the estimate c/Q of p(val(r)) to the symmetric value of the record, and second by applying the -sample theorem to uniformly approximate p across all values.