2025-11-28T14:22:19.335050

An Explicit Construction of Orthogonal Basis in $p$-adic Fields

Zhang, Deng

In 2021, the $p$-adic signature scheme and public-key encryption cryptosystem were introduced. These schemes have good efficiency but are shown to be not secure. The attack succeeds because the extension fields used in these schemes are totally ramified. In order to avoid this attack, the extension field should have a large residue degree. In this paper, we propose a method of constructing a kind of specific orthogonal basis in $p$-adic fields with a large residue degree, which would be helpful to modify the $p$-adic signature scheme and public-key encryption cryptosystem.

academic

$p$ -進体における直交基の明示的構成

基本情報

論文ID: 2410.17982
タイトル: An Explicit Construction of Orthogonal Basis in $p$ -adic Fields
著者: Chi Zhang, Yingpu Deng（中国科学院数学与系統科学研究院）
分類: math.NT（数論）、94A60（暗号学）
発表時期: 2024年10月（arXiv v2: 2025年11月14日）
論文リンク: https://arxiv.org/abs/2410.17982

要旨

2021年に、 $p$ -進格に基づく署名方式と公開鍵暗号システムが提案された。これらの方式は良好な効率性を示していたが、安全でないことが証明された。攻撃が成功した理由は、これらの方式で使用された拡大体が完全分岐（totally ramified）であったことである。このような攻撃を回避するため、拡大体は大きな剰余次数（residue degree）を持つべきである。本論文は、大きな剰余次数を持つ $p$ -進体における特定の直交基を構成する方法を提案し、 $p$ -進署名方式と公開鍵暗号システムの改善に寄与する。

研究背景と動機

1. 解決すべき核心問題

本論文が解決する核心問題は：大きな剰余次数を持つ $p$ -進拡大体において、効率的に直交基を構成する方法は何かである。

2. 問題の重要性

耐量子暗号学の必要性：Peter ShorはRSAおよびElGamalなどの古典的公開鍵暗号システムが量子コンピュータで破られることを証明し、耐量子性を持つ暗号学的原始が急務である。NISTが2022年に発表した4つの耐量子アルゴリズムのうち、3つは格に基づき、1つはハッシュに基づいており、多様性が不足している。
$p$ -進格暗号学の可能性：2021年にDengらが初めて $p$ -進格に基づく署名方式と暗号化方式を提案し、実験結果は良好な効率性を示し、耐量子暗号学の新しい候補を提供した。
セキュリティの脆弱性：Zhangは2025年に、元の方式が完全分岐拡大体を使用することが不安全であることを発見し、攻撃を回避するため大きな剰余次数を持つ拡大体の使用を推奨した。

3. 既存方法の限界

完全分岐拡大体の単純性：完全分岐拡大体 $K/\mathbb{Q}_p$ において、1つの均化子（uniformizer） $\pi$ で直交基を生成できるため、構成は単純だが安全でない。
一般拡大体の困難性：一般拡大体では、完全分岐の場合のように容易に直交基を見つけることができない。
既存アルゴリズムの複雑性：Round 2アルゴリズムとRound 4アルゴリズムは最大序（maximal order）の基を計算し、その後直交基を得ることができるが、大規模行列計算を伴い、最悪の場合 $O(n^3)$ のストレージと $O(n^4)$ を超える時間複雑性が必要である。

4. 研究の動機

別の観点から出発する：直交基を直接構成し、その後それが生成する拡大体を計算する、つまり最大序を先に計算してから直交基を求めるのではなく。この方法は最悪の場合でも $O(n^2)$ のストレージのみを必要とする。

核心的貢献

直交基の等価条件（定理3.3）：拡大体 $K/\mathbb{Q}_p$ における直交基の等価判定条件を与える。すなわち、基ベクトルが剰余体において線形独立であることが、 $p$ -進体における直交性と等価である。
特定の直交基の明示的構成（定理4.10）：単位根を利用した直交基構成方法を提案する。 $K_1=\mathbb{Q}_p(\theta)$ が剰余次数 $f$ の非分岐拡大体、 $K_2=\mathbb{Q}_p(\pi)$ が分岐指数 $e$ の完全分岐拡大体である場合、族 $(\theta^i\pi^j)_{0\leq i\leq f-1, 0\leq j\leq e-1}$ は $K=\mathbb{Q}_p(\theta,\pi)$ の直交基を構成する。
単位根に基づく実用的アルゴリズム（第5節）：Sophie Germain素数と原始単位根を利用し、多項式時間アルゴリズムを提供する。ストレージ要件は $O(n)$ （平衡の場合）または $O(n^2)$ （最悪の場合）、時間複雑性は $O(n^{1.5})$ または $O(n^3)$ であり、既存アルゴリズムより優れている。
原始元の構成（補題5.8）： $\zeta = \theta + \pi$ が $K=\mathbb{Q}_p(\theta,\pi)$ の原始元であることを証明する。ここで $\theta$ は素数位数の単位根、 $\pi$ はEisenstein多項式の根である。

方法の詳細説明

タスク定義

入力：

素数 $p$
拡大体の次数 $n = ef$ （ $e$ は分岐指数、 $f$ は剰余次数）

出力：

$\mathbb{Q}_p$ 上の次数 $n$ の拡大体 $K$
$K$ の直交基 $\{\alpha_1,\ldots,\alpha_n\}$ 。任意の $a_i\in\mathbb{Q}_p$ に対して以下を満たす： $\left\|\sum_{i=1}^n a_i\alpha_i\right\| = \max_{1\leq i\leq n}\|a_i\alpha_i\|$

制約条件：拡大体は既知の攻撃に対抗するため、大きな剰余次数 $f$ を持つべきである。

理論的基礎

1. 直交基の定義（定義2.2）

$V$ を $\mathbb{Q}_p$ 上の $n$ 次元ベクトル空間とし、 $\|\cdot\|$ をノルムとする。 $\alpha_1,\ldots,\alpha_n$ が $V$ の直交基であるとは、 $V$ が $n$ 個の1次元部分空間 $V_i$ （ $\alpha_i$ で張られる）の直和に分解でき、以下を満たす場合である： $\left\|\sum_{i=1}^n v_i\right\| = \max_{1\leq i\leq n}\|v_i\|, \quad v_i\in V_i$

2. 剰余次数と分岐指数（定義2.3）

$K/\mathbb{Q}_p$ が次数 $n$ の有限拡大である場合：

剰余次数 $f = [k:\mathbb{F}_p]$ 。ここで $k=R/P$ は剰余体
分岐指数 $e = [|K^*|:|\mathbb{Q}_p^*|]$
基本関係（定理2.4）： $ef = n$

核心定理

定理3.3（直交性の等価特性付け）

$K/\mathbb{Q}_p$ が次数 $n$ の拡大体であり、 $\alpha_1,\ldots,\alpha_m$ が $V\subseteq K$ の基であり、 $|\alpha_1|=\cdots=|\alpha_m|=\lambda_1$ であるとする。 $\pi$ を $K$ の均化子とし、 $|\pi^s|=\lambda_1$ とする。このとき：

$\alpha_1,\ldots,\alpha_m$ が直交基である $\Longleftrightarrow$ $\overline{\alpha_1},\ldots,\overline{\alpha_m}$ が $\mathbb{F}_p$ 上線形独立である

ここで $\overline{\alpha_i}$ は $\pi^{-s}\alpha_i$ の剰余体 $k=R/P$ における像である。

証明の概要：

補題3.2により、直交性は以下と等価である： $\|\sum a_i\alpha_i\|<\lambda_1$ （ $a_i\in\mathbb{Z}_p$ ）ならば $p|a_i$
これは $|\sum a_i\pi^{-s}\alpha_i|<1$ のとき $p|a_i$ と等価である
すなわち $\sum a_i\overline{\alpha_i}=0$ （ $k$ において）が $a_i=0$ （ $\mathbb{Z}_p$ において）を含意する
これはまさに $\overline{\alpha_i}$ が $\mathbb{F}_p$ 上線形独立であるという定義である

定理4.7（一般的構成）

$K/\mathbb{Q}_p$ の剰余次数が $f$ 、分岐指数が $e$ であるとする。 $\pi$ を均化子とし、 $(s_i)_{1\leq i\leq f}$ が剰余体 $k$ において $\mathbb{F}_p$ -基を構成するとする。このとき：

族 $(s_i\pi^j)_{1\leq i\leq f, 0\leq j\leq e-1}$ は $K$ の直交基である

証明の概要：

固定された $j$ に対して、定理3.3により、 $(s_i\pi^j)_{1\leq i\leq f}$ は $V_j=\text{span}\{s_i\pi^j\}$ の直交基である
異なる $V_j$ の値群は交わらない： $\{|v_j|:v_j\in V_j\}=\{0\}\cup p^{\mathbb{Z}-j/e}$
補題4.6（直交基の結合）により、全体の族は $K=\bigoplus_{j=0}^{e-1}V_j$ の直交基を構成する

定理4.10（単位根を利用した構成）

以下を設定する：

$K_1=\mathbb{Q}_p(\theta)$ は剰余次数 $f$ の非分岐拡大体であり、 $|\theta|=1$
$\theta$ の最小多項式 $F$ は法 $p$ で既約である
$K_2=\mathbb{Q}_p(\pi)$ は分岐指数 $e$ の完全分岐拡大体であり、 $\pi$ は均化子である

このとき族 $(\theta^i\pi^j)_{0\leq i\leq f-1, 0\leq j\leq e-1}$ は $K=\mathbb{Q}_p(\theta,\pi)$ の直交基である

証明の概要：

補題4.9により、 $[K:\mathbb{Q}_p]=ef$ 、剰余次数は $f$ 、分岐指数は $e$ である
定理4.3（非分岐の場合）により、 $1,\theta,\ldots,\theta^{f-1}$ は $K_1$ の直交基である
定理3.3により、それらの剰余体 $k$ における像は $\mathbb{F}_p$ -基を構成する
定理4.7を適用して証明を完成させる

アルゴリズム設計

アルゴリズム：単位根に基づく直交基構成

入力：

素数 $q$ と $q_0$ 。 $q=2q_0+1$ を満たす（Sophie Germain素数対）
素数 $p$ 。 $p\not\equiv -1\pmod{q}$ かつ $p$ が法 $q$ の非二次剰余を満たす
正整数 $e$ （分岐指数）

出力：

拡大体 $K/\mathbb{Q}_p$ （次数 $n=(q-1)e$ ）
直交基 $(\theta^i\pi^j)_{0\leq i\leq q-2, 0\leq j\leq e-1}$

ステップ：

$q$ 位数の原始単位根 $\theta$ を選択し、その最小多項式を $H$ とする
次数 $e$ のEisenstein多項式 $G$ を選択し、 $G(X)=0$ の根 $\pi$ を選択する
$\zeta=\theta+\pi$ とする（補題5.8により、 $\zeta$ は原始元である）
$F(X)=\text{Res}_Y(G(Y), H(X-Y))$ を計算する（ $\zeta$ の最小多項式）
$K=\mathbb{Q}_p(\zeta)$ （ $F$ により与えられる）と直交基 $(\theta^i\pi^j)$ を返す

関鍵補題5.8： $q\neq p$ を素数とし、 $\theta$ を $q$ 位数の原始単位根とし、 $f=q-1$ とする。 $G$ をEisenstein多項式とし、 $\pi$ をその根とする。このとき $K=\mathbb{Q}_p(\theta+\pi)$ である。

証明：補題5.7により、異なる単位根の距離は1である。すなわち $|\theta^{(s)}-\theta^{(t)}|=1$ 。一方 $|\pi^{(u)}|<1$ であるため： $\left|\frac{\pi^{(u)}-\pi^{(v)}}{\theta^{(s)}-\theta^{(t)}}\right|<1$ 補題5.6（原始元定理の構成的証明）において $h=1$ を取ることで完成する。

技術的革新点

理論的革新：定理3.3は $p$ -進体の直交性と剰余体の線形独立性の橋渡しを確立し、本論文のすべての構成の理論的基礎である。
構成戦略：「最大序を計算→直交基を求める」から「直交基を構成→拡大体を決定する」への転換により、大規模行列演算を回避する。
単位根の技巧：
- 定理5.1の利用： $p$ と互いに素な位数を持つ単位根は自動的に非分岐拡大体の直交基を生成する
- Sophie Germain素数と二次非剰余条件を利用して、原始根の位数が $q-1$ に達することを確保する
- 分圆多項式の分解（補題5.4）を利用して最小多項式の次数を決定する
原始元構成： $\zeta=\theta+\pi$ の選択は、単位根の距離が1で $\pi$ の絶対値が1より小さいという性質を巧妙に利用する（補題5.7）。これにより補題5.6のパラメータ $h=1$ となり、計算が簡略化される。
複雑性の最適化：
- 平衡の場合（ $e\approx q-1\approx\sqrt{n}$ ）：ストレージ $O(n)$ 、時間 $O(n^{1.5})$
- 最悪の場合：ストレージ $O(n^2)$ 、時間 $O(n^3)$
- いずれもRound 2/4アルゴリズムの $O(n^3)$ ストレージと $>O(n^4)$ 時間より優れている

実験設定

本論文は純粋な理論数学論文であり、実験部分を含まない。すべての結果は厳密な数学的証明である。

例による検証

論文は理論を検証するためにいくつかの具体的な例を提供している：

例4.2： $\theta$ を $p^l$ 位数の原始単位根とし、 $K=\mathbb{Q}_p(\theta)$ を次数 $n=\phi(p^l)=p^{l-1}(p-1)$ の完全分岐拡大体とする。 $X^{p^l}-1\equiv(X-1)^{p^l}\pmod{p}$ が可約であるため、 $1,\theta,\ldots,\theta^{n-1}$ は直交基ではない。実際には $|\theta-1|=|p|^{1/\phi(p^l)}$ である。

例4.8： $K=\mathbb{Q}_3(\sqrt{3+i})=\mathbb{Q}_3(\sqrt{3},i)$ 、 $[K:\mathbb{Q}_3]=4$ 、剰余次数 $f=2$ 、分岐指数 $e=2$ 。 $\sqrt{3}$ は均化子であり、 $1,i$ は $\mathbb{F}_3$ 上線形独立であるため、 $\{1,i,\sqrt{3},\sqrt{3}i\}$ は直交基である。

例5.2： $K=\mathbb{Q}_3(i)$ 、 $i^2=-1$ 。 $X^2+1$ が法3で既約であるため、 $\{1,i\}$ は直交基である。

実験結果

本論文は理論論文であり、実験結果を持たない。主な成果は以下に体現されている：

複数の定理の厳密な証明
構成アルゴリズムの複雑性分析
具体的な数値例の検証

結論と議論

主要な結論

理論的貢献：定理3.3は直交基の等価特性付けを与え、 $p$ -進体の直交性問題を剰余体の線形代数問題に変換する。
構成方法：定理4.10は単位根とEisenstein多項式を利用して、大剰余次数拡大体における直交基の明示的構成方法を提供する。
アルゴリズムの効率：提案されたアルゴリズムはストレージ（ $O(n)$ から $O(n^2)$ ）と時間（ $O(n^{1.5})$ から $O(n^3)$ ）の両面で既存のRound 2/4アルゴリズムより優れている。
暗号学的応用： $p$ -進署名および暗号化方式のセキュリティ脆弱性を修復するための技術的経路を提供する。

限界

セキュリティが完全に解決されていない：論文は第6節で、単純に $\zeta=\theta+\pi$ を使用することが安全でない可能性があることを指摘している。攻撃者は剰余次数 $f$ を推測し、 $f$ 位数の原始単位根 $\theta'$ を減算しようとすることができる。 $\theta'=\theta$ の場合、均化子 $\pi$ を取得して方式を破ることができる。
原始元構成の複雑性：より複雑な原始元 $\zeta$ を見つける必要があり、同時に時間複雑性を大幅に増加させない必要がある。
パラメータ選択の制限：アルゴリズムはSophie Germain素数対と特定の条件を満たす素数 $p$ （二次非剰余）を必要とするため、パラメータ選択に一定の制限がある。
理論的完全性：定理4.3の非分岐仮定は注記4.4で削除可能であることが言及されている（法 $\pi$ を法 $p$ の代わりに使用）が、著者はより実用的だが若干弱い版を選択した。

将来の方向

論文が明確に指摘する研究方向：

安全な方式設計：安全な $p$ -進暗号方式の設計にはさらなる努力が必要であり、特により複雑な原始元構成方法を見つけることが重要である。
その他の応用： $p$ -進体直交基構成方法は他の応用を持つ可能性があり、さらなる研究の価値がある。
パラメータ最適化：Sophie Germain素数への依存を減らし、より柔軟なパラメータ選択戦略を探索する。
困難性分析： $p$ -進格困難問題の量子耐性を深く研究し、より厳密なセキュリティ証明を確立する。

深い評価

利点

1. 理論的深さ

核心定理の優雅さ：定理3.3は複雑な $p$ -進ノルム問題を剰余体の線形代数に簡略化し、深い数学的洞察を体現している
証明の厳密性：すべての定理は完全な証明を持ち、論理の連鎖は明確である
理論的完全性：基本的定義（第2節）から等価条件（第3節）を経て具体的構成（第4-5節）へと段階的に進む

2. 方法的革新

視点の転換：「最大序を求める」から「直交基を構成する」への思考転換は本質的な効率改善をもたらす
単位根の技巧：数論における分圆理論を巧妙に利用し、抽象的問題を具体化する
複雑性の優位性：パラメータが平衡している場合、 $O(n)$ ストレージと $O(n^{1.5})$ 時間を達成。これは代数的数論アルゴリズムにおいて顕著な改善である

3. 実用的価値

暗号学との関連性： $p$ -進暗号学のセキュリティ脆弱性に直接対応し、明確な応用目標を持つ
アルゴリズムの実装可能性：第5節で提供されるアルゴリズムステップは明確で、プログラミング実装が容易である
パラメータの柔軟性：異なる $e$ と $q$ を選択することで、異なる次数の拡大体を生成できる

4. 執筆品質

構造の明確性：問題背景→理論的基礎→一般的構成→特殊構成→アルゴリズムという流れで、論理が流暢である
豊富な例：例4.2、4.8、5.2などの具体的な例が抽象的理論の理解を助ける
価値のある注記：注記3.4と4.4は追加の理論的洞察を提供する

不足

1. セキュリティ分析の不十分さ

攻撃の可能性：論文は結論で $\zeta=\theta+\pi$ が安全でない可能性があることを認めているが、詳細なセキュリティ分析や攻撃モデルを提供していない
セキュリティ証明の欠如：困難問題仮説に基づくセキュリティ帰納法がない
防御措置が曖昧：「より複雑な原始元が必要」と提案するのみで、具体的な方案を提供していない

2. 実験検証の欠落

性能テストなし：複雑性分析は提供されているが、実際の実行時間やメモリ使用量などの実験データが欠落している
比較実験なし：Round 2/4アルゴリズムとの実際の性能比較は理論分析の段階に留まっている
暗号学的実装なし：構成された直交基を実際の署名または暗号化方式にどのように適用するかが示されていない

3. パラメータの制限

Sophie Germain素数： $q_0$ と $q=2q_0+1$ の両方が素数である必要があり、このような素数対の密度は比較的低い
二次非剰余条件： $p$ は特定の数論的条件を満たす必要があり、パラメータ選択の柔軟性を制限する
最悪ケースの複雑性： $\{e,q-1\}=\{1,n\}$ の場合、 $O(n^3)$ に退化し、従来の方法との差が縮小する

4. 理論的完全性

非分岐仮定：定理4.3は非分岐拡大体を要求し、注記4.4で削除可能であることが言及されているが、本文ではより一般的な結果が提供されていない
直交基の一意性：構成された直交基が一意であるか、または異なる構成間の関係が議論されていない
剰余次数の下限：Zhang攻撃に対抗するために必要な剰余次数 $f$ の具体的な下限が与えられていない

影響力

1. 分野への貢献

$p$ -進暗号学：この新興分野に重要な技術ツールを提供し、 $p$ -進格暗号学の実用化を推進する可能性がある
代数的数論計算：直交基構成アルゴリズム自体は代数的数論研究にも価値がある
耐量子暗号：耐量子暗号学に新しい数学的ツールと思考方法を提供する

2. 理論的価値

橋渡し作用：定理3.3は $p$ -進分析と有限体理論を結び、この関連性は他の研究にも啓発を与える可能性がある
方法論的意義：「直接構成+逆推構造」の思考方法は他の代数対象の計算問題にも適用可能である

3. 実用的価値

効率改善：アルゴリズム複雑性の改善により、大次数拡大体の直交基構成が実行可能になる
実装可能性：アルゴリズムステップが明確で、ソフトウェア実装と工学応用が容易である

4. 限界

応用範囲：現在は主に $p$ -進暗号学に対応しており、他の応用シナリオはまだ明確でない
セキュリティ検証待ち：暗号学応用におけるセキュリティはさらなる研究が必要である
パラメータ依存：特殊素数への依存により、実際の応用を制限する可能性がある

適用シナリオ

1. 暗号学的応用

$p$ -進署名方式の修復：完全分岐拡大体を置き換え、大剰余次数拡大体と本論文構成の直交基を使用
$p$ -進暗号化システム：公開鍵暗号方式のセキュリティを同様に改善
陥門関数設計：直交基を利用した新しい陥門関数の構成

2. 代数的数論計算

局所体計算：明示的直交基が必要な数論問題
$p$ -進分析： $p$ -進ノルムと直交分解に関わる研究
類体論計算：局所類体論における明示的構成

3. 理論研究

$p$ -進格理論： $p$ -進格の幾何学的および代数的性質を研究するための基本ツール
局所-整体原理：数論問題の局所研究における使用

4. 不適用シナリオ

完全分岐の場合：本論文の方法は完全分岐拡大体（ $e=n, f=1$ ）に対して優位性がなく、均化子自体が直交基を生成する
小次数拡大体： $n$ が小さい場合、従来の方法で十分な効率がある
直交基が不要な応用：拡大体自体は必要だが直交基構造に関心がない場合

参考文献（主要文献）

5 Deng et al. (2024): 初めて $p$ -進格暗号方式を提案。本論文の直接的な動機源

16 Zhang (2025): 5の方式を攻撃し、大剰余次数が必要であることを指摘。本論文が解決する核心問題

14 Weil (1974): $p$ -進ベクトル空間が直交基を持つことを証明。本論文の理論的基礎

11 Robert (2000): 局所体理論の古典的教科書。本論文の主要参考文献

4 Cohen (1993): Round 2アルゴリズム。本論文の比較基準

7 Ford (1978): Round 4アルゴリズム。本論文のもう1つの比較基準

総括

これは高品質の理論数学論文であり、 $p$ -進暗号学のセキュリティ脆弱性に対応し、大剰余次数拡大体における直交基構成の革新的方法を提案している。核心的貢献は定理3.3と定理4.10である。前者は優雅な等価特性付けを与え、後者は実用的な構成アルゴリズムを提供する。論文の主な利点は理論的深さ、方法的革新、複雑性改善にあり、主な不足はセキュリティ分析と実験検証の欠落にある。

暗号学研究者にとって、本論文は $p$ -進暗号方式を修復するための技術的経路を提供するが、さらなる研究が必要である。安全な原始元構成と完全なセキュリティ証明が必要である。代数的数論研究者にとって、本論文の直交基構成方法は理論的価値を持ち、他の計算問題の解決に啓発を与える可能性がある。

推奨指数：★★★★☆（理論は優秀、応用はさらに完善が必要）

An Explicit Construction of Orthogonal Basis in $p$-adic Fields

ppp-進体における直交基の明示的構成

$p$ -進体における直交基の明示的構成