## CryptoDB

### William E. Skeith III

#### Publications

**Year**

**Venue**

**Title**

2008

EPRINT

Public-Key Encryption with Efficient Amortized Updates
Abstract

Searching and modifying public-key encrypted data (without having the decryption key) has received a lot of attention in recent literature. In this paper we re-visit this important problem and achieve much better amortized communication-complexity bounds. Our solution resolves the main open question posed by Boneh at al., \cite{BKOS07}.
First, we consider the following much simpler to state problem (which turns out to be central for the above): A server holds a copy of Alice's database that has been encrypted under Alice's public key. Alice would like to allow other users in the system to replace a
bit of their choice in the server's database by communicating directly with the server, despite other users not having Alice's private key. However, Alice requires that the server should not know
which bit was modified. Additionally, she requires that the
modification protocol should have ``small" communication complexity
(sub-linear in the database size). This task is referred to as
private database modification, and is a central tool in building a more general protocol for modifying and searching over public-key encrypted data with small communication complexity. The problem was first considered by Boneh at al., \cite{BKOS07}. The protocol of \cite{BKOS07} to modify $1$ bit of an $N$-bit database has communication complexity $\mathcal{O}(\sqrt N)$. Naturally, one can ask if we can improve upon this. Unfortunately, \cite{OS08} give evidence to the contrary, showing that using current algebraic techniques, this is not possible to do. In this paper, we ask the following question: what is the communication complexity when modifying $L$ bits of an $N$-bit database? Of course, one can achieve naive communication complexity of $\mathcal{O}(L\sqrt N)$ by simply repeating the protocol of \cite{BKOS07}, $L$ times. Our main result is a private database modification protocol to modify $L$ bits of an $N$-bit database that has communication complexity
$\mathcal{O}(\sqrt{NL^{1+\alpha}}\textrm{poly-log~} N)$, where
$0<\alpha<1$ is a constant. (We remark that in contrast with recent work of Lipmaa \cite{L08} on the same topic, our database size {\em does not grow} with every update, and stays exactly the same size.)
As sample corollaries to our main result, we obtain the following:
\begin{itemize}
\item First, we apply our private database modification protocol to
answer the main open question of \cite{BKOS07}. More specifically, we
construct a public key encryption scheme supporting PIR queries that
allows every message to have a non-constant number of keywords
associated with it.
\item Second, we show that one can apply our
techniques to obtain more efficient communication complexity when
parties wish to increment or decrement multiple cryptographic
counters (formalized by Katz at al. ~\cite{KMO01}).
\end{itemize}
We believe that ``public-key encrypted'' amortized database modification is an important cryptographic primitive in it's own right and will be a useful in other applications.

2007

EPRINT

A Survey of Single Database PIR: Techniques and Applications
Abstract

In this paper we survey the notion of Single-Database Private
Information Retrieval (PIR). The first Single-Database PIR was
constructed in 1997 by Kushilevitz and Ostrovsky and since then
Single-Database PIR has emerged as an important cryptographic
primitive. For example, Single-Database PIR turned out to be
intimately connected to collision-resistant hash functions,
oblivious transfer and public-key encryptions with additional
properties. In this survey, we give an overview of many of the
constructions for Single-Database PIR (including an abstract
construction based upon homomorphic encryption) and describe some of
the connections of PIR to other primitives.

2007

EPRINT

Algebraic Lower Bounds for Computing on Encrypted Data
Abstract

In cryptography, there has been tremendous success in building
primitives out of homomorphic semantically-secure encryption
schemes, using homomorphic properties in a black-box way. A few
notable examples of such primitives include items like private
information retrieval schemes and collision-resistant hash functions. In this paper, we illustrate a general
methodology for determining what types of protocols can be
implemented in this way and which cannot. This is accomplished by
analyzing the computational power of various algebraic structures
which are preserved by existing cryptosystems. More precisely, we
demonstrate lower bounds for algebraically generating generalized
characteristic vectors over certain algebraic structures, and
subsequently we show how to directly apply this abstract algebraic
results to put lower bounds on algebraic constructions of a number of
cryptographic protocols, including PIR-writing and private keyword
search protocols. We hope that this work will provide a simple
``litmus test'' of feasibility for use by other cryptographic
researchers attempting to develop new protocols that require
computation on encrypted data. Additionally, a precise mathematical
language for reasoning about such problems is developed in this
work, which may be of independent interest.

2007

EPRINT

Public Key Encryption that Allows PIR Queries
Abstract

Consider the following problem: Alice wishes to maintain her email
using a storage-provider Bob (such as a Yahoo! or hotmail e-mail
account). This storage-provider should provide for Alice the ability
to collect, retrieve, search and delete emails but, at the same
time, should learn neither the content of messages sent from the
senders to Alice (with Bob as an intermediary), nor the search
criteria used by Alice. A trivial solution is that messages will be
sent to Bob in encrypted form and Alice, whenever she wants to
search for some message, will ask Bob to send her a copy of the
entire database of encrypted emails. This however is highly
inefficient. We will be interested in solutions that are communication-efficient and, at the same time, respect the privacy of Alice. In this paper, we show how to create a public-key encryption scheme for Alice that allows PIR searching over encrypted documents. Our solution provides a theoretical solution to an open problem posed by Boneh, DiCrescenzo, Ostrovsky and Persiano on ``Public-key Encryption with Keyword Search'', providing the first scheme that does not reveal any partial information regarding user's search (including the access pattern) in the public-key setting and with non-trivially
small communication complexity.
The main technique of our solution also allows for Single-Database PIR writing with sub-linear communication complexity, which we consider of independent interest.

#### Coauthors

- Dan Boneh (2)
- Nishanth Chandran (1)
- Nelly Fazio (1)
- Rosario Gennaro (1)
- Eyal Kushilevitz (2)
- Rafail Ostrovsky (8)
- Irippuge Milinda Perera (1)