## CryptoDB

### Jia Xu

#### Affiliation: NUS

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Authenticating Aggregate Range Queries over Multidimensional Dataset
Abstract

We are interested in the integrity of the query results from an outsourced database service provider. Alice passes a set $\mathtt{D}$ of $d$-dimensional points, together with some authentication tag $\mathtt{T}$, to an untrusted service provider Bob. Later, Alice issues some query over $\mathtt{D}$ to Bob, and Bob should produce a query result and a proof based on $\mathtt{D}$ and $\mathtt{T}$. Alice wants to verify the integrity of the query result with the help of the proof, using only the private key.
In this paper, we consider aggregate query conditional on multidimensional range selection. In its basic form, a query asks for the total number of data points within a $d$-dimensional range.
We are concerned about the number of communication bits required and the size of the tag $\mathtt{T}$.
We give a method that requires $O(d^2)$ communication bits to authenticate an aggregate query conditional on $d$-dimensional range selection. Besides counting, summing and finding of the minimum can also be supported. Furthermore, our scheme can be
extended slightly to authenticate $d$-dimensional usual (non-aggregate) range selection query with $O(d^2)$ bits communication overhead, improving known results that require $O(\log^{d-1} N)$ communication overhead, where $N$ is the
number of data points in the dataset.

2010

EPRINT

Authenticating Aggregate Range Queries over Dynamic Multidimensional Dataset
Abstract

We are interested in the integrity of the query results from an outsourced database service provider. Alice passes a set
$\set{D}$ of $d$-dimensional points, together with some authentication tag $\set{T}$, to an untrusted service provider Bob. Later, Alice issues some query over $\set{D}$ to Bob, and Bob should produce a query result and a proof based on $\set{D}$ and $\set{T}$.
Alice wants to verify the integrity of the query result with the help of the proof, using only the private key.
Xu J.~\emph{et al.}~\cite{maia-full} proposed an authentication scheme to solve this problem for multidimensional aggregate range query, including {\SUM, \COUNT, \MIN, \MAX} and {\MEDIAN}, and multidimensional range selection query, with $O(d^2)$ communication overhead. However, their scheme only applys to static database.
This paper extends their method to support dynamic operations on the dataset, including inserting or deleting a point from the dataset. The communication overhead of our scheme is $O(d^2 \log N)$, where $N$ is the
number of data points in the dataset.

2010

EPRINT

A New Joint Fingerprinting and Decryption Scheme based on a Lattice Problem
Abstract

We propose a new encryption scheme that supports joint fingerprinting and decryption. The scheme is remarkably resistant to known-plaintext attack and collusion attack (e.g. average attack or other linear combination attack) on keys. Interestingly, the security of our scheme is relied on a lattice problem: Given a collection of random lattice points generated from a short basis of a lattice, find the short basis. The scheme can be used as a traitor-tracing scheme or a buyer-seller watermarking scheme.

2009

EPRINT

Short Redactable Signatures Using Random Trees
Abstract

A redactable signature scheme for a string of objects supports
verification even if multiple substrings are removed from the
original string. It is important that the redacted string and
its signature do not reveal anything about the content of the
removed substrings. Existing schemes completely or partially
leak a piece of information: the lengths of the removed substrings.
Such length information could be crucial for many applications,
especially when the removed substring has low entropy. We
propose a scheme that can hide the length. Our scheme consists
of two components. The first component $\mathcal{H}$, which is a
``collision resistant'' hash, maps a string to an unordered set,
whereby existing schemes on unordered sets can then be applied.
However, a sequence of random numbers has to be explicitly stored
and thus it produces a large signature of size at least $(m
k)$-bits where $m$ is the number of objects and $k$ is the size of a
key sufficiently large for cryptographic operations. The second
component uses RGGM tree, a variant of GGM tree, to
generate the pseudo random numbers from a short seed, expected to be
of size $O(k+ tk\log m)$ where $t$ is the number of removed
substrings. Unlike GGM tree, the structure of the proposed RGGM tree
is random. By an intriguing statistical property of the random tree,
the redacted tree does not reveal the lengths of the substrings
removed. The hash function $\mathcal{H}$ and the RGGM tree can be of
independent interests.

2008

EPRINT

Remote Integrity Check with Dishonest Storage Server
Abstract

We are interested in this problem: a verifier, with a small and
reliable storage, wants to periodically check whether a remote
server is keeping a large file $\mathbf{x}$. A dishonest server,
by adapting the challenges and responses, tries to discard partial
information of $\mathbf{x}$ and yet evades detection. Besides the
security requirements, there are considerations on communication,
storage size and computation time. Juels et al. \cite{Pors} gave
a security model for {\em Proof of Retrievability} ({\POR})
system. The model imposes a requirement that the original ${\bf
x}$ can be recovered from multiple challenges-responses. Such
requirement is not necessary in our problem. Hence, we propose an
alternative security model for {\em Remote Integrity Check}
({\RIC}). We study a few schemes and analyze their efficiency and
security. In particular, we prove the security of a proposed
scheme {\simplePIR}. This scheme can be deployed as a {\POR}
system and it also serves as an example of an effective {\POR}
system whose ``extraction'' is not verifiable. We also propose a
combination of the RSA-based scheme by Filho et al. \cite{DDPs}
and the ECC-based authenticator by Naor et al.
\cite{complex_memcheck}, which achieves good asymptotic
performance. This scheme is not a {\POR} system and seems to be a
secure {\RIC}. In-so-far, all schemes that have been proven
secure can also be adopted as {\POR} systems. This brings out the
question of whether there are fundamental differences between the
two models. To highlight the differences, we introduce a notion,
{\em trap-door compression}, that captures a property on
compressibility.

#### Coauthors

- Ee-Chien Chang (3)
- Chee Liang Lim (1)
- Duncan S. Wong (1)
- Anjia Yang (1)
- Jianying Zhou (1)