Giovanni Di Crescenzo
email: gdicrescenzo@appcomsci.com

Debra Cook
email: dcook@appcomsci.com

Allen Mcintosh
email: amcintosh@appcomsci.com

Euthimios Panagos
email: epanagos@appcomsci.com

Practical Private Information Retrieval from a Time-Varying, Multi-Attribute, and Multiple-Occurrence Database

We study the problem of privately performing database queries (i.e., keyword searches and conjunctions over them), where a server provides its own database for client query-based access. We propose a cryptographic model for the study of such protocols, by expanding previous well-studied models of keyword search and private information retrieval to incorporate a more practical data model: a time-varying, multi-attribute and multiple-occurrence database table. Our first result is a 2-party private database retrieval protocol. Like all previous work in private information retrieval and keyword search, this protocol still satisfies server time complexity linear in the database size. Our main result is a private database retrieval protocol in a 3-party model where encrypted data is outsourced to a third party (i.e., a cloud server), satisfying highly desirable privacy and efficiency properties; most notably: (1) no unintended information is leaked to clients or servers, and only minimal 'access pattern' information is leaked to the third party; (2) for each query, all parties run in time only logarithmic in the number of database records; (3) the protocol's runtime is practical for real-life applications, as shown in our implementation where we achieve response time that is only a small constant slower than commercial non-private protocols like MySQL.

Introduction

As reinforced by current technology trends (e.g., 'Big Data', 'Cloud-based Data Retrieval'), in today's computer system there is critical need to efficiently store, access and manage massive amounts of data. While data management and storage systems evolve to take these new trends into account, privacy considerations, already of great interest, become even more important. To partially address privacy needs, databasemanagement systems can use private database retrieval protocols, where clients submit queries and receive matching records in a way so that clients do not learn anything new about the database records (other than the content of the matching records), and database servers do not learn which queries are submitted. The research literature has attempted to address these issues, by studying private database retrieval protocols in limited database models and with limited efficiency properties. In this paper we address some of these limitations, by using a practical database model, and proposing a participant and privacy model in which data is outsourced to a third party (in encrypted form) and practical private database retrieval protocols are possible.

Our contribution. Continuing the well-studied areas of private information retrieval (PIR) [START_REF] Chor | Private information retrieval[END_REF][START_REF] Kushilevitz | Replication is not needed: Single database, computationally-private information retrieval[END_REF] and keyword search (KS) [START_REF] Chor | Private information retrieval by keywords[END_REF][START_REF] Boneh | Public key encryption with keyword search[END_REF][START_REF] Freedman | Keyword search and oblivious pseudorandom functions[END_REF], we propose a more practical database model, capturing record payloads, multiple attributes, possibly equal attribute values across different database records, and multiple answers to a given query and insertion/deletion of database records. In this model, we define suitable correctness, privacy and efficiency requirements, by showing previously not discussed technical reasons as to why we cannot use the exact same requirements from the PIR and KS areas.

We then design a first database retrieval protocol that satisfies the desired privacy properties (i.e., the server learns no information about the query value other than the number of matching records, and the client learns no information about the database other than matching database records) in our novel and practical database model (i.e., a time-varying, multi-attribute and multiple-occurrence table). This protocol is based on oblivious pseudo-random function evaluation protocols and PIR protocols and still has server time complexity linear in the database size (a source of great inefficiency in previous PIR and KS protocols), a drawback dealt with in our next result.

After expanding the participant model with a third party (i.e., a cloud server, as in the database-as-a-service model [START_REF] Hacigümüs | Executing SQL over encrypted data in the database-service-provider model[END_REF]), we design a second protocol, only based on pseudo-random functions (implemented as block ciphers), where both server and third party run queries in logarithmic time and the following privacy properties hold: the server learns nothing about the query value, the client learns nothing about the database in addition to the payloads associated with the matching records, and the third party learns nothing about the query value or the database content, other than the repeating of queries from the client and repeated access to the encrypted data structures received by the server at initialization. Thus, we solve the long-standing problem of achieving efficient server runtime at the (arguably small) cost of a 'third-party'-server and some 'access-pattern' type leakage to this third party. We stress that this protocol has efficient running time not only in an asymptotic sense, but in a sense that makes it ready for reallife applications (where such form of leakage to the third party is tolerable), answering another long-standing question in the PIR area. In our implementation, we reached our main design goal of achieving response time to be only a small constant slower than commercial non-private protocols like MySQL. Solving a number of technical challenges posed by the new data model (including a reduction step via a novel multiplicity database) using simple and practical techniques was critical to achieve this goal. The privacy loss traded for such a practicality property is rather minimal, as neither the client nor the server learn anything new, and the third party does not learn anything about the plain database content or the plain queries made, but just an 'unlabeled histogram' describing the relative occurrences of (encrypted) matching records and (encrypted) query values within the protocol. (Techniques from [START_REF] Islam | Access pattern disclosure on searchable encryption: Ramification, attack and mitigation[END_REF] can be used to mitigate privacy loss from such leakage as well.) In all our protocols, we only consider privacy against a semi-honest adversary, as there are known techniques, based on the general paradigm of [START_REF] Goldreich | How to play any mental game or a completeness theorem for protocols with honest majority[END_REF], to compile such protocols and achieve privacy against malicious adversaries. Almost all formal definitions and proofs are omitted due to space restriction. Related work. Our work revisits and extends work in the PIR and KS areas, which have received a large amount of attention in the cryptography literature. (See, e.g., [START_REF] Ostrovsky | A survey of single-database private information retrieval: Techniques and applications[END_REF].) Both areas consider rather theoretical data models, as we now discuss. In PIR, a database is modeled as a string of n bits, and the query value is an index i ∈ {1, . . . , n}. In KS, the data models differ depending on the specific paper we consider; the closest data model to ours is the one from [START_REF] Freedman | Keyword search and oblivious pseudorandom functions[END_REF], where a database is a set of records with per-record payloads, but has a single attribute, admits a single matching record per query and no record insertions/deletions. The inefficiency of the server runtime in PIR and KS protocols has been well documented (see, e.g., [START_REF] Wang | Private information retrieval using trusted hardware[END_REF]). Some results attempted to use a third party and make the PIR query subprotocol more efficient but require a practically inefficient preprocessing phase [START_REF] Di Crescenzo | Universal service-providers for private information retrieval[END_REF].

In both PIR and KS, the database owner is the server that hosts the plain data. In some related research areas, such as oblivious RAM (starting with [START_REF] Goldreich | Software protection and simulation on oblivious RAMs[END_REF]), and searchable symmetric encryption (starting with [START_REF] Song | Practical techniques for searches on encrypted data[END_REF]), the database owner is the client that uses the server to host a carefully prepared and encrypted version of the data. In public-key encryption with keyword search (starting with [START_REF] Boneh | Public key encryption with keyword search[END_REF]) the data is provided in encrypted form by multiple independent servers to a third party that helps satisfying a client's query. Because of these critical differences, results in the cited areas do not solve the problem addressed by PIR and KS and use substantially different techniques, which are not directly comparable to ours.

In the project supporting this paper, other performing teams like ours came up with different and interesting solutions to similar problems. The closest published work from any of these teams that we are aware of consists of [START_REF] Jarecki | Outsourced symmetric private information retrieval[END_REF]. Among the many differences, the cited paper uses random oracles and public-key cryptography operations, which we since random oracles have been proved to likely not exist and public-key cryptography operations are known to be less efficient than symmetric-key ones. Finally, our database retrieval protocols well combine with database policy compliance protocols from [START_REF] Di Crescenzo | Practical and privacy-preserving policy compliance for outsourced data[END_REF] that allow a server to authorize (or not) queries by a client according to a specific policy, while maintaining privacy of queries and policy.

Models and Requirements

Data and Query Models. We model a database as an n-row, m-column matrix D = (A 1 , . . . , A m ), where each column is associated with an attribute, denoted as A j , for j = 1, . . . , m. The first m -1 columns are keyword attributes, and the last column P = A m , is a payload attribute. A database entry is denoted as keyword A j (i) or, in the case j = m, as payload p(i) = A m (i). The database schema is the collection of parameters n, m and of the description of each domain associated with each of the m attributes, and to which database entries belong. The database schema is assumed to be publicly known to all parties. A database row is also called record, and is assumed to have the same length r (if data is not already in this form, techniques from [START_REF] Crescenzo | On minimizing the size of encrypted databases[END_REF] are used to efficiently achieve this property), where r is constant with respect to n. We consider a database update as an addition, deletion, or change of a single record, and refer to the current database (resp., current database schema), as the database (resp., database schema) obtained after any previously occurred updates. A query q is modeled to refer to one or more database attributes and to contain one or more query values from the relative attribute domains. We will mainly consider KS queries, such as: "SELECT * FROM main WHERE attribute name = v," where v is the query value.

A valid response to such a query consists of all payloads p(i), for i ∈ {1, . . . , n}, such that A j (i) = v, if attribute name = A j , for some j ∈ {1, . . . , m -1}. We say that the records in a valid response match the query. We will also discuss extensions of our techniques to other query types, such as conjunctions (via logical AND gates) of KS queries. The number of records containing the same query value v at attribute A j is also called the j-multiplicity of v in the database, and is briefly denoted as m j (v). KS queries are always made to a specific attribute A j , for some j ∈ {1, . . . , m -1}, and therefore in their discussion the index j is omitted to simplify notation and discussion. Participant Models. We consider the following efficient (i.e., running in probabilistic polynomial-time in a common security parameter 1 σ ) participants. The client is the party, denoted as C, that is interested in retrieving data from the database. The server is the party, denoted as S, holding the database (in the clear), and is interested in allowing clients to retrieve data. The third party, denoted as T P , helps the client to carry out the database retrieval functionality and the server to satisfy efficiency requirements during the associated protocol. By 2-party model we denote the participant model that includes C, S and no third party. By 3-party model we denote the participant model that includes C, S, and T P . (See Figure 1,2 for a comparison of the two participant models.) Database retrieval protocols. In the above data, query, and participant models, we consider a database retrieval (briefly, DR) protocol as an evolution of the KS protocol, as defined in [START_REF] Freedman | Keyword search and oblivious pseudorandom functions[END_REF] (in turn, an evolution of the PIR protocol, as defined in [START_REF] Kushilevitz | Replication is not needed: Single database, computationally-private information retrieval[END_REF]), with the following three main model and functionality extensions, which are consistent with the functioning of typically deployed databases: (1) databases contain multiple attributes (or columns with keywords); (2) each database attribute can have multiple occurrences of the same keyword; and (3) database entries may change as a result of record addition and deletion. Specifically, we define a DR protocol as a triple (Init, Query, Update) of subprotocols, as follows. The initialization subprotocol Init is used to set up data structures and cryptographic keys before C's queries are executed. The query subprotocol Query allows C to make a single query to retrieve (possibly multiple) matching database records. The record update subprotocol Update allows S to periodically update the data structures and cryptographic keys set during the Init subprotocol, as a result of a record addition or deletion. As a first attempt, we target DR protocols that satisfy the following (informal) list of requirements:

1. Correctness: the DR protocol allows a client to obtain all payloads from the current database associated with records that match its issued query; 2. Privacy: the DR protocol preserves privacy of database content and query values, ideally only revealing what is leaked by system parameters known to all parties and by the intended functionality output (i.e., all payloads in matching records to C); 3. Efficiency: the protocol should have low time, communication and round complexity; ideally, a constant number of messages per query, and time and communication sublinear in the number n of database records. It turns out that, as written, these requirement cannot be exactly satisfied, and the missing properties are different depending on whether we consider the 2-party or the 3-party model. Thus, we continue with formal definitions common to both models, and then defer different formal definitions of privacy and efficiency to later sections. Preliminary Requirement Notations: Let σ be a security parameter. A function is negligible if for all sufficiently large natural numbers σ ∈ N , it is < 1/p(σ), for any polynomial p. A DR protocol execution is a sequence of executions of subprotocols (Init, qu 1 , . . . , qu q ), where qu i ∈ {Query, Update}, for i = 1, . . . , q, for some q polynomial in σ, and all subprotocols are run on inputs provided by the involved parties (i.e., a database from S, query values from C, and database updates from S). We only consider stateless Query subprotocols, in that they can depend on the outputs of Init and Update subprotocols but not on the output of previous Query subprotocols. Correctness: for any DR protocol execution, and any inputs provided by the participants, in any execution of a Query subprotocol, the probability that C obtains all records in the current database that match C's query value input to this subprotocol, is 1. Background primitives. A random function R is a function that is chosen with distribution uniform across all possible functions with some pre-defined input and output domains. A keyed function F (k, •) is a pseudo-random function (PRF, first defined in [START_REF] Goldreich | How to construct random functions[END_REF]) if, after key k is randomly chosen, no efficient algorithm allowed to query an oracle function O can distinguish whether O is F (k, •) or O is a random function R (over the same input and output domain), with probability greater than 1/2 plus a negligible quantity. An oblivious pseudo-random function evaluation protocol (oPRFeval, first defined in [START_REF] Freedman | Keyword search and oblivious pseudorandom functions[END_REF]) is a protocol between two parties A, having as input a string k, and B, having as input a key x for a PRF F . The protocol's outcome is a private function evaluation of the value F (k, x), returned to B (thus, without revealing any information about x to B, or any information about k to A). oPRFeval protocols were constructed in [START_REF] Freedman | Keyword search and oblivious pseudorandom functions[END_REF][START_REF] Jarecki | Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection[END_REF] using number-theoretic hardness assumptions.

A single-database private information retrieval protocol (PIR, first defined in [START_REF] Kushilevitz | Replication is not needed: Single database, computationally-private information retrieval[END_REF]) is a protocol between two parties A, having as input a value i ∈ {1, . . . , n}, and B, having as input a database represented as a sequence of equal-length values x = (x[1], . . . , x[n]) The protocol consists in a private retrieval of the value x[i], returned to A (thus, without revealing any information about i to B or about

x[1], . . . , x[i-1], x[i+ 1], . . . , x[n] to A).
A semi-private PIR protocol is a protocol where privacy only consists of preventing to reveal any information about i to B. Several PIR and semi-private PIR protocols have been presented in the cryptographic literature, starting with [START_REF] Kushilevitz | Replication is not needed: Single database, computationally-private information retrieval[END_REF], using number-theoretic hardness assumptions.

Two-Party Database Retrieval

We define privacy and efficiency requirements in the 2-party model in Section 3.1 and describe our first DR protocol (for KS queries in the 2-party model) in Section 3.2.

Privacy and Efficiency in the 2-Party Model

Informally, our privacy and efficiency requirements are modified with respect to our first attempt in Section 2, so that a 2-party DR protocol can leak the number of matching records to S, has communication complexity sublinear in n if the number of matching records is also sublinear in n, and allows S to run in time linear in the number n of database records. A formal treatment follows. Privacy: Informally speaking, we require the subprotocols in a DR protocol execution do not leak information beyond the following:

1. Init: the database schema, as part of overall system parameters, will be known to all participants; 2. Query, based on query value v, attribute index j, and the current database: the pair (j, m j (v)) will be known by S and all payloads {p(i)

: i = i(1), . . . , i(m j (v))} such that A j (i(1)) = • • • = A j (i((m j (v))
)) = v will be obtained by C, as a consequence of the correctness requirement; 3. Update: on input a record addition or deletion to the current database, the current database (after the update) will be known by S, as a consequence of the correctness requirement, and the current database schema (after the update), as part of overall system parameters, will be known by all participants. Given this characterization of the intended leakage, a formal privacy definition can be derived using known definition techniques from simulation-based security and composable security frameworks often used in the cryptography literature.

Consistently with the literature on secure function evaluation, PIR and KS protocols, it might have seemed reasonable to just require that no new information about the query value is revealed to S, as we hoped to achieve in our first attempt in Section 2. It turns out that this level of privacy cannot be obtained, as we now explain. Let us consider a specific execution of subprotocol Query within a DR protocol execution. Since more than one record may match C's query value v, by the correctness property, at the end of this execution of subprotocol Query, C must be able to compute all payloads p(i(1)), . . . , p(i(m j (v))) corresponding to records matching v, where m j (v) denotes the multiplicity of v in the j-th database attribute A j . Moreover, since the executions of the Init, Update protocols only leak the database schema to C, and since subprotocol Query is stateless, all previous subprotocol executions in the DR protocol execution, do not help in computing all matching records to this specific execution of subprotocol Query. In other words, C must be able to compute all matching records from the communication received during this specific execution of subprotocol Query. By a standard application of Shannon's source coding theorem (see, e.g., [START_REF] Cover | Elements of information theory[END_REF]), this implies that the communication exchanged in this execution is an upper bound to the entropy H of payloads p(i(1)), . . . , p(i(m j (v))) (over the probability distribution of the source that generates the database payloads). Thus, we obtain the following Proposition 1. For any v, let cc(v) denote the number of bits exchanged in an execution of subprotocol Query on input query value v and attribute index j. It holds that cc(v) ≥ H(p(i(1)), . . . , p(i(m j (v)))).

In Proposition 1, the entropy term is maximized when database payloads are randomly and independently distributed, in which case the communication exchanged in each execution of subprotocol Query leaks an upper bound on the value m j (v), i.e., the number of matching records, to both C and S. Accordingly, we target the design of protocols that may leak m j (v) also to S during each execution of subprotocol Query on input query value v and attribute index j (as formulated in the above privacy requirement).

Efficiency: A DR protocol's round complexity (resp., communication complexity) is the max number of messages (resp., the max length of all messages), as a function of the system parameters n, m, σ, required by any of the Init, Query, Update subprotocols, for any inputs to them. A DR protocol's S-time complexity for subprotocol π is the max running time (as a function of the system parameters n, m, σ) required by S in subprotocol π ∈ {Init, Query, Update}, over all possible inputs to it. Asymptotic requirements consistent with the literature on PIR and KS protocols include the following: (1) the communication complexity of each execution of protocol Query is sublinear in n; (2) the S-time complexity in each execution of protocol Query is sublinear in n. Requirement ( 1) is achieved by PIR and KS protocols in the literature when up to a single record is sent as a reply to each query. However, in our DR protocols, a query could be matched by a possibly linear number of records; accordingly, we only require the communication complexity to be sublinear whenever so is the number of matching records. Requirement (2), when coupled with the privacy requirement that an execution of the Init protocol only leaks minimal information to C, is known to be unachievable in the 2-party model (or otherwise privacy of the query value v would not hold against the server), as discussed in many papers including [START_REF] Kushilevitz | Replication is not needed: Single database, computationally-private information retrieval[END_REF][START_REF] Freedman | Keyword search and oblivious pseudorandom functions[END_REF].

Our Protocol

Our 2-party DR protocol for KS queries follows the general structure outlined in Figure 1 and satisfies the following Theorem 1. Under the existence of oPRFeval protocols [START_REF] Freedman | Keyword search and oblivious pseudorandom functions[END_REF] and (single-database) PIR protocols [START_REF] Kushilevitz | Replication is not needed: Single database, computationally-private information retrieval[END_REF], there exists (constructively) a DR protocol π 1 = (Init 1 , Query 1 , Update 1 ) for KS queries in the 2-party model, satisfying:

1. correctness 2. privacy against C (i.e., it only leaks the matching records to C); 3. privacy against S (i.e., it only leaks the queried attribute and the number of matching records to S); 4. communication complexity of Query 1 is o(n) if so is the number of matching records;

5. round complexity of Query 1 is O(log n); 6. the S-time complexity in Query 1 (resp. Init 1 ) (resp.,

Update 1 ) is O(n) (resp., is O(n)) (resp., is O(log n)).
The protocol π 1 claimed in Theorem 1 is presented in two steps: first, we describe a DR protocol π 0 = (Init 0 , Query 0 ) in the restricted data model where all keywords in each database attribute are distinct, and no record additions or deletions happen, and then we describe the DR protocol π 1 that builds on π 0 to remove these restrictions.

The DR protocol π 0 . Informally speaking, this protocol is a combination of a KS protocol, denoted as Protocol 2 in [START_REF] Freedman | Keyword search and oblivious pseudorandom functions[END_REF] (in turn building on a semi-private KS protocol from [START_REF] Chor | Private information retrieval by keywords[END_REF]), and an oPRFeval protocol for computing a pseudo-random function f , as follows.

Init 0 . On input database D = (A 1 , . . . , A m ), S returns a pseudo-random version of the database, denoted as prD = (prA 1 , . . . , prA m-1 , A m ), and computed by replacing keyword entries A j (i) with pseudo-random values prA j (i) = f k (A j (i)) for all j = 1, . . . , m -1 and i = 1, . . . , n, where k is a random key. (That is, keyword entries are replaced by pseudo-random versions of them, but payloads in A m remain unchanged). Query 0 . On input query value v and attribute index j from C, and key k and database prD from S, the following steps are run:

1. C and S run an oPRFeval protocol to return f k (v) to C; 2. C sends j to S 3. C and S run the semi-private KS protocol from [START_REF] Chor | Private information retrieval by keywords[END_REF], where C uses f k (v) as query value and S provides (prA j , A m ) as a 2-column database. At the end of the protocol, C can compute the record A m (i) such that prA j (i) = f k (v), if any. Here, the semi-private KS protocol from [START_REF] Chor | Private information retrieval by keywords[END_REF] consists of using a PIR protocol, such as the one from [START_REF] Kushilevitz | Replication is not needed: Single database, computationally-private information retrieval[END_REF], to probe a conventional search data structure built by S on top of the pseudo-database keywords in a way that is oblivious to S.

Protocol π 0 can be shown to be a DR protocol in the following restricted data model: [START_REF]Project gutenberg[END_REF] no database records are added or deleted; (2) for each j = 1, . . . , m -1 the database entries A j (1), . . . , A j (n) relative to the j-th attribute are all distinct. We remove these two restrictions by combining the following ideas: S can transform the original database into one where each column A j has distinct keywords (or payload), by computing a padded database, where keywords are padded with a multiplicity counter; S can compute a preliminary multiplicity database to let C obtain the multiplicity of its query value from S using protocol π 0 ; given the multiplicity of the query value, C can request the matching records by making one query for each matching record to the padded database, using again protocol π 0 ; updating the padded and multiplicity databases and associated data structures can be done efficiently by careful choices of padding and data structures. We stress that revealing the multiplicity value to C does not provide any more information than sending the matching records (which C is entitled to receive). A more formal description follows. The DR protocol π 1 . Based on the above DR protocol π 0 = (Init 0 , Query 0 ), we define protocol π 1 = (Init 1 , Query 1 , Update 1 ) as follows. Init 1 . On input database D = (A 1 , . . . , A m ), S builds an associated padded database pD = (pA 1 , . . . , pA m ), as follows. The payload pA m is equal to A m . Then, for each j = 1, . . . , m -1, and each i = 1, . . . , n, the keyword pA j (i) is defined as (A j (i), mc(i, j)) where mc(i, j) is the multiplicity counter from {1, . . . , n} such that A j (i) is the mc(i, j)-th occurrence of value A j (i) within array (A j (1), . . . , A j (n)); Then S builds an associated multiplicity database mD = (mA 1 , . . . , mA m ), as follows. For each j = 1, . . . , m -1, and each i = 1, . . . , n, the keyword mA j (i) is defined exactly as pA j (i). The payload mA m (i) is denoted as m j (v), where m j (v) is defined as m j (v) when mc(i, j) = 1 and a null string ⊥ of the same length otherwise. Finally, S runs Init 0 to compute pseudo-random versions prpD and prmD of databases pD and mD, respectively, and to send the schema for databases mD and pD to C. Query 1 . On input query value v and attribute index j for C, and key k and databases prpD, prmD for S, the following steps are run:

1. C and S run subprotocol Query 0 on input database prmD from S, and query value (v, 1) and attribute index j from C. Let p(i) be the payload obtained by C at the end of this protocol, for some i ∈ {1, . . . , n}. If p(i) =⊥ then the protocol stops.

Otherwise C sets the value m j (v) = p(i). 2. For t = 1, . . . , m j (v), C and S run subprotocol Query 0 on input database prpD from S, and query value (v, t) and attribute index j from C.

Update 1 . In subprotocol Update 1 , we consider record addition and record deletion operations, and on each of them, we need to efficiently update any values changing as a result of these operations; specifically: 1. the data structures required in π 0 ; 2. the multiplicity value m j (v) used in mD; 3. the multiplicity counters mc(i, j) in the padding structures used in pD and mD; 4. the database schema for both pD and mD; and 5. the pseudo-random databases prpD and prmD. First, with respect to (1), we observe that the data structures used in π 0 are those from [START_REF] Chor | Private information retrieval by keywords[END_REF] and are conventional data structures with the only requirement of performing search in logarithmic time. Our added requirement of having efficient insertion and deletion does not require a modification of the data structures, since many of the data structures used in [START_REF] Chor | Private information retrieval by keywords[END_REF] (e.g., binary search trees) can be used to perform logarithmic-time search, insertion and deletion. Then, the values in (2), (4), and (5) can be updated in time constant with respect to n, as follows. As for (2), updating the multiplicity value m j (v) only requires to change one payload entry mA m (i) in the multiplicity database mD, regardless of the multiplicity of v, and can be done in O(log n). As for (4), S can just update the database schema for both pD and mD and send those to C. As for (5), S can again use key k to recompute new f k (pD j (i)) and f k (mD j (i)) values.

With respect to values in (3), we now describe how to update the multiplicity counters mc(i, j) after a record update. In the addition case, a record would also be added in the databases pD and mD, and the multiplicity counter mc(i, j) in the added record is set to m j (v) + 1. In the deletion case, a record would also be deleted in the databases pD and mD, and we cannot stop there as this would likely create a discontinuity in the sequence of multiplicity counters mc(i, j) (e.g., when m j (v) ≥ 3, deleting the record with multiplicity counter 2 would leave only records with counters 1 and 3). Instead, S resets the multiplicity counter of i-th record such that mc(i, j) = m j (v) as equal to the multiplicity counter of the just deleted record, thus keeping no discontinuity in the sequence of multiplicity counters.

Three-Party Database Retrieval

We define privacy and efficiency requirements in the 3-party model in Section 4.1 and describe our second DR protocol (for KS queries in the 3-party model) in Section 4.2.

Privacy and Efficiency in the 3-Party Model

Informally, our privacy and efficiency requirements are modified with respect to our first attempt in Section 2, so that a 3-party DR protocol can leak the number of matching records as well as 'access-pattern' leakage, to T P , and has communication complexity sublinear in n if the number of matching records is also sublinear in n. (In particular, we keep the requirement that S and T P have to run in time sublinear in the number n of database records.) A formal treatment follows. Privacy: The privacy leakage we allow in the 3-party model has two differences with respect to the 2-party model: the number of matching records is now leaked to T P instead of S; moreover, the following additional leakage to T P is allowed: repeated (or not) occurrences of the same query made by C, and repeated (or not) accesses to the same initialization information sent by S to T P at the end of the initialization protocol. Informally speaking, we require the subprotocols in a DR protocol execution in the 3-party model to not leak any information beyond the following:

1. Init: the database schema, as part of overall system parameters, will be known to all participants and an additional string eds (for encrypted data structures) will be known to T P ; here, eds is encrypted under one or more keys unknown to T P and its length is known from quantities in the database schema; 2. Query, based on query value v, attribute index j, and the current database: all payloads {p(i) : i = i(1), .., i(m j (v))} such that A j (i(1)) = •• = A j (i((m j (v)))) = v will be obtained by C, as a consequence of the correctness requirement; the pair (j, m j (v))), all bits in eds read by T P according to the instructions in the Query protocol, and which previous executions of Query used the same query value v, will be known to T P ; 3. Update: on input a record addition or deletion to the current database, the current database (after the update) will be known to S, as a consequence of the correctness requirement, and the current database schema (after the update), as part of overall system parameters, will be known by all participants; all bits in eds read and/or modified by T P according to the instructions in the Update protocol will be known to T P , who will also determine up to one record previously or currently present in the database containing the same query value as the one in the added/deleted record.

Given this characterization of the intended leakage, a formal privacy definition can be derived using known definition techniques from simulation-based security and composable security frameworks often used in the cryptography literature. Using a direct extension of Proposition 1 to the 3-party model, we can prove an analogue result with respect to leaking m j (v) to the coalition of S and T P . Thus, different 3-party DR protocols could leak m j (v) only to S, or only to T P , or somehow split this leakage between S and T P . Having to choose between one of these options, we made the practical consideration that privacy against S (i.e., the data owner) is typically of greater interest than privacy against T P (i.e., the cloud server helping C retrieve data from S) in many applications, and therefore we focused in this paper on seeking protocols that leak m j (v) to T P and nothing at all to S. The other definitional choice of leaking repetition patterns (even though not actual data) to T P is not due to a theoretical limitation, but seems a rather small privacy price to pay towards achieving the very efficient S and T P time-complexity requirements discussed below. Efficiency: The definition of a 3-party DR protocol's round complexity, communication complexity and S-time-complexity are naturally extended from those of 2-party DR protocols. We also define the T P -time-complexity by naturally adapting the server timecomplexity definition. As for 2-party protocols, we require that 3-party DR protocols have communication complexity to be sublinear whenever so is the number of matching records. Contrarily to 2-party protocols, we do require that the S-time complexity and the T P -time complexity in each execution of protocol Query is sublinear in n, whenever is the number of matching records is sublinear in n (and achieving this property is one of the major goals in the constructions in this paper). We also target a practical response time efficiency requirement: the response time within a Query execution is only a small constant c worse than the response time within the same subprotocol for a non-private protocol such as MySQL. 1. correctness 2. privacy against C (i.e., it only leaks the matching records to C); 3. privacy against S (i.e., it does not leak anything to S); 4. privacy against T P (i.e., it only leaks number of matching records, the repetition of query values and the repeated access to initialization encrypted data structures); 5. communication complexity of Query 2 (resp.

Our Protocol

Init 2 ) (resp., Update 2 ) is o(n) if so is the number of matching records (resp., is O(n)) (resp., is O(log n)); 6. S-time complexity in Query 2 (resp. Init 2 ) (resp., Update 2 ) is O(1) (resp., is O(n)) (resp., is O(log n)); 7. T P -time complexity in Query 2 (resp. Init 2 ) (resp., Update 2 ) is o(n) if the number of matching records is o(n/logn) (resp., is O(n)) (resp., is O(log n)); 8. round complexity of Query 2 is O(1).
Informally, our protocol π 2 is obtained by performing several improvements in the 3party model to protocol π 1 (which was designed in the 2-party model). As done for π 1 , we first construct a DR protocol π 0 = (Init 0 , Query 0 ) in a restricted data model, and then a DR protocol π 2 that uses π 0 and the ideas of multiplicity database and padded database to obtain a DR protocol in our more general data model. The DR protocol π 0 . Informally speaking, this protocol is a simplified construction of π 0 , taking advantage of the 3-party model. Init 0 . On input database D = (A 1 , . . . , A m ), where A 1 , . . . , A m-1 contain keywords and A m contains a payload, S first computes a shuffled version sD of database D; that is, sD = (sA 1 , . . . , sA m ), where sA j (ρ(i)) = A j (i) for j = 1, . . . , m and i = 1, . . . , n, where ρ is a random permutation over {1, . . . , n}. Then, similarly as in Init 0 , S computes a pseudo-random version of the database sD, denoted as prsD = (prsA 1 , . . . , prsA m ), and computed by replacing keyword entries sA j (i) with pseudorandom entries prsA j (i) = f k (sA j (i)) for all j = 1, . . . , m and i = 1, . . . , n, where k is a random key and f is a pseudo-random permutation (here, using a permutation instead of a function will later facilitate C's decryption of any received payloads). Moreover, S generates a search data structure (i.e., a binary search tree iT ree j ) over the keywords prsA j (1), . . . , prsA j (n) in prsD, for j = 1, . . . , m -1. Then, S sends (iT ree 1 , . . . , iT ree m-1 ), prsD to T P and the key k to C, in addition to sending the database schema to both parties. Query 0 . In this protocol, C takes as input key k, a query value v and attribute index j, S takes as input key k and database D, and T P takes as input (iT ree 1 , . . . , iT ree m-1 ), prsD. On these inputs, the protocol goes as follows:

1. C computes f k (v) and sends (f k (v), j) to T P 2. T P searches for f k (v) in the search data structure iT ree j 3. If T P finds i such that f k (v) = prsA j (i), then T P sends the associated (encrypted) payload prsA m (i) to C C computes the (plain) payload as f -1 k (prsA m (i)) We note that Query 0 significantly simplifies Query 0 in that C can directly compute f k (v), without need to run an oPRFeval protocol, and T P can directly search for f k (v) in the data structure iT ree j , without need to run a semi-private PIR protocol.

Protocol π 0 can be shown to be a DR protocol in the 3-party model and in the following restricted data model: (1) the database entries do not change; (2) for each j ∈ {1, . . . , m} the database entries A j (1), . . . , A j (n) relative to the j-th attribute are all distinct. We remove these two restrictions exactly as done in Section 3: we generate π 2 from π 0 using a padded database, a multiplicity database, and composing m j (v) + 1 times protocol π 0 . A more formal description is included for completeness.

The DR protocol π 2 . Based on π 0 = (Init 0 , Query 0 , Update 0 ), we define protocol π 2 = (Init 2 , Query 2 , Update 2 ) as follows.

Init 2 . On input database D = (A 1 , . . . , A m ), S first runs Init 0 , thus sending prsD and (iT ree 1 , . . . , iT ree m-1 ) to T P and k to C, and D's schema to both C and T P . Then S builds an associated padded database pD = (pA 1 , . . . , pA m ), and an associated multiplicity database mD = (mA 1 , . . . , mA m ), exactly as done in Init 1 . Finally, S runs Init 0 to compute pseudo-random and shuffled versions prspD and prsmD of databases pD and mD, respectively, and to send the schema for databases mD and pD to C. Query 2 . On input query value v and attribute index j for C, and key k and databases prspD, prsmD for S, the following steps are run:

1. C and T P run subprotocol Query 0 on input database prsmD from T P , and query value (v, 1) and attribute index j from C. Let p(i) be the payload obtained by C at the end of this protocol, for some i ∈ {1, . . . , n}. If p(i) =⊥ then the protocol stops. Otherwise C sets the value m j (v) = p(i).

2. For t = 1, . . . , m j (v), C and T P run subprotocol Query 0 on input database prspD from T P , and query value (v, t) and attribute index j from C, who thus obtains payloads p(i(1)), . . . , p(i(m j (v))), i(1), . . . , i(m j (v)) ∈ {1, . . . , n}, from prspD; 3. For t = 1, . . . , m j (v), C computes the t-th original payload from D as f -1 k (p(i(t))), where k is the key obtained during the execution of Init 0 . Update 2 . We consider record addition and record deletion operations, and on each of them, we need to efficiently update any changed values; specifically:

1. the data structures required in π 0 ; 2. the multiplicity value m j (v) used in mD; 3. the multiplicity counters mc(i, j) in the padding structures used in pD and mD; 4. the database schema for pD and mD; 5. the data structures (iT ree 1 , . . . , iT ree m-1 ); and 6. the pseudo-random and shuffled databases prsmD and prspD.

The updates for values in ( 1)-( 4) are done as in Update 1 . The updates to the data structure iT ree are conventional data structure updates in the presence of one insertion or one deletion. As for (6), S can again use key k to recompute new f k (pD j (i)) and f k (mD j (i)) values. Several approaches would work to update the permutation ρ; here is an example: upon a record insertion, the newly inserted record is considered the (n + 1)-th record in D and ρ(n + 1) is defined as = n + 1; upon a deletion of the i-th record, the value ρ(n) is defined as = i.

Extension: Conjunction Formulae

We extend the KS protocols from Sections 3, 4 to the conjunction formulae over KS queries; that is, the AND of c KS queries, for some c ≥ 1.

A first approach would be to process, in parallel, an individual KS query for each term in the conjunction, and then having T P compute the intersection across the matching sets. This approach is clearly undesirable both for privacy and efficiency reasons. With respect to privacy, such a protocol would reveal to C the multiplicity of the query value in each conjunct, which is not necessarily computable from the number of records matching all conjuncts. With respect to efficiency, it is not hard to find examples of conjunctive queries for which at least one conjunct is matched by a linear number of records, but the number of records matching all conjuncts is sublinear in n. On such queries, the communication complexity would be linear even though the information to which C is entitled by the DR protocol functionality is sublinear.

To avoid both problems, we designed the following 'combined-index' approach. In the initialization subprotocol, a specific combined index on the tuple of attribute values can be created by concatenating the attribute names and query values, thus allowing the conjunction to be treated as a single keyword query. For example, a conjunctive query of A 1 = a 1 and A 2 = a 2 becomes a single KS query A 1 A 2 = a 1 a 2 . The combined index for A 1 A 2 is treated exactly as indices for single attributes. The initialization, insertion and deletion subprotocols are the same as those for KS queries, working on the cartesian product of the domain. C runs the KS query algorithm using the combined attribute values. Good properties of the method include: support of conjunctive queries with an arbitrary number of conjuncts; it is only necessary to create a single combined index for each set of attribute values as opposed to each permutation of the attribute values (i.e. only an index for A 1 A 2 is necessary, not one for A 1 A 2 and one for A 2 A 1 ); and querying on the single index is faster than querying on multiple indices and determining the intersection of the results. The unattractive property is that it requires one index for each supported conjunctions, resulting in an exponential (in c) number of indices if all possible conjunctions have to be supported. Still, many practical formulae can be addressed, as the scenario where the number of attributes is constant with respect to n is the most typical, and storage is an inexpensive resource nowadays.

Performance Evaluation

We present performance results for KS queries and boolean formulae over KS queries for a small number of queries executed using our 3-party protocol π 2 (implemented with an additional SSL/TLS layer). MySQL was used for obtaining baseline results in a non-private setting using the same schema and records as for π 2 . Setup. We used 5 different database sizes: 10K, 100K, 1M, 10M, and 100M records. All records were stored in a single database table containing the following columns: The S and T P processes and an instance of MySQL server version 5.5.28 were running on a Dell PowerEdge R710 server with two Intel Xeon X5650 2.66Ghz processors, 48GB of memory, 64-bit Ubuntu 12.04.1 operating system, and connected to a Dell PowerVault MD1200 disk array with 12 2TB 7.2K RPM SAS drives in RAID6 configuration. Database clients were running on a Dell PowerEdge R810 server with two Intel Xeon E7-4870 2.40GHz processors, 64 GB of memory, 64-bit Red Hat Enterprise Linux Server release 6.3 operating system, and connected to the Dell PowerEdge R710 server via switched Gigabit Ethernet. Regular TCP/IP connections were used for MySQL. We built MySQL indices on FirstName, LastName, Gender, and Number. We built keyword indices for our protocol π 2 on FirstName, LastName, Number, and a combined index on FirstName, Gender. The following query templates were used for executing database queries. Each query was executed five times using different values, and the average query response was used. We implemented a B + -tree as the search data structure (used as attribute index) due to its sub-linear search performance for disk-resident We note that for query Q3, we did not build a combined index, but, for sake of performance comparisons, we implemented an alternative conjunction protocol (a work in progress, omitted here) with yet unclear privacy properties. Also, for Q4, we implemented a disjunction protocol where the parties simply run the query protocol for both queries at the disjuncts (also a work in progress, since disjunction protocols with improved privacy may be desirable). Results. Figures 3,4 show the performance results for our protocol π 2 and MySQL, respectively. For all database sizes, Q1-Q4 matched 1, 500, 1000 and 2000 records, respectively. We observe that the database size has minimal impact on query response time. This was expected since the same number of records were matched by query. Our protocol π 2 's performance (∼2ms) is better than MySQL (∼5ms) for Q1 despite the additional overhead of SSL/TLS communications, because of the minimalistic approach used by our implementation, in terms of simpler query execution and data structures, compared to traditional database management systems. When the number of matched records increases, MySQL outperforms our protocol by a factor of around 8.6, 119.1, and 14.4 for Q2, Q3, and Q4, respectively. Unlike MySQL, where once the first match is found in the B + -tree data structure used for the queried column then a simple forward scan of the tree leaf pages is needed for locating all matches, our protocol performs a separate scan of the search data structure (a B + -tree) for each matched value. Because these scans are for ciphertext values, it is highly unlikely that any two scans will traverse the same path from the root of the B + -tree down to the same leaf page. Thus, the number of I/O operations required for fetching B + -tree leaf pages into the in-memory cache for locating matched records is proportional to the number of matched records. Our protocol's response times in Q3 are more than 17 times slower than response times in Q2 despite the fact that they have the same structure and, in addition, Q3 matched twice as many records as Q2. Furthermore, Q3 is 5 times slower than Q4 although Q4 resulted in twice as many matched records. The main reasons for this are the inefficiency of the protocol used for Q3 as well as the fact that Q2 was answered using a combined index, while Q3 and Q4 required scanning of two B + -tree indices.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Structure of our 2-party DR protocol

Our 3 -

 3 party DR protocol for KS queries follows the general structure outlined in Figure reffi-3party and satisfies the following Theorem 2. Under the existence of a PRF, there exists (constructively) a DR protocol π 2 = (Init 2 , Query 2 , Update 2 ) for KS queries in the 3-party model, satisfying:

  Q1: SELECT * FROM main WHERE Number = value Q2: SELECT * FROM main WHERE FirstName = value AND Gender = value Q3: SELECT * FROM main WHERE FirstName = value AND LastName = value Q4: SELECT * FROM main WHERE FirstName = value OR LastName = value

Fig. 3 . 4 .

 34 Fig. 3. Our 3-party query performance Fig. 4. MySQL query performance

Acknowledgements. This work was supported by the Intelligence Advanced Research Projects Activity (IARPA) via Department of Interior National Business Center (DoI/ NBC). The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation hereon. Disclaimer: The views and conclusions contained herein are those 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.


Giovanni Di Crescenzo
email: gdicrescenzo@appcomsci.com

David Shallcross
email: dshallcross@appcomsci.com

On Minimizing the Size of Encrypted Databases

Motivated by applications to maintaining confidentiality and efficiency of encrypted data access in cloud computing, we uncovered an inherent confidentiality weakness in databases outsourced to cloud servers, even when encrypted. To address this weakness, we formulated a new privacy notion for outsourced databases and (variants of) a classical record length optimization problem, whose solutions achieve the new privacy notion. Our algorithmic investigation resulted in a number of exact and approximate algorithms, for arbitrary input distributions, and in the presence of record additions and deletions. Previous work only analyzed an unconstrained variant of our optimization problem for specific input distributions, with no attention to running time or database updates.

Introduction

As the cloud computing paradigm is entering many of today's distributed computing applications, the research community is investigating a host of associated problems in many areas, including privacy, security, and algorithmic efficiency. One central cloud computing capability consists of outsourcing data to servers in the cloud, in a way that delegates the management of the data to the cloud servers while allowing efficient data access from authorized clients. In a typical instantiation of this capability, the data owner publishes a searchable database in the cloud and clients make their ordinary database queries directly to the cloud server. Because of confidentiality requirements on the data, and of the often unknown location of cloud servers as well as unknown entities who closely manage them, the data owner typically chooses to publish an encrypted version of the database, which can be later queried using privacy-preserving database retrieval protocols, and subject to compliance to specific query-based access policies. Unfortunately, encryption alone does not suffice to protect data confidentiality in these contexts, as encryption is known to hide all partial information but the length of the encrypted data. Accordingly, a cloud server with side channel information about the length of individual database records can derive confidential information about the content of the encrypted database. (As an example from the finance industry, if stock fund prospectuses are longer than single stock prospectuses, a cloud server can detect the relative density of stock funds and/or single stocks in the database, even if encrypted). Our contribution. Our approach to overcome these shortcomings consists of a suitable combination of padding short database records and splitting long database records so to normalize all records to have the same length, while still guaranteeing efficient access to them from clients. This approach calls for a new privacy model and a new optimization problem. In our privacy model, we require that the outsourced encrypted database at most leaks a symmetric function of the original record lengths. Our optimization problem (a variant of a classical record length problem, studied in the statistical and computer memory management literature) is defined as follows: an encrypted database with a large number n of records of different sizes s 1 , . . . , s n ≤ s max , needs to be normalized, via padding (e.g., adding a fixed string of a determined length) or splitting (e.g., dividing the record into 2 or more pieces and possibly padding again on the last piece) into a database with a potentially larger number n of records, all having the same size σ. Padding obviously increases the database size, but so does splitting, as each record contains an a-bit searchable header, which has to be replicated on all pieces resulting from the record split. We want to find the (exactly or approximately) optimal σ so that the total size of the database (increased due to padding and splitting) is minimized under a constraint that bounds the increase in the maximum (or average) search time for a given record. For a cleaner problem formulation, applicable to any possible search strategy, we model this constraint by imposing an upper bound on the number of pieces derived from a split of any given record (or of all records, respectively).

Our exact algorithms perform O(n • s max ) or O(n + s max log s max ) arithmetic operations (for both the unconstrained and the two constrained versions of our problem), which is super-polynomial in the input length (being linear in s max ). Our approximation algorithms can find c-approximate, for c ∼ 2, solutions with O(n) arithmetic operations (for both the unconstrained and the two constrained versions of our problem), and a (1 + )-approximate solution with O(n * polylog(s max )) arithmetic operations (for both the unconstrained and one constrained version of our problem). The latter algorithm can be shown to maintain a (1 + )-approximated solution by only requiring O(1) amortized arithmetic operations over a sequence of record additions and deletions, for any > 0 and under very general parameter settings. (Descriptions of this result and our formal privacy model, and almost all proofs are omitted due to space restrictions.) Related work. In the model of databases outsourced to cloud servers, there is a significant amount of work on data encryption (seemingly originated in [START_REF] Hacigms | Executing SQL over encrypted data in the database-service-provider model[END_REF]), and some amount of work on privacy-preserving database retrieval protocols (see, e.g., [START_REF] Di Crescenzo | Practical Private Information Retrieval from a Time-Varying, Multi-Attribute, and Multiple-Occurrence Database[END_REF]), and querybased access policy compliance (see, e.g. [START_REF] Di Crescenzo | Practical and Privacy-Preserving Policy Compliance for Outsourced Data[END_REF]). Minimizing the record length is an old problem considered in contexts like statistics and memory management, and that does not appear to have been investigated with an algorithmic viewpoint. An unconstrained version of our problem was introduced by [START_REF] Wolman | A Fixed Optimum Cell-Size for Records of Various Lengths[END_REF], who showed that when record lengths follow some classes of continuous probability distributions, the optimal choice of target record length is a quantity close to our result for arbitrary distributions. In [START_REF] Sipala | Optimum Cell Size for the Storage of Messages[END_REF], the author analyzed this problem in terms of the characteristic function of the distribution of the record length, and gave solutions for the cases of the uniform, exponential, and geometric distributions. In [START_REF] Erickson | Optimal Sizing of records Used to Store Messages of Various Lengths[END_REF] and [START_REF] Erickson | Optimal Sizing of Records when Divided Messages Can Be Stored in Records of Different Sizes[END_REF], the authors considered several different target record sizes, and presented solutions based on dynamic programming and non-linear optimization techniques. In [START_REF] Luss | An Extended Model for the Optimal Sizing of Records[END_REF], the author considers a similar problem in an extended model (somehow merging multiple records into one), which does not preserve some of the database search functionalities. None of these works focused on minimizing the running time required to produce a solution for an arbitrary distribution of a discrete set of record lengths. We are also not aware of any work considering constrained versions of this problem or the case of dynamic databases.

Definitions, Privacy and Algorithmic Models

Preliminary definitions. A database is an indexed sequence of records that can be modified, added, and removed over time. We denote as n the current number of records in the database. For i ∈ {1, . . . , n}, the i-th database record can be seen as composed of two parts: the header, whose size a ≥ 1 is constant across all records, and the payload, whose size s i ≥ 1 is variable. We denote as s max the maximum integer among s 1 , . . . , s n . We define a fixed record length database as a database where all record lengths are equal.

Privacy model. We consider the following Private Database Outsourcing (PDO) problem: a data owner, on input a database, wants to outsource some version of the database to a cloud server so that the server only learns minimal information about the database content, and yet can engage in database retrieval protocols with one or more clients, as well as policy compliance protocols ensuring that clients' queries are authorized. In this paper we only deal with the database outsourcing part of the PDO problem, but note that our approach integrates well with privacy-preserving database retrieval solutions (e.g., from [START_REF] Di Crescenzo | Practical Private Information Retrieval from a Time-Varying, Multi-Attribute, and Multiple-Occurrence Database[END_REF]) and privacy-preserving policy compliance solutions (e.g., from [START_REF] Di Crescenzo | Practical and Privacy-Preserving Policy Compliance for Outsourced Data[END_REF]). Encryption is a natural candidate tool to keep the outsourced database private from the server, who can still later run database retrieval and policy compliance protocols using techniques based on computing over encrypted data. Although in the cryptographic literature leakage of the length of an encrypted plaintext is usually considered a very minimal privacy violation (both the formal definitions of encryption [START_REF] Goldwasser | Probabilistic Encryption[END_REF] and of 2-party and multi-party private function evaluation protocols [START_REF] Yao | How to Generate and Exchange Secrets[END_REF][START_REF] Goldreich | How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority[END_REF] admit leakage of plaintext/input lengths), leaking the lengths s 1 , . . . , s n of all database records may well be an unacceptable privacy loss. We then ask the natural privacy question of what could/should be kept private in any solution to the PDO problem. In a similar question on the encryption of multiple different-length messages, solutions used in practice include either (a) padding each message to its next block length, which leaks a close upper bound of all length values; or (b) padding all messages to a common block length, which, although not the most efficient solution, has more satisfactory privacy as it only leaks an upper bound of all length values. Both (a) and (b) leak the exact number of encrypted messages.

(Informal) Privacy requirement: In formulating our privacy model, we attempt to capture the satisfactory privacy properties of the solution approach in (b), and at the same time generalize it to allow for a richer set of solutions to the PDO problem. Specifically, we require any solution to the PDO problem to leak at most:

1. the output of a function that is symmetric1 over the record lengths s 1 , . . . , s n ; 2. an upper bound on the number n of database records.

A formal description of this requirement can be provided in the simulation-based privacy framework and is omitted due to space restrictions.

Algorithmic Model. To transform any database into a fixed record length one, we only use two types of operations: (1) padding a payload; i.e., concatenating the payload with a predefined string (e.g., a 1 followed by an all 0's string), and (2) σ-splitting a record into multiple smaller records, where each new record has a copy of the same a-bit header and a distinct σ-bit piece of the original record's payload, where the last record may be padded so to have a σ-bit payload as well. Note that while the total length of the i-th record is a + s i in the original database, this length becomes a + σ in the fixed record length database, for some σ that can be chosen from a set of allowed values P .

In particular, we can consider, without loss of generality, P = {1, . . . , s max }, in which case for any σ ∈ P , any above defined database can be transformed into a fixed record length database via the following sequence of padding and σ-splitting operations, as follows: each record with payload shorter than σ can be padded and each s i -bit record with payload longer than σ can be split into s i /σ records, the last one being padded. Then, we can compute the size of the fixed record length database as function

f (σ) = i∈[n] s i σ (σ + a), (1)
where the input σ is taken from the set P which will usually be {1, . . . , s max } or a subset of that, although in our analysis we will often abuse notation to consider σ taken from the set of real numbers. We then define our problem of interest as the problem of minimizing the Encrypted Database Size (EDS), as captured by the function f defined in Formula 1, and coming into two main variants, depending on the constraints that we pose on the number of splitting operations. In the first variant, denoted as maxEDS, there is a maximum number of pieces into which we may split any record payload. In the second variant, denoted as avgEDS, there is a maximum total number of pieces into which we may split all of the record payloads. Formal definition follows.

Definition 1. [EDS]

Given n+1 positive integers a, s 1 , . . . , s n , find the integer σ from set P = {1, . . . , s max } that minimizes f (σ).

Definition 2. [maxEDS]

Given n + 2 positive integers a, s 1 , . . . , s n , c max , find the integer σ from set P = {1, . . . , s max } that minimizes f (σ) subject to the constraints s i /σ ≤ c max , for i = 1, . . . , n.

Definition 3. [avgEDS]

Given n + 2 positive integers a, s 1 , . . . , s n and c avg , find the integer σ from set P = {1, . . . , s max } that minimizes f (σ) subject to the constraint n i=1 s i /σ ≤ c avg . We investigate algorithms that solve these problems either exactly (i.e., returning any σ * that minimizes f (σ)), or δ-approximately (i.e., returning a σ such that f (σ) ≤ δf (σ * )), or δ-approximately even across a sequence of record additions and deletions. We will not try the approach of naturally extending f so that it is defined over all real numbers, and finding an analytical expression for a σ that exactly minimizes f as f is not convex, and is discontinuous at many points. To meet our privacy requirement, we will only design algorithms A which return a value σ that is a symmetric function of the values s 1 , . . . , s n . For the exact algorithms, this can be easily verified since these algorithms return the value σ that minimizes the function f defined in Formula 1, and f is a symmetric function of s 1 , . . . , s n . For the approximate algorithms, this is verified by direct inspection that the formula used in each of these algorithms is also a symmetric function of s 1 , . . . , s n .

We discuss two exact algorithms: a naive algorithm that runs in time O(nσ max ) and an improved algorithm that runs in time O(n + σ max log σ max ). A first exact algorithm. On input a, s 1 , . . . , s n , define algorithm A 0,1 for the EDS problem as follows: for each value σ from P , evaluate f (σ) using Formula (1); finally, select the value σ that minimizes f (σ). This algorithm finds an optimal solution for EDS in O(n|P |) = O(ns max ) arithmetic operations. By further checking that the constraint is satisfied, this algorithm is directly extended to find an optimal solution for maxEDS and avgEDS in the same asymptotic running time.

A second exact algorithm. As a potential improvement, we consider algorithm A 0,2 that precomputes two sets of values related to the multiplicities of the payload sizes, and uses an alternative expression for f (σ) that is faster to compute, given the precomputed values. Specifically, the precomputed values consist of the multiplicities of the payload sizes m v = |{i ∈ N : s i = v}|, and the related values m + v = |{i ∈ N : s i ≥ v}|, defined for all v ∈ P . We note the following Fact 1. For each v = 1, . . . , s max , it holds that m + v = m + v+1 + m v . The alternative expression for f (σ) is the following:

f (σ) = smax/σ h=1 i: si/σ =h s i σ (σ + a) (2)
= smax/σ h=1 h m + 1+σ(h-1) -m + 1+σh (σ + a) (3)
Based on these definitions, we define algorithm A 0,2 for the EDS problem, as follows: Algorithm A 0,2 : On input a, s 1 , . . . , s n , do the following:

1. Calculate s max 2. Calculate m v , for each v from 1 to s max . 3. Calculate m + v , for each v from s max down to 1, using recurrence relation in Fact 1. 4. Calculate f (σ), for each σ in P , using Formula (3).

Return the value σ *

f that minimizes f . For the running time, we observe that steps 1, 2 and 3 can be run in time O(n), step 4 in time O(s max log s max ) (that is, O(s max /σ), for σ = 1, . . . , s max ), and step 5 in time O(s max ). This algorithm is directly extended to find an optimal solution for maxEDS by further checking that the constraint is satisfied, which can be done in time O(n). Checking that the constraint for avgEDS is satisfied can be done in time O(s max log s max ) by observing that the left hand side of the constraint can be rewritten similarly as in Formula (3). Thus, algorithm A 0,2 can be extended to work for maxEDS and avgEDS by keeping the same asymptotic running time. We obtain the following Theorem 1. For each of the problems EDS, maxEDS and avgEDS, we can construct an algorithm that exactly solves the problem in O(min{ns max , n + s max log s max }) arithmetic operations.

The running time in Theorem 1 is not polynomial in the input length (as it is linear in s max ) and can be too expensive in practical large databases (e.g., when n ≥ 10 9 and s max ≥ 10MB). Thus, we turn our attention to finding approximation algorithms with faster running times (possibly, linear in n and polylogarithmic in s max ). As both the algorithm's running time and the quality of the approximation are of interest, we study algorithms that attempt to minimize one metric while achieving satisfactory performance on the other one. Specifically, we study algorithms with constant approximation factor and very fast running time (i.e., O(n)) in Section 4, and algorithms with very small (i.e., (1 + ), for any > 0) approximation factor and any running time improving over A 0,1 and A 0,2 in Section 5.

Faster Algorithms with O(1) Approximation Factor

In this section we study algorithms for maxEDS and avgEDS that attempt to minimize their running time while achieving a constant approximation factor. When compared with the exact algorithms in Section 3, the algorithms in this section achieve a smaller running time (only linear in n and with no dependency on s max ) at the cost of achieving approximation factor 2 or slightly greater than 2. We start with a definition useful for both algorithms; we define function g over the set of real numbers, as follows:

g(σ) = n i=1 s i σ + 1 (σ + a), (4)
Then, our first algorithm, for problem maxEDS, and its properties are as follows.

Algorithm A max 1 : On input a, s 1 , . . . , s n , c max , compute s = n i=1 s i /n and then σ * g = √ as, and then return σ, computed as the value among σ * g , σ * g , s max /c max that is at least s max /c max and results in the smaller value for f (σ). An algorithm A 1 for problem EDS with the same running time and approximation factor can be obtained by directly simplifying A max 1 . We cannot directly adapt these techniques to avgEDS, as a value for σ satisfying the equality in constraint n i=1 s i /σ ≤ c avg may be hard to find, due to the n rounding operations. Instead, we minimize the approximating function g subject to an even tighter constraint, and bound the additional error produced. We now define an algorithm for avgEDS and state its properties.

Fast Algorithms with (1 + ) Approximation Factor

We show an algorithm for maxEDS (and thus EDS) that achieves (1 + ) approximation factor, for any > 0, and running time asymptotically smaller than the exact algorithms described in Section 4. Our algorithm extends the technique used in Section 4 where we approximated function f by a convex function g. Here, we approximate function f with several functions g k , for any integer k > 0. First, for any integers k > 0 and any real number x > 0, we define w(k, x) as x if x ≤ k -1 or 1 + x if x > k -1. Then, for any integer k > 0, we define an approximation function g k to f as

g k (σ) = i∈N w k, s i σ (σ + a)
Note that for k = 1, function g 1 is the same as function g defined in Section 4, where we have showed that g can be computed in time O(n). For k > 1, we can still evaluate function g k more efficiently than f , using some auxiliary variables and a suitable piecewise decomposition and rewriting of g k . A first set of definitions relevant to this goal include the previously defined quantities m v , m + v and some new quantities b v , c h,v , defined as follows, for each v = 1, . . . , s max , and each integer h > 0:

1

. b v = si≥v s i ; and 2. c h,v = |{i ∈ N : s i /v = h}|.
To reduce the number of candidate σ values from P from which we plan to evaluate g k (σ), for any integer k and any j = 0, . . . , q, where q is the max value such that (1 + ) q * s max /c max ≤ s max , we define the quantities:

1. τ 0 = s max /c max , τ j = (1 + ) * τ j-1 ; 2. M j = |{i ∈ N : 1 + τ j (k -1) ≤ s i < τ j+1 (k -1)}|; and 3. B j = τj+1(k-1) si≥1+τj (k-1) s i . By applying the definitions of m v , M j , b v , B j , c h,σ , m + v , we derive the following Fact 3. For each j = 0, . . . , q and each integer h > 0, it holds that 1. m + 1+τj (k-1) = m + τj+1(k-1) + M j 2. b 1+τj (k-1) = b + τj+1(k-1) + B j 3. c h,τj = m + 1+τj (h-1) -m + 1+τj h

We can then evaluate g k (σ), for all σ = τ 0 , τ 1 , . . . , τ q , as g k (σ) =

1 σ (σ + a) (6)
Based on the above, we can now construct our algorithm A max

2

, by setting k = 1/ , quickly computing g k based on Formula 6 and Fact 3, approximating f with g k , and minimizing g k subject to the constraint s max /σ ≤ c max and σ varying over the multiplicative grid of τ 0 , . . . , τ q .

Algorithm A max 2 : On input a, s 1 , . . . , s n , c max , , do the following: 1. Calculate s max and set k = 1/ . 2. Calculate all M j , for j = 0, . . . , q by scanning all s i 's only once and, for each s i , using binary search to find the associated M j . 3. Calculate all B j , for j = 0, . . . , q by scanning all s i 's only once and, for each s i , using binary search to find the associated B j . 4. Calculate m + 1+τj (k-1) , for j = 0, . . . , q, using recurrence relation in Fact 3, item 1. 5. Calculate b 1+τj (k-1) , for j = 0, . . . , q, using recurrence relation in Fact 3, item 2. 6. Calculate c h,τj , for j = 0, . . . , q, and h = 1, . . . , k -1, using recurrence relation in Fact 3, item 3. 7. Choose the value σ * g,k that minimizes g k , by examining every value of σ from {τ 0 , τ 1 , . . . , τ q } and using Formula (6) to evaluate g k (σ).

Theorem 2. A max 1 2

 1 -approximately solves the maxEDS problem in O(n) arithmetic operations.

Algorithm A avg 1 :Theorem 3 . A avg 1 (

 131 On input a, s 1 , . . . , s n , c avg , compute the quantities β = c avg /n and s = n i=1 s i /n. Then check whether √ as ≥ s/(β -1). If yes, set s * g the value among √ as and √ as that has a lower value of function g, as defined in Formula 4. If not, set s * g = s/(β -1) . Finally, return s * g . 2+1/s+1/(β(β -1)))-approximately solves the avgEDS problem in O(n) arithmetic operations, where β = c avg /n.

  σ h (σ + a) + m + 1+σ(k-1) + b 1+σ(k-1)

Theorem 4 .

 4 For any > 0, A max 2 (1 + )-approximately solves the maxEDS problem in O(n log(log(c max )/ ) + log c max / 2 ) arithmetic operations.

A function f is symmetric if it satisfies f (x1, . . . , xn) = f (x ρ(1) , . . . , x ρ(n) )for any input (x1, . . . , xn) and any permutation ρ over {1, . . . , n}.

Acknowledgement. We thank Euthimios Panagos for interesting discussions. This work was supported by the Intelligence Advanced Research Projects Activity (IARPA). The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation hereon. Disclaimer: The views and conclusions contained herein are those 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.