NW Security database policies

Network security database policy compliance

In a three party data outsourcing model, designing efficient and privacy preserving
protocols for checking compliance of a client's queries to the data owner's query compliance
policy is a critical problem. In this paper a cryptographic model is proposed for the study of
these protocols, they are defined so that they can compose with an underlying database
retrieval protocol in the same participant model. The latest trends in technology has enabled
use of big data in the cloud. Areas such as banking and government process huge data volumes
on a daily basis make use of cloud storage and computing which provide tremendous efficiency
and utility for users but they also create privacy risks. Hence the database management
systems can make use of privacy preserving data retrieval protocols that allow users to submit
queries and receive results in a way that users learn nothing about the contents of a database
except the results in a way that users learn nothing about the contents of a database except the
results of their queries and data owners do not learn which queries are submitted. The use of
access control which requires carefully crafted data access policies is very important for the
successful implementation of the model. Compliance of these policies can be enforced by the
database-management system but might need to be confidential, as the policies themselves
may reveal sensitive facts about the data and its owner. In this paper, we formalize, design, and
analyze practical and privacy-preserving policy compliance protocols for outsourced data.

The primary goal of this paper is to augment encrypted database retrieval solutions with a
query authorization property based on compliance to a policy, while preserving the privacy and
efficiency properties of the basic database retrieval solution. In this paper primary focus is on
the policy compliance building block of the three way database model. The solutions are
combined in a modular fashion with database retrieval protocols provided that they satisfy
some natural structure.

This paper investigates the modeling and design of database policy compliance (DPC) protocols
that combine with known DR protocols and that satisfy the following novel set of requirements
as described below.
1. Preservation of Query Correctness: A client that could retrieve all of the records that satisfy
its query using a DR protocol can still do so if the query is compliant.
2. Compliance Completeness: All queries that satisfy (resp., do not satisfy) the policy are found
to be compliant with probability 1.

3. Compliance Soundness: For any efficient (and even malicious) adversary impersonating the
client, the data owner can correctly compute (except with negligible probability) the policy
compliance of whichever query message is received and answered by the server according to
the DR protocol;

4. Privacy: Privacy of database values, policy values and query values is preserved, in that no
efficient semi-honest adversary corrupting one among the parties C, S,D learns more
information at the end of the protocol thanwhatever is efficiently computable from the
following: the system parameters (which are intended to be known by all parties), the
compliance bit b (if the corrupted party is D, who is intended to learn b), the query message Q_
(if the corrupted party is S, who is intended to learn Q_), where Q_ has the same distribution as
the query message Q in the DR protocol when the query is compliant, or otherwise represents a
query that does not match any records in DB (to reduce leakage of the policy-compliance result
to S or C);
5. Efficiency: The protocol should have low time, communication and round complexity. One of
the most significant design criteria we target to reduce computational overhead of query
compliance checking is to minimize or eliminate costly public-key cryptographic operations and
to achieve protocols faster than a direct application of secure function evaluation techniques.

In this paper three new protocols are introduced for enforcing compliance of keyword search
queries. Here only the whitelist policy types are considered where the query is complaint only if
the query value is equal to one of the policy values. It provides highly efficient and scalable
database policy compliance protocols that satisfy all the requirements as described below.
Requirement
Correctness
preservation
Compliance
completeness
Compliance
soundness
Privacy

Protocol π1
If DR protocol
satisfies Added
Property 1
Under no complexity
assumption.
(not satisfied)
Under PRP
assumption

Protocol π2
If DR protocol
satisfies Added
Property 2
Under no complexity
assumption.
Under no complexity
assumption
Under PRP
assumption

Protocol π3
If DR protocol
satisfies Added
Property 1
Under no complexity
assumption.
Under no complexity
assumption.
Under PRP
assumption And
based on SFE

Time
Communication
Rounds

Linear in policy size
Linear in policy size
O(1) in policy size

Linear in policy size
Linear in policy size
O(1) in policy size

Linear in policy size
Linear in policy size
O(1) in policy size

Previous work:
There has been some work done on 3-party protocols in which the data set being searched is
encrypted, the query is kept private and queries are only allowed if they satisfy certain
structural conditions. There hasn’t been much previous work on privacy preserving , efficient,
query policy compliance checking for database queries and there were no studies in which the
restriction on allowable queries depends on the query and is kept private from the clients. The
current work in the area focuses on policy conditions that mainly depend on the database
attributes or on the identity of the clients or consider different kinds of access control in such
systems. Some cryptographic work has been done in a 3 party model with respect to oblivious
transfer protocols and with respect to private information retrieval. The work done in this
paper is related to a number of areas in theoritical and appliedcryptography, including private
information retrieval, searchable symmetric encryption, searchable public key encryption and
oblivious RAMs.

Data, Query and policy models:
In this paper the database table is modeled as a matrix DB with n rows and m columns, where
each row is associated with a data record, each column is associated with a data attribute and
each database entry DB(i,j) is the value of the jth attribute of the ith record. The database
scheme consists of n,m and the domains of each of the m attributes and is assumed to be
known by all the parties that participate in the protocol. The domains are assumed to be large
and in that a randomly chosen domain element is with a very high probability, not in DB.
A query q contains a database attribute and a query value v from the corresponding attribute
domain. Here keyword match queries are considered which are of the following form “SELECT
∗ FROM main WHERE attribute name = v”.

A data owner’s query compliance policy (briefly, policy) contains, for each attribute j ∈ {1, . .
.,m}, a set Wj = {wj,1, . . . , wj,cj} of policy values drawn from the j-th domain. All of the clients
that access DB through this data owner are subject to the same policy. On input a query value v,
an attribute name, and a set of attribute values Wj, the policy returns 1 to denote query
compliance and the policy returns 0 for non compliance.
Two types of policies are studied in this paper.
1. Whitelist policy: If query q refers to the j-th attribute, then p returns 1 iff v ∈ Wj ;
2. Blacklist policy: If query q refers to the j-th attribute, then p returns 1 iff v _∈ Wj .

A blacklist policy captures a set of forbidden queries whereas a whitelist only allows a set of
allowed query values. It is assumed that the lengths of the blacklist and whitelist are known to
all parties.

DPC Protocols:
The three DPC protocols are described below.
1. Protocol π1 : Protocol π1 is the most basic protocol, it allows efficient enforcement of policy
compliance for keyword search queries with whitelist policies. In this protocol C sends two
double encryptions of its query value v to D, once using kc,d,que as the inner layer, and a
second time using key kc,d,com. Then D and S interact to analogously compute ciphertexts for the
policy values as follows. first, D encrypts each of the policy values w1, . . . , wc using key
kc,d,com and sends the resulting ciphertexts to S; then, S further encrypts each of these
ciphertexts using key kc,s, and returns the resulting ciphertexts, reordered using a random
permutation π, to D. At this point, D computes the whitelist policy output by simply checking
whether one or zero of the policy value ciphertexts is equal to the ciphertext received by C.
After the policy compliance calculation, if the query is compliant, D simply forwards the
received encryption kc,d,que to S, who can remove the outer layer of encryption and fulfill the
query. Otherwise, D performs query rewriting, sending S a random value indistinguishable from
a double-encrypted query.
The two main technical ideas embedded in this protocol are using equality-preserving
encryption to allow D to calculate the policy output without revealing the policy values to S or C
and without learning why the policy was or was not satisfied and using query rewriting to allow
D to rewrite the query q obtained by C into a query q_ which guarantees that the same
database records match q and q_ if q is compliant, or no records match q_ otherwise, without S
or C obtaining any additional information on which is the case.

2. Protocol π2 : Protocol π2 provides security against malicious attacks where Protocol π1 fails.
protocol π1 is that a malicious C can violate the soundness property by sending two different
queries for compliance verification and query rewriting. Here the problem is solved by storage
of a triple encryption F(kc,d, F(kc,s, F(kc,d, v))) of each database value, as in Added DR Property
2, instead of a single encryption F(kc,d, v), as in π1. The structure of the protocol is similar as for

π1. At query time, C encrypts the query value with both of its keys and sends the resulting
doublyencrypted value F(kc,s, F(kc,d, v)) toD. ThenD encrypts each of the policy values wi using
key kc,d and sends them to S, which then re-encrypts each of these using key kc,s, randomly
permutes the order of keywords, and returns the re-encrypted values to D.
As before,Dchecks the encrypted query for equality with the double-encrypted policy values. If
the query is non-compliant, D sends to S a random query indistinguishable from a tripleencrypted real query; otherwise, D re-encrypts F(kc,s, F(kc,d, v)) using kc,d, and sends the
triple-encrypted value F(kc,d, F(kc,s, F(kc,d, v))) to S for its answer generation in the DR
protocol. Note that the outermost layer of encryption prevents S from identifying whether the
query matches policy items it had previously encrypted from D—thus eliminating the need for
separate com and que encryptions. The triplyencrypted database of Added DR Property 2 can
be generated during the setup phase as follows. First, D encrypts all items in the database with
kc,d and sends them to S, which re-encrypts them using kc,s and returns them to D. Then D
adds a third layer of encryption, again using kc,d, and sends the triply-encrypted database to S.

3. Protocol π3 : Protocols π1, π2 come with some leakage to D across multiple query executions,
D learns, by checking for repetitions in the first message sent by C to D, whether the query
value in the current execution is equal to a previously executed query. protocol π3 that keeps
all properties in π1, the compliance soundness property achieved in π2 and satisfies privacy
against D without the mentioned leakage. Protocol π3 uses an additional cryptographic
tool, 2-party Secure Function Evaluation (SFE) protocols. Instead of using a triple encryption as
in π2, protocol π3 uses a different shared key k_c,d for query rewriting. After the policy check,
which remains unchanged, D and S perform a two-party SFE protocol, returning to S a
newlyencrypted form of the query. First, C sends F(kc,s, F(kc,d, v)) to D, at which point the same
policy compliance check as in π2 takes place. After the compliance check, D and S engage in a
two-party SFE protocol, where D inputs F(kc,s, F(kc,d, v)), kc,d, k_c,d, a random query r, and the
(one-bit) result of the compliance check. S inputs kc,s. Together, the two parties securely
compute the following output, which is received only by S: if the query was non-compliant,
random value r is output; if the query was compliant, the doubly-encrypted value F(kc,s, F(kc,d,
v)) is decrypted twice to produce v, which is then encrypted using key k_c,d, and the result, F(k_
c,d, v) is released to S. S then proceeds to compute the answer based on the DR protocol.
The resulting DPC protocol π3, inherits the same properties as π1 and π2, plus multi-query
privacy against D. The protocol π3 is strictly not optimal compared to protocols π1 and π2 as it
has longer running time and it requires inputs as large as the policy itself.

Results:
The setup used to calculate the performance of the protocols introduced in this paper are as
follows. The Data Owner and Server processes were run on a Dell PowerEdge R710 server with
two Intel Xeon 2.66 Ghz processors and 48GB of memory, running 64-bit Ubuntu 12.04.1. The
R710 server was connected to a Dell PowerVault MD1200 disk array containing 12 2TB 7.2K
RPM SAS drives arranged in a RAID6 configuration. The Client was run on a Dell PowerEdge
R810 server with two Intel Xeon 2.40 GHz processors and 64GB of memory, running 64-bit Red
Hat Enterprise Linux Server release 6.3 and connected to the R710 server via switched Gigabit
Ethernet. The database was populated by generating random values about fictitious people
using demographic information from the US Census Bureau. A single table with 23 columns was
used including several columns containing large text fields and one column containing binary
data. The following policies are considered .
 F All queries are rejected as non compliant
 T All queries are accepted as compliant
 B1 A conjunction of at least 3 keyword queries on state, lname, and zip
 B2 A conjunction of at least 3 keyword queries on state, lname, and any
 one of the remaining columns, excluding fingerprint
 W1 A keyword query on lname with query value in a 1-entry whitelist
 W2 A keyword query on lname with query value in a 100-entry whitelist
 W3 A keyword query on lname with query value in a 1000-entry whitelist
 W4 A keyword query on lname with query value in a 10000-entry whitelist
 W5 A keyword query on lname with query value in a 20000-entry whitelist
Each query template was executed several times using different values. We note that policies F,
T, B1 and B2 only refer to the query structure or database attributes and do not depend on
query values, contrarily to queries W1, . . . , W5, which depend on values in the query and in
the (variable-length) whitelist.
The observations made from the simulations are :
(1) running time for B1 is almost the same as for the trivial policies T and F;
(2) running time for B1 and B2 is almost the same for the two policy types Q1
and Q2, with differences smaller than 3 %;
(3) running time for B1 and B2 is essentially linear with policy size.
The computation results show that running time is almost the same again for the two policy
types Q1 and Q2, with differences of less than 7% for shorter policies and less than 2% as
policies get longer and the time required by π1 grows linearly with the size of the whitelist.
It is also observed that as the size of the whitelist grows, so does the time it takes to doubly
encrypt its values, send/receive them between D and S, and checking by using sequential
scan whether an attribute value referenced in C’s query belongs to the doubly encrypted and
permuted whitelist values. It is also observed that the impact of running π1 when checking
compliance is essentially minimal for policies with short-size whitelists.