Ring-LWEとModule格子

標準LWEでは大規模な行列とベクトルの積が必要となるため、鍵サイズが大きくなります。Lyubashevsky、Peikert、Regevによって2010年に導入されたRing-LWEでは、ベクトルと行列を、環R_q = Z_q[X]/(f(X))内の多項式に置き換えます。この構造化された設定により、鍵を大幅に小型化し、算術演算を高速化できるため、Ring-LWEは実世界の格子暗号における実用的な基盤となっています。

Ring-LWEで使用される多項式f(X)は、通常f(X) = X^n + 1です。ここでnは2のべき乗です。これは2n次の円分多項式です。これが選ばれるのは、Z上で既約であり、環R_qに優れた代数的性質をもたらし、効率的な乗算のための数論変換（NTT）を可能にするためです。円分環は長年にわたって深く研究されており、安全だと考えられています。

Ring-LWEでは、秘密鍵sはR_q内の多項式であり、サンプルは（a, b = a*s + e）の形を取ります。ここでaは環から一様ランダムに選ばれた要素で、eは小さな誤差多項式です。攻撃者にはこのようなサンプルが多数与えられ、sを復元するか、一様ランダムなサンプルと見分けることが求められます。その困難性はRing-LWE仮定に依存しており、これはイデアル格子上の最悪時問題からの帰着を持ちます。

Ring-LWEは攻撃者にとってより困難ですが、通常のLWEとは少し異なる安全性の帰着を伴います。この帰着は任意の格子ではなく、イデアル格子上の最悪時問題（ideal-SVP）からのものです。イデアル格子が持つ追加構造によって、原理的には一般の格子よりも解きやすくなる可能性があり、これは現在も活発に研究されている分野です。この構造を悪用する実用的な攻撃は、現在知られていません。

Module-LWE（M-LWE）は、単一の環要素や整数の大規模行列ではなく、環要素からなるk x k行列を扱うことで、LWEとRing-LWEの両方を一般化します。k = 1の場合はRing-LWEに帰着し、kが大きくなるにつれて標準LWEに近づきます。この調整可能なパラメータkによって、安全性への信頼と性能のバランスを取ることができます。

CRYSTALS-Kyber（現在はML-KEM、FIPS 203）は、R_q上のランクkの行列を用いるModule-LWEに基づいています。パラメータkは安全性レベルを直接制御します。k=2は128ビット安全性（ML-KEM-512）、k=3は192ビット（ML-KEM-768）、k=4は256ビット（ML-KEM-1024）を目標とします。モジュール構造により、kを変更するだけで安全性を調整できる単一のコードベースを実現できます。

R_q = Z_q[X]/(X^n + 1)における多項式乗算は、性能上のボトルネックです。数論変換（NTT）はZ_q上の離散フーリエ変換であり、多項式を評価形式に変換します。この形式では、乗算が要素ごとの乗算になります。NTTを適用できるようにqを選ぶと、多項式乗算の計算量はO(n^2)からO(n log n)に削減されます。これはML-KEMとML-DSAにおける重要な最適化です。

NTTでは、qが q = 1 mod 2n を満たす素数であり、これによって Z_q が1の原始 2n 乗根を含むことが必要です。n = 256 の ML-KEM では、q = 3329 がこの要件を満たします。Z_3329 上の NTT は、SIMD命令を備えた最新のハードウェア上で非常に高速に動作し、市販のCPUで毎秒数千回の ML-KEM 操作を可能にします。

Ring-LWEとModule-LWEは、標準LWEと比較して鍵サイズを大幅に削減します。128ビットのセキュリティを実現する標準LWEの公開鍵は1 MBになる場合がありますが、Ring-LWEでは約800バイトに削減でき、Module-LWE（ML-KEM-768）では、192ビットのポスト量子セキュリティを備えた1184バイトの公開鍵を実現します。このコンパクトさにより、格子方式はTLSや組み込みシステムで実用的になります。

一部の暗号研究者は、円分環に備わる追加の代数構造によって、通常のLWEには適用できない攻撃が可能になるのではないかと懸念しています。2024年には、Elias Rokickiらが 2n 次円分多項式の分析を発表し、実用的な攻撃は見つからなかったものの、継続的な精査の重要性を指摘しました。NISTのPQCプロセスではこのリスクが考慮され、単一のリング構造への依存を減らすことも理由の一つとして、Module-LWEが選択されました。

Kyber以外にも、Ring-LWEはNISTが標準化した署名方式であるCRYSTALS-Dilithium（ML-DSA）の基盤になっています。MicrosoftのSEALライブラリは、Ring-LWEによる準同型暗号を実現します。Googleの暗号ライブラリTinkには、ML-KEMのサポートが含まれています。Ring-LWEは、NISTの標準化プロセスに後押しされ、理論上の構成から本番環境への導入へと、驚くほど短期間で移行しました。

Ring-LWEが標準LWEに対して持つ主な利点は何ですか？

Ring-LWEはLWEを多項式環 R_q = Z_q[X]/(X^n+1) に移し、鍵サイズを大幅に削減するとともに、NTTに基づく高速な算術演算を可能にします。Module-LWEはこれをランクkの構造に一般化したもので、ML-KEM（FIPS 203）とML-DSA（FIPS 204）の基盤になっています。NTTに適した素数 q = 3329 によって、効率的な実装が可能になります。安全性は、イデアル格子およびモジュール格子上の問題の困難性に基づいています。