Locally-APN Binomials with Low Boomerang Uniformity in Odd Characteristic

以下は、Koo らによる論文「Locally-APN Binomials with Low Boomerang Uniformity in Odd Characteristic（奇標数における低ブーメラン一様性を持つ局所 APN 二項式）」の詳細な技術的要約です。

1. 問題定義

本論文は、有限体 $\mathbb{F}_q$（ここで $q = p^n$ は奇素数べき）上で定義された特定の関数クラスの暗号学的性質を取り扱います。焦点は、以下の形式の関数に置かれています。
$$F_r(x) = x^r(1 + \chi(x)) = x^r + x^{r + \frac{q-1}{2}}$$
ここで、$\chi(x) = x^{\frac{q-1}{2}}$ は二次指標です。

本研究は、これらの関数に対して 2 つの重要なセキュリティ指標を決定することを目的としています。

1. 差分一様性（$\delta_F$）： 差分暗号解析に対する耐性を測定します。関数が $\delta_F = 2$ である場合、Almost Perfect Nonlinear (APN) と呼ばれます。これらの関数は多くのパラメータにおいて厳密な意味での APN ではないため、著者らはこれらが局所 APN（Locally-APN）（すなわち、すべての $b \in \mathbb{F}_q \setminus \mathbb{F}_p$ に対して $\delta_F(1, b) \le 2$ を満たす）であるかどうかを調査します。
2. ブーメラン一様性（$\beta_F$）： ブーメラン攻撃に対する耐性を測定します。本論文は $\beta_F \le 2$ であることを確立し、完全なブーメランスペクトル（ブーメラン接続表における解の数の分布）を決定することを目指しています。

具体的には、単項式 $x^r$ が低い差分一様性（しばしば Perfect Nonlinear または APN）を持ち、かつ $\gcd(r, q-1) \mid 2$ となる指数 $r$ の部分クラスに対して、これらの性質が成り立つかどうかを調査します。

2. 手法

著者らは、代数整数論、指標和解析、および有限体上の組合せ論的数え上げを組み合わせた手法を採用しています。

• 解集合の分解： 著者らは、$x$ と $x+1$ の二次指標に基づいて体 $\mathbb{F}_q$ を分割します。$i, j \in \{0, 1\}$ に対して、集合 $S_{ij} = \{x \in \mathbb{F}_q : \chi(x) = (-1)^i, \chi(x+1) = (-1)^j\}$ を定義します。
• 差分解析： $F_r(x+a) - F_r(x) = b$ の解を数えるために、問題を特定の集合 $S_{ij}$ 内における方程式 $(x+1)^r - x^r = b$ の解析に帰着させます。$S_{00}$（$x$ と $x+1$ の両方が二次剰余である場合）においてこの方程式が最大 1 つの解しか持たない場合、関数が局所 APN であることを証明します。
• ブーメラン解析： ブーメラン接続表（BCT）を定義する方程式系を解析します。解空間 $(x, y)$ を集合の積 $S_{ij} \times S_{kl}$ に分解することで、解の数を評価します。
• 指標和： 著者らは Weil 限界および二次指標の特定の性質（例：$\sum \chi(f(x))$）を利用して解の数を推定し、特定のケースに対する正確な差分およびブーメランスペクトルを導出します。
• 線形同値： 補題 2.8 を利用して、特定の指数（例：$3^{k+1}/2$）が他の指数と線形同値であることを示し、結果を一般化します。

3. 主要な貢献

A. 一般的な理論的枠組み

二項式 $F_r$ が局所 APN かつ低いブーメラン一様性を持つための十分条件を確立しました。

• 条件： $\gcd(r, q-1) \mid 2$ であり、かつすべての $b \in \mathbb{F}_q^*$ に対して方程式 $(x+1)^r - x^r = b$ が $S_{00}$ 内で最大 1 つの解を持つ場合、以下のことが成り立ちます。
  • $\delta_{F_r} = \frac{q+1}{4}$（局所 APN）。
  • $\beta_{F_r} \le 2$。

B. 特定の指数に対する検証

著者らは、上記の条件が指数 $r$ のリスト（論文の表 3 に要約）に対して成り立つことを検証しました。これには以下が含まれます。

• $r = p^k + 1$（$n$ が奇数の場合）。
• $r = \frac{3^{k+1}}{2}$（一般化された Coulter-Matthews 指数）。
• $r = 3$ および $r = \frac{2q-1}{3}$（$q \equiv 11 \pmod{12}$ の場合）。
• $r = \frac{3^{n+1}-1}{2}$ および $r = \frac{3^{n+1}-1}{8}$（$p=3$ の場合）。

C. 正確なスペクトルの決定

• 差分スペクトル： 論文は、$q \equiv 11 \pmod{12}$ である場合の $F_3$ および $F_{\frac{2q-1}{3}}$ に対する正確な差分スペクトルを導出しました。
  • $F_3$ の場合、スペクトルは指標和 $\Gamma$ に依存します。
  • $F_{\frac{2q-1}{3}}$ の場合、スペクトルは明示的に $\{\omega_0 = \frac{q-3}{2}, \omega_1 = \frac{q+5}{4}, \omega_2 = \frac{q-3}{4}, \omega_{\frac{q+1}{4}} = 1\}$ として計算されます。
• $F_2$ のブーメランスペクトル（$p=3$）： 論文は、$p=3$ かつ $n$ が奇数の場合の $F_2$ に対する最初の完全なブーメランスペクトルを提供しました。

4. 主要な結果

1. 局所 APN 性質： 表 3 にリストされたすべての指数に対して、関数 $F_r$ が差分一様性 $\frac{q+1}{4}$ を持つ局所 APN であることが証明されました。
2. ブーメラン一様性の上限： 同じ指数クラスに対して、ブーメラン一様性が最大 2 であることが証明されました。
3. 既存文献の訂正（重要な発見）：
   • 先行研究（Mesnager と Wu、[14]）は、$q$ が大きい場合、$F_2$ のブーメラン一様性が 2 であると予想し、証明していました。
   • 本論文は標数 3 においてこれを反証しました。 著者らは、$p=3$ かつ $n$ が奇数の場合、$F_2$ のブーメラン一様性が正確に1であることを証明しました。
   • 理由： 標数 3 において恒等式 $1 = -2$ が成り立つため、以前の証明で考慮された特定のケースが互いに矛盾するか、退化することになり、より低い一様性をもたらします。
4. $F_2$ の明示的なブーメランスペクトル（$p=3$）：
   スペクトルは $\nu_0 = \frac{3q-5+2\Lambda}{4}$ および $\nu_1 = \frac{q+1-2\Lambda}{4}$ で与えられます。ここで $\Lambda = \sum_{x \in \mathbb{F}_q} \chi(x+1)\chi(x^2+1)$ です。

5. 意義

• 暗号設計： 本結果は、奇標数体上で動作するブロック暗号における S-ボックスの新たな候補を提供します。低い差分およびブーメラン一様性を持つ関数は、現代の暗号解析攻撃に対する耐性において不可欠です。
• 理論的進展： 本論文は、よく研究されている偶標数のケースを超えて「局所 APN」関数の理解を拡張しました。特定の指数構造を持つ二項式を分析するための統一的な枠組みを提供しています。
• 限界の精緻化： ブーメラン一様性が 2 から 1 に低下する特定のケース（$p=3$）を特定することにより、有限体暗号における標数固有の分析の重要性を浮き彫りにし、一般的な標数研究で行われていた仮定を訂正しました。
• スペクトルの特性化： 一様性の限界だけでなく、正確な差分およびブーメランスペクトルを提供することは、これらの関数のセキュリティマージンをより正確に評価することを可能にします。

結論として、本論文は、奇標数における広範な二項式クラスに対して局所 APN 性質を成功裡に一般化し、それらの低いブーメラン一様性を証明するとともに、標数 3 における $F_2$ の理解に対する重要な訂正を提供しました。