講演抄録/キーワード |
講演名 |
2014-03-10 09:45
バイアス付きオラクルに対する量子アドバイスを用いたアルゴリズム ○河内亮周(東工大) COMP2013-61 |
抄録 |
(和) |
バイアス付きオラクルは元々量子版Goldreich-Levinの定理の証明における
量子帰着のために提案されたが,量子オラクル計算の文脈でもいくつか研究が
なされている.本稿では量子アドバイス状態を用いて
Beaudrap-Cleve-Watrousのアルゴリズムのバイアス付きオラクル版を提案し,
その解析を与える.またその応用としてある特殊な量子一方向性関数に
対するハードコア述語の一般的構成およびその量子帰着による安全性を与えるが,
この構成の古典一方向性関数に対する安全性はある特殊な古典一方向性置換の
存在性仮定の下で古典帰着では不可能であることも証明する. |
(英) |
The biased oracles, which were
originally motivated from cryptographic
quantum reductions for the quantum Goldreich-Levin theorem,
have been investigated in the contexts of the
quantum oracle computation.
In this note, we propose the biased-oracle version
of the Beaudrap-Cleve-Watrous algorithm using
the quantum advice state. As an application
of the biased-oracle algorithm,
we give a general construction of hardcore predicates
for some special quantum one-way function, of
which security for classical one-way functions
cannot be proved by classical cryptographic reductions
under the assumption that some special classical
one-way permutation exists. |
キーワード |
(和) |
オラクル計算 / バイアス付きオラクル / 量子帰着 / / / / / |
(英) |
oracle computation / biased oracles / quantum reductions / / / / / |
文献情報 |
信学技報, vol. 113, no. 488, COMP2013-61, pp. 9-15, 2014年3月. |
資料番号 |
COMP2013-61 |
発行日 |
2014-03-03 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-61 |