量子絡み合い状態を利用した秘匿計算プロトコル
著者名(日)
三原 孝志
雑誌名
工業技術 : 東洋大学工業技術研究所報告
号
31
ページ
57-61
発行年
2009
URL
http://id.nii.ac.jp/1060/00002038/
Creative Commons : 表示 - 非営利 - 改変禁止三原孝志＊
1．はじめに
量子的な計算方法の発想はJ1982年，物理学者
Feynmanの問から生まれたと考えられる．彼は「現在 のディジタルコンピュータは物理現象を効率的に模倣 することができるか？」という疑問を投げかけ，量子状 態の力を借りなければ効率的に模倣することができな いのではないかと推測した1）．量子コンピュー．一タの誕生 である．しかし，Feynmanは量子コンピュータを数学 的に定式化するには至らなかった．その後，1985年に Deutschは量子コンピュータを量子チューリング機械 という形でモデル化した2）．彼もまた物理学者であり， このモデルも数学的に納得できるほど定式化されたも のではなかった．数年後，BernsteinとVazirani，が最初 にDeutschの量子チューリング機械を数学的に詳細に 定義しなおした3）． さらに，量子コンピュータ上で実行される量子アルゴ リズムも多数提案されている．代表的なアルゴリズムと しては，Shorの量子素因数分解アルゴリズム4）とGrover の量子探索アルゴリズム5）が挙げられる．一方，量子情報セキュリティの歴史は，1984年の
BennettとBrassardの論文に始まる6）．彼らの量子暗 号プロトコルは秘密鍵配送方式の一種であり，無条件に 安全なプロトコルであることが証明されている．彼らの プロトコルは量子状態の受け渡しをする方式であるが， 量子絡み合い状態を利用し，古典情報の受け渡しのみを 行う量子暗号も提案されている7・8）． 本論文では，マルチパーティによる量子秘匿計算につ いて述べる．秘匿計算とは，複数のパーティが，各自自 分が所有する情報（数値）を開示せずに四則演算等の演 算を行い，計算結果を得る計算を意味する．古典的なマ ルチパーティプロトコルはYaoの論文に始まると考え られる9）．一方，量子的な秘匿計算は，文献10）により， 入出力が量子状態の場合，無条件に安全な量子プロトコ ルが提案されている．本論文では，入出力を古典情報と し，プロトコルの途中の計算に量子状態を用い，無条件 に安全な量子プロトコルを示す．また，量子状態として 絡み合い状態を許している．同様の結果は文献11）によ り示されているが，本論文では，より簡潔なプロトコル に改良し，さらに一部拡張を加えている． 次に，本論文で示すプロトコルを構成する上での条件 を述べる．本論文で用いる通信路に関しては公共通信路 を仮定する．公共通信路とは，情報を見られても構わな いが改ざんを許さない通信路を意味する．外部の攻撃者 （盗聴者）に対しては無限の計算能力を仮定するが，内 部のプロトコル参加者はプロトコルを逸脱しないとす る．文献10）ではプロトコルの逸脱者の割合も考慮され， この点が本結果と異なる点である．また，EPRペアと 呼ばれる絡み合い状畦（1・・）・1・・〉）が安全にパーティ 間で共有できると仮定する．この形の絡み合い状態は文 献12）により安全に共有できることが示されている． 最後に，本論文の構成を述べる．第2章では，本論文 で用いられる数学記法，量子演算にっいて概説する．第 3章では，量子加算，乗算，排他的論理和の秘匿計算プ ロトコルを示す．最後に，第4章で全体のまとめを述べ る．2．準備
まず，本論文で用いる記法を述べる，整数の集合をZ， Bニ｛O，1｝とする．a，b∈Zに対し，法nに対しaとbが合同 であることをa≡b（mod n）で表す． c， d∈脇n，すなわち， c，dをnビット列としたとき，内積をc・d，排他的論理和 をc㊥dで表す． 次に，量子計算で用いられる記法を述べる．1量子ビ ット（qubit）を10＞＝（10）T， 11＞＝（01）Tで表す．ここで， ATは行列Aの転置行列を意味する．本論文では，計算基 底，観測基底共に｛10＞，11＞｝とする．一般の量子ビットは， 1ψ〉＝Ci 10＞＋c211＞のように重ね合わせ状態として表現 できる．ここで，c1， c2は複素数であり，lc，12＋lc212＝1を 満たす．n量子ビットの基底は，演算子⑭をテンソル積 としたとき，lb，）⑧lb2＞⑧…⑧lbn）＝lb、，b2，＿，bn＞（bi∈ B，i∈｛1，2，＿，n｝）で表される． 一般のN進数の場合も同様の表現を用いる．すなわち， lx＞（x∈｛0，1，＿，N｝））を基底とし， n個の基底状態の場合， それらのテンソル積で表す．また，表現を簡略化するた め，n個のIX＞のテンソル積をIX， X，．．．，X＞＝lxn＞と略記する， また，ある量子状態1ψ〉が1ψ1＞⑧1ψ2＞のように分解できない状態のとき，その状態を絡み合った状態
（entangled state）と呼ぶ． では，量子計算とはどのような計算か？ 量子計算は 初期状態を1ψs＞，最終状態を1ψt＞としたとき， 1ψt＞＝Ulψs＞ により実行される．ここで，Uはユニタリ行列であり， 量子計算は，ある（初期）量子状態にユニタリ行列を作 用させることにより実行され，悼t＞を計算結果とみなす． このとき，1ψt＞＝Σ㌫；c，lx＞とすると， xを得る確率が lCxl2となる．また上記の計算を，量子絡み合い状態を利用した秘匿計算プロトコル u lψ，〉→1ψt＞ と表現する場合もある． 次に，量子計算で用いられる演算子（ユニタリ行列） を述べる．まず，1量子ビットの演算を実行する基本ユ ニタリ行列を挙げる．演算子 ・・（1 00 −1） は，ZlO＞＝IO＞，Zil＞＝ −11＞と計算され，量子ビットが1 のときのみ位相を反転させる．より一般的な位相演算子 として， ・（・）・（；，9，） が用いられる．アダマール演算子
H・芸（LD
1 1は，HlO＞＝7il（10＞＋11＞），Hl1＞＝吉（IO＞−11＞）となり，重 ね合わせ状態を生成する演算子である． さらに，N進の場合の演算子として，まず，量子フー リエ変換（QFT）が挙げられる． N−1 Q・Tl・〉一吉Σ卿川1・＞ y＝O また，位相演算子としては， SE（θ）lx＞＝ ei”eXlx＞ がS（θ）から構成できる11）．3．量子秘匿計算
3．1 量子秘匿加算プロトコル
本節では，秘匿加算計算のための量子マルチパーティ プロトコルを示す．文献11）において，最下位ビットか ら最上位ビットまで順次計算することにより秘匿加算 を行う量子プロトコルを示した．本論文では，まず，す べてのビットを一度に計算する量子プロトコルに改良 する． ［加算問題］ P＝｛P1， P2，＿，Pm｝をmパーティの集合とし，各パー ティPiは整数ni∈Z（i∈｛1，2，．．”m｝）を持っているとする． このとき，パーティQは加算値s＝Σ巴、niを得ることを目 標とする．ただし，パーティPiは自分が所有する値niを 一切他人に知られないようにする． 減算計算も同様のプロトコルで実行できることを意味 する， ［量子加算プロトコル1］ （1）P1は下記の量子状態を作成する． N−1 吉Σ，・＞ X＝O （2）i＝1からmまで順番に下記の処理を実行する． （i） 各Piは乱数riを選び， SE（2ni／N＋ri）を作用 させる． （ii） 量子状態をPi＋、に送る（PmはQに送る）． （3）Qは乱数rm＋1を選び， SE（rm＋1）を作用させる．状態 は， N−1吉Σ・》嘔叫＞
x＝0 N−1一去Σ・竿剛㌍・㌔＞
x＝O となる． （4）QはPlに量子状態を送る． （5）i＝1からmまで順番に下記の処理を実行する． （i） 各PiはSE（−ri）を作用させる． （ii） 量子状態をPi＋1に送る（P．はQに送る）． （6）QはSE（−rm．1）を作用させる．状態は， N−1去Σ・雫ω
X；O となる． （7）Qは量子フーリエ変換を実行する． N−1吉Σ・竿1・＞
X＝O N−1N−1 Q9《ΣΣ・『込1・）−1−・（m・dN）） y＝Ox＝O （8）Qは結果を観測することにより一s，すなわち，加 算値sを得る． 明らかに，本プロトコルではniを一切他人に知られる ことはない．なぜなら，情報（量子状態）のやり取りが行 われても，乱数riのため， niを知ることはできないから である． ここで，パーティはs＜NなるNを知っていると仮定す る．また，niが負の数の場合， Nの補数を採ることによ り，加算計算を行わせることができる．このことは逆に， 次に，量子絡み合い状態を用いた秘匿加算プロトコル を示す． 東洋大学工業技術研究所報告［量子加算プロトコル2］ （1）Pl， P2，＿，Pm，Qは下記の絡み合い状態を共有して いるとする．ここで，Piは第i番目の量子状態， Qは 最後の量子状態を持っているとする． N−1 去Σ1・m＋・＞ X＝O （2）各PiはSE（2ni／N）をi番目の量子状態に作用させる． N−1
吉Σ戸鵬酬卿・＞
x＝O N−1・吉Σ・一〔・＞
X＝O （3）各PiおよびQは各自所有する状態に対し量子フー リエ変換を実行する． N−1去Σ｝陪…＞
X＝0 QFT 1 −一ｨ一
NXi〈i、、Σ1・r・・…’・m＋・＞ s＋Σ巴主1yl三〇（mod N） （4）各PiおよびQは各自所有する量子状態を観測し，そ の結果（y、）をQに送る． （5）Qはs＋Σ巴tly1≡0（modN）からs（加算値）を得る． 明らかに，本プロトコルでもniを一切他人に知られる ことはない．なぜなら，情報のやり取りが行われ漏れる 可能性があるのはステップ（4）のみであるが，ステップ （4）の値を知られても，加算値sを得ることはできないか らである．3．2 量子秘匿乗算プロトコル
本節では，秘匿乗算計算のための量子マルチパーティ プロトコルを示す．文献11）において，加算と同様，最 下位ビットから最k位ビットまで順次計算することに より秘匿乗算を行う量子プロトコルを示した．本論文で は，すべてのビットを一度に計算する量子プロトコルに 改良する．さらに，3パーティ以上の場合の計算時間が 指数時間かかる問題も解決する． ［乗算問題］ P＝｛Pl， P2，＿，Pm｝をmパーティの集合とし，各パー ティPiは整数ni∈Z（i∈｛1，2，＿，m｝）を持っているとする． このとき，パーティQは乗算値t＝n巴1n」を得ることを目 標とする．ただし，パーティPiは自分が所有する値niを 一切他人に知られないようにする． ここで，加算と同様，パーティはt＜NなるNを知っ ていると仮定する． まず，2パーティ間の乗算プロトコルを示し，そのプ ロトコルをサブルーチンとして用い，一般のマルチパー ティ間の乗算プロトコルに拡張する． 基本的なアイデアは，n、ニΣ｝≒1 bi2i（b、∈脇｝）と2進 数で表現したとき， ・・×・・＝Σ・・2i 1∈Sl となることを用いる．ここで，S1＝｛i lb，＝1（i∈ ｛1，2，＿，n｝）｝であり， biが1のときのみ，2iをn2に掛けれ ばよいことがわかる． ［2パーティ間量子乗算プロトコル］ （1）Pl， P2，Qは下記の量子状態を共有しているとする． N−1吉Σ医綱
x＝0 ここで，P1は最初の量子状態， P2は第2量子状態， Qは第3，4量子状態を持っているとする． （2）Qは乱数rQを選び， SE（2rQ）を最後の量子状態に作 用させる．このとき，状態は， N−11ψ〉・吉Σ͡1・綱
x＝0 となる．Qは最後の量子状態をPlに送る． （3）Plは乱数rp、を選び， SE（2rp、）を最後の量子状態に 作用させる． 1，pL（；）〉＝S，（2・，、）1ψ〉 また，ダミー状態として1tpL（i）〉を準備する． （4）i＝OからL−1まで順番に下記の処理を実行する． （i） （ii） 1 21 N i lψ；（2）〉＝SE（2・，、、）1・1・12）〉 を実行し，1ψ1（1）〉，1ψ1②〉をPlに送る ・ Pl ｝ま SE（−2rp，） ， Plはb1＝1ならば，1ψl i）〉＝ltplSi？〉， 1ψ12））＝1ψ；8？〉，biニ0ならば， 1ψli）〉＝1ψ巴？），1ψ12）〉＝1ψ1聾）とし， 1ψli）川ψ！2）〉をP2に送る（正確にはそれら の最後の量子状態であるが，以後の説明 では省略する）． P2は乱数rp、iを選び， 1ψ！…〉．・，（2（rp＋里））1ψ…〉 （5）QはSE（−2rQ） P2‘ま SE（−2Σ旨rp、i）を各自の量子状態に作用させる と，状態は下記となる． N−1去Σ拠酬繊・＞
X＝O量子絡み合い状態を利用した秘匿計算プロトコル N−1
