Blind Seer: A Scalable Private DBMS
Vasilis Pappas∗ , Fernando Krell∗ , Binh Vo∗ ,Vladimir Kolesnikov† , Tal Malkin∗ , Seung Geol Choi‡ , Wesley George§ , Angelos Keromytis∗ , Steven Bellovin∗∗ Columbia University, {vpappas,binh,fkrell,smb,angelos,tal}@cs.columbia.edu† Bell Labs, kolesnikov@research.bell-labs.com‡ US Naval Academy, choi@usna.edu§ University of Toronto, wgeorge@cs.toronto.edu

Abstract—Query privacy in secure DBMS is an importantfeature, although rarely formally considered outside the theoretical community. Because of the high overheads of guaranteeing
privacy in complex queries, almost all previous works addressing
practical applications consider limited queries (e.g., just keyword
search), or provide a weak guarantee of privacy.
In this work, we address a major open problem in private
DB: efficient sublinear search for arbitrary Boolean queries. We
consider scalable DBMS with provable security for all parties,
including protection of the data from both server (who storesencrypted data) and client (who searches it), as well as protectionof the query, and access control for the query.
We design, build, and evaluate the performance of a rich
DBMS system, suitable for real-world deployment on today
medium- to large-scale DBs. On a modern server, we are able toquery a formula over 10TB, 100M-record DB, with 70 searchable
index terms per DB row, in time comparable to (insecure)
MySQL (many practical queries can be privately executed withwork 1.2-3 times slower than MySQL, although some queries arecostlier).
We support a rich query set, including searching on arbitrary
boolean formulas on keywords and ranges, support for stemming,and free keyword searches over text fields.
We identify and permit a reasonable and controlled amount ofleakage, proving that no further leakage is possible. In particular,
we allow leakage of some search pattern information, but protect
the query and data, provide a high level of privacy for individual
terms in the executed search formula, and hide the difference
between a query that returned no results and a query that
returned a very small result set. We also support private andcomplex access policies, integrated in the search process so thata query with empty result set and a query that fails the policy
are hard to tell apart.

I. I NTRODUCTION
Motivation. Over the last two decades, the amount of data
generated, collected, and stored has been steadily increasing. This growth is now reaching dramatic proportions andtouching every aspect of our life, including social, political,
commercial, scientific, medical, and legal contexts. With therise in size, potential applications and utility of these data,
privacy concerns become more acute. For example, the recent
revelation of the U.S. Government’s data collection programs
reignited the privacy debate.
We address the issue of privacy for database management
systems (DBMS), where the privacy of both the data andthe query must be protected. As an example, consider the
scenario where a law enforcement agency needs to search

airline manifests for specific persons or patterns. Because of
the classified nature of the query (and even of the existence ofa matching record), the query cannot be revealed to the DB.
With the absence of truly reliable and trusted third parties,
today’s solution, supported by legislation, is to simply require
the manifests and any other permitted data to be furnishedto the agency. However, a solution that allows the agency to
ask for and receive only the data it is interested in (without
revealing its interest), would serve two important goals:
allay the negative popular sentiment associated with large
personal data collection and management which is not
publicly accounted.
• enhance agencies’ ability to mine data, by obtaining
permission to query a richer data set that could not belegally obtained in its entirety.
•

In particular, we implement external policy enforcement on
queries, thus preventing many forms of abuse. Our systemallows an independent oblivious controller to enforce that
metadata queries satisfy the specificity requirement.
Other motivating scenarios are abundant, including private
queries over census data, information sharing between law
enforcement agencies (especially across jurisdictional and national boundaries) and electronic discovery in lawsuits, whereparties have to turn over relevant documents, but don’t want toshare their entire corpus [33], [43]. Often in these scenarios
the (private) query should be answered only if it satisfies acertain (secret) policy. A very recent motivating example [3]involves the intended use of data from automated license plate
readers in order to solve crimes, and the concerns over its use
for compromising privacy for the innocent.
While achieving full privacy for these scenarios is possiblebuilding on cryptographic tools such as SPIR [24], FHE [21],ORAM [27] or multiparty computation (MPC), those solutions
either run in polynomial time, or have very expensive basic
steps in the sublinear algorithms. For example, when ORAM
is used to achieve sublinear secure computation between two
parties [29], its basic step involves oblivious PRF evaluation.
[29] reports that it takes about 1000 seconds to run a binary
search on 220 entries; subsequent works [22], [39] remain too
expensive for our setting. On the other hand, for data sets ofmoderate or large sizes, even linear computation is prohibitive.
This motivates the following.
Design goals.

Build a secure and usable DBMS system,with rich functionality, and performance very close to existing
insecure implementations, so as to maintain the current modus
operandi of potential users such as government agencies andcommercial organizations. At the same time, we must provide
reasonable and provable privacy guarantees for the system.
These are the hard design requirements which we achievewith Blind Seer (BLoom filter INDex SEarch of Encrypted
Results). Our work can be seen as an example of applying cryptographic rigor to design and analysis of a large
system. Privacy/efficiency trade-offs are inherent in manylarge systems. We believe that the analysis approach we take(identifying and permitting a controlled amount of leakage,and proving that there is no additional leakage) will be usefulin future secure systems.
Significance. We solve a significant open problem in private
DB: efficient sublinear search for arbitrary Boolean queries.
While private keyword-search was achieved in some models,
this did not extend to general Boolean formulas. Natural breaking of a formula to terms and individual keyword-searchingof each leaks formula structure and encrypted results for eachkeyword, significantly compromising privacy of both queryand data. Until our work, and the (very different) independentand concurrent works [11], [31], it was not known how toefficiently avoid this leakage. (See Section IX for extended
discussion on related work.)
A. Our Setting
Traditionally, DB querying is seen as a two-player engagement: the client queries the server operated by the data owner,
although delegation of the server operation to a third player isincreasingly common.
Players. In our system, there are three main players: client C,
server S, and index server IS (there is another logical entity,
query checker QC, whose task of private query compliancechecking is technically secondary, albeit practically important.
For generality, we consider QC as a separate player, although
its role is normally played by either S or IS). We split off
IS from S mainly for performance reasons, as two-player
private DBMS querying has trivial linear in DB size lower
bounds1 , while three non-colluding players allow for far better
privacy-performance trade-offs. We note also that our system
can be generalized to handle multiple clients in several ways(presenting different trade-offs), but we focus our presentationon the single client setting.
Allowed leakage. The best possible privacy for us would
guarantee that C learns only the result set, and IS and S
learn nothing at all. However, achieving this would be quite
costly, and almost certainly far too expensive as a replacement
for any existing DBMS. Indeed, practically efficient equality
checking of encrypted data would likely require the use deterministic encryption, which allows to identify and accumulate
access patterns. Additionally, for certain conjunctive queries,
1 This lower bound can be circumvented if we allow precomputation, as
done for example in the ORAM based schemes mentioned above. However,
the resulting solution is far too inefficient for practice, as even its online phase
is several orders of magnitude slower than our solution.

sublinear search algorithms are currently unknown, even for
insecure DBMS. Thus, unless we opt for a linear time for all
conjunctive queries, the running time already inevitably reveals
some information (see Section VI-B for more discussion).
As a result, we accept that certain minimal amount ofleakage is unavoidable. In particular, we allow players C and IS
to learn certain search pattern information, such as the patternof returned results, and the traversal pattern of the encrypted
search tree. We stress that we still formally prove security of
the resulting system – our simulators of players’ views are
given the advice corresponding to the allowed leakage. We
specify the allowed leakage in more detail in Section VI.
We note that this work was performed under the IARPA
SPAR program [1]. Many of the privacy and functionality requirements we address are suggested by IARPA. In Section X
we provide further motivation, examples and discussion of oursetting and choices.
B. Our Contributions
We design, prove secure, implement and evaluate the first scalable privacy-preserving DBMS which simultaneously satisfies
all the following features (see the following sections for a more
complete description and comparison to previous works):• Rich functionality: we support a rich set of queries
including arbitrary Boolean formulas, ranges, stemming,and negations, while hiding search column names andincluding free keyword searches over text fields in the
database. We note that there is no standard way in
MySQL to obtain the latter.
• Practical scalability. Our performance (similarly to
MySQL) is proportional to the number of terms in thequery and to the result set size for the CNF term withthe smallest number of results.
For a DB of size 10TB containing 100M records with 70
searchable index terms per DB row, our system executes
many types of queries that return few results in well undera second, which is comparable to MySQL.
• Provable security. We guarantee the privacy of the datafrom both IS and C, as well as the privacy of C’s queryfrom S and IS. We prove security with respect to welldefined, reasonable, and controlled leakage. In particular,
while certain information about search patterns and thesize of the result set is leaked, we do provide some
privacy of the result set size, suited for the case whenidentifying that there is one result as opposed to zero
results is undesirable (Section V-B).
• Natural integration of private policy enforcement. We
represent policies as Boolean circuits over the query, andcan support any policy that depends only on the query,with performance that depends on the policy circuit size.
• Support for DB updates, deletions and insertions.
To our knowledge the combination of performance, featuresand provable security of our system has never been achieved,
even without implementation, and represents a breakthroughin private data management. Indeed, previous solutions either
require at least linear work, address a more limited type ofServerIndex Server
0. Index construction

2.
E

n fo

rce
p

ol i

cy

3.
E

keys
yption4. Decr

nc
ry
1.
pt
Se
ed
ar
re
ch
co
rd
s

5. Modifications

Query Checker
ClientFigure 1. High-level overview of Blind Seer. There are three different
operations depicted: preprocessing (step 0), database searching (step 1-4) anddata modifications (step 5).

queries (e.g., just keyword search), or provide weaker privacy
guarantees. The independent and concurrent work of [11], [31](also performed under IARPA SPAR program) is the only
system comparable to ours, in the sense that it too features asimilar combination of rich functionality, practical scalability,
provable security, and policy enforcement. However, the trade
offs that they achieve among these requirements and theirtechnical approach are quite different than ours.
Our scale captures moderate-to-large data, which encompasses datasets in the motivating scenarios above (such as thecensus data, on which we ran our evaluation), and represents
a major step towards privacy for truly “big data”. Our work
achieves several orders of magnitude performance improvement as compared to the fully secure cryptographic solution,and much greater functionality and privacy as compared topractical single keyword search and heuristic solutions.
II. S YSTEM D ESIGN OVERVIEWParticipants. Recall, our system consists of four participants:
server S, client C, index server IS, and query checker QC.
The server owns a database DB, and provides its encrypted
searchable copy to IS, who obliviously services C’s queries.
QC, a logical player who can be co-located with and may
often be an agent of S, privately enforces a policy over thequery. This is needed to ensure control over hidden queries
from C. Player interaction is depicted in Figure 1.
Our approach. We present a high-level overview of ourapproach and refer the reader to Section IV for technical details. We adhere to the following general approach of building
large secure systems, in which full security is prohibitively
costly: in a large problem, we identify small privacy-criticalsubproblems, and solve those securely (their outputs must beof low privacy consequence, and are handled in plaintext).
Then we use the outputs of the subtasks (often only a small

portion of them will need to be evaluated) to complete theoverall task efficiently.
We solve the large problem (encrypted search on largeDB) by traversing an encrypted search tree. This allows thesubtasks of privately computing whether a tree node has a child
matching the (arbitrarily complex) query to be designated as
security-critical. Further, unlike the protected input and theinternals of this subtask, its output, obtained in plaintext by
IS, reveals little private information, but is critical in pruning
the search tree and achieving efficient sublinear (logarithmic
for some queries) search complexity. Putting it together, oursearch is performed by traversing the search tree, where
each node decision is made via very efficient secure function
evaluation (SFE).
We use Bloom filters (BF) to store collections of keywords
in each tree node. Bloom filters serve this role well because
they support small storage, constant time access, and invariance of access patterns with respect to different queries andmatch outputs. For SFE, we use state-of-the-art Yao’s garbled
circuits.
Because of SFE’s privacy guarantee in each tree node, theoverall leakage (i.e. additional information learned by theplayers) essentially amounts to the traversal pattern in theencrypted search tree.
We discuss technical details of these and other aspects ofthe system, such as encrypted search tree construction, data
representation, policy checking, etc., in Section IV. We stressthat many of these details are technically involved.
III. P RELIMINARIES
We assume that readers are familiar with pseudorandom
generators (PRG), pseudorandom functions (PRF), and semihomomorphic encryption schemes with semantic security [28],e.g., ElGamal encryption [19].
Notations. Let [n] = {1, . . . , n}. For `-bit strings a andb, let a ∨ b (resp., a ∧ b and a⊕b) denote the bitwiseOR (resp. bitwise-AND and bitwise-XOR) of a and b. Let
S = (i1 , i2 , . . . , iη ) be a sequence of integers. We define a`
projection of a ∈ {0, 1} on S as a ↓S = ai1 ai2 · · · aiη ; forexample, with S = (2, 4), we have 0101 ↓S = 11. We also
define a filtering of a = a1 a2 . . . a` by S as a‡S = b1 b2 . . . b`
where bj = aj if j ∈ S, or bj = 0 otherwise; for example, withS = (2, 4), we have 1110‡S = 0100. We define a shrinking
function ζm : Nη →Nη as ζm (i1 , i2 , . . . , iη ) = (j1 , j2 , . . . , jη ),where jk = (ik − 1) mod (m + 1); for example, we have
ζ3 (1, 3, 4) = (1, 3, 1).
Bloom filter (BF). A Bloom filter [8] is a well-known data
structure that facilitates efficient search. The filter B is a string
initialized with 0` and associated with a set of η different∗
hash functions H = {hi : {0, 1} →[`]}ηi=1 . For a keyword∗
α ∈ {0, 1} , let H(α) the sequence of the hash results of α,i.e.,H(α) = (h1 (α), h2 (α), . . . , hη (α)).
To add a keyword α to the filter, the hash result H(α) is added
to it, that is, B := B ∨ (1` ‡H(α) ). To see if a keyword β is

in the filter, one needs to check if B contains H(β), that is,?
B↓H(β) = 1η . Bloom filters guarantee no false negatives, andallow the false positive rate to be tuned:ηηt
1 ηt η 
FPbf = 1 − 1 −≈ 1 − e− ` ,
`

...

...

BF...

...
BF1

BF2

... BF10

BF...

BF...

... BF...

R1

R2

R10

R...

R...

R...

BF tree...

...

BF1,10

BF1,N/10...

BF1,N/10...

where t is the number of keywords in the Bloom filter. In
our system, we choose η = 20 and ` = 28.86t to achieve
FPbf ≈ 10−6 .

BF1,N

BFN-9,N

BFN-9 BFN-8
RN-9

RN-8

... BFN
RN

Records

A. Secure Computation Based on Yao’s GC
Yao’s garbled circuit (GC). Yao’s garbled circuits allow
circuits to be evaluated obliviously by one party on hidden
inputs provided by another party. Let C be a Boolean circuitwith n input wires, m gates, and one output wire; let (1, . . . , n)be the indices to the input wires and q = n + m + 1 be
the index to the output wire. To generate a garbled circuit
C̃, a pair of random keys wi0 , wi1 are associated with eachwire i in the circuit; key wi0 corresponds to the value ‘0’ onwire i, while wi1 corresponds to the value ‘1’. Then, for eachgate g in the circuit, with its input wires i, j and its output
wire k, a garbled gate g̃ (consisting of four ciphertexts) isg(b ,b )constructed so that it will enable one to recover wk i j frombwibi and wj j (refer to [14], [36], [40], [48] for more detail.)
The garbled circuit C̃ is simply the collection of all the garbled
gates. By recursively evaluating the garbled gates, one cancompute the garbled key wqb given the keys (w1a1 , . . . , wnan ),where b = C(a1 , . . . , an ). We will sometimes call wire keys
corresponding to input/output garbled input/output, and denotethem by ã and b̃, i.e., ã = (w1a1 , . . . , wnan ), b̃ = wqb . We will
also use the notation of garbled evaluation b̃ = C̃(ã).
Oblivious transfer. An oblivious transfer (OT) [20], [46]is a two-party protocol supporting a sender that holds values(x0 , x1 ) and a receiver that holds an index r ∈ {0, 1}. The
receiver learns xr , but neither the sender nor the receiver learns
anything else, i.e., the receiver learns nothing about any othervalues held by the sender, and the sender learns nothing about
the receiver’s index. We use the Naor-Pinkas protocol [42] asa basis and optimize the performance using OT extension [30]and OT preprocessing [5].
Secure computation. It is known that Yao’s garbled circuit,in combination with any oblivious-transfer protocol yields a
constant-round protocol for secure two-party computation withsemi-honest security [38], [52], [53]. In fact, due to the privacy
guaranteed by Yao’s GC [7], even if the circuit C is a private
input from Alice along with xA , Yao’s GC can also hide
the circuit C from Bob, revealing only the topology of C.
We use GCs not only for search tree traversal but also forpolicy enforcement. Yao’s GC is one of the most efficientalgorithms known for secure computation of functions. For
example, a recent work [51] demonstrated secure evaluationof AES (a circuit with 33880 gates) in 0.2 seconds. We use
the standard techniques of Free-XOR [14], [36] and point-andpermute [40], [48] in constructing garbled circuits.

Let (Ri , . . . , Rn ) be the overall database records. The Bloom filter
BFa,b contains all the keywords of records Ra , Ra+1 , . . . , Rb .
Figure 2. Index structure: Bloom-filter-based search tree.

IV. BASIC S YSTEM D ESIGNIn this section, we will begin by describing the basic systemdesign supporting only simple private query. In the next
section, we will augment this basic design with more features.
A. BF Search TreeOur key data structure enabling sublinear search is a BF searchtree for the database records. We stress that there is only one
global search tree for the entire database. Let n be the numberof database records and T be a balanced b-ary tree of heightlogb n (we assume n = bz from some positive integer z for
simplicity). In our system, b is set to 10. In the search tree,
each leaf is associated with each database record, and eachnode v is associated with a Bloom filter Bv . The filter Bv
contains all the keywords from the (leaf) records that the nodev have (as itself or as its descendants). For example, if a nodecontains a record that has Jeff in the fname field, a keyword
α = ‘fname:Jeff’ is inserted to Bv . The length `v of Bv
is determined by the upper bound of the number of possible
keywords, derived from DB schema, so that two nodes of thesame level in the search tree have equal-length Bloom filters.
The insertion of keywords is performed by shrinking the outputof the hash functions ζ`v (H(α)) to fit in the corresponding BF
length `v . Here, H is the set of hash functions associated withthe root node BF. See Figure 2.
Search using a BF search tree. Consider a simple recursivealgorithm Search below. Let α and β be keywords and r theroot of the search tree. Note that Search(α∧β, r) will output
all the leaves (i.e., record locations) containing both keywords
α and β; any ancestor of a leaf has all the keywords that theleaf has, and therefore there should be a search path fromthe root to each leaf containing α and β. This algorithm canbe easily extended to searching for any monotone Boolean
formula of keywords.
Search(α∧β, v):
If the BF Bv contains α and β, thenIf v is a leaf, then S
output {v}.
Otherwise, output c: children of v Search(α∧β, c).
Otherwise, output ∅.

B. Preprocessing
Roughly speaking, in this phase, S gives an encrypted DB to
IS. To be more specific, by executing the following protocols,
the two parties encrypt and permute the records, create a searchtree for the permuted records, and prepare record decryption
keys.
Encrypting database index/records. In this step, the server
first permutes its DB to hide information of the order ofrecords in the DB and then creates BF-search tree on thispermuted DB; these DB and search tree are encrypted andsent to the index server.
1) (Shuffle and encrypt the records.) The server generates a key pair (pk , sk ) for a public-key semihomomorphic (e.g., additively homomorphic) encryption scheme (Gen, Enc, Dec). Given a database of nrecords, the server S randomly shuffles the records. Let(R1 , . . . , Rn ) be the shuffled records. S then chooses
a random string si , and computes s̃i ← Encpk (si ) andR̃i = G(si )⊕Ri , where G is a PRG.
2) (Encrypt the BF search tree.) S constructs a BF searchtree T for the permuted records (R1 , . . . , Rn ). It thenchooses a key k at random for a PRF F . The Bloom
filter Bv in each node v is encrypted as follows:B̃v = Bv ⊕ Fk (v). (This encryption can be efficiently
decrypted inside SFE evaluation by GC.)
3) (Share) Finally, the S sends the (permuted) encrypted
records (pk , (s̃1 , R̃1 ), . . . , (s̃n , R̃n )) and the encrypted
search tree {B̃v : v ∈ T } to the index server. The client
will receive the PRF key k, and the hash functions H ={hi }ηi=1 used in the Bloom filter generation.
Preparing record decryption keys. To save the decryption
time in the on-line phase, the index server and the server
precompute record decryption keys as follows:(Blind the decryption keys) The index server IS chooses
a random permutation ψ : [n]→[n]. For each i ∈ [n], it
chooses ri randomly and computes s̃0ψ(i) ← s̃i ·Encpk (ri ).
Then, it sends (s̃01 , . . . , s̃0n ) to S. Then, the server decrypts each s̃0i to obtain the blinded key s0i . Note that it
holds s0ψ(i) = si ri .
C. Search
Our system supports any SQL query that can be represented asa monotone Boolean formula where each variable corresponds
to one of the following search conditions: keyword match,range, and negation. So, without loss of generality, we support
non-monotone formulas as well, modulo possible performance
overhead (see how we support negations below). See Figure 3
as an example.
Traversing the search tree privately. The search procedure
starts with the client transforming the query into the corresponding Boolean circuit. Then, starting from the root of thesearch tree, the client and the index server will compute thiscircuit Q via secure computation. If the circuit Q outputs true,
the parties visit all the children of the node, and again evaluate

Query: SELECT * FROM main WHERE(fname = JEFF OR fname = JOHN) AND zip = 34301 AND income ≤ 200
Logic Circuit:

Circuit:

∧
∧

∨
T1

∧

=⇒

T2

T1 :fname = JEFF
T2 :fname = JOHN

T3

T4

∧

∨
T1

T3

T2

T4

T3 :zip = 34301
T4 :income≤200

Figure 3. High level circuit representation of a query.

this circuit Q on those nodes recursively, until they reach leaf
nodes; otherwise, the traversal at the node terminates. Notethat evaluation of Q outputs a single bit denoting the search
result at that node. It is fully secure, and reveals no information
about individual keywords.
In order to use secure computation, we need to specify thequery circuit and the inputs of the two parties to it. However,since the main technicalities lie in constructing circuits for thevariables corresponding to search conditions, we will describe
how to construct those sub-circuits only; the circuit for the
Boolean formula on top of the variables is constructed in astandard manner.
Keyword match condition. We first consider a case wherea variable corresponds to a keyword match condition. For
example, in Figure 3 the variable T1 indicates whether theBloom filter Bv in a given node v contains the keyword α =‘fname:JEFF’. Consider the Bloom filter hash values for the
keyword α, and let Z denote the positions to be checked, i.e.,
Z := ζ`v (H(α)). If the Bloom filter Bv contains the keyword
α, the projected bits w.r.t. Z should be all set, that is, we needto check?
Bv ↓Z = 1η .
(1)
Recall that the index server has an encrypted Bloom filter
B̃v = Bv ⊕ Fk (v), and the client the PRF key k and the hashfunctions H = {hi }ηi=1 . Therefore, the circuit to be computed
should first decrypt and then check the equation (1). That is,
the keyword match circuit looks as follows:
KM((b1 , . . . bη ), (r1 , . . . , rη )) =

η
^
i=1

(bi ⊕ri ).

Here, (b1 , . . . , bη ) is from the encrypted BF and (r1 , . . . , rη )from the pseudorandom mask. That is, to this circuit KM, theindex server will feed B̃v ↓Z as the first part (b1 , . . . , bη ) of
the input, and the client will feed Fk (v) ↓Z as the second(r1 , . . . , rη ). In order that the two parties may execute securecomputation, it is necessary that the client compute Z andsend it (in plaintext) to the index server.
Range/negation condition. Consider the variable T4 in Figure 3 for example. Using the technique from [47], we augment
the BF to support inserting a number x ∈ Z2n , say withn = 32, and checking if the BF contains a number in a given
range.

To insert an integer a in a BF, all the canonical ranges
containing a are added in the filter. A canonical range withlevel i is [x2i , (x + 1)2i ) for some integer x, so for each level,
there is only one canonical range containing the number a.
In particular, for each i ∈ Zn , compute xi such that a ∈[xi 2i , (xi + 1)2i ) and insert ‘r:income:i:xi ’ to the Bloom
filter.
Given a range query [a, b), we check whether a canonicalrange inside the given query belongs to the BF. In particular,
for each i ∈ Zn , find, if any, the minimum yi such that[yi 2i , (yi + 1)2i ) ∈ [a, b) and the maximum zi such that[zi 2i , (zi + 1)2i ) ∈ [a, b); then check if the BF contains a
keyword ‘r:income:i:yi ’ or ‘r:income:i:zi ’. If any of
the checks succeeds for some i, then output yes; otherwise
output no. Therefore, a circuit for a range query is essentiallyORs of keyword match circuits.
For example, consider a range query with Z24 . When inserting a number 9, the following canonical ranges are inserted:[9, 10), [8, 10), [8, 12), [8, 16). Given a range query [7, 11),the following canonical ranges are checked: [7, 8), [10, 11),[8, 10). We have a match [8, 10).
Negation conditions can be easily changed to range conditions; for example, a condition ‘NOT work hrs = 40’ isequivalent to ‘work hrs ≤ 39 OR work hrs ≥ 41’.
Overall procedure in a node. In summary, we describe theprotocol that the client and the index server execute in a nodeof the search tree.
1) The client constructs a query circuit corresponding to
the given SQL query. Then, it garbles the circuit andsends the garbled circuit, Yao keys for its input, and thenecessary BF indices.
2) The client and the index server execute OT so that IS
obtains Yao keys for its input (i.e., encrypted BF). Then,the index server evaluates the garbled circuit and sends
the resulting output Yao key to the client.
3) The client decides whether to proceed based on the
result.

Record Retrieval. When the client and the index server
reach some of the leaf nodes in the tree, the client retrieves
the associated records. In particular, if computing the query
circuit on the ith leaf outputs success, the index server sends(ψ(i), ri , R̃i ) to the client. Then, the client sends ψ(i) to S,
and gets back s0ψ(i) . Note that it holds s0ψ(i) := si ri . The clientC decrypts R̃i using si and obtains the output record.
V. A DVANCED F EATURESIn this section, we discuss how our system supports advanced
features such as query policies, and one-case indistinguishability. We also overview insert/delete/update operations fromthe server.
A. Policy Enforcement
The policy enforcement is performed through a three-party
protocol among the query checker QC (holding the policy),
the client C (holding the query), and the index server IS. A

policy is represented as a circuit that takes a query as input
and outputs accept or reject. In our system, QC garbles thispolicy circuit, and IS evaluates the garbled policy circuit on
the client’s query. A key idea here is to have the client andthe query checker share the information of input/output wire
key pairs in this garbled policy circuit; then, the client canlater construct a garbled query circuit (used in the search tree
traversal) to be dependent on the output of the policy circuit.
Assuming semi-honest security, this sharing of information canbe easily achieved by having the client choose those key pairs(instead of QC) and send them to QC. The detailed procedure
follows.
Before the tree search procedure described in the previous
section begins, the client C, the query checker QC, and theindex server IS execute the following protocol.
m1) Let q = (q1 , . . . , qm ) ∈ {0, 1} be a string that
encodes a query (we will discuss our encoding method
in Appendix A). The client generates Yao key pairs
10)) for the input wires, wm
Wq = ((w10 , w11 ), . . . , (wmof the policy circuit, and a key pair Wx = (t0 , t1 ) for
the output wire. The client sends the key pairs Wq andWx to query checker QC. It also sends the index serverqm).
the garbled input q̃ = (w1q1 , w2q2 , . . . , wm2) Let P be the policy circuit. QC generates a garbled
circuit P̃ using Wq as input key pairs, and Wx as theoutput key pair (QC chooses the other key pairs of P̃ atrandom). Then, QC sends P̃ to the index server.
3) The index server evaluates the circuit P̃ on q̃ obtaining
the output wire key x̃ = P̃ (q̃). Note that x̃ ∈ Wx .
After the execution of this protocol, the original search tree
procedure starts as described before. However, the procedureis slightly changed when evaluating a leaf node as follows:
1) Let Q0 (b, r, x) = Q(b, r) ∧ x be an augmented circuit,
where Q is the query circuit, b and r are the inputs
from IS and C respectively, and x is a bit representing
the output from the policy circuit. The client C generates
a garbled query circuit Q̃0 using wire key pair Wx for thebit x. Then, it sends (Q̃0 , r̃) to the index server, wherer̃ is the garbled input of r.
2) After obtaining the input keys b̃ for b from OT withC, the index server IS evaluates Q̃0 (b̃, r̃, x̃) and sends
the resulting output key to the client. Recall that it has
already evaluated the garbled policy circuit P̃ (q̃) andobtained x̃.
3) The client checks the received key and decides to accept
or reject.
Regarding privacy, the client learns nothing about the policy,
since it never sees the garbled policy circuit. The index server
obtains the topology of the policy circuit (from the garbled
policy circuit).
Note that the garbled policy circuit is evaluated only once,
before the search tree execution starts. Therefore, the policy
checking mechanism introduces only a small overhead. It isalso worth observing that, so far, we have not assumed any
restriction on the policy to be evaluated. Since Yao-based

computation can compute any function represented as a circuit,in principle, we could enforce any policy computable in areasonable time (as long as it depends only on the query). We
describe our own implemented policy circuit in more detail in
Appendix A.

chosen with Pr[b = 1] = δ, and v is the view of the index
server when the query q is run on Db . The system satisfies 
one-case indistinguishability if for any (q, D0 , r), δ and v, itholds
Pr[b = 1|v] ≤ (1 + )δ.

B. One-case Indistinguishability

Augmenting the design. To achieve these indistinguishability
notions, we change the design such that the client chooses asmall random number of paths leading to randomly selected
leaves. In particular, let D be the probability distribution on
the number of random paths defined as follows:

So far, in our system the index server learns how manyrecords the client retrieved from the query. In many use cases,
this leakage should be insignificant to the index server, inparticular, when the number of returned results is expected tobe, say, more than a hundred. However, there do exist some use
cases in which this leakage is critical. For example, supposethat a government agent queries the passenger database ofan airline company looking for persons of interest (POI). We
assume that the probability that there is indeed a POI is small,and the airline or the index server discovering that a query
resulted in a match may cause panic. Motivated from the above
scenario, we consider a security notion which we call one-caseindistinguishability.
Motivation. Consider a triple (q, D0 , r) where q is a query,and D0 is a database with the query q resulting in no record,
but r satisfies q. Let D1 be a database that is the same as
D0 except that a record is randomly chosen and replaced withr. Let VIEW0 (resp. VIEW1 ) denote the view of IS when theclient runs a query q with the database D0 (resp., D1 ).
A natural start would be to require that for any such(q, D0 , r), the difference between the two distributions VIEW0and VIEW1 should be small  (in the computational sense),
which we call  zero-one indistinguishability. However, it does
not seem possible to achieve negligible difference  without
suffering significant performance degradation (in fact, oursystem satisfies this notion for a tunable small constant ).
Unfortunately, this definition does not provide a good security
guarantee when the difference  is non-negligible, in particular,
for the scenario of finding POIs. For example, let Π be adatabase system with perfect privacy and Π0 be the same asΠ except that when it is 1-case (i.e., a query with one result
record), the client sends the index server the message “the 1case occurred” with non-negligible probability. It is easy to
see that Π0 satisfies the definition with some non-negligible ,
but it is clearly a bad and dangerous system.
One-case indistinguishability. Observe that in the use case offinding POIs, we don’t particularly worry about “the 0-case”,
that is, it is acceptable if the airline company sometimes knowsthat a query definitely resulted in no returned record. Motivated by this observation, this definition intuitively requiresthat if the a-priori probability of a 1-case is δ, then a-posteriori
probability of a 1-case is at most (1+)δ. For example, for = 1, the probability could grow from δ to 2δ, but nevermore than that, no matter what random choices were made.
Moreover, if the a-priori probability was tiny, the a-posteriori
probability remains tiny even if unlucky random choices were
made. In particular, consider (q, D0 , r) and D1 as before. Now
consider a distribution E that outputs (b, v) where b ∈ {0, 1}

E

Distribution D:

For 1 ≤ x ≤ α − 1, PrD [x] = 1/α.

For x ≥ α, PrD [x] = (1/α) · 1/2x−α+1 .

Here, α is a tunable parameter. The client chooses x← D,
and then it also chooses x random indices (j1 , . . . , jx )← [n]x .
When handling the query, the client superimposes the basic
search procedure above with these random paths. Our system
is 1/α zero-one indistinguishable and  one-case indistinguishable with  = 1. Intuitively, the leakage to the index server isthe tree traversal pattern, and these additional random paths
make the 0-case look like 1-case with a reasonably good
probability. We give more detail in Appendix B.
If we slightly relax the definition and ignore views taking place with a tiny probability, say 2−20 , we can evenachieve both 1-case and 0-case indistinguishability at the sametime; the probability of the number x of fake paths is now
1/2|x−α|+2 with a parametrized center α, say α = 20 (except
when x = 0, i.e., Pr[x = 0] = 1/2α+1 ).
Against the server. One-case indistinguishability against theserver is easily achieved by generating a sufficient number ofdummy record decryption keys in the preprocessing phase; theindex server will let the client know the (permuted) positionsof the dummy keys. When zero records are returned from aquery, the client asks for a dummy decryption key from theserver. For brevity, we omit the details here, and exclude thisfeature in the security analysis.
C. Delete, Insert, and Update from the Server
Our system supports a basic form of dynamic deletion,
insertion, and update of a record which is only available
to the server. If it would like to delete a record Ri , thenthe server sends i to the index server, which will markthe encrypted correspondent as deleted. For newly inserted(encrypted) records, the index server keeps a separate list forthem with no permutation involved. In addition, it also keeps
a temporary list of their Bloom filters. During search, thetemporary list is also scanned linearly, after the tree. Whenthe length of the temporary Bloom filter list reaches a certain
threshold, all the current data is re-indexed and a new Bloom
filter tree is constructed. The frequency of rebuilding the tree
is of course related to the frequency of the modifications andalso the threshold we choose for the temporary list’s size. Our
tree building takes one hour/100M records. Finally, update issimply handled by atomically issuing a delete and an insert
command.

Functionality Fdb
Parameter: Leakage profile.
Init: Given input (D, P ) from S, do the following:
1) Store the database records D and the policy P . Letn be the number records in D. Shuffle D and let(R1 , . . . , Rn ) be the shuffled records. Choose a random
permutation π : [n]→[n]. Construct a BF-search tree for(R1 , . . . , Rn ) using the hash functions H.
2) To handle the client’s queries, it chooses hash functions
H = {hi : {0, 1}∗ →[`]}ηi=1 for Bloom filters withparameters (η, `) to maintain false positive rate of 10−6 .
3) Finally, return a DONEinit and the leakage to all parties.
Query: Given input q from C, do the following:
1) Check if q is allowed by P . If the check fails, thendisallow the query by setting y = ∅. Otherwise, for each0i ∈ [n], let Bi ∈ {0, 1}` be the Bloom filter associatedwith the ith leaf in the BF tree. For i = 1, . . . , n, checkif the query passes according to the filter Bi (refer to
Section II); if so, add (i, Ri ) to the result set Y .
2) Return Y to C and return a DONEquery message andleakage to all parties.
Figure 4. The Ideal Functionality Fdb

We note that updates is not our core contribution; we
implement and report it here, but don’t focus on its design
and performance. A more scalable update system would use
a BF tree rather than a list; its implementation is a simple
modification to our system.
VI. S ECURITY A NALYSIS
In this section, we present an overview of the security of oursystem. A full analysis with formal definitions and extensive
proofs is completed and written separately.
We consider static security against a semi-honest adversarythat controls at most one participant. We first describe an
ideal functionality Fdb parameterized with a leakage profile
in Figure 4, and then show that our system securely realizes
the functionality where the leakage is essentially the searchtree traversal pattern and the pattern of accessed BF indices.
For the sake of simplicity, we only consider security where
there are no insert/delete/update operations,2 and unify theserver and the query checker into one entity. We also assume
that all the records have the same length.
We use the DDH assumption (for ElGamal encryption andNaor-Pinkas OT), and our protocols are in the random oracle
model (for Naor-Pinkas OT and OT extension). We also use
PRGs and PRFs, and those primitives are implemented withAES.
2 As access patterns are revealed, additional information for inserted/deleted/updated records is leaked. For example, C or IS may learn
whether a returned record was recently inserted; they also may get advantage
in estimating whether the query matched a recently deleted record. We stressthat this additional leakage can be removed by re-running the setup of thesearch structure.

A. Security of Our System
With empty leakage profile, the ideal functionality Fdb in
Figure 4 captures the privacy requirement of a databasemanagement system in which each query is handled deterministically. The client obtains only the query results, but
nothing more. The index server and the server learn nothing.
Realizing such a functionality incurs a performance hit. Our
system realizes the functionality Fdb with the leakage profile
described below. The security of our system can be proved
from the security of the secure computation component, andis deferred to the full version.
Leakage in Init. Since the server has all the input, the leakage
to S is none. The leakage to C is n, that is, the total numberof records. The leakage to IS is n and |R1 |.

Leakage to S in each query. We first consider the leakage
to the server. The server is involved only when the record is
retrieved. Let ((i1 , Ri1 ), . . . , (ij , Rij )) be the query results.
Then, the leakage to the server is (π(i1 ), π(i2 ), . . . , π(ij )).
Leakage to C in each query. The leakage to the client is
the BF-search tree traversal paths, that is, all the nodes v inwhich the query passes according to the filter Bv .
Leakage to IS in each query. The leakage to the index
server is a little more than that to the client. In particular,
the nodes in the faked paths that the client generates due
to one-case indistinguishability are added to the tree searchpattern. Also, the topology of the query circuit and of thepolicy circuit is leaked to IS as well. Finally, the BF indices arealso revealed to IS (although not the BF content), but assumingthat the hash functions are random, those indices reveal little
information about the query. However, based on this, after
observing multiple queries, IS can infer some correlations a
C’s queries’ keywords.
B. Discussion
Leakage to the server. We could wholly remove the leakage
to the server by modifying the protocol as follows:
Remove the decryption key preparation (and blindedkeys) in the preprocessing; instead, the client receives the secret key sk from the server. The client(as the receiver) and the index server (as the sender)
execute oblivious transfer at each leaf of the searchtree. The choice bit of the client is whether the
output of the query circuit is success. The two
messages of the index server is the encrypted recordand a string of zeros.
However, we believe that it is important for the server to beable to upper-bound the number of retrieved records. Without
such control, misconfiguration on the query checker side may
allow overly general queries to be executed, causing too manyrows to be returned to the client; in contrast, in our approach,S releases record decryption keys at the end, and therefore
it is easy to enforce the sanity check of the total number ofreturned records. Moreover, if S has a commercial DB, it may

be convenient to implement payment mechanism in association
with key release by S.
OR queries. For OR queries passing the policy, our system
leaks extremely small information. In particular, the leakage
to the client is minimal, as the tree traversal pattern can bereconstructed from the returned records. As a consequence, if
the client retrieves only document ids, the client learns nothing
about the results for individual terms in his query. The leakage
to the index server is similar. We believe that the topologyof the SQL formula and the policy circuit reveals small
information about the query and the policy. If desired, we caneven hide those information using universal circuits [37] witha circuit size blow-up of a logarithmic multiplicative factor.
AND queries. For AND queries, the tree traversal patternconsists of two kinds of paths. The first are, of course, thepaths reaching the leaves (query results). The second stopat some internal nodes due to our BF approach3 ; although
the leakage from this pattern reveals more information about
which node don’t contain a given keyword, we still believe
this leakage is acceptable in many use cases.
We stress that the second leakage is related to the fact thata large linear running time seems to be inherent for someAND queries, irrespective of privacy, but depending only on
the underlying database (see Section VIII-C for more detail).
Therefore, if we aim at running most AND queries in sublinear
time, the running time will inherently leak information on theunderlying DB.
VII. I MPLEMENTATION
We built a prototype of the proposed system to evaluate
its practicality in terms of performance. The prototype wasdeveloped from scratch in C++ (a more than a year effort,
almost two years including designing) and consists of about
10KLOC. In this section, we describe several interesting partsof the implementation that are mostly related to the scalabilityof the system.
Crypto building blocks. We developed custom implementations for all the cryptographic building blocks that werepreviously described in Section II. More specifically, weused the GNU Multiple Precision (GMP) library to implement oblivious transfers, garbled circuits and the semihomomorphic key management protocol. The choice of GMP
was mostly based on thread-safety. As for AES-based PRF, weused the OpenSSL implementation because it takes advantageof the AES-NI hardware instructions, thus delivering better
performance.
Parallelization. The current implementation of Blind Seer
supports parallel preprocessing and per-query threading whensearching. For all the multi-threading features we used Intel’sThreading Building Blocks (TBB) library. To enable multithreaded execution of the preprocessing phase we created
3 For example, consider a query q that looks for two keywords, say, q =α∧β. Let v be some node and c1 , . . . , cb be the children of v in the searchtree. If c1 contains only α, and c2 contains only β, then v will contain both
α and β, and so the node v will pass the query; however, neither c1 nor c2
would.

a 3-stage pipeline. The first stage is single-threaded and it
is responsible for reading the input data. The second stage
handles record preprocessing. This stage is executed in parallelby a pool of threads. Finally, the last stage is again singlethreaded and is responsible for handling the encrypted records.
Concurrently supporting multiple queries was straightforward
as all the data structures are read-only. To avoid accessing theBloom filter tree while it is being updated by a modificationcommand, we added a global writer lock (which does notblock reads). Since we only currently support parallelization on a one-thread-per-query basis, it only benefits query
throughput, not latency. However, long-running queries involvea large amount of interaction between querier and serverthat is independent and thus amenable to parallelization. The
improvement we see in throughput is a good indicator for how
much we could improve latency of slow queries by applying
parallelization to these interactions.
Bloom filter tree. This is the main index structure of
our system which grows by the number of records and the
supported features (e.g., range). For this reason, the space
efficiency of the Bloom filter tree is directly related to thescalability of the system. In the current version of our system
we have implemented two space optimizations: one on the
representation of the tree and another on the size of Bloom
filter in each tree node.
Firstly, we avoided storing pointers for the tree representation, which would result in wasting almost 1G of memoryfor 100M records. This is achieved by using a flat array with
fixed size allocations per record.
Secondly, we observed that naively calculating the numberof items stored in the inner nodes by summing the items of
their children is inefficient. For example, consider the caseof storing the ‘Sex’ field in the database, which has only
two possible values. Each Bloom filter in the bottom layerof the tree (leaves) will store either the value sex:male orsex:female. However, their parent nodes will keep space for
10 items, although the Sex field can have only two possible
values. Thus, we estimate the number of items that need to be
stored in a given level as the minimum between the cardinalityof the field and the number of leaf-nodes of the current subtree.
This optimization alone reduced the total space of the tree bymore than 50% for the database we used in our evaluation.
Keyword search and stemming. Although we focus on
supporting database search on structured data, our underlying
system works with collections of keywords. Thus, it cantrivially handle other forms of data, like keyword searchover text documents, or even keyword search on text fields
of a database. We actually do support the latter – in oursystem we provide this functionality using the special operator CONTAINED_IN(column, keyword). Also, we support
stemming over keyword search by using the Porter stemmingalgorithm [2].
VIII. E VALUATIONIn this section, we evaluate our system. We first evaluate oursystem as a comparison with MySQL as a baseline, to establish

300

0.7

MySQL

MySQL

Total query time (secs)

Total query time (sec)0.8

BlindSeer

0.6
0.5
0.4
0.3
0.2

250

BlindSeer

200

150

100

50

0.1
0

0

0

int−id int−star str−id str−starsingle single single single

int−id2−10int−star2−10

str−id2−10

str−star
2−10

1000

2000

3000

4000

5000

Number of results

Figure 5. Comparison with MySQL for single-term queries that have a single
result (first four bar groups) and 2 to 10 results (last four bar groups). The
search terms are either strings (str) or integers (int) and the returned result iseither the id or the whole record (star).

Figure 6. Comparison of the scaling factor with respect to the result set
size, using single-term queries. Both MySQL and Blind Seer scale linearly,
however, Blind Seer’s constant factor is 15× worse (mostly due to increased
network communication).

what the performance cost of providing private search is. We
then generalize the performance expectations of our system byperforming a theoretical analysis based on the type of queries.
Dataset. The dataset we use in all of our tests for the firstpart of the evaluation is a generated dataset using learned
probability distributions from the US census data and text
excerpts from “The Call of the Wild”, by Jack London. Each
record in our generated database contains personal information
generated with similar distributions to the census. It also
contains a globally unique ID, four fields of random text
excerpts ranging from 10 − 2000 bytes from “The Call of theWild”, and a “fingerprint” payload of random data ranging
from 50000 to 90000 bytes. The payload is neither searchable
nor compressible, and is included to emulate reasonable datatransfer costs for real-world database applications. The census
data fields are used to enable various types of single-term
queries such as term matching and range queries, and the text
excerpts for keyword search queries.
Testbed. Our tests were run on a four-computer testbed
that Lincoln Labs set up and programmed for the purposeof testing our system and comparing it to MySQL. Each
server was configured with two Intel Xeon 2.66 Ghz X5650
processors, 96GB RAM (12x8 GB, 1066 MHz, Dual Ranked
LV RDIMMs), and an embedded Broadcom 1GB Ethernet
NICS with TOE. Two servers were equipped with a 50TB
RAID5 array, and one with a 20TB array. These were used
to run the owner and index server. MySQL was configured
to build separate indices for each field. DB queries were notknown in advance for MySQL or for our system.

are further grouped into those which are run on integer fields(int) and string fields (str), and those which return only record
ids (id) and those which return full record content (star). For
each group, we executed 200 different queries to avoid cachingeffects in MySQL.
As we can see, for single result set queries, our system
is very consistent. Unlike with MySQL, the type of query
has no effect on performance, since all types are stored
and queried the same way in the underlying Bloom filter
representation. Also, the average time is dominated by theaverage number of results, which is slightly larger for integer
terms. Unexpectedly, there is also no performance difference
for returning record ids versus full records. This is likely
because for a single record, the performance is dominatedby other factors like circuit evaluation, tree traversal and key
handling, rather than record transfer time. Overall, aside fromsome bad-case scenarios, we are generally less than 2× slower.
Variation in performance of our system is much larger whenreturning a few results. This is because the amount of tree
traversal that occurs depends on how much branching mustoccur. This differs from single result set queries, where eachtree traversal is a single path. With the larger result sets, we
can also begin to see increased query time for full records as
opposed to record ids, although it remains a small portion of
the overall run time.

A. Querying Performance
Single term queries with a small result set. Figure 5
shows a comparison of single term queries against MySQL.
We expect the run time for both our system and MySQL todepend primarily on the number of results returned. The first
four pairs show average and standard deviation for query timeon queries with exactly one result in the entire database, andthe latter four for queries with a few (2-10) results. Queries

Scaling with result set size. Figure 6 expands on both
systems’ performance scaling with the number of results
returned. This experiment is also run with single term queries,
but on a larger range of return result set sizes. As one would
expect, the growth is fairly linear for both systems, although
our constant factor is almost 15× worse. This indicates that for
queries with a small result set, the run time is dominated byadditive constant factors like connection setup for which weare not much slower than MySQL. However, the multiplicative
constant factors involved in our interactive protocol are muchlarger, and grow to dominate run time for longer runningqueries. This overhead is mostly due to increased network
communication because of the interactiveness of the search

1000

Total query time (sec)MySQL
BlindSeer
100

10

1
0
and−1−1

and−1−100

and−1−10K

dnf−mondnf−neg

Figure 7. Boolean queries having a few results (< 10). The first three are
two-term AND queries where one of the terms has a single result and theother varies from 1 to 10K results. The fourth group includes monotonic DNF
queries with 4-9 terms, the last includes 5-term DNF queries with negations.

protocol. Although this is inherent, we believe that there isroom for implementation optimizations that could lower thisconstant factor.
Boolean queries. Figure 7 shows our performance on various
Boolean queries. The first three groups show average query
time for 2-term AND queries. In each case, one term occurs
only once in the database, resulting in the overall Boolean
AND having only one match in the database. However, thesecond term increases up to 10000 results in the database.
As we can see, our query performance does not suffer; aslong as at least one term in a Boolean is infrequent we will
perform well. The next two groups are more complex Boolean
queries issued in disjunctive normal form, the latter including
negations. The first one includes queries with 4-9 terms, andthe second one, with 5 terms. These incur a larger cost, as
the number of a results is larger and possibly a bigger partof the tree is explored. As we can see, MySQL incurs a
proportionally similar cost.
We note that the relatively large variation shown in the graphis due to the different queries used in our test. Variation ismuch smaller when we run the same query multiple times.
Parallelization. We have implemented a basic form ofparallelization in our system, which enables it to execute
multiple queries concurrently. As there are no critical sections
or concurrent modifications of shared data structures during
querying, we saw the expected linear speedup when issuingmany queries up to a point where the CPU might not be
the bottleneck anymore. In our 16-core system, we achieved
approximately factor 6x improvement due to this crude parallelization.
Discussion. We note several observations on our system,
performance, bottlenecks, etc.
Firstly, we note that our experiments are run on a fast local
network. A natural question is how this would be translated
into the higher-latency lower bandwidth setting. Firstly, there
will be performance degradation proportional to bandwidth
reduction, with the following exception. We could use theslightly more computationally-expensive, but much less com-munication intensive GESS protocol of [34] or its recent
extension sliced-GESS [35], instead of Yao’s GC. In reducedbandwidth settings, where bandwidth is the bottleneck, slicedGESS is about 3x more efficient than most efficient Yao’s
GC. Further, we can easily scale up parallelization factor to
mitigate latency increases. Looking at this in a contrapositive
manner, improving network bandwidth and latency would
make CPU the bottleneck.
All search structures in our system are RAM-resident. Only
the record payloads are stored on disk. Thus, disk should not
be a bottleneck in natural scenarios.
B. Other Operations
Although querying is the main operation of our system, we
also include some results of other operations. First, we startwith the performance of the setup phase (preprocessing). Blind
Seer took roughly two days to index and encrypt the 10TB
data. As mentioned before, this phase is executed in parallel
and is computationally efficient enough to be IO-bounded in
our testbed. We note that the corresponding setup of MySQL
took even longer.
Policy enforcement was another feature for which we
wanted to measure overhead. However, in our current implementation, it cannot be disabled (instead, we use a dummy
policy). We experimentally measured the overhead of enforcing the dummy policy versus more complex ones, but there
was no noticeable difference. We plan to add the functionality
to totally disable policy enforcement – because it is an optionalfeature – and measure its true performance overhead. Our
expectation is that it will be minimal.
Finally, we performed several measurements for the supported modification commands: insert, update and delete. Allof them execute in constant time in the order of a few hundred
microseconds. The more expensive part though is the periodic
re-indexing of the data that merges the temporary Bloom filter
list in the tree (see Section V-C). In our current prototype,we estimated this procedure to take around 17 minutes, while
avoiding re-reading the entire database. This can be achievedby letting the server store some intermediate indexing data
during the initial setup and reusing it later when constructing
the Bloom filter tree.
C. Theoretical Performance Analysis
In this section, we discuss the system performance for various
queries by analyzing the number of visited nodes in the searchtree. Let α1 , . . . , αk be k single term queries, and for eachi ∈ [k], let ri be the number of returned records for the query
αi , and n be the total number of records.
OR queries. Our system shows great performance with OR
queries. In particular, consider a query α1 ∨ · · · ∨ αk . The
number of visited nodes in the search tree is at most r log10 n,
where r = r1 + . . . + rk is the number of returned records.
Therefore, performance scales with the size of the result set,just like single term queries.
AND queries. The performance depends on the best constituent term. For the AND query α1 ∧ · · · ∧αk , the number ofvisited nodes in the search tree is at most min(r1 , . . . , rk ) ·log10 n. Note that the actual number of returned records may
be much smaller than ri s. In the worst case, it may even be0; consider a database where a half of the records contain α(but not β) and the other half β (but not α). The running
time for the query α∧β in this case will probably be linear
in n. However, we stress that this seems to be inherent, even
without any security. Indeed, without setting up an index, every
algorithm currently known runs in linear time to process thisquery.
This can be partially addressed by setting up an index, in
our case by using a BF. For example, for AND queries on
two columns, for each record with value a for column A,
and value b for column B, the following keywords are added:
A:a, B:b, AB:a.b. With this approach, the indexed AND
queries become equivalent to single term queries. However,this cannot be fully generalized, as space grows exponentiallyin the number of search columns.
Complex queries. The performance of CNF queries can beanalyzed by viewing them as AND queries where each disjunct(i.e, OR query) is treated as a single term query. In general, anyother complex Boolean query can be converted to CNF andthen analyzed in a similar manner. In other words, performancescales with the number of results returned by the best disjunctwhen the query is represented in CNF. Note that we do not
actually need to convert our queries to this form
(nor know anything about the data, in particular, which
are high- or low-entropy terms) in order to achieve thisperformance (this aspect is even better than MySQL).
Computation and Communication. Both computationaland communication resources required for our protocol areproportional to the query complexities described above.
False Positives. As our system is built on Bloom filters, false
positives are possible. In our experiments, we set each BF
false positive rate to 10−6 . Assuming the worst-case scenario
for us, where the DB is such that many of the search paths doreach and query the BFs at the leaves, this gives 10−6 false
positive probability for each term of the query. Of course, thefalse positive is a tunable parameter of our system.
IX. R ELATED W ORK
The problem of private DBMS can be solved by general purpose secure computation schemes [26], [38], [52], [53]. These
solutions, however, involve at least linear (often much more)work in the database size, hence cannot be used for practicalapplications with large data. Oblivious RAM (ORAM) [27]can be used to completely hide the client’s query pattern,
and can also be used as a tool to achieve sublinear amortized
time for secure computation if we allow to leak the program
running time [29], [39]. Nonetheless, computational costs arestill prohibitively high, rendering these solutions impractical
for the scale we are interested in.
Private Information Retrieval protocols (PIR) [16] consider
a scenario where the client wishes to retrieve the ith record of
the server’s data, keeping the server oblivious of the index i.

Symmetric PIR protocols [24] additionally require that client
should not learn anything more than the requested record.
While most PIR and SPIR protocols support record retrieval
by index selection, Chor et al. [15] considered PIR by keyword. Although these protocols have sublinear communication
complexity, their computation is polynomial in the number ofrecords, and inefficient for practical uses.
Another approach would be to use fully homomorphic
encryption (FHE). In 2009, Gentry [21] showed that FHE istheoretically possible. Despite this breakthrough and many follow up works, current constructions are too slow for practicaluse. For example, it is possible to homomorphically compute
720 AES blocks in two and a half days [23].
Little work has appeared on practical, private search ona large data. In order to achieve efficiency, weaker security(some small amount leakage) has been considered. The workof [44], [47] supports single keyword search and conjunctions.
However, the solution does not scale well to databases witha large number of records (say millions); its running time islinear in the number of DB records. One of the interesting
features of this work is the way they address range queries.
Our system also uses their idea to achieve range queries,and extends it to support negations (since we use a sublinear
underlying OR query, our range queries are also sublinear, incontrast to them). A more efficient solution towards this end
was proposed in [18]. However, they only considered single
keyword search.
Any single keyword search solution can be used to solve(insecurely) arbitrarily Boolean formulas; solve each keyword
in the formula separately and then combine (insecurely).
Obviously, however, this leaks much more information to theparties (and also has work proportional to the sum of the workfor each term). Our system, in contrast, provides privacy ofthe overall query (and work proportional to just the smallestterm).
There has been a long line of research on searchable
symmetric encryption (SSE) [11]–[13], [17], [25], [41], [50].
Note that, although many of the techniques used in SSE
schemes can be used in our scenario, the SSE setting focuses
on data outsourcing rather than data sharing. That is, in SSE
the data owner is the client, and so no privacy against theclient is required. Additionally, SSE solutions often offer either
a linear time search over the number of database records[12], [41], [50], or a restricted type of client’s queries [17],[32], namely single keyword search or conjunctions. One
exception is the recent SSE scheme of [11], which extended
the approach of [17] to allow for any Boolean formula of theform k0 ∧φ(k1 , ..., km−1 ), where φ(·) is an arbitrarily Boolean
formula. Their search time complexity is O(m×D(k0 )), whereD(k0 ) is the number of records containing keyword k0 . Notethat an arbitrary formula could be represented this way, as
k0 can always be set to true, but then the complexity will
be linear in the number of records. On the other hand, if theclient can format the query so that k0 is a term with very
few matches, the complexity will go down accordingly. In
contrast, our solution addresses arbitrary Boolean formulas,with complexity proportional to the best term in the CNF
representation of the formula. Searchable encryption has also
been studied in the public key setting [4], [6], [9], [10], [49].
Here, many users can use the server public key to encrypt theirown data and send it to the server.
The CryptDB system [45] addresses the problem of DB
encryption from a completely different angle, and as such islargely incomparable to our work. CryptDB does not aim toaddress the issue of the privacy of the query (but it does
achieve query privacy similar to the single-keyword searchsolution described above). Their threat scenario focuses on
DB data confidentiality against the curious DB administrator,
and they achieve this by using a non-private DBMS over what
they call SQL-aware encrypted data. That is, the SQL query is
pre-processed by a fully trusted proxy that encrypts the searchterms of the query. The query is then executed by standard
SQL, which combines the results of individual-term encrypted
searches. Additionally, for free-text search, CryptDB uses thelinear solution of [50].
The closest to our setting/work is a a very recent extension [31] of the SSE solution [11], which additionally(to the SSE requirements) addresses data privacy against theclient (and hence, as we do, addresses private DB). We notethat the work of [11], [31] is performed independently andconcurrently to ours. [31] support the same class of functions
as [11] (discussed above). In the worst case, such as when theclient has little a priori information about the DB and chooses
a sub-optimal term to appear first in the query term, thecomplexity of the [31] solution can be linear in the DB size.
In contrast, our solution for general formulas does not dependon the client’s knowledge of data distribution or representation
choice (beyond the size of the formula). However, we note thatfor typical practical applications this is not a serious issue,
as the client can represent his query as a conjunction, andmoreover, can make a good guess for which term will have
low frequency in the data and is a good choice as the firstterm. Thus, a large majority of practically useful queries canbe evaluated by [31] with asymptotic complexity similar toours. In terms of security, our guarantees vary: [31] achieves
security against malicious client, which is much stronger thanour semi-honest setting, and of particular importance for thepolicy enforcement. Our leakages vary and are incomparable.
We and [31] leak different access pattern structures (searchtree for us and index lookups for [31]). Because we use amore expensive basic step of SFE, our protection of queryrelated data, at least in some cases, is somewhat better. For
example, depending on the DB data, we may hide everything
about the individual terms of the query, while [31] leak to
the client and (their counterpart of the) IS the support sizes
for individual terms of the disjunctive queries (individual term
supports are revealed to the client, but this is only an issue if
the query does not ask for all the columns of the records).
At the same time, the concrete query performance of [31] issomewhat better than ours, due to their elegant non-interactive
approach. The very expensive step of DB setup is faster for
us, and the CPU load is lower, as we use mainly symmetric-

key primitives. We also note that our interactive approachallows significant flexibility. For example, the 0-1 security(cf. Section V-B), is naturally and cheaply achievable in oursystem; it appears harder/more expensive to achieve in a noninteractive system, and in fact is not considered in [10]. The
use of GC as the basic block similarly provides significant
flexibility and opportunities for feature expansion. Finally, [31]naturally support multiple clients, while our natural extensions
to multiple clients require that all clients share a secret key
not known to IS.
Because of the different trade offs presented by our workand that of [31], each system is better suited for different
applications/use cases. It is interesting to note that these twoworks, the first ones to address the major open problem of
truly practical, provably secure, and very rich (including any
formula) query DBMS, are based on very different technicalapproaches. We believe that this adds to the value and strengthof each of these systems.4
X. D ISCUSSION AND M OTIVATION OF O UR S ETTING
Semi-honest model. Semi-honest model is often reasonablein practice, especially in the Government use scenarios. For
example, C, S and index server may be Government agencies,
whose systems are verified and trusted to execute the prescribed code. Further, regular audits will help enforce semihonest behavior.
Security against malicious adversaries can be added by standard techniques, but this results in impractical performance.
In follow up work we show how to amend our protocols toprotect against one malicious player (C or IS) at a very small
cost (ca. 10% increase). This is possible mainly because theunderlying GC protocols are already secure against malicious
evaluator.
Impact of the allowed leakage. Formally pinning down
exact privacy loss is beyond the reach of state-of-the-art
cryptography, even with no leakage beyond the output andamount of work (the field of differential privacy is working
on this problem, with very moderate success). Therefore,
understanding our leakage and its impact for specific applications is crucial to ascertain whether it’s acceptable. We
informally investigated the impact of leakage in several natural
applications, such as population DBs and call-record DBs
and query patterns (see example below); we believe that ourprotection is insufficient in some scenarios, while in manyothers it provides strong guarantees.
Rough leakage estimation for call-records DB. Consider
a call-records DB, including columns (Phone number,Callee phone number, time of call). The client C
is allowed to only ask queries of the form select * wherephone number = xxx AND callee phone number= yyy AND time of call ∈ {interval}.
For typical call patterns (e.g.,0-10 calls/person/day), thequery leakage will almost always constitute a tree with
4 We note that in an earlier stage there were two other performers on
the IARPA SPAR program. However, we do not know the details of theirapproaches, and are not aware of published work presenting their solutions.

branches either going to the leafs (returned records) or truncated one or two levels from the root. We believe that for many
purposes this is acceptable leakage. Again, we stress that thisis not a formal or detailed analysis (which is beyond the reachof today’s state-of-the-art); it is included here to support ourbelief that our system gives good privacy protection in manyreasonable scenarios.
Reliance on the third party. While a two-party solution isof course preferable, these state-of-the-art solutions are ordersof magnitude slower than what is required for scalable DB
access. Probably the most reasonable approach would be to
use ORAM, which is set up either by a trusted party or asa (very expensive) 2-PC between data owner and the querier.
Then the querier can query the ORAM held by the data owner.
Due to privacy requirements, each ORAM step must be done
over encrypted data, which triggers performance that is clearly
unacceptable for the scale required in our application (cf. [29]).
Further, in Government use cases, employing third party isoften seen as reasonable. For example, such a player can be
run by a neutral agency. We emphasize that the third party is
not trusted with the data or queries, but is trusted not to share
information with the other parties.
XI. C ONCLUSION
Guaranteeing complete search privacy for both the client andthe server is expensive with today’s state of the art. However,a weaker level of privacy is often acceptable in practice,especially as a trade-off for much greater efficiency. We
designed, proved secure, built and evaluated a private DBMS,
named Blind Seer, capable of scaling to tens of TB’s of data.
This breakthrough performance is achieved at the expenseof leaking search tree traversal information to the players.
Our performance evaluation results clearly demonstrate thepracticality of our system, especially on queries that returna few results where the performance overhead over plaintext
MySQL was from just 1.2× to 3× slowdown.
We note that the range from complete privacy to best
performance is wide and our work only targets a specific point
within it. We see it as a step towards exploring several othertrade-offs in this space. Our goal for future work is to develop
a highly tunable system which will be able to be configured
and match many practical scenarios with different privacy andperformance requirements.
Acknowledgments. This work was supported in part by theIntelligence Advanced Research Project Activity (IARPA) via
Department of Interior National Business Center (DoI/NBC)
contract Number D11PC20194. The U.S. Government is authorized to reproduce and distribute reprints for Governmental
purposes notwithstanding any copyright annotation thereon.
Disclaimer: The views and conclusions contained herein arethose of the authors and should not be interpreted as necessarily representing the official policies or endorsements,
either expressed or implied, of IARPA, DoI/NBC, or the U.S.
Government.
Fernando Krell was supported by BECAS CHILE, CONICYT, Gobierno de Chile.

This material is based upon work supported by (while author
Keromytis was serving at) the National Science Foundation.
Any opinion, findings, and conclusions or recommendations
expressed in this material are those of the author(s) anddo not necessarily reflect the views of the National Science
Foundation.
We thank MIT Lincoln Labs researchers for supporting
this program from the beginning to the end and facilitating
extensive testing of our code.
Finally, we thank our colleagues from other IARPA SPAR
teams for great collaboration and exchange of ideas.
R EFERENCES[1] IARPA Security and Privacy Assurance Research (SPAR) program. http://www.iarpa.gov/Programs/sso/SPAR/spar.html.
[2] The porter stemming algorithm.
http://tartarus.org/martin/
PorterStemmer/.
[3] Privacy groups file lawsuit over license plate scanners. http://www.
therepublic.com/view/story/210d27e7585543a3941f5e577cf7f627/
CA--License-Plate-Suit.
[4] M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange,
J. Malone-Lee, G. Neven, P. Paillier, and H. Shi. Searchable encryption revisited: Consistency properties, relation to anonymous IBE, andextensions. J. Cryptol., 21(3):350–391, 2008.
[5] D. Beaver. Precomputing oblivious transfer. In D. Coppersmith, editor,
CRYPTO’95, volume 963 of LNCS, pages 97–109. Springer, Aug. 1995.
[6] M. Bellare, A. Boldyreva, and A. O’Neill. Deterministic and efficiently
searchable encryption. In Proceedings of CRYPTO’07, 2007.
[7] M. Bellare, V. T. Hoang, and P. Rogaway. Foundations of garbled
circuits. In T. Yu, G. Danezis, and V. D. Gligor, editors, ACM CCS
12, pages 784–796. ACM Press, Oct. 2012.
[8] B. H. Bloom. Space/time trade-offs in hash coding with allowable errors.
Commun. ACM, 13(7):422–426, 1970.
[9] D. Boneh, G. D. Crescenzo, R. Ostrovsky, and G. Persiano. Public key
encryption with keyword search. In Proceedings of EUROCRYPT’04,
pages 506–522, 2004.
[10] D. Boneh and B. Waters. Conjunctive, subset, and range queries on
encrypted data. In S. P. Vadhan, editor, TCC 2007, volume 4392 of
LNCS, pages 535–554. Springer, Feb. 2007.
[11] D. Cash, S. Jarecki, C. S. Jutla, H. Krawczyk, M.-C. Rosu, and
M. Steiner. Highly-scalable searchable symmetric encryption withsupport for boolean queries. In R. Canetti and J. A. Garay, editors,
CRYPTO 2013, Part I, volume 8042 of LNCS, pages 353–373. Springer,
Aug. 2013.
[12] Y.-C. Chang and M. Mitzenmacher. Privacy preserving keyword searches
on remote encrypted data. In ACNS, volume 3531, 2005.
[13] M. Chase and S. Kamara. Structured encryption and controlled disclosure. In M. Abe, editor, ASIACRYPT 2010, volume 6477 of LNCS,
pages 577–594. Springer, Dec. 2010.
[14] S. G. Choi, J. Katz, R. Kumaresan, and H.-S. Zhou. On the securityof the “free-XOR” technique. In R. Cramer, editor, TCC 2012, volume7194 of LNCS, pages 39–53. Springer, Mar. 2012.
[15] B. Chor, N. Gilboa, and M. Naor. Private information retrieval by
keywords. Technical Report TR-CS0917, Dept. of Computer Science,
Technion, 1997.
[16] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information
retrieval. J. ACM, 45(6):965–981, 1998.
[17] R. Curtmola, J. A. Garay, S. Kamara, and R. Ostrovsky. Searchable
symmetric encryption: improved definitions and efficient constructions.
In ACM CCS 06, pages 79–88, 2006.
[18] E. De Cristofaro, Y. Lu, and G. Tsudik. Efficient techniques for privacypreserving sharing of sensitive information. In TRUST’11, pages 239–
253, 2011.
[19] T. ElGamal. A public key cryptosystem and a signature scheme based on
discrete logarithms. IEEE Transactions on Information Theory, 31:469–
472, 1985.
[20] S. Even, O. Goldreich, and A. Lempel. A randomized protocol forsigning contracts. In D. Chaum, R. L. Rivest, and A. T. Sherman,
editors, CRYPTO’82, pages 205–210. Plenum Press, New York, USA,1982.

[21] C. Gentry. Fully homomorphic encryption using ideal lattices. In
M. Mitzenmacher, editor, 41st ACM STOC, pages 169–178. ACM Press,
May / June 2009.
[22] C. Gentry, K. A. Goldman, S. Halevi, C. Julta, M. Raykova, and
D. Wichs. Optimizing oram and using it efficiently for secure computation. In Privacy Enhancing Technologies, pages 1–18. Springer,
2013.
[23] C. Gentry, S. Halevi, and N. P. Smart. Homomorphic evaluation of the
AES circuit. In R. Safavi-Naini and R. Canetti, editors, CRYPTO 2012,
volume 7417 of LNCS, pages 850–867. Springer, Aug. 2012.
[24] Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin. Protecting data
privacy in private information retrieval schemes. Journal of Computerand System Sciences, 60(3):592–629, 2000.
[25] E.-J. Goh. Secure indexes. IACR Cryptology ePrint Archive, 2003:216,
2003.
[26] O. Goldreich, S. Micali, and A. Wigderson. How to play any mental
game or A completeness theorem for protocols with honest majority.
In A. Aho, editor, 19th ACM STOC, pages 218–229. ACM Press, May
1987.
[27] O. Goldreich and R. Ostrovsky. Software protection and simulation on
oblivious rams. J. ACM, 43:431–473, 1996.
[28] S. Goldwasser and S. Micali. Probabilistic encryption. Journal ofComputer and System Sciences, 28(2):270–299, 1984.
[29] S. D. Gordon, J. Katz, V. Kolesnikov, F. Krell, T. Malkin, M. Raykova,
and Y. Vahlis. Secure two-party computation in sublinear (amortized)
time. In ACM CCS 12, pages 513–524, 2012.
[30] Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivioustransfers efficiently. In D. Boneh, editor, CRYPTO 2003, volume 2729
of LNCS, pages 145–161. Springer, Aug. 2003.
[31] S. Jarecki, C. S. Jutla, H. Krawczyk, M.-C. Rosu, and M. Steiner.
Outsourced symmetric private information retrieval. In A.-R. Sadeghi,
V. D. Gligor, and M. Yung, editors, ACM CCS 13, pages 875–888. ACM
Press, Nov. 2013.
[32] S. Kamara and C. Papamanthou. Searching Dynamic Encrypted Data
in Parallel. In FC 2013, 2013.
[33] D. M. Kays. Reasons to “friend” electronic discovery law. Franchise
Law Journal, 32(1), 2012.
[34] V. Kolesnikov. Gate evaluation secret sharing and secure one-roundtwo-party computation. In B. K. Roy, editor, ASIACRYPT 2005, volume3788 of LNCS, pages 136–155. Springer, Dec. 2005.
[35] V. Kolesnikov and R. Kumaresan. Improved secure two-party computation via information-theoretic garbled circuits. In I. Visconti and
R. D. Prisco, editors, SCN 12, volume 7485 of LNCS, pages 205–221.
Springer, Sept. 2012.
[36] V. Kolesnikov and T. Schneider. Improved garbled circuit: Free XOR
gates and applications. In L. Aceto, I. Damgård, L. A. Goldberg, M. M.
Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, editors, ICALP 2008,
Part II, volume 5126 of LNCS, pages 486–498. Springer, July 2008.
[37] V. Kolesnikov and T. Schneider. A practical universal circuit construction and secure evaluation of private functions. In G. Tsudik, editor, FC
2008, volume 5143 of LNCS, pages 83–97. Springer, Jan. 2008.
[38] Y. Lindell and B. Pinkas. A proof of security of Yao’s protocol for twoparty computation. Journal of Cryptology, 22(2):161–188, Apr. 2009.
[39] S. Lu and R. Ostrovsky. Distributed oblivious ram for secure two-party
computation. In TCC, pages 377–396, 2013.
[40] D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay - secure two-party
computation system. In USENIX Security Symposium, pages 287–302,
2004.
[41] T. Moataz and A. Shikfa. Boolean symmetric searchable encryption.
In ASIACCS 2013: 8th ACM Symposium on Information, Computer andCommunications Security, 2013.
[42] M. Naor and B. Pinkas. Computationally secure oblivious transfer.
Journal of Cryptology, 18(1):1–35, Jan. 2005.
[43] J. E. Pace III. Testing the security blanket: An analysis of recent
challenges to stipulated blanket protective orders. Antitrust Magazine,
19(3), 2005.
[44] V. Pappas, M. Raykova, B. Vo, S. M. Bellovin, and T. Malkin. Private
search in the real world. In ACSAC ’11, pages 83–92, 2011.
[45] R. A. Popa, C. M. S. Redfield, N. Zeldovich, and H. Balakrishnan.
Cryptdb: protecting confidentiality with encrypted query processing. In
SOSP ’11, pages 85–100. ACM, 2011.
[46] M. O. Rabin. How to exchange secrets by oblivious transfer. In Technical
Report TR-81. Aiken Computation Laboratory, Harvard University,
1981.

[47] M. Raykova, B. Vo, S. Bellovin, and T. Malkin. Secure anonymous
database search. In CCSW 2009., 2009.
[48] P. Rogaway. The round complexity of secure protocols. PhD thesis,
Massachusetts Institute of Technology, 1991.
[49] E. Shi, J. Bethencourt, H. T.-H. Chan, D. X. Song, and A. Perrig. Multidimensional range query over encrypted data. In 2007 IEEE Symposium
on Security and Privacy, pages 350–364. IEEE Computer Society Press,
May 2007.
[50] D. X. Song, D. Wagner, and A. Perrig. Practical techniques for searches
on encrypted data. In Proceedings of the 2000 IEEE Symposium on
Security and Privacy, SP ’00, pages 44–, Washington, DC, USA, 2000.
IEEE Computer Society.
[51] J. K. Yan Huang, David Evans and L. Malka. Faster secure two-party
computation using garbled circuits. In USENIX Security Symposium.
USENIX Association, 2011.
[52] A. C.-C. Yao. Protocols for secure computations (extended abstract). In
23rd FOCS, pages 160–164. IEEE Computer Society Press, Nov. 1982.
[53] A. C.-C. Yao. How to generate and exchange secrets (extended abstract).
In 27th FOCS, pages 162–167. IEEE Computer Society Press, Oct. 1986.

A PPENDIX A
R EPRESENTING Q UERY & P OLICY
Encoding a query. In our system, a query is represented
as a Bloom filter. This filter contains all the relevant columns
and operations, and search terms and conditions. For example,
consider the following query:
SELECT id WHERE fname = ALICE AND dob <= 1975-1-1
AND CONTAINED_IN(notes1, engineer)(2)

The bloom filter will contain the following:
fname, fname:=, fname:ALICE, fname:=:ALICE
dob, dob:<=, dob:1975-1-1, dob:<=:1975-1-1• notes1,
notes1:contained_in,
notes1:engineer,notes1:contained_in:engineer••

Policy circuit. The current implementation provides a parser
for any policy that can be represented as a monotone DNF
where each variable indicates whether some policy condition(BF keyword) belongs to the input BF representing a query as
described above; if the formula output is true, then the client’s
query is disallowed. For example, a policy may disallow aquery if it contains an equality check on fname with value
ALICE and a range in dob. In this case, the policy circuit isa simple formula V1 AND V2 , where the variable V1 is true
if the input BF contains fname:=:ALICE, and V2 is true if
the filter contains dob:<=. Indeed, query (2) above will bedisallowed.
We believe that this provides a wide coverage of policies.
For example, our parser also supports a policy that allows only
range operation on fname, indirectly. One technical issue isthat we do not want to allow any false approval of a querythat fails the policy (though a tunable small probability offalse rejection of a good query is acceptable), but the Bloom
filters allow no false negatives. We can fix this issue by adding
keywords representing absence column, or column operators
to the BF. In the example above the system adds the following
keywords:•

NOT:fname:range, NOT:dob:=,
NOT:notes1:stem,
NOT:lname, NOT:zip, NOT:marital_status ....

Now, the aforementioned policy is equivalent to one that
disallows queries if the corresponding the BF contains fnameand NOT:fname:range. If the check succeeds, then the queryis disallowed. Likewise, a policy allowing only equality operation on dob will check if the filter has dob and NOT:dob:=.
In addition, the policy can now disallow queries that do notcontain an equality on dob column or that do not containlname. More importantly, the policy can now enforce thatthe query must have lname value if fname was present.
A PPENDIX B
O NE -C ASE I NDISTINGUISHABILITY
Here, we give a formal definition of one-case indistinguishability. Since our system realizes the ideal functionality Fdb , thedefinitions concern only input/output behavior and the leakage
profile L.
The distribution E discussed in Section V-B with δ isdefined as follows:
Let (D0 , q, r) be a database, a query and a record
as specified in Section V-B. Choose a record in D0
uniformly at random and replace it with r. Let D1
be the modified database. Choose a bit b ∈ {0, 1}
according to the following distribution:Pr[b = 1] = δ, Pr[b = 0] = 1 − δ.
Run Fdb , calling Init with (D0 , P ), and Query with
q. Let v be the leakage to the index server. Output(b, v).
We show that our system satisfies one-case indistinguishability. Note that the initial leakage is none, and therefore,
we only need to consider the query leakage which is thequery pattern and the tree search pattern. This implies that
we only need to consider the tree search pattern since thesame query is considered in the experiment. Observe that the
newly introduced record r is equivalent to adding a random
paths in terms of the tree search pattern. Therefore, it suffices
to focus on the number of added random paths. In particular,
let D+ be defined as follows:x← D; output (x + 1).
Now, consider a following game X:
Choose a bit b ∈ {0, 1} such that Pr[b = 1] = δ andPr[b = 0] = 1 − δ. If b = 0, let x← D; otherwise
let x← D+ . Output (b, x).
Now, we show that for any x, it holds thatPr[b = 1| x] ≤ 2δ.
X

We show this by using case analysis:+• When x ≤ 1, it never comes from D , so the inequality
trivially holds.
• When 2 ≤ x ≤ α − 1, it holds thatPr[b = 1| x] =δ/αPr[X = (1, x)]
=
= δ.
Pr[x]
δ/α + (1 − δ)/α•

When x ≥ α, it holds that

Pr[X = (1, x)]Pr[x]δ · (1/α) · 1/2x−αx−αδ · (1/α) · 1/2+ (1 − δ) · (1/α) · 1/2x−α+1
δ
2δ
=
≤ 2δ.
δ + (1 − δ)/2
1+δPr[b = 1| x] ===