kenmaro です。
秘密計算、特に準同型暗号のことについて記事を書いています。
秘密計算エンジニアとして得た全ての知見をまとめた記事はこちら。
https://qiita.com/kenmaro/items/74c3147ccb8c7ce7c60c
これから準同型暗号について勉強したいリサーチャー、エンジニアの方へのロードマップはこちら。
https://qiita.com/kenmaro/items/f2d4fb84833c308a4d29
今話題のゼロ知識証明について解説した記事はこちら。
https://qiita.com/kenmaro/items/d968375793fe754575fe
概要
今回は、格子暗号を用いた鍵交換のアルゴリズムについて少しまとめてみたいと思います。
LWE問題とNTRU問題をベースにした鍵交換アルゴリズムはそれぞれ、
NTRUベースの鍵交換
https://eprint.iacr.org/2013/718.pdf
LWEベースの鍵交換
https://eprint.iacr.org/2012/688.pdf
を参照しています。
NIST（アメリカ国立標準技術研究所）は、鍵交換の手法に耐量子のアルゴリズムを使うことを優先事項として取り上げています。
このLWEやNTRUベースの鍵交換手法はそれらを踏まえ、量子耐性をもった鍵交換を実装するためのプロトコル提案となっています。
実際、去年パブリッシュされたOpenSSLバージョン9.0では、鍵交換プロトコルにNTRUベースのプロトコルを公式にサポートしたことで話題になりました。
今までの楕円ディフィーヘルマン（ECDH、詳細は後述）と、新しいNTRUベースのハイブリッド形式を実装し、採用しています。
まずは鍵交換とはなんなのか、
DHとはなんなのか、
KEM（Key Encapsulating Module)とはなんなのか
をみた後に、格子ベースの鍵交換プロトコルについて簡単にまとめていければと思います。
実際の数式については論文を参照していただきたいと思っていますが、概念的なところを中心に自分で咀嚼したものを書いてみます。
鍵交換とは
鍵交換とは、TLSなどで通信を暗号化する時に使用する共通鍵方式の暗号において、
その暗号化を行うための共通鍵を、データの送信者と受信者の間で「安全に」共有するプロトコルのことです。
以前TLSについて今一度まとめてみるような記事を書きましたが、
その中で鍵交換アルゴリズムについても言及しました。
鍵交換にはDH型（Diffie Helman)と呼ばれるプロトコルが使われています。
DHを使用する数学の代数体はいくつかあります（例えば楕円暗号を使用したもの）が、
元となるDHは離散対数問題の求解困難性をもとに作られているため、量子コンピュータが台頭してきた時には簡単に（多項式時間で解かれると呼ばれますが）解かれてしまうと言われています。
従って、DH以外の量子コンピュータに耐性のあると言われている手法で鍵交換を実行しようという研究は進んでおり、
その一環として量子耐性があると言われている「格子問題」と呼ばれる数学の求解困難な問題を利用して鍵交換を行うための基盤が整備されています。
DHプロトコル
DHプロトコルは、簡単に言えば、鍵を共有したい２つのパーティがそれぞれ、
- 公開鍵と秘密鍵のペアを作成
- 公開鍵を互いに交換
- 自身の秘密鍵と受け取った公開鍵を使って共有鍵を生成
すると、最後の共有鍵を「オフラインで」共有できるというプロトコルです。
ここで、「オフラインで」と書いた意味は、前もって公開鍵を共有さえしておけばどのタイミングでも共有鍵を各パーティが生成可能ということです。
図はいろいろとわかりやすいものがありますが、一つ参照しておきます。
KEM プロトコル
鍵交換を行うプロトコルには、他にもKEM（Ken Encapsulating Mechanism) を使用することができます。
例えばRSAタイプのKEMを用いると、
- Aが乱数をRSAで、Bの公開鍵を使い暗号化してBに送信
- Aは乱数をもとにKDF（Key Defined Function) を使って鍵を生成
- Bは自身の秘密鍵を使い復号して乱数を得る
- Bは乱数をもとにKDFを使って鍵を生成
- AとBは鍵を共有
となります。
もしくは、今回の論文 https://eprint.iacr.org/2012/688.pdf
の1.1 DH Protocol vs Encryption で書かれているように、
- Aが乱数を生成、暗号化してBに送信
- Bが乱数を生成、暗号化してAに送信
- A,Bはそれぞれ秘密鍵で復号し、乱数を取得
- お互いの乱数を組み合わせて鍵を生成
というプロトコルを組むこともできます。
プロトコルの詳細は
こちらがわかりやすかったです。
既存のDHプロトコルには、
- Elliptic curve-based DH
- Recurrence equations-based DH
- XTRDH
と呼ばれるものがあります。
格子問題を利用した鍵共有プロトコルのマッピング
- DL問題（Descrete Log 離散対数問題）
- 楕円上の離散対数問題
- 格子問題（SVPやCVP問題）
を利用した
- 公開鍵暗号プロトコル
- デジタル署名プロトコル
- 鍵交換プロトコル
のマッピングは以下のテーブルをみると非常にわかりやすいです。
この？の箇所を今回NTRUベースの鍵交換として論文はプロトコルを提案しています。
LWE問題とNTRU問題
LWE問題とNTRU問題は格子を利用した求解困難問題として有名なものですが、どちらを使っても鍵交換が行えるようなアルゴリズムは研究されています。
NTRU問題を利用した暗号プロトコル
DHプロトコルが２フローによる鍵交換であるのに対し、NTRU方式では３フローとなっていますが、
これが現状提案するプロトコルだと論文では説明しています。
フロー自体は論文の図が一番わかりやすいですが、大事なのは
Aが生成したf_i と、Bが生成したf_j の掛け算したものを、最終的に両者が f_i * f_j として共有できているところです。
このf_i, f_j はNTRU格子の要素であり、多項式になります。
例えば多項式の次数が1024だった場合、一回のプロトコルで1024ビット長の鍵を共有できます。
論文第５章では、NTRUベースの鍵交換のメリットとデメリットが議論されています。
NTRUベース鍵交換のメリット
NTRUを用いた鍵交換のメリットについては、以下のように述べられています。
- ECDHより高速
- ECDHより軽量
- ECDHでは楕円パラメータの選定が難しいが、NTRU問題ではパラメータの選定が簡単
- 多項式乗算はハードウェアとの相性が良い
- コンピュータの並列計算に対してNTRUの方が耐性がある、理由は、格子問題を解く時のLLLと呼ばれるアルゴリズムが直列的な実装しかできないため、一方でDL問題は並列で計算可能
- 量子耐性がある。DL問題に対してはShorアルゴリズムで対応されてしまう
NTRUベース鍵交換のデメリット
加えて、デメリットは以下の通りです。
- フローの回数が１回多い
- 秘密鍵の大きさはECDHより大きいので、スペースを取ること
- 確率的に鍵のミスマッチが起こる可能性がある（格子問題特有であるが、適切なパラメータ選定で限りなくこの確率を小さくすることは可能）
LWE問題を利用した暗号プロトコル
LWE問題は、NTRU問題と同様に格子をベースにした求解困難な問題であり、
数学的にはLWE問題もSVP（最短ベクトル問題）に帰着することが知られています。
このLWE問題をベースにした暗号を用いて、NTRUのときと同様に格子ベースで鍵交換プロトコルを構成することが可能です。
NTRUを利用したプロトコルと同様に、３フローによる構成になります。
格子問題が異なるだけで、ほとんどフローはNTRUの時と同じです。
LWEを用いれば１ビットを一回のプロトコルで共有することができますし、
RingLWEを用いれば多項式の長さ分の（例えば 1024ビット等）を一回のプロトコル実行により共有可能になります。
最後に
アルゴリズムのところは論文に丸投げになってしまいましたが、
LWE問題やNTRU問題を知っていれば構成はとても単純だということが理解できるかと思います。
実際、今回紹介したNTRUを用いた鍵交換プロトコルは、
OpenSSLバージョン9.0（2022年8月から）で実装されています。
今の所既存のECDHとハイブリッドという形での実装ですが、もう実運用されているということは驚きですね。
これから格子ベースの暗号ももっと使われていくと思いますし、NISTの耐量子暗号の標準化が済んだ後には、
格子を使った公開鍵暗号方式や、電子署名など、他のプロトコルにももっと格子暗号の名前を見る日もきそうですね。
これからもキャッチアップしていきましょう。
今回はこの辺で。