| 講演名 | 2005-07-22 検索語の秘匿と検索結果の一貫性検証を可能とするデータ検索プロトコルにおける通信量の削減 中山 敏, 吉田 真紀, 岡村 真吾, 藤原 晶, 藤原 融, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | データ検索では, 検索語をもつユーザが検索対象であるデータベースをもつサーバに対して問い合わせを行い, それに対する返答から検索結果としてデータベースの情報を得る.データ検索に対する安全性要件として, 検索語の秘匿, データベースの秘匿, 検索結果の一貫性検証がある.著者等はこれまでに, 三つの安全性要件を満たしたデータ検索プロトコルを提案した.サーバはMerkle木を用いて一貫性検証を可能とする値(コミット値と証明値)を生成する.ユーザはOblivious Transfer (OT)を用いて検索結果と証明値をサーバから得る.データ検索では通信量が少ないことが望まれるため, サーバはユーザから受け取った検索結果に対する問い合わせを変換して, 証明値に対する問い合わせとしても利用している.しかし, 変換後の問い合わせに対する返答の通信量がデータベースの大きさに比例してしまい効率が悪い.そこで, 本稿では変換後の問い合わせに対する返答の通信量がデータベースの大きさに比例しないOTを提案し, それを用いることによって通信効率の良いデータ検索プロトコルを実現した. |
| 抄録(英) | 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. |
| キーワード(和) | データ検索 / 検索語の秘匿 / データベースの秘匿 / 検索結果の一貫性検証 / Merkle木 / 通信効率 |
| キーワード(英) | Data Retrieval / Privacy of a User / Privacy of the Server / Consistency of an Answer / Merkle Tree / Oblivious Transfer / Efficiency |
| 資料番号 | ISEC2005-61 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2005/7/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 検索語の秘匿と検索結果の一貫性検証を可能とするデータ検索プロトコルにおける通信量の削減 |
| サブタイトル（和） | |
| タイトル（英） | Reducing Communication Complexity of the Private Data Retrieval Protocol with Consistent Results |
| サブタイトル（和） | |
| キーワード(1)（和/英） | データ検索 / Data Retrieval |
| キーワード(2)（和/英） | 検索語の秘匿 / Privacy of a User |
| キーワード(3)（和/英） | データベースの秘匿 / Privacy of the Server |
| キーワード(4)（和/英） | 検索結果の一貫性検証 / Consistency of an Answer |
| キーワード(5)（和/英） | Merkle木 / Merkle Tree |
| キーワード(6)（和/英） | 通信効率 / Oblivious Transfer |
| 第 1 著者 氏名（和/英） | 中山 敏 / Satoshi NAKAYAMA |
| 第 1 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 2 著者 氏名（和/英） | 吉田 真紀 / Maki YOSHIDA |
| 第 2 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 3 著者 氏名（和/英） | 岡村 真吾 / Shingo OKAMURA |
| 第 3 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 4 著者 氏名（和/英） | 藤原 晶 / Akira FUJIWARA |
| 第 4 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 5 著者 氏名（和/英） | 藤原 融 / Toru FUJIWARA |
| 第 5 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 発表年月日 | 2005-07-22 |
| 資料番号 | ISEC2005-61 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 194 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |