| Presentation | 2005-07-22 Reducing Communication Complexity of the Private Data Retrieval Protocol with Consistent Results Satoshi NAKAYAMA, Maki YOSHIDA, Shingo OKAMURA, Akira FUJIWARA, Toru FUJIWARA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A data retrieval protocol between a database server, who has a database, and a user, who has an index, allows the user to obtain an item in the database. Security requirements for data retrieval are the privacy of a user, the privacy of the database server, and the consistency of an answer. We have proposed a data retrieval protocol which satisfies the three security requirements. The server uses Merkle tree to generate a commitment and a proof which enable the user to verify the consistency of an answer, and publishes the commitment. The user executes Oblivious transfer (OT) with the server to obtain not only the item but also the proof. To make the protocol efficient, the server transforms a query for the item into a query for the proof and uses it. However, the size of an answer for a query obtained by the transformation is linear in the size of the database. That is, the previous protocol is inefficient. In this paper, we propose an efficient OT such that the size of an answer for the query obtained by the transformation is not linear in the size of the database, and realize an efficient data retrieval protocol by using the proposed OT. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Data Retrieval / Privacy of a User / Privacy of the Server / Consistency of an Answer / Merkle Tree / Oblivious Transfer / Efficiency |
| Paper # | ISEC2005-61 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2005/7/15(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Reducing Communication Complexity of the Private Data Retrieval Protocol with Consistent Results |
| Sub Title (in English) | |
| Keyword(1) | Data Retrieval |
| Keyword(2) | Privacy of a User |
| Keyword(3) | Privacy of the Server |
| Keyword(4) | Consistency of an Answer |
| Keyword(5) | Merkle Tree |
| Keyword(6) | Oblivious Transfer |
| Keyword(7) | Efficiency |
| 1st Author's Name | Satoshi NAKAYAMA |
| 1st Author's Affiliation | Graduate School of Information Science and Technology, Osaka University() |
| 2nd Author's Name | Maki YOSHIDA |
| 2nd Author's Affiliation | Graduate School of Information Science and Technology, Osaka University |
| 3rd Author's Name | Shingo OKAMURA |
| 3rd Author's Affiliation | Graduate School of Information Science and Technology, Osaka University |
| 4th Author's Name | Akira FUJIWARA |
| 4th Author's Affiliation | Graduate School of Information Science and Technology, Osaka University |
| 5th Author's Name | Toru FUJIWARA |
| 5th Author's Affiliation | Graduate School of Information Science and Technology, Osaka University |
| Date | 2005-07-22 |
| Paper # | ISEC2005-61 |
| Volume (vol) | vol.105 |
| Number (no) | 194 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |