技術的概要：RankGuard-Polar

問題定義

本論文は、機密メッセージの情報理論的秘匿性を維持しつつ、共有公共リソース（例：ブロードキャストリンク、クラウドストレージ）上でポラール符号の符号語座標の一部分を安全に公開する課題に取り組む。古典的なワイヤーテップシナリオでは盗聴者がノイズのあるチャネルの出力を観測するが、本研究は公共リソースのチャネル入力に直接アクセスできる「強力な盗聴者」を想定する。核心的な運用上の問いは、特定の符号語座標を公共チャネル上で意図的に露出させた場合、機密メッセージについてどれだけの情報が漏洩するか、である。

著者は、送信者がプライベートチャネルとパブリックチャネルの間で時間共有を行う枠組みにおいて、特に有限長のポラール符号（二項体 $\mathbb{F}_2$ 上）に焦点を当てる。目的は、情報ビットの独立した線形結合を露出させることなく、どのインデックスを公開できるかを決定することであり、そのためには「凍結ビット」が正当な受信者のみが知る新しい秘密の乱数（マスク）として機能し得る、ポラール符号の固有の構造を利用する。

手法

提案される枠組み RankGuard-Polar は、ポラール生成行列の部分行列のランク特性から導出される、情報漏洩の正確な代数的特徴付けに依存する。

1. システムモデル

• エンコーダ: エンコーダは符号語 $x = uG_N$ を生成する。ここで $u = (u_A, u_F)$ は情報ビット ($u_A$) と凍結ビット ($u_F$) から構成される。重要なのは、$u_F$ が一様分布 ($\text{Bernoulli}(1/2)$) から i.i.d. に抽出され、エンコーダとデコーダ間の共有秘密鍵として機能するが、敵対者には未知である点である。
• 公開露出: インデックスの部分集合 $P \subset [1:N]$ が公開される。盗聴者は $x_P = u_A G_{A,P} \oplus u_F G_{F,P}$ を観測する。ここで $G_{A,P}$ と $G_{F,P}$ は、それぞれ行 $P$ と列 $A$ および列 $F$ に制限された生成行列の部分行列である。
• 漏洩の定義: 漏洩は相互情報量 $L(P) = I(u_A; x_P)$ として定義される。

2. 漏洩恒等式

本論文は、相互情報量と行列のランクを結びつける基本的な恒等式を確立する：
$$L(P) = \text{rank}(G_P) - \text{rank}(G_{F,P})$$
ここで、$G_P$ は $G_N$ の行 $P$ とすべての列に制限された部分行列であり、$G_{F,P}$ は行 $P$ と凍結列 $F$ に制限された部分行列である。

• 解釈: $L(P)$ は、盗聴者が公開観測 $x_P$ から復元できる情報ベクトル $u_A$ の独立した線形結合の数を表す。
• 漏洩証明書: $L(P) = 0$ の場合、$u_A$ に関する情報は一切露出しない（$G_{A,P}$ の列は完全に $G_{F,P}$ の列空間内に存在する）。$L(P) = r > 0$ の場合、最大 $r$ 個の独立した情報ビットが露出する。

3. 構成的抽出

本論文は、$L(P) = r$ である場合、明示的な線形抽出行列 $R$ が存在することを証明する：

1. $G_{F,P} R = 0$（凍結ビットの影響を排除）。
2. $\text{rank}(G_{A,P} R) = r$。
   公開観測に $R$ を乗算すると $x_P R = u_A (G_{A,P} R)$ となり、盗聴者にメッセージビットに関する $r$ 個の独立した線形方程式が提供される。

4. 選択アルゴリズム (ScoreGreedy)

漏洩を最小化するためにサイズ $k$ の最適な集合 $P$ を網羅的に探索することは、組み合わせ的に高価である ($O(\binom{N}{k} \cdot Nk^2)$) ため、著者は ScoreGreedy (SG) アルゴリズムを提案する：

• スコア付け: 各行 $i$ に対して、$s_i = f_i - a_i$ に基づいてスコアを算出する。ここで $f_i$ はその行における凍結列の非ゼロ要素の数、$a_i$ はその行における情報列の非ゼロ要素の数である。
• 選択: アルゴリズムは、最も高いスコアを持つ上位 $k$ 行を選択する。
• 理論的 bound: 定理 3 は決定論的上界を提供し、選択された集合に対する $a_i$ の和が漏洩を束縛することを示す。これにより、情報列との接触を最小化しつつ凍結列との接触を最大化するという代理目的関数が正当化される。

主要な貢献

1. 正確な漏洩証明書: 有限長のポラール符号における任意の公開インデックス集合に対する、正確かつ漸近的でない情報漏洩の尺度を提供する、ランク差の恒等式 $L(P) = \text{rank}(G_P) - \text{rank}(G_{F,P})$ の導出。
2. 構成的抽出器: 特定の公開集合 $P$ によって漏洩するメッセージビットの線形結合を明示的に構築する行列 $R$ の存在証明。
3. 効率的な認証手順: 漏洩を計算し、任意のインデックス集合の安全性を認証する効率的なアルゴリズムの開発。漸近的な秘匿レート分析を超えて、有限ブロック長保証へと移行。
4. 実用的な選択アルゴリズム: 漏洩を最小化する公開インデックスを選択するための高速 ($O(N^2)$) ヒューリスティックである ScoreGreedy アルゴリズムの導入。理論的上界によって検証済み。

結果と例

本論文は、理論的証明と例示的な例（例：$N=4$ のポラール符号）を通じて枠組みを検証する：

• シナリオ 1: 情報ビットを直接運ぶ座標を公開すること（例：$x_4 = u_4$）は $L(P)=1$ をもたらし、そのビットを完全に露出させる。
• シナリオ 2: 情報ビットと凍結ビットの線形結合である座標を公開すること（例：$x_1 = u_4 \oplus u_3 \oplus u_2 \oplus u_1$）は、凍結ビットが効果的に情報ビットをマスクする場合、$L(P)=0$ となり、独立した線形結合は一切露出しない。
• 混合集合: 一部のビットがマスクされているにもかかわらず、座標の集合が情報ビット間の線形関係を露出させる場合、本枠組みは部分的な漏洩（例：$L(P)=2$）を正確に定量化する。

意義と主張

著者は、RankGuard-Polar を公共リソースを利用するシステムのための 運用上の監査・制御レイヤ として位置づける。

• 有限長焦点: ブロック長 $N \to \infty$ における漸近的な秘匿レートに依存することが多い古典的なワイヤーテップ文献とは異なり、本研究は正確な有限-$N$ 保証を提供する。
• 強力な敵対者モデル: この枠組みは、チャネル出力を観測する標準的なワイヤーテップモデルとは異なり、チャネル入力を観測する強力な盗聴者を想定して設計されている。
• 実用性: この手法は漸近的なワイヤーテップ構成を置き換えるものではないが、スループット向上やコスト削減のために混合されたパブリック/プライベートチャネルの使用が不可欠な実システムにおいて、漏洩を認証し制御するメカニズムを提供する。
• 代数的透明性: 秘匿性を線形代数（行列のランク）に還元することで、複雑な暗号学的仮定や秘密の生成行列に依存することなく、セキュリティ特性を検証する透明性があり計算可能な方法を提供する。

本論文は、RankGuard-Polar により、どの符号語座標を露出させ、どれだけの情報が侵害されるかを正確に決定するための厳密で構成的な方法を提供することで、公共チャネルの安全な活用が可能になると結論づけている。