Based on a novel extension of the security properties of \emph{bilinear-map accumulators} as well as on a primitive called \emph{accumulation tree}, our authenticated data structure is the first to achieve \emph{optimal} verification and proof complexity (i.e., only proportional to the size of the query parameters and the answer), as well as \emph{optimal} update complexity (i.e., constant), and without bearing any extra asymptotic space overhead. Queries (i.e., constructing the proof) are also efficient, adding a \emph{logarithmic} overhead to the complexity needed to compute the actual answer.
In contrast, existing schemes entail high communication and verification costs or high storage costs as they recompute the query over authentic data or precompute answers to all possible queries. % Applications of interest include efficient verification of keyword search and database queries. We base the security of our constructions on the \emph{bilinear $q$-strong Diffie-Hellman} assumption.
Category / Keywords: authenticated data structures, lattice-based cryptography Date: received 23 Aug 2010, last revised 1 Mar 2011 Contact author: cpap at cs brown edu Available format(s): PDF | BibTeX Citation Version: 20110301:201132 (All versions of this report) Short URL: ia.cr/2010/455 Discussion forum: Show discussion | Start new discussion