お知らせ 研究会の開催と会場に参加される皆様へのお願い(2022年6月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2005-03-18 09:25
任意の量子一方向性関数に対するハードコア述語の一般的構成法
河内亮周東工大)・山上智幸Trent大
抄録 (和) 本論文で我々は任意の量子一方向性関数に対するハードコア述語の一般的構成法を示す.我々のその構成方法は与えられた量子アルゴリズムの設計方法の基礎となる枠組に基づいており,その枠組は与えられた誤りなしオラクルを同定する量子アルゴリズムの典型的設計手法となっている.
また一方でハードコア述語のための安全性帰着は誤りありオラクルが与えられた場合にその同定問題を解くことに相当しており,我々はそのアルゴリズムの枠組がそのような誤りありオラクルに対しても頑健に動作することを証明することで,その枠組がハードコア述語の安全性帰着に利用できることを示す.
従って,その枠組の上で効率良く解けるオラクル同定問題から,任意の量子一方向性関数に対するハードコア述語を構成でき,Goldreich-Levinの定理を包含するようなハードコア述語の広いクラスを与えることができる.
この我々の構成方法の具体的応用として,任意の量子一方向性関数に対する以下の二つの新しいハードコア述語を得た.
一つ目の述語$\QNR_x(r)$は,ある適当な素数$p$に対して$x+r\mod p$が平方剰余でなければ$\QNR_x(r) = 1$,平方剰余であれば$0$と定義される.二つ目の述語$\XOREQ_x(r)$は,もし$x_ix_{i+1} = r_ir_{i+1}$ならば$\EQ(x_ix_{i+1}, r_ir_{i+1}) = 1$,そうでなければ$0$としたときに$\XOREQ_x(r) = \bigoplus_{i=1}^{n/2}\EQ(x_ix_{i+1}, r_ir_{i+1})$で定義される.
これらは古典計算において任意の一方向性関数に対するハードコア述語であるかどうか知られていない. 
(英) 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 {\em perfect\/} oracle.
On the other hand, we can regard a security reduction for a hard-core predicate as the identification problem with an {\em 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 $\XOREQ_x(r)$ is defined as $\XOREQ_x(r) = \bigoplus_{i=1}^{n/2}\EQ(x_ix_{i+1}, r_ir_{i+1})$, where $\EQ(x_ix_{i+1}, r_ir_{i+1}) = 1$ if $x_ix_{i+1} = r_ir_{i+1}$ and $0$ otherwise.
It is not known whether these are hard-core predicates or not in the classical computation.
キーワード (和) ハードコア述語 / 量子一方向性関数 / 量子還元 / オラクル同定問題 / / / /  
(英) hard-core predicates / quantum one-way functions / quantum reduction / oracle identification problems / / / /  
文献情報 信学技報, vol. 104, no. 743, COMP2004-74, pp. 9-16, 2005年3月.
資料番号 COMP2004-74 
発行日 2005-03-11 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
PDFダウンロード

研究会情報
研究会 COMP  
開催期間 2005-03-18 - 2005-03-18 
開催地(和) 東京工業大学 
開催地(英) Tokyo Institute of Technology 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2005-03-COMP 
本文の言語 英語(日本語タイトルあり) 
タイトル(和) 任意の量子一方向性関数に対するハードコア述語の一般的構成法 
サブタイトル(和)  
タイトル(英) 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  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 河内 亮周 / Akinori Kawachi / カワチ アキノリ
第1著者 所属(和/英) 東京工業大学 (略称: 東工大)
Tokyo Institute of Technology (略称: Tokyo Inst. Tech.)
第2著者 氏名(和/英/ヨミ) 山上 智幸 / Tomoyuki Yamakami /
第2著者 所属(和/英) Trent大学 (略称: Trent大)
Trent University (略称: Trent Univ.)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2005-03-18 09:25:00 
発表時間 25 
申込先研究会 COMP 
資料番号 IEICE-COMP2004-74 
巻番号(vol) IEICE-104 
号番号(no) no.743 
ページ範囲 pp.9-16 
ページ数 IEICE-8 
発行日 IEICE-COMP-2005-03-11 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会