Our second result is a primitive which we call a \emph{verifiable database} (VDB). Here, a weak client outsources a large table to an untrusted server, and makes retrieval and update queries. For each query, the server provides a response and a proof that the response was computed correctly. The goal is to minimize the resources required by the client. This is made particularly challenging if the number of update queries is unbounded. We present a VDB scheme based on the hardness of the subgroup membership problem in composite order bilinear groups.
Category / Keywords: cryptographic protocols / verifiable computation, diffie-hellman, bilinear maps Publication Info: An extended abstract of this paper will be published in the proceedings of Crypto'11 Date: received 15 Mar 2011, last revised 11 Jul 2011 Contact author: evahlis at cs columbia edu Available format(s): PDF | BibTeX Citation Note: Because of a LaTeX compiling error, the PDF of previous version lacked ToC and references. Version: 20110711:144333 (All versions of this report) Short URL: ia.cr/2011/132