符号理論ベース一方向関数を用いた
暗号学的に安全な疑似乱数生成器の構成
元ネタ：
1. はじめに
疑似乱数生成器（Pseudorandom Generator, PRG）は暗号の中核的構成要素であり、
暗号化、署名、鍵生成など、ほぼすべての暗号技術に利用されている。
本記事では、Goppa 符号に基づく復号困難性を利用し、
- 誤りベクトル → シンドローム
- 秘密鍵を知る者のみが逆写像を計算可能
という性質を持つ関数を**一方向関数（OWF）として捉え、
そこから暗号学的に安全な疑似乱数生成器（CSPRNG）**を構成する。
本構成は McEliece / Niederreiter 暗号と同系統に属し、
安全性は Syndrome Decoding Problem に帰着される。
2. 前提：符号理論的設定
2.1 基本パラメータ
- 有限体：
$$
\mathbb{F}_{2^m}
$$ - 符号長：( n )
- 誤り訂正能力：( t )
- Goppa 多項式（秘密鍵）：
$$
T(x)
$$
2.2 誤りベクトル
誤りベクトル ( $e \in \mathbb{F}_2^n$ ) は
- 重み：
$$
\mathrm{wt}(e) = t
$$
とする。
3. 基本関数の定義（一方向関数）
3.1 関数定義
次の関数を定義する：
$$
f(e) = s = eH
$$
ここで：
- ( f )：パターソンアルゴリズムにおける鍵方程式によるシンドローム生成関数
- ( s )：シンドローム
3.2 一方向性
-
順方向計算：
$( e \mapsto s )$ は線形計算で容易 -
逆計算：
$( s \mapsto e )$ は
→ Goppa 符号の復号問題
→ 秘密鍵 ( T ) がなければ計算困難
この問題は既知の Syndrome Decoding Problem に帰着される。
4. 復号（秘密鍵側）
秘密鍵 ( T ) を知る者は以下のいずれかで復号できる：
- ユークリッドアルゴリズムによる復号
- パターソン法による復号
ここでは次を仮定する：
$$
\mathrm{Dec}(T, s) = e
$$
5. 一方向関数から疑似乱数生成器へ
5.1 理論的背景
暗号理論の基本定理により：
一方向関数が存在すれば
暗号学的に安全な疑似乱数生成器が構成可能
（Håstad–Impagliazzo–Levin–Luby 定理）
6. PRG の構成
6.1 シード
- シード：
$$
\text{seed} = e
$$ - ( e ) はランダムに生成された重み ( t ) の誤りベクトル
6.2 出力生成
基本構成は次の通り：
$$
\text{PRG}(e) = \mathrm{Ext}(eH)
$$
ここで：
- $( \mathrm{Ext} )$：ビット抽出関数
（全ビットをそのまま使わず、部分的に用いる）
例
$$
\text{output} =
(s_1, s_2, \dots, s_k)
\quad \text{where } s = eH
$$
または カウンタ$i$ を用いて：
$$
s_i = H(e \parallel i)
$$
7. 安全性考察
7.1 擬似乱数性
攻撃者が区別しようとする場合：
- ランダム列
- 本 PRG 出力
を区別できれば、
→ 低重み誤り復元問題を解ける
→ 矛盾
7.2 IND-CPA との関係
本 PRG を用いて：
- ランダムマスク生成
- ストリーム暗号構成
を行えば、
Niederreiter 型暗号と同様に IND-CPA 安全性が得られる。
8. 実装上の注意
8.1 やってはいけないこと
- 同じ ( e ) の再利用
- 出力を線形にすべて公開
- 重みが小さすぎる設定
8.2 推奨
- nonce / カウンタを付加
- 出力ビットを制限
- 復号は秘密鍵側のみで使用
9. 関連研究との位置付け
| 構成 | 本方式 |
|---|---|
| McEliece | 類似 |
| Niederreiter | ほぼ同型 |
| LPN-based PRG | 同思想 |
| Goppa-based PRG | 本記事 |
10. おわりに
本記事では、Goppa 符号に基づく復号困難性を一方向関数として捉え、
そこから暗号学的に安全な疑似乱数生成器を構成した。
この構成は：
- 既存理論に基づく
- 実装可能
- IND-CPA 暗号への拡張も自然
という特徴を持つ。
「符号理論は暗号のための乱数源である」という視点を
改めて示す一例になれば幸いである。
具体例の構成（Hashなし）
パターソン復号ベース秘密鍵暗号の非線形設計
1️⃣ 前提
- 秘密鍵 (T)：パターソン復号用の Goppa 多項式 (g(x))
- 平文 (m)：暗号化したいデータ（ビット列）
- ランダム化 (l)：誤り位置ベクトル
- 暗号文 (c)：復号器 Dec(T,·) を通して生成
- 再帰入力：暗号文の一部を次回暗号化の誤り位置決定に利用
2️⃣ 非線形性の確保
- パターソン復号自体が 多項式演算＋平方根計算 で非線形性を提供
- Hash を使わなくても、誤りベクトル (e) の生成に秘密鍵 (T) とランダム位置 (l) を組み合わせるだけで十分非線形
例：誤りベクトル生成
$$
e = f(T, l, m) = Dec(T, g)
$$
- (g) は平文 (m) とランダム位置 (l)、秘密鍵 (T) から生成
- (Dec(T,g)) はパターソン復号の非線形演算により、単純な線形予測は困難
3️⃣ 再帰入力の構造
- 暗号文 (c) の一部を次回暗号化に利用することで擬似乱数的な変動を作る
- Hash を使わずに、 線形写像や置換 を用いて再帰入力を作る
再帰入力例
$$
l_{\text{next}} = \pi(c_{\text{half}})
$$
- $(c_{\text{half}})$：暗号文の半分
- $(\pi)$：公開された置換関数
- この方法で、暗号文の出力と次回暗号化の入力の間に非線形な依存関係が生成される
Hash に頼らず、暗号文自身の情報を再利用することで疑似乱数効果やカウンタ効果を実現
4️⃣ アルゴリズム概略
- ランダム位置 (l) を生成
- 平文 (m) と (l)、秘密鍵 (T) から符号多項式 (g) を作る
- $(Dec(T,g) \rightarrow e)$ を計算
- 暗号文 (c = e) とする
- 暗号文の一部 ($c_{\text{half}}$) を再帰入力として次回の ($l_{\text{next}}$) を決定
5️⃣ 特徴
- Hash 関数不要：全てパターソン復号の演算＋置換で非線形性確保
- 再帰構造：暗号文から次回入力を生成
- 疑似乱数的効果：暗号文が次の暗号化に影響を与えるため、固定平文に対するパターンを避けられる
- 量子耐性の可能性：McEliece 系の安全性がそのまま利用可能（パラメータ次第）
💡 ポイント
- Hash は補助的にしか使わない設計より、暗号構造そのもので非線形性を担保する方が評価しやすい
- 再帰入力は 暗号文自身の一部 + 置換関数 で実現可能
- これにより Hash を使わず安全性を理論的に検討できる秘密鍵暗号 が設計可能
もし希望なら、次のステップとして Python 擬似コードでの動作例 も作れます。
作りますか？