International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Yan-Cheng Chang

Publications

Year
Venue
Title
2006
JOFC
2004
EPRINT
Single Database Private Information Retrieval with Logarithmic Communication
Yan-Cheng Chang
In this paper, we study the problem of single database private information retrieval, and present schemes with only logarithmic server-side communication complexity. Previously the best result could only achieve polylogarithmic communication, and was based on certain less well-studied assumptions in number theory \cite{CMS99}. On the contrary, our construction is based on Paillier's cryptosystem \cite{P99}, which along with its variants have drawn extensive studies in recent cryptographic researches \cite{PP99,G00,CGGN01,DJ01,CGG02,CNS02,ST02,GMMV03,KT03}, and have many important applications (e.g., the Cramer-Shoup CCA2 encryption scheme in the standard model \cite{CS02}). Actually, our schemes can be directly used to implement $1$-out-of-$N$ {\em $\ell$-bit string} oblivious transfer with $O(\ell)$ sender-side communication complexity (against semi-honest receivers and malicious senders). Note the sender-side communication complexity is independent of $N$, the constant hidden in the big-$O$ notation is in fact small, and $\ell$ is unrestricted. Moreover, We also show a way to do communication balancing between the sender-side and the receiver-side. In addition, we show how to handle malicious receivers with small communication overheads, which itself is a non-trivial result.
2004
EPRINT
Privacy Preserving Keyword Searches on Remote Encrypted Data
Yan-Cheng Chang Michael Mitzenmacher
We consider the following problem: a user \U\ wants to store his files in an encrypted form on a remote file server \FS. Later the user \U\ wants to efficiently retrieve some of the encrypted files containing (or indexed by) specific keywords, keeping the keywords themselves secret and not jeopardizing the security of the remotely stored files. For example, a user may want to store old e-mail messages encrypted on a server managed by Yahoo or another large vendor, and later retrieve certain messages while traveling with a mobile device. In this paper, we offer solutions for this problem under well-defined security requirements. Our schemes are efficient in the sense that no public-key cryptosystem is involved. Indeed, our approach is independent of the encryption method chosen for the remote files. They are also incremental, in that \U\ can submit new files which are totally secure against previous queries but still searchable against future queries.
2002
ASIACRYPT
2001
ASIACRYPT