B03

数理・論理・量子情報/考え方をかんがえる

Computation, Logic, Quantum information

計算量理論、暗号

Computational Complexity Theory, Cryptography

計算量理論と暗号の安全性

Computational Complexity Theory and the Security of Cryptography

代表者名

平原秀一

共同発表者名

所属分野

情報学プリンシプル研究系

Principles of Informatics Research Division

pdf-image

要旨

通信の秘密を守るために暗号技術は広く用いられていますが、実は本当に安全かどうかわかっていません。本ポスターでは100万ドルの懸賞金が懸けられている「P≠NP予想」と暗号の安全性に関して概観を与えます。

Cryptographic technologies are widely used in order to protect the security of our daily communications. However, these are not proved to be secure yet. In this poster, we provide an overview of the relationship between cryptography and “”the P versus NP problem””, which is one of the millennium prize problems.

関連動画

コメント

  1. yamasaki より:

    質問:素人で大変申し訳ないのですが、質問させてください。「現在のクレジットカード等の暗号化技術は安全かどうかわかっていない」とのことですが、今、普通にネットショッピング等で入力しているのですが、使用しない方が良いのでしょうか?

    1. 平原秀一 より:

      ご質問ありがとうございます。使用しても大丈夫です。
      より詳しく述べると「研究者たちは暗号化技術が安全だと予想しているが、その安全性が数学的に証明されていない」ということです。
      原理的には、予想に反して誰かが暗号を既に破っている可能性を否定できませんが、現状ではネットショッピング等を利用することに問題はないでしょう。

  2. Anonymous より:

    NIST SP800-90Aの疑似乱数生成器は、暗号学的擬似乱数の定義を満たしません(即ち、AES-CTRは識別可能です、詳細は開示できなくて恐縮ですが)。仮に存在証明が肯定的に解決されたとしても、擬似乱数を少なくとも古典計算機で構成出来ないのではないかと個人的には考えています。この辺りの、存在と実装の隔たりに関してご意見を頂ければと存じます。

    1. 平原秀一 より:

      ご質問ありがとうございます。
      現実に暗号や疑似乱数生成器を作る場合には、計算の効率性(つまり暗号化にかかる時間)も考慮に入れる必要があります。一般に、安全性と計算の効率性にはトレードオフがあります。現在広く使われているAESなどの暗号は、実用的にするために計算の効率性を優先した結果、ご指摘の通り安全性が犠牲になっている可能性があります。
      もし計算の効率性を無視してもよいのであれば、理論に基づくより強固な暗号を作ることができます。例えば、任意の一方向性関数から暗号学的疑似乱数生成器を構成することができます。ただし、現状の構成ではオーバーヘッドが大きく実用に耐えませんが、少しずつ効率が改善されています。ですので、究極的には効率的かつ安全な疑似乱数生成器が、確固たる理論に基づいて構築することができる可能性が高いと思われます。

      1. Anonymous より:

        ご返信ありがとうございます。
        NIST SP800-90AのCTR_DRBG, HASH_DRBG, HMAC_DRBGではダメでした。

        ∃一方向性関数 ⇔ ∃暗号学的疑似乱数生成器
        ですので、一方向性関数も仮に存在が証明できたとしても、実際に実現できるかはまた別の話しではないかと考えています。

      2. 平原秀一 より:

        確かに存在することを証明することと、実際に構成を与えることは違います。ですが、現状の証明方法はほとんどすべてが実際の構成を与えています。
        一方向性関数は疑似乱数生成器より作りやすく、例えば、(平均時計算量の意味の)素因数分解の計算困難性に基いて、Rabinの一方向性関数という構成が知られています。現状では、素因数分解を解く効率的なアルゴリズムは知られていないので、Rabinの一方向性関数から作られる疑似乱数生成器が安全である可能性が非常に高いと考えています。(すでに述べた通り、現状では非効率な構成ですが。)
        この意味で、疑似乱数生成器の存在が証明されるときには、実際には既に知られている疑似乱数生成器の構成が安全だと証明される可能性が高いと予想します。