技術要約：同次数の多項式系の解法における複雑性

問題の定義

多変量暗号やポスト量子設定における数多くの暗号スキームの安全性は、有限体上の多変量多項式系の解法の計算困難性に依存している。グレブナー基底法によるこのような系の解法の複雑性は、主に正則次数（$d_{reg}$）および解法次数（solving degree）によって決定される。正則次数はグレブナー基底計算の複雑さの上界を提供するものであるが、暗号学的なサイズの系に対しては、その計算や推定が困難である場合が多い。

一般的な慣習は、系が半正則（または暗号学的に半正則）であるというヒューリスティックな仮定に依存しており、これにより正則次数の明示的な公式が得られる。しかし、この仮定は常に妥当であるとは限らない。特定のパラメータ選択や体においては、半正則な列が存在しない場合がある。したがって、半正規則性の仮定に依存することなく、正則次数が有限である系に対して適用可能な、証明された非ヒューリスティックな正則次数および解法次数の上界が必要とされている。

手法

著者らは可換代数のツールを用いてこの問題にアプローチしており、具体的には、与えられた次数 $D$ において、多項式の最高次部分によって生成されるイデアルが $n$ 個の多項式からなる正則列を含む系に焦点を当てている。

1. フレームワーク: 本論文では、体 $F$ 上の $n$ 変数 $m$ 個の多項式からなる系 $F = \{f_1, \dots, f_m\}$ を検討する。解析では、最高次部分 $f_1^{top}, \dots, f_m^{top}$ が線形独立であり、かつ系が次数 $D$ において正則である（すなわち、最高次部分によって生成されるイデアルが、次数 $D$ の $n$ 個の多項式からなる正則列を含む）ことを前提としている。
2. LPPイデアルへの還元: カステルヌオーヴォ・ムンフォモ・レギュラリティ（Castelnuovo-Mumford regularity。正則次数が有限であればこれと一致する）を抑えるために、著者らはEisenbud-Green-Harris (EGH) 予想を利用する。この予想は、特定の次数の正則列を含むすべての斉次イデアルの中で、Lex-Plus-Powers (LPP) イデアルが最大のレギュラリティを持つと主張している。
3. 組合せ論的解析: 著者らは、与えられたパラメータ（$n, m, D$）に関連する特定のLPPイデアルを構成する。これらのイデアルを辞書式順序の下で解析することにより、元の系のレギュラリティの上界となるLPPイデアルのレギュラリティを決定する（EGH予想を条件とする）。
4. 体の方程式: この手法は、体方程式（$x_i^q - x_i$）が付加された系へと拡張される。これは、多項式の次数 $D$ が体サイズ $q$ 以上である場合、特に有限体 $\mathbb{F}_q$ 上の系において極めて重要である。

主要な貢献と結果

1. 次数 $D$ において正則な系に対する上界（体の方程式なし）

定理 23 は、系が次数 $D$ において正則であると仮定した場合の、$n$ 変数 $m$ 個の次数 $D$ の方程式の系の正則次数の鋭い上界を提供する。

• この界は、方程式の数（$m$）、変数（$n$）、および次数（$D$）に依存する。
• 公式は、組み合わせ和（$\sigma_{k,t}$）によって定義される特定の区間内に $m-n$ が入るような、一意な整数 $k$ および $t$ を特定することを含む。
• 得られる界は、$d_{reg}(F) \le (D - t) + (n - k)(D - 1)$ である。
• この界はすべての $m, n, D$ の値に対して**鋭い（sharp）**ものであり、最高次部分が特定のLPPイデアルを形成する系によって達成される。

系 27 は、これをミュータント（mutant）アルゴリズムに対する解法次数の上界へと変換する：
$$\text{solv. deg}_m(F) \le D - t + 1 + (n - k)(D - 1)$$

2. 体の方程式を持つ系に対する上界

本論文は、体方程式が系に追加されたケースに対処しており、これは $D \ge q$ の場合に不可欠である。

• 命題 31: 極めて過決定された系（$m$ が体の方程式による多項式空間の次元を超える場合）において、正則次数は正確に $D$ である。
• 定理 33: $q \le D \le n(q-1)$ であり、最高次部分が体の方程式に関して線形独立である系について、著者らは正則次数の上界を提供する。
  • この界は、$(x_1^q, \dots, x_n^q)$ モジュロの次数 $D$ の単項式の辞書式順序における $m$ 番目の単項式の位置を解析することによって導出される。
  • 界は、$B = q - t + (n - k)(q - 1)$ を用いて表現される（ここで $k$ と $t$ は $m$ を含む区間によって決定される）。
  • $m, D, t$ に関する特定の条件に応じて、界は $B$ または $B-1$ となる。

系 34 は、これらの結果をバイナリ系（$q=2$）に特化させ、$\mathbb{F}_2$ 上の次数 $D$ の系の正則次数および解法次数の簡略化された公式を提供する。

3. 特定のスキームへの適用

著者らは、これらの界を具体的な暗号スキームに適用している：

• Cubic Simple Matrix: 著者らは、証明された界 $d_{reg} \le 2n - 1$ を導出した。これはこの系に対する初の証明された界であり、従来のヒューリスティックな推定値とは対照的である。
• Unbalanced Oil and Vinegar (UOV): 境界は $\mathbb{F}_2$ 上のUOV系に適用され、体方程式が含まれる場合に正則次数がどのように振る舞うかを示している。

意義と主張

本論文は、主に多項式系の複雑さに対する証明された非ヒューリスティックな界を提供することに意義があると主張している。

• 信頼性: 半正則性の仮定に基づく推定（特定のパラメータにおいて失敗する可能性がある）とは異なり、これらの界は、正則次数が有限であり、かつ与えられた次数において正則であるあらゆる系に対して成立する。
• 汎用性: 結果は任意の体上の系に適用され、体の方程式の有無の両方のケースをカバーしている。
• 鋭さ（Sharpness）: これらの界は「鋭い」と記述されており、これは特定の系（LPPイデアル）によって達成されることを意味し、セキュリティ分析のための現実的な最悪ケースの推定値を提供する。
• 限界: 著者らは、自分たちの界が一般に、半正則性のヒューリスティックの下で得られるものよりも**緩い（値が大きい）**ことを明示的に認めている。しかし、彼らは、特に半正則な列が存在しないシナリオにおいて、未証明の仮定を避けるためにはこのトレードオフが必要であると主張している。

本研究は、新しいアルゴリズムや実験的な実装を提案するものではなく、暗号学に関連する広範な多項式系に対する既存のグレブナー基底法（標準的なものとミュータントの両方）の複雑さの理論的限界を確立するものである。