| 講演名 | 2005-03-18 任意の量子一方向性関数に対するハードコア述語の一般的構成法 河内 亮周, 山上 智幸, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本論文で我々は任意の量子一方向性関数に対するハードコア述語の一般的構成法を示す. 我々のその構成方法は与えられた量子アルゴリズムの設計方法の基礎となる枠組に基づいており, その枠組は与えられた誤りなしオラクルを同定する量子アルゴリズムの典型的設計手法となっている. また一方でハードコア述語のための安全性帰着は誤りありオラクルが与えられた場合にその同定問題を解くことに相当しており, 我々はそのアルゴリズムの枠組がそのような誤りありオラクルに対しても頑健に動作することを証明することで, その枠組がハードコア述語の安全性帰着に利用できることを示す. 従って, その枠組の上で効率良く解けるオラクル同定問題から, 任意の量子一方向性関数に対するハードコア述語を構成でき, Goldreich-Levinの定理を包含するようなハードコア述語の広いクラスを与えることができる. この我々の構成方法の具体的応用として, 任意の量子一方向性関数に対する以下の二つの新しいハードコア述語を得た. 一つ目の述語QNR_x(r)は, ある適当な素数pに対してx+r mod pが平方剰余でなければQNR_x(r)=1, 平方剰余であれば0と定義される. 二つ目の述語EQ^<2+>_x(r)は, もしx_ix_ |
| 抄録(英) | We propose a general construction of hard-core predicates for any quantum one-way function in this paper. Our construction is based on a certain quantum algorithmic framework for oracle computation used in many quantum algorithms, which efficiently identify a given perfect oracle. On the other hand, we can regard a security reduction for a hard-core predicate as the identification problem with an imperfect oracle. We prove that the algorithmic framework works robustly even for such an imperfect oracle. Thus, we can provide a wide class of hard-core predicates for any quantum one-way function, including the quantum Goldreich-Levin theorem shown, from efficiently solvable identification problems for perfect oracles. As for applications of our construction, we obtain new hard-core predicates for any quantum one-way function. The first predicate QNR_x(r) is defined as QNR_x(r) = 1 if x + r mod p is not a quadratic residue for some prime p and 0 otherwise. The second predicate EQ^<2+>_x(r) is defined as EQ^<2+>_x(r) = [○!+]^ |
| キーワード(和) | ハードコア述語 / 量子一方向性関数 / 量子還元 / オラクル同定問題 |
| キーワード(英) | hard-core predicates / quantum one-way functions / quantum reduction / oracle identification problems |
| 資料番号 | COMP2004-74 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2005/3/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 任意の量子一方向性関数に対するハードコア述語の一般的構成法 |
| サブタイトル（和） | |
| タイトル（英） | A General Construction of Hard-Core Predicates for Any Quantum One-Way Function |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ハードコア述語 / hard-core predicates |
| キーワード(2)（和/英） | 量子一方向性関数 / quantum one-way functions |
| キーワード(3)（和/英） | 量子還元 / quantum reduction |
| キーワード(4)（和/英） | オラクル同定問題 / oracle identification problems |
| 第 1 著者 氏名（和/英） | 河内 亮周 / Akinori KAWACHI |
| 第 1 著者 所属（和/英） | 東京工業大学 大学院情報理工学研究科 / Graduate School for Information Science and Engineering, Tokyo Inst. of Tech. |
| 第 2 著者 氏名（和/英） | 山上 智幸 / Tomoyuki YAMAKAMI |
| 第 2 著者 所属（和/英） | Computer Science Program, Trent University |
| 発表年月日 | 2005-03-18 |
| 資料番号 | COMP2004-74 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 743 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |