パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

量子コンピュータへの道:2ビットの論理演算に成功」記事へのコメント

  • by Anonymous Coward on 2003年10月31日 10時38分 (#424403)
    ( CRYPTO2000レポートより抜粋 [iij4u.or.jp] )

    その中で今年の目玉は、この量子公開暗号の発表だったといえるでしょう。

    Quantum public-key cryptosystems
    岡本龍明, 田中圭介、内山成憲
    NTT 研究所

    量子物理学の技術を応用した、量子コンピュータという計算機のモデルがあります。1つの量子が複数の状態を持つことを利用して同時にいくつもの状態をつくり出そうというものです。現在のコンピュータの持つ0,1の値を持つビットに対応するのが、量子コンピュータではキュービットです。このキュービットが0,1の値を取るとして、このキュービットが10個あれば2^10の状態を同時に持つことができます。一方、同じことをビットで行おうとすると2^10回の計算を行う必要があります。簡単なモデルにして比較すると、キュービットが20 個あれば2^20倍の速度、30個あれば2^30倍、1024個あると2^1024倍も現在のコンピュータより速く計算できます。ただし実用にはまだ30年や50年はかかるでしょう。

    もうちょっと詳しくモデルを解説しましょう。ちょっとコンピュータ科学をかじった人なら、私達の現在使っているコンピュータはチューリングマシン(TM : Turing Machine)と呼ばれる計算モデルであるということは知っていると思います。チューリングマシンは無限の長さを持つテープが一本あって、それを読むヘッドがあります。量子コンピュータでチューリングマシンは、量子チューリングマシン(QTM : Quantum Turing Machines)といい、キュービットが1つ増えると、並列にTMがもう1つ出来ると考えます。 現在の主流となっている公開鍵暗号の安全性は、RSA方式のように素因数分解を行うのが難しい、あるいはElGamal方式のように離散対数問題を解くのが難しいといったことを拠り所としています。しかし、1997年にQTMを用いれば簡単に問題が解けてしまうということがShorによって示されました。もちろん現在は実用的な量子コンピュータは存在しませんが、将来、実用的な量子コンピュータが現われた時点で、現在の公開鍵暗号は崩壊します。そこで、現在の公開鍵暗号に代わる新しい暗号が必要になります。

    既に「量子暗号」というアイデアがありますが、これは一本の光ファイバ上で盗聴されているかどうかを検知するというもののためインターネットのように色々なネットワークを経由するようなものでは使えません。また、この量子暗号は「守る」ということではなく「盗まれたことを検知する」という方法なので、もし、通信路を流れるデータがすべて盗聴されている場合には、この通信路は使えないということがわかるだけで、それ以上のことは出来ません。

    量子公開鍵暗号

    この量子公開鍵暗号( QPKC : Quantum Public Key Cryptosystem )は、防御側が公開鍵暗号の「鍵のパラメータ」を作るために量子コンピュータを利用します。さて、今回提案された岡本・田中・内田(OTU : Okamoto-Tanaka-Uchida ) のQPKCは「TMでも解くのが困難な問題はQTMでも解くのが困難だろう」という仮定をおいています。専門的な言い回しをすると「QTMでもprobabilistic polynomial time algorithでNP-complete problemを解こうとすることはhard、あるいはNPはBQPに含まれないと推論される」となります。これは理論的な証明されていませんが、多くの研究者が、たぶんそうだろうと考えています。

    そこでNP完全問題(NP-complete problem)を利用するような公開鍵暗号方式を使えば、量子コンピュータが存在していても安全だろうということです。NP完全問題といえば、巡回セールスマン問題やナップサック問題などがよく解説されますが、かつて、公開鍵暗号の方式としてナップサック問題を応用したナップサック暗号というのがありました。この方式は1970年代後半から80年代前半に流行った方式ですが、1982年にAdi Shamirがそれまで提案されていたナップサック暗号は安全ではない(多項式時間内に解ける)ということを証明しました。

    理論上は離散対数問題を解いて公開鍵と秘密鍵で利用する鍵パラメータを作るという方法がありますが、これは通常のコンピュータでは非現実的な方法です。なぜなら離散対数問題を解くということ自体が今のコンピュータでは極端に大変なのです。ですから離散対数問題を使った公開鍵暗号方式が成立しているのです。このようなわけでナップサック暗号は、はるか過去の話になっていました。若い暗号研究者などは名前は聞いたことがあっても、アルゴリズム自体は知らないというのもざらです。ナップサック暗号の解説書も滅多に見かけることもなく、筆者の知っている範囲でナップサック暗号を初学者向けに解説している本はアルトサロマーの「公開鍵暗号系(東京電機大学出版局 1992)」ぐらいしか知りません。

    さて、これですべての要素が1つの線で結ばれました。

    • 量子コンピュータは離散対数問題を簡単に解く
    • ナップサック暗号はNP完全問題をベースにしている
    • ナップサック暗号の鍵パラメータを離散対数問題を解いて作る
    • NP完全問題は量子コンピュータでも難しい

    つまり、量子コンピュータでナップサック暗号のための公開鍵と秘密鍵に使うパラメータを作れば、そのナップサック暗号は量子コンピュータでも解読できないということです。しかも、ナップサック暗号自体の処理は今のコンピュータで極めて高速に行えます。 (あと省略)

    すずきひろのぶ

開いた括弧は必ず閉じる -- あるプログラマー

処理中...