International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Jia Xu

Affiliation: NUS

Publications

Year
Venue
Title
2014
EPRINT
2010
EPRINT
Authenticating Aggregate Range Queries over Multidimensional Dataset
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
Jia XU
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
Jia XU
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
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
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.