For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Private and Consistent Data Retrieval Scheme with Log-Squared Communication
Satoshi NAKAYAMA Maki YOSHIDA Shingo OKAMURA Toru FUJIWARA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2007/01/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
data retrieval, privacy of a user, secrecy of the database, consistency of answers, communication complexity,
Full Text: PDF(412.2KB)>>
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.