量子一方向性置換の計算量理論的特徴付け
スポンサーリンク
概要
- 論文の詳細を見る
この論文では量子一方向性置換の計算の複雑さのクラスによる特徴付けという観点から量子一方向性関数の存在について議論する.GrollmannとSelman[GS88]の技法をもとにHomanとThakurはP≠UP∩coUPと一方向性置換の存在の等価性を示し[HT03],Kashefi,Nishimura,Vedralは逆方向の計算に量子計算を許した場合の一方向性関数(c-q量子一方向性関数)の特徴付けとしてEQP⊉UPとc-q量子一方向性関数の存在の等価性を示した[KNV02].本論文では,まず初めにこの結果を拡張して,EQP⊉UP∩coUPとc-q量子一方向性置換の存在の等価性を証明する.二つ目の結果としてUPの量子版UQPを定義することによって,逆方向の計算に加え順方向の計算にも量子計算を許すような量子一方向性置換(q-q量子一方向性置換)においてもEQP≠UQP∩coUQPとq-q量子一方向性置換の存在が等価であることを証明する.
- 社団法人電子情報通信学会の論文
- 2008-04-11
著者
関連論文
- 量子公開鍵暗号の安全性概念(量子情報処理論文)
- 共通鍵ブロック暗号SC2000の乱数性
- 文字列(1,2)-紛失通信からRabin型紛失通信への直接帰着
- 量子一方向性置換の計算量理論的特徴付け
- 離散対数問題にもとづく高速擬似乱数生成
- ユニバーサルな一方向無近傍ハッシュ関数について
- ユニバーサルな一方向無近傍ハッシュ関数について
- ユニバーサルな一方向無近傍ハッシュ関数について
- 逆像サイズ近似可能な量子一方向性関数からの統計的秘匿量子ビット委託方式の構成
- DS-1-9 分散既知な分布の最小・最大エントロピーと平均エントロピーの関係(DS-1. COMP学生シンポジウム,シンポジウムセッション)
- セキュリティネットワークを支える物理乱数生成技術[II] : 物理乱数生成の理論的側面