{'fraction_non_alphanumeric': 0.03899874532087641, 'fraction_numerical': 0.008440568649612708, 'mean_word_length': 4.337318058553324, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Don’t Be a Tattle-Tale: Preventing Leakages through Data Dependencies on Access Control Protected Data

—We study the problem of answering queries when (part of) the data may be sensitive and should not be leaked to the querier. Simply restricting the computation to non-sensitive part of the data may leak sensitive data through inference based on data dependencies. While inference control from data dependencies during query processing has been studied in the literature, existing solution either detect and deny queries causing leakage, or use a weak security model that only protects against exact reconstruction of the sensitive data. In this paper, we adopt a stronger security model based on full deniability that prevents any information about sensitive data to be inferred from query answers. We identify conditions under which full deniability can be achieved and develop an efﬁcient algorithm that minimally hides non-sensitive cells during query processing to achieve full deniability. We experimentally show that our approach is practical and scales to increasing proportion of sensitive data, as well as, to increasing database size.

Example 1. Consider an Employees table ( Figure 1) and a FGAC policy by a user Bobby to hide his salary per hour (SalPerHr) from all the queries by other users. If the semantics of the data dictate that any two employees who are faculty should have the same SalPerHr, then hiding SalPerHr of Bobby would not prevent its leakage from a querier who has access to Carrie's SalPerHr.
In general, leakage may occur from direct/indirect inferences due to different type of data dependencies, such as conditional functional dependencies (CFD) [10], denial constraints [11], aggregation constraints [12], and/or functional constraints that exist when a dependent data values are derived/computed using other data values as shown below.
Example 2. Consider the Employee and Wage tables shown in Table 1. Let Danny specify FGAC policies to hide his SalPerHour in Employee Table and Salary in Wage Table. Suppose there exists a constraint that employees with role Staff cannot have a higher salary per hour than a faculty in the state of California. Using Bobby's salary per hour that is leaked in Example 1, the new constraint about the staff salary, and the functional constraint between that Salary and the fields function of WorkHrs and SalPerHr, information about the salary and the salary per hour of Danny will be leaked even though they are sensitive.
To gain insight into the extent to which leakage could occur due to data semantics, we conducted a simple experiment on a synthetic dataset [11], [13] that contains the address and tax information of individuals. The tax data set consists of 14 attributes and has associated with it 10 data dependencies, an example of which is a denial constraint "if two persons live in the same state, the one earning a lower salary has a lower tax rate". An adversary can use the above dependency to infer knowledge about the sensitive cells. Suppose the salary attribute of an individual is sensitive and therefore hidden. If the disclosed data contains information about another individual who lives in the same state and has a lower tax rate, an adversary can infer the upper bound of this individual's salary using the dependency. To demonstrate this leakage, we considered an attribute with large number of data dependencies defined on them (e.g., state) to be sensitive, and thus, replaced its values by NULL. We then used the state-of-the-art data cleaning  Table   software, Holoclean [14], as a real-world attacker to reconstruct the NULL values associated with the sensitive cells. Holoclean was able to reconstruct the actual values of the state 100% of the time highlighting the importance of preventing leakage through data dependencies on access control protected data.
Prior literature has studied the challenge of controlling inferences about sensitive data using data dependencies and called it the "inference control problem". [8]. Existing techniques used to protect against inferences can be categorized based on when the leakage prevention is applied [15]. In the first category, inference channels between sensitive and non-sensitive attributes are detected and controlled at the time of database design [16], [17]. A database designer uses methods in this category to detect and prevent inferences by upgrading classification of inferred attributes. However, they result in poor data availability if a significant number of attributes are marked as sensitive to prevent leakages. The second category of works include detection and control at the time of query answering. Works such as [15], [18] determine if answers to the query could result in inferences about sensitive data using data dependencies, and reject the query if such an inference is detected. Such query control approaches can lead to rejection of many queries when there are non-trivial number of sensitive cells and background knowledge. Another limitation of the prior work is the weak security model used in determining how to process queries. All prior work on inference control considers a query answer to leak sensitive data if the answer can be used to reconstruct the exact value of a sensitive object. Leakages that do not reveal the exact value but, perhaps, limit the values a sensitive object may take are not considered as leakage. For instance, in Example 2 above, since the constraints do not reveal Danny's exact salary but only that it is below $200 per hour, prior works will not consider it to be a leakage even though querier/adversary could eliminate a significant number of possible domain values based on the data constraints. As we explain in detail in Section 8, the existing solutions to the inference control cannot be easily generalized to prevent such leakages.
In this paper, we study the problem of answering user queries under a new, much stronger model of security -viz., full deniability. Under full deniability, any new knowledge learned about the sensitive cell through data dependencies is considered as leakage. Thus, eliminating a domain value as a possible value a attribute / cell can take violates full-deniability. One can, of course, naively, achieve full deniability by hiding the entire database. Instead, our goal is to identify the minimal additional non-sensitive cells that must be hidden so as to acheive full deniability. In addition, we require the algorithm that identifies data to hide in order to achieve full deniability to be efficient and scalable to both large data sets and to large number of constraints.
We study our approach to ensuring full deniability during query processing under two classes of data dependencies 1 : • Denial Constraints (DCs): that are general forms of data dependencies expressed using universally quantified first order logic. They can express commonly used types of constraints such as functional dependencies (FD) and conditional functional dependencies (CFD) and are more expressive than both • Function-based Constraints (FCs): that establish relationships between input data and the output data it is derived from, using functions. Such constraints arise naturally when databases stored materialized aggregates or when data sensor data, collected over time (e.g., from sensors), is enriched (using appropriate machine learning tools) to higher level observations.
To achieve full deniability, we first develop a method for Inference Detection, that detects, for each sensitive cell, the nonsensitive cells that could result in violation of full deniability. The candidate cells identified by Inference Detection are passed to the second function, Inference Protection that minimally selects the non-sensitive data to hide to prevent leakages. Our technique is geared towards maximizing utility when preventing inferences for large number of sensitive cells and their dependencies. After hiding additional cells, Inference Detection is invoked repeatedly to detect any indirect leakages on the sensitive cells through the new set of hidden cells and their associated dependencies. These methods are invoked cyclically until no further leakages are detected either on the sensitive cells or any additional cells hidden by Inference Protection. Using these two different methods, we are able to achieve the security, utility, and performance objectives of our solution.
The main contributions in our paper are: • A security model, entitled Full deniability to protect against leakage of sensitive data due to data semantics in the form Denial Constraints and Function-based Constraints. • Identification of conditions under which full deniability can be achieved and efficient algorithms for inference detection and protection to achieve full deniability while only minimally hiding additional non-sensitive data. • A prototype middleware (∼10K LOC) that works alongside DBMS to ensure full deniability given set of dependencies and policies. • Experimental results on two different data sets show that our approach is efficient and only minimally hides non-sensitive cells while achieving full deniability. Paper Organization. We introduce the notations used in the paper and describe access control policies and data dependencies in 1. Other data dependencies such as Join dependencies (JD) and Multivalued dependencies are not common in a clean, normalized database and therefore not interesting to our problem setting. A schema level data dependency / set δ , S ∆ An instantiated data dependency / set Cells(δ) Cells involved inδ Preds(δ) The set of predicates associated with a DC Preds(δ, c) The set of predicates inδ that involves the cell c Preds(δ\c) The set of predicates inδ without the cell c V(C) Set of value assignments for cells in C I(c | V,δ) Inference function for the cell c Section 2. In Section 3, we present the security model -full deniability -proposed in this work. In Section 4, we describe how the leakage of sensitive data occurs through dependencies and introduce function-based constraints. We present in Section 5, the algorithms for inference detection and protection along with optimizations to improve utility. In Section 7, we present results from an end-to-end evaluation of our approach with two different data sets and different baselines. In Section 8 we go over the related work and we conclude the work by summarizing our contributions, and possible future extensions in Section 9. We will use the cell-based representation of a relation to simplify notation when discussing the fine-grained access control policies and data dependencies. Figure 1 shows two tables, the Employee table with cells c 1 to c 28 and the Wages table with cells c 29 to c 40 . Note that in the cell-based notation each table, row, column corresponds to a set of cells. For instance, the second tuple/row of Wages table is the set of cells {c 32 , c 33 , c 34 } and the column for attribute Zip in the Employee table is the set {c 3 , c 10 , c 17 , c 24 }. Each cell has an associated value. For instance, the value of cell c 11 is "CA".

Access Control Policies
Data sharing is controlled using access control policies, or simply policies. We classify users U as data owners, who set the access control policies, and as queriers, who pose queries on the data. Ownership of data is specified at tuple level and a data owner of a tuple may specify policies marking one or more cells (c i ) in the tuple t as sensitive against queries by other users. When another user queries the database, the returned data has to be 2. We say the domain size in the context of an attribute with discrete domain values and for continuous attributes we discretize their domain values into a number of non-overlapping bins. policy compliant (i.e., policies relevant to the user are applied to the query results).
Definition 1 (Sensitive Cell). Given a policy P , we say that a cell c is sensitive to a user U if after applying P c is replaced with NULL. The set of cells sensitive to the user U is denoted by C S U or simply C S when the user is clear from the context.
We assume queries have associated metadata that contains information about the querier 3 .
Definition 2 (Query model). : The SELECT-FROM-WHERE query posed by a user U is denoted by Q. In our model, we consider that queries have associated metadata which consists of information about the querier and the context of the query. This way, we assume that for any given query Q, it contains the metadata such as identity of the querier (i.e., Q querier ) as well as the purpose of the query (i.e., Q purpose ). For example, Q querier ="John" and Q purpose ="Analytics".
A policy P is expressed as <OC, SC, AC>, where AC corresponds to the action, i.e., either deny or allow, SC corresponds to the subject condition i.e, the user to whom the policy applies (e.g., identity of the querier, or the group for which the policy applies, in case queriers are organized into groups), and OC corresponds to a set of object conditions i.e., the cells on which the policy is to be enforced. Each object condition OC i consists of three parts: A policy P is represented using the 3-tuple {R, σ, Φ} where R is the relation to which P applies, σ is the set of selection conditions that select the set of tuples in R to which P applies, and finally Φ is the projection conditions that identifies the set of columns to which the policy is applied. The application of an policy is done by a function over the database that returns NULL for a cell if it is disallowed by the policy or the original cell value if it is allowed. This is modelled after FGAC policy models used in previous works [6], [20]. We denote the set of cells identified by OC i as C OCi .
Definition 3 (Sensitive Cell). Given a policy P =<OC, SC, AC>, we say that a cell c is sensitive to a user U if c ∈ C OCi where OC i ∈ OC, U = SC.querier, and AC = deny. The set of cells sensitive to the user U is denoted by C S U or simply C S when the context is clear. Example 3. An example policy from scenario in Section is <{Employee, EName = "Carrie Sea", SalPerHr}, {"John Doe", }, {deny}>. The policy specifies that access to tuples with EName = "Carrie Sea" in the Employee table should be denied (i.e., such tuples are sensitive ) to the Querier = "John Doe" .

Data Dependencies
Semantics of data is expressed in the form of data dependencies, that restrict the set of possible values a cell can take based on the values of other cells in database. Several types of data dependencies have been studied in the literature such as foreign keys, functional dependencies (FDs), and conditional functional dependencies (CFDs), etc. We consider two types of dependencies as follows: Denial Constriants (DC), is a first-order formula of the form ∀ t i , t j , . . . ∈ D, δ : ¬(Pred 1 ∧ Pred 2 ∧ . . . ∧ Pred N ) where Pred i 3. In general, policies control access to data based not just on identity of the querier, but also on purpose [19]. Thus, metadata associated with the query will also contain purpose in addition to the querier identity.
is the ith predicate in the form of t x [A j ]θt y [A k ] or t x [A j ]θconst with x, y ∈ {i, j, . . .}, A j , A k ∈ R, const is a constant, and θ ∈ {=, >, <, =, ≥, ≤}. DCs are quite general -they can model dependencies such as FDs & CFDs and are flexible enough to model much more complex relationships among cells. Data dependencies in the form of DCs has been used in recent prior literature for data cleaning [21], [22], query optimization [23], and secure databases [15], [24]. Moreover, systems, such as [11], have been designed to automatically discover DCs in a given database. This is the type of DCs considered throughout the paper.
Function-based Constraints (FCs) capture the relationships between derived data and its inputs. As described in Example 2, the Salary in the Wages table (see Table 1) is a attribute derived using WorkHrs and SalPerHr i.e., Salary := fn(WorkHrs, SalPerHr). In general, given a function f n with r 1 , r 2 , . . . , r n as the input values and s i as the derived or output value, the FC can be represented by f n(r 1 , r 2 , . . . , r n ) = s i .

FULL DENIABILITY
In this section, we discuss the assumptions in our setting and present the concept of view of a database for the querier and formalize an inference function with respect to the view and data dependencies. We formally define our security model -Full Deniability -based on the inference function and use it to determine the leakage on sensitive cells.

Assumptions
We will assume that tuples (and cells in tuples) are independently distributed except for explicitly specified dependencies that are either learnt automatically or specified by the expert. The database instance is assumed to satisfy the data dependencies. The querier, who is the adversary in our setting, is assumed to know the dependencies and can use them to infer the sensitive data values. This assumption leads to a stronger adversary than the standard adversary considered by many algorithms for differential privacy or traditional privacy notions like k-anonymity or access controls, which assumes the adversary knows no tuple correlations (or tuples are independent). A querier is free to run multiple queries and can attempt to make inferences about sensitive data based on the results of those queries. Two queriers, however, do not collude (i.e., share answers to the queries). We note that if such collusions were to be allowed, it would void the purpose of having different access control policies for different users.
As queriers are service providers or third parties who are interested in obtaining user data to provide a service and therefore we assume that queriers and data owners do not overlap. We also assume that a querier cannot apriori determine if a cell is sensitive or not (i.e., they do not know the access control policies) 4 . To see why this is important, consider a FD defined on the Employee table (Table 1) Zip→State. Suppose c 11 (State = "CA") is sensitive based on the policy and in order to prevent inferences using the FD, let c 24 be hidden. If the querier has knowledge that c 24 is hidden due to our approach (and hence know that c 11 was sensitive), they can deduce that c 25 and c 11 have the same value. 4. In the extended version of our paper, we have included a discussion on relaxing both these assumptions.

Querier View
For each querier, given the set of policies applicable to the querier, the algoritm first determines which cell is sensitive to them. Such cells are set to NULL in the view of the database shared with the querier. As noted in the introduction, if only the sensitive cells are set to NULL and all the non-sensitive cells retain their true values, the querier may infer information about the sensitive cells through the various dependencies defined on the database. It is necessary, therefore, to set some of the non-sensitive cells to NULL in order to prevent leakages due to dependencies. Henceforth, we will refer to the cells, both sensitive and non-sensitive, whose values will be replaced by NULL as hidden cells, denoted by C H . We now present the concept of a querier view on top of which queries are answered.
Definition 4 (Querier View). The set of value assignments for a set of cells C in a database instance D with respect to a querier is denoted by V(C) or simply V when the set of cells is clear from the context. The value assignment for a cell could be either the true value of this cell in D or NULL value (if it is hidden).
We also define a concept of the base view of database for a querier, denoted by V 0 . In V 0 , all the cells in D are set to be NULL. We consider the information leaked to the querier based on computing the query results over the base view V 0 as the least amount of information revealed to the querier. For instance, the base view may provide querier with information about number of tuples in the relation, but, by itself it will not reveal any further information about the sensitive cells, despite what dependencies hold over the database. Our goal in developing the algorithm to prevent leakage would be to determine a view V for a querier that hides the minimal number of cells, and yet, leaks no further information than the base view. Next, we define an inference function that captures what the querier can infer about a sensitive cell in a view using dependencies.

Inference Function
Dependencies such as denial constraints are defined at schema level, such as the dependency δ on Table 1: Given a database instance D, the schema level dependencies can be instantiated using the tuples. If the Employee Table has 4 tuples, then there are 4 2 = 6 number of instantiated dependencies at cell level. For example, one of the instantiated dependencies for δ isδ where {c 11 , c 18 , c 12 , c 19 , c 14 , c 21 } correspond to t 2 [State], dependencyδ ∈ S ∆ , when every cell c i ∈ Cells(δ) is assigned with a value x i ∈ Dom(c i ), denoted byδ(. . . , c i = x i , . . .), the expression associated with an instantiated dependency can be evaluated to either True or False. Note that since the database is assumed to satisfy all the dependencies, all of the instantiated dependencies must evaluate to True for any instance of the database. We use the notation I(c | V) to denote the set of values (inferred by the querier) that the cell c can take given the view V but without any knowledge of the set of dependencies. Likewise, I(C | V) denote the cross product of the inferred value sets for cells in the cell set C, i.e., I(C | V) = × c∈C I(c | V). Clearly, if in a view, a cell is assigned its original/true value (and not NULL) then I(c | V) consists of only its true value. We will further assume that: Assumption 1. Let V be a view and c be a cell with value NULL assigned to it in V. I(c | V) = Dom(c). That is, a querier without knowledge of dependencies, cannot infer any further information about the value of the cell beyond its domain.
Knowledge of the dependencies can, however, lead the querier to make inferences about the value of the cell. The following example illustrates that the querier may be able to eliminate some domain values as possible assignments of Dom(c).  Table 1 be sensitive for a querier and let the view V be the same as the original table with c 14 replaced with NULL. Furthermore, letδ (Eqn. (1)) (that refers to c 14 ) hold. If the querier is not aware of this dependencyδ, the inferred value set for c 14 is the full domain, i.e., I(c 14 | V) = Dom(c 14 ). However, knowledge ofδ leads to the inference that c 14 ≤ 200 since the other two predicates (c 11 = c 18 , c 12 = c 19 ) are True.
Definition 5 (Inference Function). Given a view V and an instantiated dependencyδ for a cell c i ∈ Cells(δ), the inferred set of values for c i byδ is defined as where n denotes the size of the cell set |Cells(δ)| and x i ∈ Dom(c i ). Given a view V and a set of instantiated dependencies S ∆ = {. . . ,δ, . . .}, the inferred value for a cell c is the intersection of the inferred values for c i over all the dependencies, i.e.,

Security Definition
We can now formally define the concept of full deniability of a view. Note that given a view V and a set of dependencies S ∆ , the following always holds: I(c|V, S ∆ ) ⊆ I(c|V 0 , S ∆ ). We say that a V achieves full deniability if the two set are identical i.e., the query results does not enable the querier to infer anything further about the database than what the querier could infer from the V 0 (which, as mentioned in Sec. 3.2, is the least amount of information leaked to the querier).
Definition 6 (Full Deniability). Given a set of sensitive cells C S in a database instance D and a set of instantiated dependencies S ∆ , we say that a querier view V achieves full deniability if for all c * ∈ C S ,

FULL DENIABILITY WITH DATA DEPENDENCIES
In this section, we first identify conditions under which denial constraints could result in leakage of sensitive cells (i.e., violation of full deniability) and further consider leakages due to functionbased constraints (discussed in Section 2).

Leakage due to Denial Constraints
An instantiated denial constraint consists of multiple predicates in the form ofδ = ¬(Pred 1 ∧ . . . ∧ Pred N ) where each predicate is either Pred N = c θ c or Pred N = c θ const. A valid value assignment for cells in C(δ) has at least one of the predicates iñ δ evaluating to False so that the entire dependency instantiatioñ δ evaluates to True. Based on this observation, we identify a sufficient condition to prevent a querier from learning about a sensitive cell c * ∈ C S in an instantiated DCδ i with value assignments.
As shown in Example 4, for an instantiated DCδ with cell value assignments, when all the predicates except for the predicate containing the sensitive cell (Pred(δ\c * )) evaluates to True, a querier can learn that the remaining predicate Pred(δ, c * ) evaluates to False even though c * is hidden. Thus, it becomes possible for the querier to learn about the value of a sensitive cell from the other non-sensitive cell values. We can prevent such an inference by hiding additional non-sensitive cells.
Example 5. Suppose, in Example 4, we hide the non-sensitive cell (e.g., c 11 ) in addition to c 14 (i.e., replace it with NULL). Now, the querier will be uncertain of the truth value of c 4 = c 11 , and as a result, cannot determine the truth value of the predicate c 14 > c 21 containing the sensitive cell. Since the predicate, c 14 > c 21 could either be true or false, the querier does not learn anything about the value of the sensitive cell c 14 .
We can formalize this intuition into a sufficient condition that identifies additional non-sensitive cells to hide which we refer to as the Tattle-Tale Condition (TTC) 5 in order to prevent leakage of sensitive cells, as follow: Definition 7 (Tattle-Tale Condition). Given an instantiated DCδ, a view V, a cell c ∈ Cells(δ), and Preds(δ\c) = φ where eval(Pred, V) refers to the truth value of the predicate Pred in the view V using the standard 3-valued logic of SQL i.e., a predicate evaluates to true, false, or unknown (if one or both cells are set to NULL). The predicates only compare between the values of two cells or the value of a cell with a constant as defined in Sec 2.2.
Note that T T C(δ, V, c) is True if and only if all the predicates except for the predicate (s) containing c (Preds(δ, c)) evaluate to True in which case, the querier can infer that the one of the predicates containing c must be false and, as a result, could 5. Tattle-Tale refers to someone who reveals secret about others exploit the knowledge of the predicate (s) to restrict the set of possible values that c could take. This leads us to a sufficient condition to achieve full deniability as captured in the following two theorems. In proving the theorems, we will assume that none of the predicates in the denial constraints are trivial That is, there always exist a domain value for which the predicate can be true or false. This also means that in the base view V 0 (where all cells are hidden), for any cell c i ∈ cells(δ) and for any predicate Pred ∈ Preds(δ, c), there exists a possible assignment for c i in Theorem 1. Given an instantiated DCδ, a view V, and a sensitive cell c * ∈ Cells((δ)) whose value is hidden in this view. If the Tattle-Tale Condition T T C(δ, V, c * ) evaluates to False, then the set of inferred values for c * from V is the same as that from the base view V 0 (where all the cells are hidden), i.e., I(c * |V,δ) = I(c * |V 0 ,δ).
Proof. Based on the definition in Section 3, we have I(c * |V,δ) ⊆ I(c * |V 0 ,δ). Next, we show that for any possible value assignment to c * in the base view, x * ∈ I(c * |V 0 ,δ), x * is also in I(c * |V,δ) when the TTC is False. We prove this based on the two cases when T T C(δ, V, c * ) evaluates to False (see Equation 5).
Case 1: At least one of the predicates Pred i in Preds(δ\c * ) evaluate to False based on the true cell value assignments in V i.e., eval(Pred i , V) = False. Therefore, the sensitive cell c * can take any value x * ∈ I(c * |V 0 ,δ) to ensureδ to be True, i.e. ¬(· · · ∧ False ∧ · · · ) = True always.
Case 2: At least one of the predicates Pred i in Preds(δ\c * ) evaluate to Unknown based on c j ∈ Cells(Pred i ) being hidden in V. Based on the assumption stated earlier, we know that there exists x j ∈ I(c j | V 0 ,δ) ⊆ V(c j ) that leads to Pred i evaluating to False. Hence, for any x * ∈ I(c * |V 0 ,δ), there exists x j ∈ I(c j | V) for any c j ∈ Cells(δ)\{c * } such that Corollary 1. Given a set of instantiated DCs S ∆ , a view V, and a sensitive cell c * whose value is hidden in this view. If for each of the instantiationsδ i ∈ S ∆ , TTC(δ i , V, c * ) evaluates to False then the set of inferred values c * from the V is same as that from the base view V 0 i.e., Proof. From Theorem 1, we know that for eachδ i ∈ S ∆ when the TTC is False, we have I(c * |V,δ i ) = I(c * |V 0 ,δ i ). As each individual set based on individual dependency instantiation are equal in both the released view and base view, the joint set of values in both views computed by the intersection of all the sets should also be equal i.e., δ i ∈S∆ I(c * |V,δ i ) = δ i ∈S∆ I(c * |V 0 ,δ i ). According to Equation 3, this joint set is the final inferred set of values for c * based on S ∆ in a given view and as they are equal If the dependencyδ only contains a single predicate, the Tattle-Tale condition evaluates to True even in V 0 when all the cells are hidden T T C(δ, V 0 , c i ) =True in the cases of Pred(c i ) and therefore it is not possible to prevent querier from learning about the truth value of the sensitive predicate.

Selecting Cells to Hide
As shown in Theorem 1, the Tattle-Tale condition evaluating to False is the sufficient condition of achieving full deniability requirement. T T C(δ, V, c) evaluates to False when one of the following holds: (i) none of the predicates involve the sensitive cell i.e., Preds(δ, c * ) = φ (trivial case); (ii) one of the other predicates in Preds(δ\c * ) evaluates to False in V; or (iii) one of the other predicates in Preds(δ\c * ) involve a hidden cell in V and thus evaluates to Unknown.
We define cuesets 6 as the set of cells in an instantiated DC that can be hidden to falsify the Tattle-Tale condition.
Ifδ only contains a single predicate, we consider the remaining cell in the cueset(c,δ) = c j given that Pred(c) = c i θc j . We could falsify the Tattle-Tale condition w.r.t. a given cell c and dependencyδ by hiding any one of the cells in the cueset independent of their values in V. The cuesets for a cell c is defined for a given dependency instantiation. We can further define cueset for c for given a set of instantiated DCs S ∆ by simply computing the cueset(c,δ) for each instantiated dependency in the setδ ∈ S ∆ . In order to prevent leakage of c throughδ, we will hide one of the cells in the cueset(c,δ) corresponding to each of dependency instantiationsδ ∈ S ∆ . This, alone, however, might not still falsify the tattle-tale condition to achieve full-deniability. Leakage can occur indirectly since the value of the cell, say c j chosen from the cueset(c * ,δ i ) to hide (in order to protect leakage of a sensitive cell c * ) could, in turn, be inferred due to additional dependency instantiation, saỹ δ j . If this dependency instantiation does contain c * (as in that case c * is already hidden and therefore it cannot be used to infer any information about c j ), such a leakage can, in turn, lead to leakage of c * as shown in the following example.
Example 7. Consider we hide the cell c 11 in the cueset shown in Example 6 to protect the sensitive cell c 14 . Letδ j be another instantiated dependency, that is ¬((c 10 = c 24 )∧(c 11 = c 25 )) (i.e. a FD indicating Zip determines State). The dependencyδ j itself does not lead to the leakage to the sensitive cell c * . However, based on dependencyδ j , the querier can first infer the value of the hidden cell c 11 , which in turn, leads to leakage of the sensitive cell c * .
Achieving full deniability for the sensitive cells requires us to recursively select cells to hide from the cuesets of not just sensitive cells, but also, from the cuesets of all the hidden cells. This recursive hiding of cells terminates when the cueset of a newly hidden cell includes an already hidden cell. The following theorem states that after the recursive hiding of cells in cuesets has terminated, the querier view achieves full deniability.
Theorem 2 (Full Deniability for a Querier View). Let S ∆ be the set of dependencies, C S be the sensitive cells for the querier 6. These cells give a cue about the sensitive cell to the querier. and C S ⊆ C H be the set of hidden cells resulting in a V for the querier. V achieves full deniability if ∀c i ∈ C H , ∀δ ∈ S ∆ , ∀ non-empty cueset(c i ,δ) ∈ cuesets(c i , S ∆ ), there exists a c j ∈ C H such that c j ∈ cueset(c i ,δ).
Proof. We prove this by induction on the number of dependency instantiations n. Base case: When n = 0, then there are no dependency instantiations that apply to c i ∈ C H and hence in the shared querier V, there exists no possibility of leakage for all c i . Induction step: Suppose the Theorem 2 is True for n = k i.e., V achieves full deniability when there are k dependency instantiations. Now we consider the case when there exists n = k + 1 dependency instantiations. Ifδ k+1 does not include any c i ∈ C H then by default V achieves full deniability. Supposeδ k+1 includes a cell c i ∈ C H and there is leakage on c i despite it being hidden because T T C(δ k+1 , c i , V) is True. In the rest of the proof we show that such a leakage is impossible.
Ifδ k+1 only contains a single predicate of the form Pred(δ k+1 ) = c i θconst), then since c i is hidden, such a dependency cannot cause leakage. On the other hand, if the single predicate is of the form Pred(δ k+1 ) = c i θc j , then cueset(c i ,δ) contains c j . As a result, c j must also be hidden (by the property of C H described in the theorem) and thus, again such a dependency cannot lead to leakage. If additional predicate(s) exists inδ k+1 and T T C(δ k+1 , c i , V) is True, it must be the case that all the other predicates (Preds(c(δ k+1 )\c i )) are True. Thus, by the property of C H described in the theorem, there must exist another cell c j from Preds(c(δ k+1 )\c i ) such that it is also hidden. As T T C(δ k+1 , c i , V) returned True even though c j from its cueset is hidden, it must be the case, that there exists another dependency instantiation for which tattle tale condition for such a c j holds. But as the induction step established full deniability for all the dependency instantiations up to k and therefore no leakage, it cannot exist. Hence, the V achieves full deniability if C H satisfies the condition in the theorem.

Leakage due to Function-based Constraints
In order to study the leakages due to Function-based Constraints (FC) we first define the property of invertibilty associated with functions.
Definition 9 (Invertibility). Given a function f n(r 1 , r 2 , . . . , r n ) = s i , we say that f n is invertible if it is possible to infer knowledge about the inputs (r 1 , r 2 , . . . , r n ) from its output s i . Conversely, if s i does not lead to any inferences about (r 1 , r 2 , . . . , r n ), we say that it is non-invertible The Salary function, in Example 2, is invertible as given the Salary of an employee, a querier can determine the minimum value of SalPerHr for that employee given that the maximum number of work hours in a week is fixed. Complex user-defined functions (UDFs) (e.g., sentiment analysis code which outputs the sentiment of a person in a picture), oblivious functions, secret sharing, and many aggregation functions are, however, non-invertible. Instantiated FCs can be represented similar to denial constraints. For instantiated FCs, if the sensitive cell corresponds to an input to the function, and the function is not invertible, then for cs ∈ cuesets do 6 if cs.overlaps(C H ) then 7 cuesets.remove(cs) leakage cannot occur due to such an FC. Thus, the T T C(c * ,δ, V) returns False when the function is non-invertible. For all other cases, the leakage can occur in the exact same way as in denial constraints. We thus, need to to ensure the Tattle-Tale Condition for all the instantiations of a FC evaluates False.
Cueset for Function-based Constraints. The cueset for a FCδ is determined depending on whether the derived value (s i ) or input value ({. . . , r j , . . .}) is sensitive and the invertibility property of the function f n.
. . , r j , . . .} φ f n is non-invertible and if c ∈ {. . . , r j , . . .} As the instantiation for FC is in DC form and their Tattle-Tale Conditions and cueset determination are almost identical, in the following section we explain the algorithms for achieving full deniability with DCs as extending it to handle FCs requires only a minor change (disregard cuesets when one of the input cell(s) is sensitive and function is non-invertible).

ALGORITHM TO ACHIEVE FULL DENIABILITY
In this section, we present an algorithm to determine the set of cells to hide to achieve the full-deniability based on Theorem 2. Full-deniability can trivially be achieved by sharing the base view V 0 where all cells values are replaced with NULL. Our goal is to ensure that we hide the minimal number of cells possible while achieving full deniability.

Full-Deniability Algorithm
As shown in Figure 2, our approach (Algorithm 1) takes as input a user U, a set of schema level dependencies S ∆ , and a view of the database V (initially set to the original database). The algorithm first determines the set of sensitive cells C S (Sensitivity Determination function for U and V). Sensitivity determination identifies the policies applicable to a querier using the subject conditions in policies and marks a set of cells as sensitive thus assigning them with NULL in the view. The set of sensitive cells are added into a set of hidden cells (hidecells) which will be finally hidden in the secure view (V S ) that is shared with the user U. Next, the algorithm generates the cuesets for cells in hidecells using S ∆ and V (Inference Detection, Step 3). Given the cuesets, the algorithm chooses a set of cells to hide such that the selected cells covers each of the cuesets (Inference Protection). This process of cueset identification protection continues iteratively as new hidden cells get added. The algorithm terminates when for all of the cuesets there exists a cell that is already hidden. Finally, we replace the value of hidecells in V S (initialized to V) with NULL and returns this secure view to the user (Steps 13-16). The following theorem states that the algorithm successfully implements the recursive hiding of cells in C H which is required for generating a querier view that achieves full deniability (as discussed in Theorem 2). Theorem 3. When Algorithm 1 terminates, ∀c i ∈ C H , ∀δ ∈ S ∆ , for all cueset(c i ,δ) that is non-empty, there exists c j ∈ cueset(c i ,δ) such that c j ∈ C H (i.e., Algorithm 1 has recursively hidden at least 1 cell from all the non-empty cuesets of cells in C H ).

Inference Detection
Inference detection (Algorithm 2) takes as input the set of sensitive cells (C S ), the set of schema-level dependencies (S ∆ ), and a view of the database (V) in which sensitive cells are hidden by replacing with and others are assigned the values corresponding to the instance. For each sensitive cell c * , we consider the given set of dependencies S ∆ and instantiate each of the relevant dependencies δ using the database view V (Steps 5-7). The DepInstantiation function returns the corresponding instantiated dependencyδ. For each such dependency instantiation, if it is a dependency containing a single predicate i.e.,δ = ¬(Pred) where Pred = c * θc k , we add the non-sensitive cell (c k ) to the cueset (Steps 9, 10). If the dependency contains more than a single predicate, we determine if there is leakage about the value of the sensitive cell by checking the Tattle-Tale Condition (TTC) for the sensitive cell c * (Step 11) 7 . If T T C(δ, V, c * ) evaluates to False, we can skip that dependency instantiation as there is no leakage possible on c * due to it (Step 12). However, if T T C(δ, V, c * ) evaluates to True, we get all the 7. While not shown in the algorithm for simplicity, when an input cell is sensitive in a FC instantiation, if the FC is non-invertible we ignore its cuesets as they are empty.

Algorithm 2: Inference Detection
Input: A set of sensitive cells C S , Schema-level data dependencies S ∆ , A view of the database V Output: A set of cuesets cuesets 1 Function InferenceDetect(C S , S ∆ , V): For each instantiated dependency. 9 if |Preds(δ)| = 1 then Note that in our inference detection algorithm, we did not choose the non-sensitive cell c in Pred(c * ) = c * θc as a candidate for hiding. We illustrate below using a counter-example why hiding c might not be enough to prevent leakages.
Example 8. Consider a relation with 3 attributes A 1 , A 2 , A 3 and 3 dependencies among them (δ 1 : . Let there be two tuples in this relation t 1 : 1(c 1 ), 2(c 2 ), 2(c 3 ) and t 2 : 1(c 4 ), 2(c 5 ), 2(c 6 ). Suppose c 6 is sensitive. As leakage of the sensitive cell is possible through the dependency instantiationδ 2 : ¬((c 2 = c 5 ) ∧ (c 3 = c 6 )), c 5 is hidden. In the next iteration of the algorithm, to prevent leakages on the hidden cell c 5 through dependency instantiatioñ , c 2 is also hidden. Note that c 2 is in the same predicate as c 5 inδ 1 . However, the querier can still infer the truth value of the predicate c 2 = c 5 as True based on the two non-hidden cells, c 1 and c 4 , and the dependency instantiatioñ The querier also learns that c 3 = c 6 evaluates to True inδ 2 which leads to them inferring that c 6 = 2 (same as c 3 ) and complete leakage.
To prevent any possible leakages on the sensitive cell c * and its corresponding predicate Pred(c * ), we only consider the solution space where a cell from a different predicate (Preds(δ\c * )) is hidden. 8. If we wish to relax the assumption that queriers and data owners do not overlap stated in Section 3.1, we can do so here by only including the cells in the cueset that do not belong to the querier. We prove the correctness of this modification in Section 6

Inference Protection
After identifying the cuesets for each sensitive cells based on their dependency instantiations, we now have to select a cell from each of them to hide to prevent leakages. The first strategy for cell selection, described in Algorithm 3, randomly selects a cueset and cell from it to hide (if no cells in it have been hidden already). We use this approach as our first basline (Random Hiding) in Section 7. The second strategy for cell selection, described in Algorithm 4 utilizes Minimum Vertex Cover (MVC) [25] to minimally select the cells to hide from the list of cuesets. In this approach, each cueset is considered as a hyper-edge and cell selection strategy finds the minimal set of cells that covers all the cuesets. MVC is known to be NP-hard [26] and therefore we utilize a simple greedy heuristic based on the membership count of cells in various cuesets. Algorithm 4 takes as input the set of cuesets and returns the set of cells to be hidden to prevent leakages. First, we flatten all the cuesets into a list of cells and insert this list into a dictionary with the cell as key and their frequency count as the value (Steps 4-5). Next, we select the cell from the dictionary with the maximum frequency and add it to the set of cells to be hidden and remove any cuesets that contain this cell (steps 7-10). These steps are repeated until all the cuesets are covered i.e., at least one cell in it is hidden, and finally we return the set of cells to be hidden.

Query-based Optimization for Inference Detection
The inference detection algorithm is to search for a list of cells that can leak information to the sensitive cell according to the Tattle-tale condition. The algorithm could be time-and spaceconsuming with a large database, because for each dependency and each sensitive cell, it will first instantiate the dependency to generate |D| − 1 many dependency instances and then iterate over all instatiations. In each iteration the algorithm checks Tattletale condition and project the instatiation to a cueset. To speed up cueset detection, we propose an optimization technique that rewrites Tattle-condition to SQL queries and generate cuesets based on the query result on the database. This optimization takes in a list of sensitive cells and produces one query per dependency for all sensitive cells. The first step in this optimization is retrieve the tuples containing sensitive cells, and store these tuples in a materialized view temp while setting the value of the sensitive cells as NULL. Then we interpret the Tattletale condition into a join query between the temp table and the original database. For example, considering the denial constraint ¬((Zip = Zip) ∧ (State = State)). The program will produce the following query based on this dependency and the Tattle Note that the join table contains all instantiations of this denial constraint. Then the "WHERE" conditions of this query is the conjunction of the clauses that are generated for all predicates of this dependency. Each clause captures either the predicate is sensitive (therefore T2.Zip is NULL), or the predicate is evaluated as TRUE (e.g. T1.Zip=T2.Zip). In addition, we use the T1.tid = T2.tid condition for non-unary dependencies. This interpretation is correct, because Tattle-tale condition says, if every predicates except the sensitive predicate are evaluated as TRUE, the cells in this instance will leak information to the sensitive cell. Hence, we can readily project the query results and the sensitive tuples to a list of cuesets.

Convergence and Complexity Analysis
Algorithm 1 starts with s number of hidden cells. At each iteration, we consider that each hidden cell (including cells are hidden in previous iterations) is expanded to f number of cuesets on average by the Inference Detection algorithm (Algorithm 2). Among the cuesets, the average number of cells that are hidden, such that it satisfies full deniability, is given by f m where m is the coverage factor determined by minimum vertex cover (MVC). Then, at the end of ith iteration, the number of average hidden cells will be s i = s( f m ) i , and the average number of cuesets will be cs i = sf ( f m ) i−1 . As s i is bounded by the total number of cells in the database, denoted by N , the number of iterations (T ) to converge is bounded by log f /m (N/s), when f > m (which was verified in our experiments).
Given |∆| which is the number of schema-level dependencies, we can estimate the time complexity with respect to I/O cost. At ith iteration of Algorithm 1, the I/O cost of (i) the dependency instantiation is O(|∆|(N + s i )) (implemented using a "JOIN" query given sufficient, i.e. Θ(N ), memory) and (ii) minimum vertex cover (MVC) with an I/O cost of O(cs i ). Hence, the overall given T ≤ log f /m (N/s) and thus is linear to the data size.
To be more clear on the complexity derivation, as explained in the Section 5.4, the cost of the dependency instantiation for the ith iteration depends on the I/O cost of the join query which is O(N + s i ) when given sufficient (i.e., Θ(N )) memory, and this query is executed |∆| times. Hence, the cost for the dependency instantiation is O (|∆|(N + s i )).
Hence, the total estimated I/O cost for T iterations can be derived as follows given T ≤ log f /m (N/s).
We complement the complexity analysis with the discussion on the required sufficient memory storage. For (i) dependency instantiation, the join query between two tables of size N and s i , we need memory size Ω(N + s i ) = Ω(N ) since s i ≤ N . In (ii) the algorithm of computing MVC, all cuesets are read into the memory, which requires the memory size Ω(c i ) = Ω(N * m) = Ω(N ) for constant m. Thus we need Ω(N ) memory to finish all operations in our system implementation, which is feasible in practice. We also note that this complexity analysis only holds with Θ(N ) size of memory, in which case the cost of memory operations is much cheaper than the overhead of I/O operations. Given Ω(N 2 ) memory, which can be impractical, all the operations can then be finished within memory and the total computational cost is bounded by O(N 2 ), according to the following analysis.
If all operations are taken within memory, then the cost of dependency instantiation is bounded by O(N s i ) and the computational cost of the MVC algorithm is bounded by O(c 2 i ). Then we derive the following bound similarly.

Scaling out our approach
The complexity analysis in Section 5.5 shows that our algorithm is linear to the data size given sufficient large memory. However, on larger datasets, our system will generate a large number of dependency instantiations and cuesets, which can be costly in terms of memory storage. In order to deal with this issue and  return binQueue.pop() make our system be able to run with constant memory size, we have implemented a binning-then-merging wrapper algorithm (Algorithm 5). The high-level idea of the algorithm is illustrated in Figure 3. Algorithm 5 partitions the full dataset into a number of bins (specified by the parameter b which is the bin size). It then calls the Full Algorithm (presented in Section 5.1 and denoted by runMain() in Algorithm 5) on each of these bins in order to generate a view per bin that satisfies full deniability. Next, it merges these bins (which is controlled by the parameter m (merge size) and executes Full Algorithm on the merged bins. It iterates over the bins until there is only 1 bin left and after executing the Full Algorithm on this last bin, the final view that satisfies full deniability is returned. The output view generated by Algorithm 5 trivially satisfies full-deniability as the Full Algorithm is executed on the full view in the final step. Several sensitivity-dependent heuristics can be applied to further improve the performance of this binning-then-merging algorithm. We briefly discuss one potential heuristic as an example and leave others for future work. The basic binning-then-merging only describes a way to split the dataset into bins and how to correctly merge the safe views (after running the Full Algorithm) to achieve full deniability. As a heuristic, for which we call it adaptive splitting heuristic, the original dataset can be partitioned based on the distribution of the sensitive cells. Therefore, each bin might not necessarily contain the same number of tuples in the dataset, but instead, contain approximately the same ratio of the number of sensitive cells to the number of tuples. This heuristic can control the number of dependencies and the number of cuesets to be approximately the same among different bins.

DISCUSSION
While full deniability studied in this paper offers a strong security model to protect sensitive data from inference attacks through data dependencies, it is not without limitations. In this section, we discuss these limitations and explore possible extensions to overcome them.

Weaker Security Model
The first potential limitation is from the perspective of utility as full deniability hides a number of non-sensitive cells to prevent leakages. It is possible to relax full deniability to a weaker security model which we call, k-percentile deniability in order to potentially hide fewer cells and thus improve utility.
Definition 10 (k-percentile Deniability). Given a set of sensitive cells C S in a database instance D and a set of instantiated dependencies S ∆ , we say that a querier view V achieves kpercentile deniability if for all c * ∈ C S , where 1 |I(c|V0,S∆)| ≤ k ≤ 1. Note that if k = 1, then k-percentile deniability is the same as full deniability, where the set of values inferred by the adversary from view V is the same as the set from the base view. With k < 1, it allows for a bounded amount of leakage. We also note that the security models used in prior works is subsumed by the notion of k-percentile deniability defined above. For instance, the model used in [15] ensures that the querier cannot reconstruct the exact value of the sensitive cell using data dependencies, which can be viewed as a special case of k-percentile deniability with the value of k = 2 |I(c|V0,S∆)| , i.e., the number of values sensitive cell can take is more than 1. Algorithms to achieve k-percentile deniability. In k-percentile deniability or simply k-den, we quantify the leakage on the sensitive cell in a given view V and the set of instantiated data dependencies S ∆ . The decision to hide additional cells is only made if the set of possible values inferred by the querier is larger than the given threshold (k). The set of inferred values for a c * given by the I(c | V, S ∆ ) (defined in Section 3.3) can be represented as follows When attribute for the cell c is discrete, the operator θ in Pred(c) is limited to either = or =. Therefore, we represent the inferred set of values by a set, called minus set, containing the values that cannot be assigned to the cell in the view V. On the other hand, when attribute for the cell c is continuous, the operator θ could be one of the following: {>, ≥, <, ≤} and therefore we use a range, denoted by (low, high) to represent the set of values. In Algorithm 6, we describe how to compute the . Based on the operator θ 9 in this predicate, we either put the value of non-sensitive cell c k in the given V to minus set (when Dom(c * ) is discrete) or determine low and high (when Dom(c * )) is continuous). This function computes the exact leakage on a sensitive cell with respect to various instantiated dependencies. We utilize this to implement k-den where for each sensitive cell, after we detect the cuesets (Step 3 in Algorithm 1), we compare the the leakage on a sensitive cell due to the instantiated dependencies (associated with the cuesets). The k parameter, specified as a fraction of the maximum domain size of a sensitive cell, provides a bound on the acceptable leakage on a sensitive cell. If the sensitive cell c * has a discrete domain and |c * .minus set| ≤ |Dom(c * )| × (1 − k) evaluates to True, we do not hide any cells from any of its cuesets. On the other hand, for a sensitive cell c * with a continuous domain we check if high − low ≥ |Dom(c * )| × (k) evaluates to True. The difference between low and high gives the actual domain size after taking into count leakages due to dependencies.
When the leakage is under the threshold, k-den approach prunes away a large number of cuesets from further consideration in the remaining steps of the full algorithm. If the leakage is above the threshold, then we order the cuesets in the descending order of leakage and hide cells from them (using Inference Protection) 9. We consider "≤" and "<" (similarly "≥" and ">") operators as identical in the above algorithm for simplification. until leakage is below the threshold. We execute Maximum Vertex Cover (MVC) in Inference Protection on all the cuesets of the sensitive cell even if only a portion of them have hidden cells. This ensures that the final solution generated by k-den is strictly an improvement over the strict full deniability model. Theorem 4. The algorithm we describe (i.e. algorithm 7) to achieve k-percentile deniability always performs as good as (or better than) the algorithm to achieve full-deniability (i.e. algorithm 1).
In Section 7, we show through experiments that the algorithm that achieves k-percentile deniability only marginally improves on full deniability even with low values of k (i.e., complete leakage). Therefore this approach is not useful in improving the utility in realistic settings. It is possible that in more complex domains with large number of sensitive cells, k-percentile deniability is more effective and this needs to be studied further.

Limitations of Security Model
The second potential limitation is from the perspective of security as our security model is based on the assumption that no correlations exist between attributes and tuples i.e., they are independently distributed other than what is explicitly stated through dependencies (that are either learnt automatically or specified by the expert). However, typically in databases, other correlations do exist which can be exploited to infer the values of the hidden cells. These correlations can be also learned by the database designer using dependency discovery tools or data analysis tools. If the correlations are very strong (e.g. hard constraints with no violations in the database), we call them out as constraints and consider them in our algorithms. For weak correlations, or soft constraints that only apply to a portion of the data, we do not consider them. Otherwise, everything in the database will become dependent, in which case our algorithm would be too conservative and hide more cells than necessary based on these soft constraints.
Hence, in our experiments (Section 7), we consider only the data dependencies (a set of hard constraints) that were defined on the database. To understand how this assumption plays out in inference attacks, we deployed a data cleaning adversary who tries to exploit all possible correlations in the data to reconstruct the values of the sensitive cells. The results (Section 7.5) show that by considering the major data dependencies, the adversary is only able to recover a small portion of the sensitive cells (14 out of 90 sensitive cells).

Relaxing Assumptions for Full Deniability Algorithm (FDA)
In this subsection, we explore relaxing the two important assumptions stated in Section 3.1 about the adversary. We propose possible solutions and modifications needed to the algorithms presented in the paper in order to implement these solutions. If needed, we also provide theorems stating the correctness of the proposed solutions.

Adversary Knows the Sensitive Attributes
We stated assumption in Section 3.1 that the adversary cannot apriori determine a cell is sensitive or not. There may be scenarios where the adversary can accurately guess the relative sensitivity of the attributes in a database schema. For example, in an employee table Salary is more likely to be sensitive than Zip Code and if    bestCuesets.add(lcs) 20 cellCuesets.remove(lcs) 21 Recalculate the state of the cell.  return True Based on k-deniability. 38 return False both are hidden in a tuple the adversary can guess that one was due to policy and the other due to the algorithm. This situation can be handled by our algorithm with a slight modification under the assumption that any tuple in the database instance could contain a sensitive cell. This means that while the adversary knows that salary is more likely to be sensitive, they do not know salaries of exactly which employees are sensitive.
The key idea behind this modified algorithm is to hide the sensitive cell in a tuple where only the non-sensitive cell is  hidden. From the previous example, we would also hide the Salary attribute of a tuple (even when it is not sensitive) if our algorithm chooses to hide Zip Code. Therefore the adversary cannot be certain whether all the hidden cells under Salary attribute was done so by policy or the algorithm. We slightly modify the original Inference Protection algorithm (Algorithm 4) and propose Algorithm 8 in order to handle this relaxed assumption (the modifications are highlighted in blue). First, the original Inference Detection algorithm (Algorithm 2) identifies the cuesets based on dependency instantiations as an input to the Inference Protection algorithm. Second, original Inference Protection algorithm will select at least 1 cell from each cueset to hide. Third, the steps in modified Inference Protection Algorithm (Steps 13-21) goes through the set of hidden cells and for each of them check if they belong to a non-sensitive attribute. If it does, then add the cells under sensitive attribute from the corresponding tuple to the set of hidden cells.
An example is illustrated in Figure 4 where we have a view V with c 2 marked as sensitive. We assume that the adversary knows that attribute B is more likely to be sensitive than attribute A. After running FDA, the original Inference Protection algorithm will generate V * (with c 3 also hidden). The modified Inference Protection algorithm will generate V * modif ied (with c 2 , c 4 also hidden) which stops adversary from learning whether c 2 was hidden due to policies or FDA since all tuples are independently distributed and are equally likely to contain sensitive cell(s).
We note that the assumption of equal likelihood of tuple containing sensitive cell can be further relaxed by adopting a probabilistic approach (motivated by OSDP) in which certain non- sensitive cells are randomly hidden to prevent adversary from inferring if it was part of a sensitive cell's cueset. However, such an approach will be a non-trivial extension and is an interesting future direction to explore.

When Adversary Can Be A Data Owner
We stated in Section 3.1 that queriers and data owners are nonoverlapping parties. If we want to relax this assumption to consider an adversary that is a querier and data owner, we can modify our Inference Detection algorithm to only include cells that do not belong to the querier in the cueset.
The proof sketch for correctness of this modified algorithm is as follows. Theorem 4.5 in the paper (Full Deniability for a Querier View) states that V achieves full deniability if for any cell c i in the set of hidden cells, there exists another cell c j from c i 's cueset that is also in the set of hidden cells. In the modified algorithm, we have only updated Inference Detection (which generates cuesets) and not Inference Protection (which hides cells from the cuesets). Each of these modified cuesets contain at least one cell as the dependencies are binary which leads to Inference Protection successfully hiding a cell from these cuesets in the next step. Therefore, based on theorem 4.5 it satisfies the necessary condition for achieving full deniability which is to have at least one cell from each cueset be present in the set of hidden cells. If in a dependency instantiation, both tuples belong to the querier then it is possible its corresponding cueset is empty using this modified algorithm. However in such a case, the sensitive cell in the dependency instantiation already belongs to the querier so it is not possible to prevent them from learning about it.

Extending FC constraints
We now describe a general model of Function-based Constraints by extending the model to invertibility as follows for a a function f n(r 1 , r 2 , . . . , r n ) = s i where r 1 , r 2 , . . . , r n are the general representation for input values (e.g., WorkHrs) and s i is the general representation of the derived value or the output of the function (e.g., Salary).

Definition 11
((m, n)-Invertibility). For a function f n(r 1 , r 2 , . . . , r p ) = s i , given its output s i and any m − 1 out of p inputs, if we could find another function f n (r t , r t+1 , . . . , r t+m−2 ; s i ) = {r k , r k+1 , . . ., r k+n−1 } that disclose n of the rest input values, we say this function f n is (m, n)−invertible; otherwise, we say this function is (m, n)−non-invertible.
The previously mentioned Salary function is (2, 1)-invertible as given any two of the three variables, the rest one could be disclosed.
Definition 12 (Fully invertible). If a function f is (1, n)-invertible, we say this function is fully invertible.
Cross product (Cartesian product) is an example of full invertibility, since all the input values can be inferred if given the result of cross product. That is to say, cross product is (1, n)invertible. Other examples of commonly used functions are userdefined functions (UDFs) (e.g. oblivious functions, secret sharing), and aggregation functions.
Computing Leakage for FCs. As for a (m, n)-invertible function, denoted by f n (r 1 , r 2 , . . . r n ) = {s 1 , s 2 , . . . , s m }, it can be apparently observed that, given the m inputs, the function will lead to the leakage towards n values. Take, for example, the Salary, WorkHrs and the SalPerHr. Since as analyzed, the function to calculate the salary is (2, 1)-invertible, it means that if taking any two values of the three attributes, the adversary can fully convert and leak the exact value of the remaining attribute. We call this case full leakage from FC. However, a subset of the m input values of an (m, n)-invertible function could also leak some information of some disclosable values based on some domain knowledge. As an example, suppose the adversary knows that the salary of a employee is 8,000 but they do not know the exact WorkHrs and SalPerHr. Even though, with some background knowledge, for e.g., the information that no one could work more than 40 hours per week by law, the adversary could reduce the domain of possibilities the SalPerHr value could take. We call this partial leakage from FC. We leave further exploration of this extended model as future work.

EXPERIMENTAL EVALUATION
In this section, we present the experimental evaluation results for our proposed approach to implement full-deniability. First, we explain our experimental setup including details about the datasets, dependencies, baselines used for comparison, evaluation metrics, and system setup. Second, we present the experimental results for each of the following evaluation goals: 1) comparing our approach against baselines in terms of utility, performance, and number of cuesets generated; 2) evaluating the impact of dependency connectivity, and 3) studying the extensions and limitations presented in Section 6.

Evaluation Setup
Datasets. We perform our experiments on 2 different datasets. Some statistics of the datasets are summarized in Table 2. The first one is Tax dataset [13], a synthetic dataset with 10k tuples and 14 attributes, where 10 of them are discrete domain attributes and the rest are continuous domain attributes. Every tuple from the tax table specifies tax information of an individual with information such as name, state of residence, zip, salary earned, tax rate, tax exemptions etc. The second dataset is the Hospital dataset [11] which is a real-world 100k dataset where all of the 15 attributes are discrete domain attributes. We select a subset of this dataset (which includes the first 10k tuples of the dataset), called Hospital10k, for the experiments included in the paper. We then conduct scalability experiment that makes use of the binning-then-merging wrapper on the full Hospital dataset to show the scalability of our system. It is also notable that both datasets have a large domain size, as shown in Table 2. The active domain size in the table refers to the domain of the attributes participating in the data dependencies that we consider in the experiments. Schema Information. Every tuple (T ID) from the Tax table specifies tax information of an individual with their first name (FName), last name (LName), gender (Gender), area code for phone number (AreaCode), phone number (Phone), city (City), state of residence (State), zip (Zip), marital status (MaritalStatus), Has Children (HasChild), salary earned (Salary), tax rate (Rate), Single Exemption rate (SingleExemp), Married Exemption rate (MarriedExemp), and Child Exemption rate (ChildExemp). As for the Hospital table, each tuple has the information of hospitals, which includes the provider number (ProviderNumber), the hospital name (HospitalName), city (City), state of the hospital (State), zip (ZIPCode), county name (CountyName), phone number for contact (PhoneNumber), the type of the hospital (HospitalType), the owner of the hospital (HospitalOwner), emergency service (EmergencyService), conditon (Condition), measure code (Mea-sureCode), measure name (MeasureName), the number of patient samples (Sample), and the state average (StateAvg). Data Dependencies. For both datasets, we identify a large number of denial constraints by using a data profiling tool, Metanome [27]. Many of the output DCs identified by Metanome were soft constraints which are only valid for a small subset of the database instance. After manually analyzing and pruning these soft DCs, we selected 10 and 14 hard DCs for the Tax dataset and the Hospital dataset respectively. We also added a FC based on the continuous domain attribute named "tax" which is calculated as a function "tax = f n(salary, rate)". Since the Hospital dataset does not have continuous domain attributes, we cannot create a functionbased constraint on it and just use the 14 DCs for evaluation. If any of them were soft DCs, we updated/deleted the violating tuples to turn them into hard DCs. The data dependencies used for experiments can be found in Table 3 (for the Tax dataset) and  Table 4 (for the Hospital10k dataset). Policies. (described in Section 2) control the sensitivity of a cell. The number of sensitive cells is equivalent to the number of policies and it helps us in precisely controlling the number of sensitive cells in experiments using policies. While the experiments are performed for a single querier, the extension to multiple queriers is trivial. Metrics. We compare our approach against the baseline methods using the following metrics: 1) Utility: measures the number of total cells hidden; 2) Performance: measures the run time in seconds. System Setup. We implemented the system in Java 15 and build the system dependencies using Apache Maven. We ran the experiments on a machine with the following configuration: Intel(R) Xeon(R) CPU E5-4640 2.799 Ghz, CentOS 7.6, with RAM size 64GB. We chose as the underlying database management system MySQL 8.0.3 with InnoDB. For each testcase, we perform 4 runs and report the mean and standard deviation. Baselines. In the following experiments we test our approach which implements Algorithm 1, denoted by Our Approach against baselines.
To best of our knowledge, there exists no other systems which solves the same problem and therefore we have developed 2 different baseline strategies for comparison. In each baseline method, we replace one of the key modules in our system, determining cuesets and selecting cell to hide from the cueset, with a naïve strategy but without compromising full deniability of the generated querier view.
• Baseline 1: Random selection strategy for hiding (Random Hiding): which replaces the minimum vertex cover approach with an inference protection strategy that randomly selects cells from cuesets to hide.
• Baseline 2: Oblivious cueset detection strategy (Oblivious  "tax" = fn("salary", "rate")  Cueset): which disregards Tattle-Tale Condition and uses an inference detection strategy that creates as many dependency instantiations as the number of tuples in the database for each dependency and generates cuesets for all of them.

Experiment 1: Baseline Comparison
We compare our approach against the aforementioned baselines and measure the utility as well as performance (see Figure 5(a)). We increase the number of policies from 10 to 100 (step=10) where each each sensitive cell participate in at least 5 dependencies. This ensures that there are sufficient inference channels through which information about sensitive cells could be leaked. The number of cells hidden by Our Approach increases linearly w.r.t the increase in number of policies/sensitive cells compared to Random Hiding (5.3×Our Approach) and Oblivious Cueset (1.4×Our Approach). Random Hiding performs the worst because it randomly hides cells without checking the membership count of a cell in cuesets (as with using MVC in Algorithm 4). The performance of Oblivious Cueset is better because it uses the same Inference protection strategy as Our Approach. However, it generates a larger number of cuesets as it doesn't check the Tattle-Tale Condition for the dependency instantiations (like in Algorithm 2)) and therefore has to hide more cells to ensure full deniability.
We also compare the performance (run time in seconds) against number of policies of these 3 approaches (see Figure5(b)).  and it is expensive to run inference detection on such a large number of cuesets. In Random Hiding, we restrict the execution to the fifth invocation of the inference detection algorithm (Algorithm 2) i.e., if the execution doesn't complete by then, we force stop the execution. In order to study this further, we analyzed the total number of cuesets generated by Random Hiding vs. Our Approach (see Figure 7) in each invocation of Inference Detection. Due to the usage of MVC optimization in Inference Protection, Our Approach terminates after a few rounds where as with Random Hiding the number of cuesets generated in each invocation keeps increasing. We also note that Our Approach is more stable in different test cases and has a lower standard deviation on number of cuesets and hidden cells compared to Random Hiding.
We show the supplementary evaluation results on the Hos-pital10k dataset. Figure 6 presents the end-to-end comparison between Our Approach and Oblivious Cueset, and supports our claim.

Experiment 2: Dependency Connectivity
In the next set of experiments, we study the impact of dependency connectivity on the utility as well as performance. The relationship between dependencies and attributes can be represented as a hypergraph wherein the attributes are nodes and they are connected via data dependencies. We define the dependency connectivity of a node, i.e., an attribute, in this graph based on the summation of the degree (number of edges incident on the node) as well as the degrees of all the nodes in its closure. Using dependency connectivity, we categorize attributes on Tax dataset into three groups: low, medium, and high where attributes in high, low, and medium groups have the highest, lowest, and average dependency connectivity respectively. In Tax dataset, the high group contains 3 attributes (e.g. State), while the medium group has 3 attributes (e.g. Zip) and the low group includes 4 attributes (e.g. City).
The results (see Figure 8) show that when sensitive cells are selected from attributes with higher dependency connectivity, Our Approach hides more cells than when selecting sensitive cells with lower dependency connectivity. This is because higher dependency connectivity leads to a larger number of dependency instantiations and therefore a larger number of cuesets from each of which at least one cell should be hidden. Figure 9 demonstrate the data utility and performance evaluation among the (low, medium, high) dependency connectivity groups. This result verifies our argument.

Experiment 3: Scalability Experiments
The results of the scalability experiments are shown in Figure 10. The y axis records the time consumption while the x axis denotes  the size of the database (spanning from 10k tuples to 100k tuples). We consider two different settings for selecting sensitive cells, 1) randomly sample a fixed number of sensitive cells regardless of the database size, and 2) incrementally sample a fixed ratio of sensitive cells w.r.t the database size. The results of these two settings are presented in Figure 10(a) and Figure 10(b), resp. In both cases, we set the bin size as 10k tuples and the merging size as 5. In the first setting, the number of sensitive cells is set as 30 whereas, in the second setting, the ratio of sensitive cells to the total number of cells is 30 cells per 10k tuples. We note that the starting point of the plot (x = 10k tuples) corresponds to the experiments presented in Section 7 i.e., running our main algorithm on the dataset of size 10k (as there is only 1 bin). As shown in Figure 10, we can observe the time consumption scales near-linearly (depending on the data itself) to the size of the datasets.

Experiment 4: Extensions
In the final set of experiments, we test the extensions and limitations of Our Approach discussed in Section 6. First, we implemented Our Approach with a relaxed notion of security, kpercentile deniability, where k is a relative parameter based on the domain size of the sensitive cell. We analyze the utility of Our Approach when varying k and measure the utility. For the results shown in Figure 11(a), the sensitive cell is selected from "State" which is a discrete attribute with high dependency connectivity. Clearly, when k = 0, i.e., full leakage, Our Approach will only hide sensitive cells and when k = 1 i.e, Full deniability, Our Approach hides the maximum number of cells. When k = 0.5, i.e., the inferred set of values is half of that of the base view, Our Approach hides almost the same number of cells as k = 1 i.e., full deniability. When k = 0.1, i.e, the inferred set of values is 1 10 of that of the base view, Our Approach hides ≈ 15% less cells than the one that implements full deniability. On the Hospital dataset (results included in extended version), the utility improvement  was marginal with k set to the smallest value possible (besides full leakage) i.e., k = 1 |Dom(c * )| . We note that Our Approach that implements full deniability is able to provide high utility with a stronger security model on both datasets compared to the one that implements k-percentile deniability.
Second, we study the effectiveness of Our Approach against inference attacks, i.e., to what extent can an adversary reconstruct the sensitive cells in a given querier view. We consider two types of adversaries. The first type of adversary uses weighted sampling where for each sensitive cell c * , the adversary learns the distribution of values in Dom(c * ) by looking at the values of other cells in the view. The querier, then tries to infer the sensitive cell value by sampling from this learned distribution. The second type of adversary utilizes a state-of-the-art data cleaning system, Holoclean [14], which compiles data dependencies, domain value frequency, and attribute co-occurrence and uses them into training a machine learning classifier. The adversary then leverages this classifier to determine values of sensitive cells by considering them as missing data in the database. The sensitive cell for this experiment is selected from "State" which is a discrete attribute with high dependency connectivity. We consider the 10 dependencies and drop the FC because Holoclean doesn't support it. We increase the number of policies from 10 to 90 and input the querier view (in which the values of hidden cells are replaced with NULL) to both adversaries. We measure the effectiveness by repair precision = #correct repairs #total repairs (where a repair is an adversary's guess of the value of a hidden cell) and therefore lower the repair precision of the adversary is, the more effective Our Approach is. The results "Holoclean (before)" in Figure 11 (b) show that when only sensitive cells are hidden, an adversary such as Holoclean, is able to correctly infer the sensitive cells. When additional cells are hidden by Our Approach, indicated by "Holoclean (after)", the maximum precision of Holoclean is 0.15. On the other hand, the weighted sampling employed by the other type of adversary, indicated by "Weighted Sampling (after) ", could reconstruct between 3% and 10% of the sensitive cells. Note that Holoclean uses the learned data correlations (and attribute cooccurrence, domain value frequency) in addition to the explicitly stated data dependencies. However, it is only able to marginally improve upon weighted random sampling given the querier view generated by Our Approach.

RELATED WORK
The challenge of preventing leakage of sensitive data from query answers has been studied in prior work on inference control primarily in the context mandatory access control (MAC) wherein policies specify the security clearances for the users (subject) and the security classification/label for the data. Early work by Denning et al. [28] designed commutative filters to ensure answers returned by a query are equivalent to that which would be returned based on authorized view for the user. This work, however, did not consider data dependencies.
Preventing leakage through dependencies has been explored along different directions. One such direction is to control inferences by design time modifications by adding more MAC policies. Qian et al. [29] developed a tool to analyze potential leakage due to foreign keys in order to elevate the clearance level of data if such a leakage is detected. Delugachi et al. [16] generalized the work in [29] and developed an approach based on analyzing a conceptual graph to identify potential leakage from more general types of data associations (e.g., part-of, is-a). Later works such as [30], however, established that inference rules for detecting inferences at database design time is incomplete and hence is not a viable approach for preventing leakage from query answers. Design time approaches for disclosure control, however, have successfully been used in restricted settings such as identifying the maximal set of non-sensitive data to outsource such that it prevents inferences about sensitive data [24], [31], [32], [33].
Prior work has also explored query time approaches to prevent inferences from data dependencies. Thuraisingham [18] developed a query control approach in the context of MAC policies that uses an inference engine to determine if query answers can lead to leakage (in which case the query is rejected). While [18] assumed a prior existence of an inference detection engine, Brodsky et al. [15] developed a framework, entitled DiMon, based on chase algorithm for constraints expressed as Horn clauses. DiMon takes in current query results, user's query history, and Horn clause constraints to determine the additional data that maybe inferred by the subject. Similar to [18], if inferred data is beyond the security clearance of the subject then their system refuses the query. Such work (that identify if a query leaks/does not leak data) differs from ours since it cannot be used be used directly to identify a maximal secure answer that does not lead to any inferences -the problem we study in this paper. Also, the above work on query control is based on a much weaker security model compared to the full-deniability model we use. It only prevents adversary from reconstructing the exact value of a sensitive cell but cannot prevent them from learning new information about the sensitive cell.
Miklau & Suciu [34] also study the challenge of preventing information disclosure for a secret query given a set of views. Their security model is based on perfect secrecy as they characterize whether there exists any possible database instance for which information disclosure is possible through sharing of views. Our problem setting is different as we check for a given database instance whether it is possible to answer the query hiding as few cells as possible while ensuring full deniability. We could, of course, apply [34] to check if a query is unsafe and in such a case disallow the query. Such a usage of [34] will be extremely pessimistic as most queries will be rejected for a database with non-trivial number of dependencies.
Let us illustrate the differences between their work and ours more concretely using simple examples. Consider a relation schema R with three attributes A, B, C and a functional dependency A → B, and a secret query S that projects the B values of tuples which have C = 5. Also, consider a view V that projects attribute A, B. This view and secret query can be the expressed in the data log notation used by Miklau & Suciu as follows: Based on the secret query and the above view definitions, Miklau & Suciu [34] will determine that V violates perfect secrecy since there exists a database for which the view may reveal sensitive data. As an example, consider the instance of the table R(A, B, C) = {< 1, 1, 5 >, < 1, 1, 6 >}. Note that the value of B for the first tuple is sensitive since the corresponding value of C is 5. Given the functional dependency, the view V (A, B) will indeed leak the sensitive data.
In contrast to [34] which is motivated by determining if a specific view definition could lead to leakage of sensitive data in a data exchange scenario (i.e., if there can exist a database such that the published view may leak information about the secret in that database) our paper is motivated by access control. Our goal is, for a given instance of the database, answer the query, hiding as few cells as possible while ensuring full deniability for sensitive cells (i.e., the adversary cannot eliminate any possible value from the domain of the sensitive cell). In the example above, we will allow a view V to be computed with some cells hidden to ensure full deniability. In particular, a possible answer could be V (A, B) : t 1 : {< 1, N U LL >, t 2 :< N U LL, 1 >} since it allows full deniability of the sensitive cell t 1 [B]. As another example, consider a different instance of D with R(A, B, C) = {< 1, 1, 5 >, < 2, 1, 6 >}. For the above database, given a query that projects attributes A, B, we will return the answer V (A, B) : {t 1 :< 1, N U LL >, t 2 :< 2, 1 >} since for the above instance, the result of the query do not reveal any information about the sensitive cell t 1 [B]. Thus, the work by Miklau & Suciu [34], as mentioned above, does not address access control but determining if view definitions violate perfect secrecy. As a result, irrespective of the database instance, [34] will consider the above view definition to be unsafe.
We note that we could implement access control using the framework developed in their work. In particular, given a query V and sensitive cells (expressed as sensitive query), and constraints encoded as prior knowledge of the adversary, we could check if V violates secrecy of S. If V does violate perfect secrecy, access control can be implemented by preventing V to execute. However, to the best of our knowledge, this is not the intended use case for [34] since the resulting mechanism would be too pessimistic for it to be useful. It would disallow a view (query) for which there exists a database instance that could result in leakage. We thus believe that [34] as described in their work is unsuitable for access control and hence, consider their work to be addressing a different, though loosely related issue. The follow-up work to [34] [35] that relaxed the notion of perfect secrecy to make it more practical 10 . However, none of the extensions addressed the challenge of access control 11 . As such, extensions, along with work by [34] is best suited for determining safety of data publishing and not access control.
Differential Privacy (DP) mechanisms promises to protect against an adversary with any prior knowledge [36]. In our problem setting of access control, the data is either hidden or shared depending upon whether it is sensitive which differs from querier to querier. This is called the Truman model of access control [7], in which the query is answered based on non-sensitive data. In such a model, the expectation of a querier is that the result doesn't include any randomized answers. However, DP based mechanisms involve randomized answers. Weaker notions of DP such as Onesided differential privacy (OSDP) [37] aim to prevent inferences on sensitive data by using a randomized mechanism when sharing non-sensitive data. An advantage of OSDP based approaches in the context of access control is that they offer security guarantees without the knowledge of (or the need to) explicitly specify data dependencies. However, such techniques offer only probabilisitic guarantees (and cannot implement security guarantees such as full deniability), and that too with the suppression of large amount of data. From the results on the expected percentage of released non-sensitive data as a function of privacy parameter presented in [37], OSDP suppresses approx. 91% non-sensitive data at = 0.1 and approx. 37% at = 1. In contrast, our techniques requires only a very small percentage of data to be suppressed by exploiting data dependencies explicity in inference control. OSDP may allow some non-sensitive data to be released based on a coin toss even when their values could lead to leakage of a sensitive cell as it doesn't take into account data dependencies. The current model of OSDP only supports hiding at the row level and is designed for scenarios where the whole tuple is sensitive or not. It is nontrivial to extend to suppress cells with fine-grained access control policies considered in our setting. Furthermore, most DP-based mechanisms (including OSDP) assume that no tuple correlations exist even through explicitly stated data dependencies.

CONCLUSIONS
We studied the inference attacks on access control protected data through data dependencies, DCs and FCs. We developed a new stronger security model called full deniability which prevents a querier from learning about sensitive cells through data dependencies. We presented conditions for determining leakage on sensitive cells and developed algorithms that uses these conditions to implement full deniability. The experiments show that we are able to achieve full deniability for a querier view without significant loss of utility for two different datasets. In future, we would like to extend the security model to not only consider hard constraints explicitly specified in the form of data dependencies but also soft constraints that exist as correlations between data items. The invertibility model in FCs could also be extended to 10. The original definition of perfect secrecy disallowed any leakage, while new definition allow for bounded leakages. Furthermore, checking perfect secrecy is π P 2 -complete even for simple databases which makes it computationally intractable.
11. That is, with the goal to suppress as few cells as possible while answering a query Q given a database D. model probabilistic relationship between input and output cells, instead of being deterministic as in the current model. Improving utility while implementing full deniability is also an open challenge. In k-percentile deniability, the improvement in utility as a factor of k needs to be studied further as factor of different properties of the dataset such as type of attributes, dependency connectivity, dependency instantiations, and possible number of cuesets for a given sensitive cell. Along with further exploration of k-percentile deniability considered in our paper, one could also consider releasing non-sensitive values (like in OSDP) randomly instead of hiding all. However, this requires addressing challenges of any inadvertent leakages through dependencies when sharing such randomized data.

ACKNOWLEDGEMENTS
This work was supported by NSF under Grants 2032525, 1952247, 2008993, and 2133391. This material was based on research sponsored by DARPA under Agreement Number FA8750-16-2-0021. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes not withstanding any copyright notation there on. The views and conclusions contained here in are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of DARPA or the U.S. Government. We thank the reviewers for their detailed comments which helped to improve the paper during the revision process.

APPENDIX A SECURITY AGAINST ATTACKS BASED ON KNOWL-EDGE OF ALGORITHM
Unlike algorithms used for achieving differential privacy (e.g., adding laplace noise to query output), the algorithm (denoted by FDA) used to generate a view with full deniability is deterministic, and as a result, it could be vulnerable to attacks based on knowledge of the algorithm. In particular, an adversary, with knowledge of (a) the output of the FDA algorithm executed over the real dataset, and (b) the FDA algorithm could reexecute FDA against database instances that are consistent with the algorithm's output on the real data and compare the outputs to narrow down the set of possible database instances that might correspond to the real data. Such an attack has been referred to as reverse engineering attack in [38]. Reverse engineering attacks that eliminate possible database instance could, in turn, violate full deniability.
Our goal in this section is to show that reverse engineering attack does not lead to elimination of any viable database instance in FDA. In other words, let D a = {D 1 , . . . , D n } be adversarial apriori knowledge. That is, the adversary knows that the real database, denoted by D real corresponds to one of these database instances D i ∈ D a prior to observing the output of the FDA algorithm. For an adversary with no knowledge of the actual database, D a could be the set of all possible database instances based on the schema that are consistent with the data dependencies. Alternatively, it could be some subset of the above possible instances.
Now consider the adversary with the knowledge of the output of FDA on D real and a set of sensitive cells C S , i.e., FDA(D real , C S ) = (D * , C H ), where D * is the output view with full deniability, and C H is the set of hidden cells in D * . Let D p ⊆ D a be the posterior knowledge of the adversary based on the output of FDA, (D * , C H ) and the knowledge of the algorithm FDA(·, ·). We want to show that any database instance D i ∈ D a from the adversarial apriori knowledge is either (i) incompatible with D * , i.e., the values of the cells that are not hidden in D * do not match with the values of corresponding cells in D i ; or (ii) undeniable, i.e., it cannot be eliminated in the posterior knowledge, i.e., D i ∈ D p .
For the first case, if a D i ∈ D a is incompatible with D * , such an elimination of a database instance from the posterior knowledge does not constitute violation of full deniability since the adversary can determine that D real = D i based on simply the value of the visible cells. For the second case, for a D i ∈ D a that is compatible with D * , if the adversary finds that it is impossible to generate the output (D * , C H ) by running FDA on D i , then there is a leakage as D i cannot be D real and should be eliminated from D p . In order to run FDA, the adversary needs to input a guessed database instance and a set of sensitive cells which can only be a subset of the hidden cells C H . To eliminate D i , the adversary needs to test all possible subsets of C H . We would like to prove that such an elimination is not possible and formalize the security guarantee as follows.
Theorem 5. Let apriori knowledge of adversary be that D real is one of the database instances in D a = {D 1 , . . . , D n }. Let FDA run on D real with a set of sensitive cells C S and output (D * , C H ). For all D i ∈ D a that is compatible with D * , there exists a subset of the hidden cells C H j ⊆ C H such that running FDA(D i , C H j ) returns (D * , C H ).
Proof. (Sketch) For any D i ∈ D a that is compatible with D * , we can show that FDA(D i , C H )=(D * , C H ). In particular, D i that starts with C H as the sensitive cells and hence all hidden already achieves full deniability. FDA does not need to hide more cells, and thus the output is (D * , C H ).

ACKNOWLEDGMENTS
This work was supported by NSF under Grants 2032525, 1952247, 2008993, and 2133391. This material was based on research sponsored by DARPA under Agreement Number FA8750-16-2-0021. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes not withstanding any copyright notation there on. The views and conclusions contained here in are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of DARPA or the U.S. Government. We thank the reviewers for their detailed comments which helped to improve the paper during the revision process.