<a href="http://h2np.net/docs/crypto-2006.html">CRYPTO2006 カンファレンスレポート</a>について

高木浩光＠自宅の日記 - 公開鍵暗号方式の誤り解説の氾濫をそろそろどげんかせんとを見て.
そういえばすずきひろのぶさんの記事についてメモを書いてあったので公開します. 格子暗号についての間違いの指摘です. (当方, 格子暗号を専門にしているので.) Oded RegevのサイトにCRYPTO 2006で使われた発表資料が置いてあるのでそれを見ると良く分かると思います.

2006レポートより引用

今年の招待講演は次の2つです。

Lattice-Based Cryptography Oded Regev (Tel Aviv University, Israel)

Cryptograhic Protocols for Electronic Voting David Wagner (UC Berkeley,USA)

Lattice-Based Cryptographyは、最も短いベクトルを見つける問題、the shortest vector problem (SVP)などに基づく計算量的に安全な公開鍵暗号アルゴリズム群です。計算量的には現在知られている解き方では指数時間が必要な難しい(difficult)と考えられていますがNP困難(NP-hard)ではないと考えられています。さて、公開鍵暗号として有名なRSAは量子コンピュータができると2のO(n log log n/log n)乗という計算量で解けてしまいます。ですが、情報理論的に難しい問題は量子コンピュータを使っても難しい問題なので、よって、Lattice-Basedの暗号は安全です。Oded Regevもそのあたりを強調していました。理論的にはおもしろいと思う人はいるかも知れません(筆者はその面白さがわかりませんけれども)。そもそも筆者の回りでも、あまり興味を持つ人がいないので、その意味ではLattice-Based Cryptographyを俯瞰する形で話を聞くことは滅多にないので、よかったはよかったかな、と思いました。ただし量子コンピュータができた時の保険という意味で有用性があるかどうかは疑問です。なぜならば、量子コンピュータを前提とした暗号アルゴリズムが既に提案されていたりするからです。

指摘

指摘1

計算量的には現在知られている解き方では指数時間が必要な難しい(difficult)と考えられていますがNP困難(NP-hard)ではないと考えられています。

SVPは近似度を小さくすると (任意の定数やほぼnで) l_2ノルムでランダム帰着のもとNP困難です. 暗号に使われているのはSVPの近似度が O(n log^c n) から O(n^{1.5} log^c n) のものです. Aharonov and Regevにより, 近似度が O(n^{0.5}) のSVPはNPかつco-NPです. 従って, 暗号にの基盤として用いられるようなSVP (SVP_γ, γ=poly(n)) はNP困難ではなさそうというのが正確な説明です.
Regevの資料を見るとその辺りには気を使っているようです. γ-approximate SVP for γ=poly(n)を対象として考えていて, この場合はGoldreich and Goldwasser 2000やAharonov and Regev 2004の結果よりNP-hardではなさそうという説明です. また小さい字ですけど, NP-hard for subpolynomial γ [Khot 04]と書かれています.

指摘2

さて、公開鍵暗号として有名なRSAは量子コンピュータができると2のO(n log log n/log n)乗という計算量で解けてしまいます。

量子コンピュータができなくてもその辺りのオーダーで解けます. GNFS (一般数体篩法) でn-bit数に対してO(exp(cn^{1/3} (ln n)^{3/2})) = 2^{O(n^{1/3} (log n)^{2/3})}です. 量子を使わなくても2のO(n log log n/log n)乗で解けます.

指摘3

ですが、情報理論的に難しい問題は量子コンピュータを使っても難しい問題なので、よって、Lattice-Basedの暗号は安全です。Oded Regevもそのあたりを強調していました。

先ほどご自分で「Lattice-Based Cryptographyは、最も短いベクトルを見つける問題、the shortest vector problem (SVP)などに基づく計算量的に安全な公開鍵暗号アルゴリズム群です。」と書かれていますよね. 実際, 総当りで解けるので情報理論的に安全ではありません.

指摘4

ただし量子コンピュータができた時の保険という意味で有用性があるかどうかは疑問です。なぜならば、量子コンピュータを前提とした暗号アルゴリズムが既に提案されていたりするからです。

量子コンピュータを前提とした暗号アルゴリズムというのはOTU暗号 (CRYPTO 2000) のことでしょうか? だとすると良く分からない説明です. OTUはナップサック系の暗号であり, これらは適切な問題を設定して安全性の帰着を行っていません.
有用性というか実用性が無いと言うならば, 狭義の格子暗号は一般に効率が悪いので同意です.
あと, Regev05暗号は, ある意味では量子コンピュータを前提としています. あれは暗号文が0のものか1のものか見分けられれば, 量子コンピュータが存在するなら任意のSVP_{O(n^{1.5} log^c n)}が解けるということを示しているからです.