An alternative approach towards attacks against fully-split PLWE instances

技術要約：完全分解型PLWEインスタンスに対する攻撃への代替的アプローチ

問題提起
多項式学習エラー（PLWE）問題は、その代数的な構造の特性から、Ring-LWEよりも効率的であるとしてポスト量子暗号において好まれる、基礎となる問題である。しかし、この構造は潜在的な脆弱性を導入する可能性がある。先行研究、特に[5, 6]およびそれらを一般化した[2]は、有限体上の特定の多項式因子（$n$-イデアル因子 $x^n - a$ として知られる）の存在を利用する「ルートベース攻撃（root-based attacks）」を導入した。これらの攻撃は、評価準同型とトレース演算を利用して、PLWEのサンプルを一様分布から区別するものである。

[2]では、これらの攻撃を体拡大上の多項式へと一般化した。しかし、重要な未解決の問いが残されていた。「『安全な』PLWEインスタンスに脆弱な因子が存在しない場合、そのインスタンスを、適切な$n$-イデアル因子を持つ『脆弱な』インスタンスへと環同型写像によって写すことで、攻撃者は回避できるのではないか？ そして、そこで攻撃を実行し、元のインスタンスの安全性を推論できるのではないか？」という問いである。本論文は、このような同型写像による移行戦略が、完全分解型PLWEインスタンスに対して意味のある優位性をもたらすかどうかを調査するものである。

手法
著者らは、異なる多項式環の間でPLWEサンプルを転送することの実現可能性を分析するために、厳密な代数的アプローチを採用している。その手法は、主に以下の2つのフェーズで進行する。

1. 任意の分解への一般化： 本論文では、まず$n$-イデアル因子を持たない多項式へのルートベース攻撃の拡張を検討する。補題1を利用することで、著者らは任意の既約因子に対してトレース演算を定義できることを示す。しかし、そのような攻撃の成功確率は、因子のゼロ係数の数に大きく依存することを示している。任意の多項式においてはこの数は通常低いため、一般的なケースにおける攻撃は実用的なものとはならない。

2. 完全分解設定における同型分析： 本研究の核心は「同型アプローチ」にある。著者らは、共に次数 $N$ を持ち、$\mathbb{Z}[x]$ 上で既約である2つの多項式 $f(x)$ と $g(x)$ を考える（すなわち、それらは同じ次数の既約因子に分解される）。

   • 構成： 中国剰余定理を用いて、環 $R_q = \mathbb{F}_q[x]/(f(x))$ と $R'_q = \mathbb{F}_q[x]/(g(x))$ の間の明示的な同型写像 $\psi$ を構築する。完全分解ケース（両方の多項式が線形項に完全に分解される場合）において、この同型写像はヴァンデルモンド行列の積 $\psi = V_g^{-1} \cdot V_f$ によって表される。
   • 歪み分析： 著者らは、この同型写像をPLWEサンプルに適用した後に $g(x)$ の根 $\beta$ で評価した場合の影響を分析する。彼らは、この結果得られる評価が、元のサンプルを対応する根 $\alpha$ で評価することと数学的に等価であることを証明する。
   • 一意性の証明： 手法の重要な部分は、このような完全分解型多項式環の間の「いかなる」環同型写像も、この特定の形式（評価準同型の合成と構築された同型写像）をとらなければならないことを証明することである。これは、補題2、3、4、および定理1を通じて確立される。

主な貢献

• 同型不変性の形式的証明： 本論文は、完全分解型PLWEインスタンスにおいて、環同型写像を介してサンプルを脆弱な設定へ移行しようとするいかなる試みも、新たな脆弱性を生み出さないことを形式的に証明している。同型写像によって導入されるノイズ（誤差）はサンプルを歪ませ、その結果、区別可能性の条件は元のインスタンスと同一になる。
• 環同型の特徴付け： 著者らは、完全分解型多項式環の同型写像の完全な集合を特徴付け、それらが根の写像によって一意に決定されることを示している。これにより、ノイズの歪みを回避できるような「隠れた」同型写像は存在しないことが証明される。
• 任意の分解への拡張： 本研究は、ルートベース攻撃を$n$-イデアル因子を持たない多項式に適用することは理論的には可能であるが、構造的な制約（具体的にはゼロ係数の数）が成功確率を著しく制限するため、実用的な脅威としての一般化の道は閉ざされていることを明確にしている。

結果

• ノイズの歪み： 同型写像 $\psi$ の適用と $g(x)$ の根 $\beta$ における評価は、$b(\beta) = \sum a_j \alpha^j$ （ここで $\alpha$ は $f(x)$ の対応する根）という式をもたらす。これは、変換された設定における攻撃が、元の設定における攻撃と数学的に同一であることを示している。
• 移行戦略の失敗： 分析の結果、もし元のPLWEインスタンスに対してルートベース攻撃が失敗する場合（高いノイズや区別可能性の欠如により）、それは同型なインスタンスに対しても失敗することが確認された。同型写像はノイズを「浄化」するのではなく、むしろ問題の根本的な困難さを保持する。
• 特定の根の分析： 論文では、評価の根 $\beta$ が $0$、$1$、または任意の根である特定のケースを分析している。いずれの場合も、結果としての評価は元の多項式の対応する根での評価に帰着し、優位性は得られないことが確認された。

意義
本論文は、完全分解型PLWEインスタンスに関する直感は正しいと結論付けている。すなわち、初期のPLWEインスタンスに対してルートベース攻撃が成功しないのであれば、環同型写像を介してサンプルをより弱いPLWE設定に移されたとしても、依然として成功しない。

この結果は、効率性（例：数論変換）のために用いられることが多い、完全分解型PLWEインスタンスの安全性に対する信頼の源となる。本研究は、「同型移行」がこれらの特定のインスタンスに対する新たな攻撃を生成するための実行可能なベクトルではないことを効果的に排除している。著者らは、この分析が完全分解多項式に特化したものであることを注記しており、非完全分解インスタンスの安全性や、他の攻撃ベクトル（導入部で言及されたスティッケルベルガー・イデアル攻撃など）を解決するものではないが、完全分解ドメイン内におけるルートベース攻撃の理解を強固にするものである。