🔢 mathematics

List-Decoding Counterexamples Yield Lower Bounds on Mutual Correlated Agreement Error

本論文は、リスト復号不可能性に対する明示的な反例が、高い相互相関一致誤差を持つことが証明された符号へと構成的に変換可能であることを示し、それによって、代数幾何符号およびリード・ソロモン符号におけるリスト復号の失敗と、この特定の誤差指標に対する下界との間の直接的な関連性を確立するものである。

原著者： Yiwen Gao, Hong Yang, Yang Xu, Haibin Kan

公開日 2026-07-14

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Yiwen Gao, Hong Yang, Yang Xu, Haibin Kan

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、スパイ（コードワード）のグループがセキュリティ・チェックポイント（コード）をすり抜けようとしているのを捕まえようとしている、ある探偵だと想像してください。デジタル通信の世界では、これらの「スパイ」は、ノイズによってわずかに形を変えられたメッセージです。通常、メッセージが正しいパターンから離れすぎていると、セキュリティ・システムは「いや、それは有効なメッセージではない」と言って、それを破棄します。

しかし、時として厄介なことが起こります。単一の形を変えられたメッセージが、同時に多くの異なる有効なスパイ・パターンに怪しく近い状況を想像してみてください。符号理論の世界では、これは**リスト復号の反例（list-decoding counterexample）**と呼ばれます。これは、容疑者が群衆の中にいる5人の別々の人物の記述に当てはまってしまうようなものです。この場合、標準的なセキュリティ・チェックは混乱し、「まあ、そのうちの一人かもしれない」と言ってしまうかもしれません。本来はそうあるべきではないのに。

Yiwen Gao、Hong Yang、Yang Xu、そして Haibin Kan によるこの論文は、この特定の、非常に重要なバージョンの問題に取り組んでいます。彼らは、**相互相関合意（Mutual Correlated Agreement）**というセキュリティ・テストについて調べています。このテストは、形を変えられたメッセージの「グループ全体」が、ランダムに混ぜ合わされたとき（例えば、5つのスムージーを1つにブレンドするように）、依然として有効なスパイ・パターンに見えるかどうかを確認するものです。

大きな発見：「悪いミックス」のレシピ

著者たちは、非常に具体的な、構成的な事実を証明しています。もし、リスト復号の反例（多くの有効なコードに近く見えるメッセージ）を見つけることができるなら、それを使って、「相互相関合意」テストに確実に失敗する、少し異なる新しいコードを構築できるということです。

ここで使われている魔法のトリックを、キッチンでの比喩で説明しましょう。

セットアップ： あなたには、 $L+1$ 個の異なる「有効な」レシピ（コードワード）のリストがあります。これらはすべて、奇妙に形を変えられた料理（受信語）に対して、驚くほど似た味を持っています。
拡張： 著者たちは元のコードを取り、すべてのレシピに一つの追加の「材料」（座標）を加えます。これにより、2つの特別な料理、 $\pi_0$ $π_{0}$ と $\pi_1$ $π_{1}$ が作成されます。
- $\pi_0$ は、元の形を変えられた料理の最後にゼロを加えたものです。
- $\pi_1$ は、最後に一つの「1」がある以外はすべてゼロである料理です。
混ぜ合わせ： 次に、これら2つの料理を、秘密のスパイスの量 $\alpha$ $α$ を使って混ぜ合わせると想像してください。新しい料理は $\pi_0 + \alpha \cdot \pi_1$ $π_{0} + α \cdot π_{1}$ です。
- 元の料理の部分については、依然として形を変えられた単語のように見えます。
- 一番最後では、スパイスの量 $\alpha$ と全く同じ味になります。
罠：元の形を変えられた単語が $L+1$ 個の異なる有効なレシピに近いということは、 $L+1$ 個の特定のスパイスの量（ $\alpha$ の値）が存在し、それらが混合された料理を、新しい材料を含めた一つの有効なレシピに完璧に一致させることを意味します。
グリッチ（不具合）： しかし、2つの料理 $\pi_0$ と $\pi_1$ 自体は、この新しい、より大きな材料のセットにおいて、コードとの共通のパターンを共有していません。つまり、混合プロセスによって、存在するはずのない「偽の」合意が作り出されたのです。

論文は、これら $L+1$ 個の近くにあるコードワードがある場合、少なくとも一定数のこれらの「悪いスパイスの量」（悪い結合点）が存在することを証明しています。具体的には、悪い点の数は以下の通りです：
$\left\lceil \frac{(L+1)q}{q+L} \right\rceil$
ここで、 $q$ は「フレーバー・パレット」（有限体）のサイズです。

「パンクチャー・アンド・アペンド」の魔法のトリック

一つ問題があります。その追加の材料を加えたことで、料理が大きくなってしまいました（コード長が増加しました）。しかし、現実の世界では、メッセージのサイズを勝手に変えることはできません。サイズは同じである必要があります。

著者たちは、巧妙な「パンクチャー・アンド・アペンド（穿孔と付加）」という操作を行います。

パンクチャー（穿孔）： 著者たちは元のコードから、コードの構造を壊さない一つの材料（座標）を取り除きます。これにより、コードはわずかに小さくなります。
アペンド（付加）： 先ほど見つけた新しい「悪い」材料を付け加えます。
結果： コードは元のサイズに戻りました！

論文は、この新しいコード $C'$ が、元のコードとほぼ同一であることを示しています。セキュリティ・マージン（最小距離）は最大でも $1/n$ だけ減少しますが、これは相互相関合意テストにおいて高いエラー率を持つことが保証されています。実際、エラー確率は少なくとも次の方になります：
$\frac{1}{q} \left\lceil \frac{(L+1)q}{q+L} \right\rceil$

形を保つこと：構造保存型コード

著者たちはそこで止まりませんでした。彼らは、現実の世界では、コードはリード・ソロモン符号（CDやQRコードで使用される）や代数幾何（AG）符号のように、特別な「形」を持っていることが多いことを知っていました。これらのコードは単なる数字のリストではなく、特定の数学的な写像（特定の点における多項式の評価など）を使用して構築されています。

論文は、単にランダムな材料を投げ込むことはできず、それはレシピに適合しなければならないと主張しています。著者たちは、コードの特別な構造を保ったまま、この「パンクチャー・アンド・アペンド」のトリックを実行できることを示しています。

リード・ソロモン符号の場合、一つの評価点を別の評価点と入れ替えるだけです。
AG符号の場合、一つの「場所」（幾何学的形状上の点）を別の場所に置き換えます。

彼らは、たとえこれらの厳格なルールがあっても、元のコードにリスト復号の反例が存在する場合、同じファミリー内の新しいコードを構築でき、それが相互相関合意テストにおいて高いエラー率を持つことを証明しています。

この論文が述べて「いない」こと

この論文が何をしていないかを知っておくことは重要です。

これらのコードがすべての目的において壊れていると言っているわけではありません。これは、特定の「相互相関合意」の失敗が存在することを示しているに過ぎません。
問題を解決すると主張しているわけでもありません。むしろ、エラー確率を限りなくゼロにすることは不可能であることを示すための、反例を構築しています。これは「不可能性の証明」です。
これがすべてのコードで起こることを示唆しているわけでもありません。これは、リスト復号の反例（ $L+1$ 個の近くのコードワードがあるメッセージ）が存在する場合にのみ適用されます。

どれほどの確信度か？

著者たちは非常に自信を持っています。彼らは単に推測したり、コンピュータでシミュレーションしたりしているわけではありません。彼らは**構成的な証明（constructive proof）**を提供しています。これは、単に「可能である」と言ったのではなく、新しいコードと、エラーの存在を証明する証拠となる単語のペアを構築するための、ステップ・バイ・ステップのレシピ（アルゴリズム）を与えたことを意味します。

彼らは、受信語と $L+1$ 個の近くのコードワードが与えられたとき、この構成法が新しいコードと証拠となる単語を明示的に生成することを明記しています。これは、単なる示唆ではなく、数学的な事実です。

好奇心旺盛なティーンエイジャーへのまとめ

この論文を、「特定の種類のセキュリティ・テストを、ループホール（抜け穴）を使って突破する方法」のマスタークラスだと考えてください。

ループホール： メッセージが多くの有効なコード（ $L+1$ ）に近い場合、システムはすでに困難な状況にあります。
突破： 著者たちは、他の2つのメッセージを混ぜ合わせることで、「偽の」有効なメッセージを作り出す方法を示しています。
結果： エラー率は $1/q$ に $L$ と $q$ を含む特定の数を掛けたもの以上になると証明できます。

この論文は本質的にこう言っています。「もしリスト復号の反例があるなら、あなたのコードがこれらの混合攻撃に対して完全に安全であると主張することはできません。ここに、その攻撃を構築する方法と、エラーがどの程度になるかの正確な数学的根拠があります。」

リード・ソロモン符号（QRコードに使われているもの）の場合、エラーの下限は次のようになります：
$\frac{1}{q} \left\lceil \frac{(L+1)q}{q+L(k-1)} \right\rceil$
ここで $k$ はコードの次元です。

論文は、結論として、「リスト復号可能性」と「相互相関合意」の関係は密接であることを示しています。一方が失敗すれば、もう一方も必ず失敗します。そして、ここにはそれを証明するための正確な数学があります。

技術要約：リスト復号の反例による相互相関合意誤差の下界

1. 問題提起

本論文は、線形符号の文脈における**相互相関合意（Mutual Correlated Agreement; MCA）**という根本的な問いに取り組んでいる。MCAは、バッチ近似テスト（簡潔な非対話型知識証明（SNARKs）や、近傍プロキシティ・インタラクティブ・オラクル証明（IOPPs）で使用されるメカニズム）の健全性に不可欠な特性である。

具体的には、MCAは、受信された語のランダムな線形結合が、元の語の相関合意構造によって説明できないにもかかわらず、誤って大きな合意ドメインを生成してしまうかどうかを調査するものである。様々な符号族に対して、ある程度の境界までは正の結果（近傍性のギャップ）が存在するが、コードがリスト復号可能でない場合に、エラー確率（「悪い」結合点の発生確率）がどの程度大きくなり得るかを理解する必要がある。

核心となる問題は、リスト復号の反例（特定の距離内に $L$ 個を超える符号語を持つ受信語）と、MCA誤差の下界との間に、構成的かつ直接的な関連性を確立することである。先行研究では、リスト復号可能性と相関合意との関連性が示されているが、本論文は、コード族の構造的特性を維持しつつ、リスト復号の失敗からMCA誤差の明示的な下界を導出するための、一般的かつ構成的な手法を提供することを目的としている。

2. 手法

著者らは、**「パンクチャ・アンド・アペンド（穿孔と付加）」**技術を中心とした構成的なアプローチを採用している。この手法は、以下の3つの論理的段階で進行する。

ドメイン外への拡張（Out-of-Domain Extension）:
$(p, L)$ -リスト復号可能ではない線形符号 $C$ から出発し、著者らは受信語 $y$ と、距離 $p$ 以内にある $L+1$ 個の異なる符号語 $c_1, \dots, c_{L+1}$ を特定する。次に、新しい座標を付加することで、長さ $n+1$ の拡張符号 $C'$ を構成する。
- 拡張ドメイン上の2つの語 $\pi_0$ と $\pi_1$ を定義する。 $\pi_0$ は元の受信語 $y$ （ゼロを付加したもの）を運び、 $\pi_1$ は元のドメインではゼロであり、新しい座標では1となる。
- 著者らは、線形代数的な衝突境界（補題1）を利用して、ベクトル $a$ （生成行列の付加される列を定義するもの）を選択する。これにより、 $m_i \cdot a^T$ の値（ここで $m_i$ は近傍の符号語のメッセージベクトルである）が、多数の異なる値を含むようにする。
- それぞれの異なる値は、「悪い結合点」 $\alpha$ に対応する。この点において、線形結合 $\pi_0 + \alpha \pi_1$ は、拡張された符号語と大きな集合上で一致するが、元のペアとの相関合意は持たない。
パンクチャ・アンド・アペンド（長さの保存）:
結果として得られる符号が元のブロック長 $n$ と同じであることを保証するため、新しいものを付加する前に、元の符号から1つの座標をパンクチャ（除去）する。
- 元の符号が $(p, L)$ -リスト復号可能でない場合、次元と非リスト復号性を（相対距離パラメータのわずかな調整を伴いつつ）保持する座標の除去が存在することを証明する。
- この「1つをパンクチャし、1つを付加する」手順により、拡張ステップで導出された大きな悪い結合点の集合を保持したまま、長さ $n$ の符号 $C'$ が得られる。
構造保存型の一般化（Structure-Preserving Generalization）:
これを特定の符号族（リード・ソロモン符号や代数幾何符号など）に適用するために、著者らはこの構成をインデックス付き符号族へと一般化する。
- 付加される列のために任意のベクトルを選択する代わりに、写像 $v: \Omega \to \mathbb{F}_q^k$ を用いて、有限集合 $\Omega$ からインデックスを選択する。
- インデックス集合に対する衝突境界 $\lambda$ を導入し、異なるメッセージが利用可能なインデックス上で頻繁に衝突しないことを保証する。これにより、構成が（例えば、AG符号において評価点を1つ変更するだけで済むように）同じ符号族内に留まることが可能になる。

3. 主な貢献と結果

定理1（一般線形符号）:
本論文は、次元 $k$ および長さ $n$ の線形符号 $C$ が $(p, L)$ -リスト復号可能でない場合（ $p < \Delta(C) - 1/n$ ）、以下の条件を満たす関連する符号 $C'$ が存在することを確立する：
$\text{err}_{\text{MCA}}(C', p) \geq \frac{1}{q} \left\lceil \frac{(L+1)q}{q+L} \right\rceil$
さらに、 $C'$ の相対最小距離は $\Delta(C') \geq \Delta(C) - 1/n$ を満たす。もし $C$ の最小重み符号語がすべての座標をカバーしていない場合、距離は正確に保持される（ $\Delta(C') \geq \Delta(C)$ ）。この構成は明示的であり、 $C'$ と誤差を証拠立てる一対の語の両方を作成する。

定理2（構造保存版）:
列写像 $v$ を持つインデックス集合 $\Omega$ によってインデックス付けされた符号族について、衝突境界 $\lambda$ （任意の非ゼロベクトル $u$ が、 $u \cdot v(\omega)^T = 0$ となるインデックス $\omega$ を最大で $\lambda$ 個持つ）を仮定すると、この構成は同一のファミリー内の符号 $C'$ をもたらす。

$C'$ は、 $C$ の座標インデックスを最大で1つだけ変更したものである。
MCA誤差の下界は以下のようになる：
$\text{err}_{\text{MCA}}(C', p) \geq \frac{1}{q} \left\lceil \frac{(L+1)N}{N+L\lambda} \right\rceil$
ここで $N = |\Omega|$ である。

特定の符号族に対する系:

代数幾何（AG）符号: $\Omega$ を有理点集合とし、 $\lambda = \deg(G)$ と設定することで、AG符号がリスト復号可能でない場合、評価因子 $D$ を最大で1つの点を変更することで、指定されたMCA誤差の下界を持つ符号が得られることを示す。結果として得られる符号は、同一の関数体およびリーマン・ロッホ空間上に留まる。
リード・ソロモン（RS）符号: $\Omega = \mathbb{F}_q$ および $\lambda = k-1$ （多項式の次数）である特殊なケースとして、この結果は $\frac{1}{q} \lceil \frac{(L+1)q}{q+L(k-1)} \rceil$ という誤差の下界を与える。これは、RS符号におけるリスト復号の失敗が、直接的に重大なMCA誤差を意味することを裏付けている。

4. 意義と主張

本論文は、リスト復号の反例を、相互相関合意誤差の下界へと変換するための構成的かつ一般的な手法を提供することを主張している。

先行研究との対比: 著者らは、先行研究（Ben-Sassonら、CritesおよびStewart）が、 $X-\beta$ による除算のような特定の操作を用いてリード・ソロモン符号の同様の下界を導出していたことを指摘している。それらの操作は本質的に符号の次数をシフトさせてしまう（ $k$ から $k+1$ へ）。対照的に、本論文の構成は、符号の次元およびブロック長を保持し、次数シフトを必要とせずに任意の線形符号に適用できる。
構造的完全性: 符号の構造的ファミリー（例えば、AG符号を同一の空間上のAG符号として維持すること）を、単一の座標を変更するだけで維持できる能力は、重要な貢献である。これは、基礎となる代数的構造によって符号のファミリーが固定されているアプリケーションにおいて極めて重要である。
健全性への影響: リスト復号の失敗から高いMCA誤差を持つ符号を明示的に構成することにより、本論文はバッチ近似テストの健全性の限界を定量化している。すなわち、もしある符号がリスト復号可能でないならば、ランダムな線形結合が、高い確率でその符号から遠い状態に留まることを保証できないこと、具体的には、エラー確率が導出された式によって下限付けられることを示している。

本研究は、新しい実験的プロトコルや将来の応用を提案するものではない。その主要な貢献は理論的なものであり、リスト復号の特性と相互相関合意誤差の下界との間の、厳密かつ構成的な架け橋を確立することにある。

大きな発見： 「悪いミックス」のレシピ