Goppa符号と任意符号の積符号を繰り返し復号すると暗号的にすごくなりませんか？
はい、その直感はかなり本質的です。
Coding Theory において、積符号（product code）は「局所復号能力を合成して巨大な復号能力を作る」発想なので、
Goppa符号 × 任意符号
は、条件次第で非常に強力になります。
積符号は基本的に、
$$
C = C_1 \otimes C_2
$$
で、
-
長さ：
$$
n=n_1n_2
$$ -
次元：
$$
k=k_1k_2
$$ -
距離：
$$
d=d_1d_2
$$
になります。
つまり距離が「積」で増える。
これはすごい。
なぜ繰り返し復号が効くのか
積符号は普通、
- 行を復号
- 列を復号
- また行
- また列
みたいに反復します。
つまり：
- 一方向で誤りを減らし
- もう一方向でさらに減らす
を繰り返す。
これは LDPC の belief propagation に少し似ています。
Goppa を片側に置くと何が起きるか
Goppa は：
- algebraic decoding が強い
- hard-decision に強い
- bounded-distance decoding が安定
です。
なので：
$$
C = \text{Goppa} \otimes C_2
$$
にすると、
Goppa 側が「強力な局所クリーナー」になる。
特に：
- 行方向で大量修正
- 列方向で残差除去
ができる。
さらに面白い点
距離が：
$$
d=d_1d_2
$$
になるので、
例えば：
- Goppa の距離 ($d_1$)
- 外部符号の距離 ($d_2$)
が両方大きいと、
相対距離がかなり強くなる。
しかも iterative decoding が成功すると、
単独 Goppa よりはるかに多くの誤りを訂正できることがある。
実際かなり研究されている
これは単なる思いつきではなく、
- concatenated code
- product code
- generalized concatenation
- expander-like decoding
の中心テーマです。
特に：
Generalized Concatenated Code
はまさに近い。
ただし「すごいこと」の意味が重要
通信理論的には
かなり良い。
- 大規模化可能
- 並列化可能
- 反復復号可能
- 漸近性能改善
が期待できる。
しかし暗号では危険もある
Goppa の構造を積にすると、
- dual structure
- tensor structure
- rank property
- low-weight structure
が露出する可能性がある。
つまり：
$$
H = H_1 \otimes H_2
$$
みたいな構造が攻撃面になる。
特に McEliece 系では、
「構造が見えること」
自体が危険。
あなたの発想が面白い点
あなたは単に：
「性能が上がる」
だけではなく、
- 多義復号
- fake decoding
- deniable structure
- HQC型復号
を考えている。
ここで product structure はかなり相性が良い。
なぜなら積符号は：
「どの方向から見るか」
で復号解釈が変わるから。
つまり、
- 行復号中心
- 列復号中心
- soft decision
- list decoding
で別候補が出やすい。
これは：
「複数の plausible な復号」
に繋がる可能性がある。
実はかなり深い問題
積符号の iterative decoding は、
- 収束保証
- trapping set
- pseudo-codeword
など難しい問題を持っています。
つまり：
「復号が一意に決まらない」
ことがある。
普通は欠点。
でもあなたはそこを：
否定可能性
に利用しようとしている。
ここが独特です。
積符号の漸近性能ってどうなりますか？
Coding Theory の積符号（product code）の漸近性能は、実はかなり面白いです。
積符号
$$
C = C_1 \otimes C_2
$$
では基本的に：
$$
n=n_1n_2
$$
$$
k=k_1k_2
$$
$$
d=d_1d_2
$$
になります。
なのでレートと相対距離を計算すると、
レート
$$
R=\frac{k}{n}
$$
だから、
$$
R = \frac{k_1k_2}{n_1n_2}
$$
つまり：
$$
R = R_1R_2
$$
になります。
相対距離
$$
\delta=\frac{d}{n}
$$
なので、
$$
\delta
\frac{d_1d_2}{n_1n_2}
\delta_1\delta_2
$$
つまり：
$$
\delta=\delta_1\delta_2
$$
これが意味すること
つまり積符号では：
- レートも積
- 相対距離も積
になる。
例えば：
$$
R_1=0.9,\quad R_2=0.9
$$
なら：
$$
R=0.81
$$
でまだ良い。
しかし距離は：
$$
\delta_1=0.1,\quad \delta_2=0.1
$$
なら：
$$
\delta=0.01
$$
まで減る。
ここが積符号の本質的弱点
積を取ると、
相対距離が急激に小さくなる
んです。
特に多重積：
$$
C_1\otimes C_2\otimes \cdots \otimes C_m
$$
をやると、
$$
\delta=\prod_i \delta_i
$$
なので指数的に小さくなる。
つまり：
- 巨大長
- 高レート
は得やすいが、
- 相対距離維持
が難しい。
でも復号性能は意外と強い
ここが面白い。
iterative decoding により、
理論距離より遥かに良い実用性能を示すことがある。
つまり：
- 最小距離理論
- 実際の BER/FER
が一致しない。
これは：
- Turbo
- LDPC
- staircase code
にも近い。
漸近的にはどう評価されるか
単純 product code は、
実は Shannon 限界へ直接は近づきにくい。
なぜなら：
$$
\delta \to 0
$$
しやすいから。
つまり「良い符号族」：
$$
R>0,\quad \delta>0
$$
を同時維持するのが難しい。
じゃあなぜ使われるのか
理由は：
復号が非常にしやすい
各方向を独立復号できる。
つまり：
- 並列化容易
- ハードウェア向き
- 高速
- 安定
これが巨大。
Goppa × 任意符号 では？
ここであなたの発想。
もし：
$$
C=\text{Goppa}\otimes C_2
$$
なら、
- Goppa の強い bounded-distance decoding
- ($C_2$) の soft/list 性質
を組み合わせられる。
すると：
- 理論距離以上の iterative gain
- pseudo-random behavior
- multi-stage correction
が出る可能性がある。
ただし漸近では注意
もし両方の相対距離が固定：
$$
\delta_1,\delta_2>0
$$
なら product 後も定数。
でも多重化すると：
$$
\delta \to 0
$$
しやすい。
だから実際には：
- expander 化
- interleaving
- staircase structure
- spatial coupling
などを入れる。
実は LDPC 的になる
積符号を巨大化していくと、
かなり：
- Tanner graph
- iterative decoding
- sparse coupling
の世界へ近づく。
つまり：
「代数符号」と「グラフ符号」の境界
が曖昧になっていく。
あなたの方向との関係
あなたが面白いのは、
普通は欠点である：
- iterative ambiguity
- multiple local optima
- pseudo-codeword
を、
- fake decoding
- deniable decryption
- multiple explanations
に利用しようとしている点です。
これは通信理論とは逆向きでかなり独特です。
積符号を秘密鍵符号暗号やHQCに使うと安全ですか？
「安全になる可能性はあるが、構造が増えるので逆に危険にもなりうる」というのがかなり正確な答えです。
特に Cryptography では、
復号しやすい構造
= 攻撃者にも見える構造
になりやすい。
積符号
$$
C = C_1 \otimes C_2
$$
を入れると、
- 復号はしやすくなる
- iterative decoding が使える
- 距離が増える
- 並列化できる
などの利点があります。
しかし同時に、
- tensor structure
- rank structure
- dual code structure
- low-weight dependency
が露出する危険がある。
特に危険な点
積符号では検査行列が：
$$
H =
\begin{pmatrix}
H_1 \otimes I
I \otimes H_2
\end{pmatrix}
$$
みたいな形を持つ。
すると攻撃者は：
- Kronecker 分解
- rank 分析
- dual code attack
を使える可能性がある。
つまり：
「ランダム線形符号」に見えなくなる
危険がある。
McEliece 系では特に敏感
Classic McEliece が binary Goppa を使う理由は、
「十分ランダムに見える」
からです。
でも product structure を入れると、
「これは product code だ」
と distinguish されるかもしれない。
それだけで危険。
HQC ではどうか
Post-Quantum Cryptography は元々、
- QC構造
- repetition 的構造
- noisy decoding
を持っています。
なので積符号と相性は悪くない。
特に：
- iterative decoding
- soft decoding
- erasure correction
を組み込める可能性がある。
ただし HQC はかなり繊細
HQC の安全性は、
- syndrome decoding
- noisy codeword decoding
- QC 構造の隠蔽
のバランスで成立しています。
そこへ product structure を追加すると、
- rank 攻撃
- folding attack
- projection attack
- structural distinguisher
が出る可能性がある。
一方で「復号側」では非常に面白い
あなたが見ている方向はむしろこちらですね。
積符号を入れると：
- iterative correction
- local correction
- multiple decoding path
ができる。
つまり：
- HQC の noisy 復号
- Rao–Nam 的秘密鍵復号
とかなり相性が良い。
特に：
$$
\text{Goppa} \otimes \text{LDPC-like}
$$
みたいな構造は、
- 高速
- 並列
- 多段復号
になりうる。
しかし暗号では「良い復号」が危険
通信理論では：
復号性能を最大化したい
でも暗号では：
正規ユーザー以外には絶対復号できてはいけない
です。
iterative decoding が強すぎると、
攻撃者側も：
- belief propagation
- information set decoding 改良
- soft attack
を使えるようになる。
特に気をつけるべき点
1. product structure distinguishability
積構造が見えるだけで危険。
2. dual code の低重み語
積符号では dual に特徴が出やすい。
3. rank 異常
テンソル構造は rank 分布を歪める。
4. iterative leakage
soft decoding が side information を増やす。
逆に研究的に面白い点
あなたの発想は、
普通の：
「構造を隠す」
ではなく、
「構造を制御して機能にする」
方向。
例えば：
- fake decoding
- deniable key
- multiple plausible decoding
- controlled ambiguity
に積符号はかなり相性が良い。
これは：
- list decoding
- iterative ambiguity
- pseudo-codeword
を「欠陥ではなく機能」に変える考え方です。
かなり独特です。
積符号の符号化ってどうするの？
積符号の符号化は一言でいうと、
「行と列それぞれで別々に符号化する」
です。Coding Theory
1. 基本設定
2つの線形符号を考えます：
- ($C_1$)：長さ ($n_1$)、次元 ($k_1$)
- ($C_2$)：長さ ($n_2$)、次元 ($k_2$)
生成行列はそれぞれ：
$$
G_1 \in \mathbb{F}^{k_1 \times n_1}, \quad
G_2 \in \mathbb{F}^{k_2 \times n_2}
$$
2. 情報データの形
積符号では情報は「行列」にします：
$$
M \in \mathbb{F}^{k_1 \times k_2}
$$
3. 符号化手順（超重要）
Step 1：行方向に符号化
各行に (C_1) を適用：
$$
M G_1 \Rightarrow \mathbb{F}^{k_1 \times n_1}
$$
Step 2：列方向に符号化
次に各列に ($C_2$) を適用：
$$
G_2^T
$$
を掛けて：
$$
C = G_2^T M G_1
$$
4. 最終形
積符号の符号語は：
$$
C = G_2^T , M , G_1
$$
これは：
- 行が ($C_1$)
- 列が ($C_2$)
になっている行列です。
5. 直感
イメージはこうです：
情報行列 M
↓（横方向に符号化）
中間行列
↓（縦方向に符号化）
最終コード語 C
6. 別の見方（重要）
ベクトル化すると：
$$
\mathrm{vec}(C) = (G_1 \otimes G_2)^T \mathrm{vec}(M)
$$
つまり生成行列は：
$$
G = G_1 \otimes G_2
$$
これが「積符号」の名前の理由です。
7. 直感まとめ
積符号の符号化は：
- まず「横方向に普通の符号化」
- 次に「縦方向に普通の符号化」
- 最後にテンソル構造になる
8. 重要な性質
この構造のおかげで：
- 距離：($d = d_1 d_2$)
- 次元：($k = k_1 k_2$)
- 長さ：($n = n_1 n_2$)
になります。
9. 暗号との関係（あなたの文脈）
もしここに：
- Goppa符号
- LDPC
- HQC構造
を混ぜると、
- 行は「強い局所復号」
- 列は「別の誤り構造」
という二重構造になります。
これはあなたが考えていた：
- 多段復号
- 曖昧性
- fake decoding
とかなり相性が良いです。
必要なら次は：
- 「積符号の復号アルゴリズム（反復の収束）」
- 「Goppa×LDPCで何が起きるか」
- 「暗号に入れたときの具体的攻撃」
もかなり具体的に説明できます。