A Private and Consistent Data Retrieval Scheme with Log-Squared Communication

Satoshi NAKAYAMA  Maki YOSHIDA  Shingo OKAMURA  Toru FUJIWARA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.1   pp.204-215
Publication Date: 2007/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.1.204
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Application
Keyword: 
data retrieval,  privacy of a user,  secrecy of the database,  consistency of answers,  communication complexity,  

Full Text: PDF(412.2KB)>>
Buy this Article




Summary: 
Data retrieval is used to obtain a particular data item from a database. A user requests an item in the database from a database server by sending a query, and obtains the item from an answer to the query. Security requirements of data retrieval include protecting the privacy of the user, the secrecy of the database, and the consistency of answers. In this paper, a data retrieval scheme which satisfies all the security requirements is defined and an efficient construction is proposed. In the proposed construction, the size of a query and an answer is O((log N)2), and the size of data published by the database server when the database is updated is only O(1). The proposed construction uses the Merkle tree, a commitment scheme, and Oblivious Transfer. The proof of the security is given under the assumption that the used cryptographic schemes are secure.