技術要約：高速な有界独立関数とその双対

問題提起

本論文は、定数時間（計算量）のオーバーヘッドを維持しつつ、ランダム関数やランダム線形符号の統計的性質を模倣する暗号プリミティブを構築するという課題に取り組んでいる。具体的には、以下の条件を満たす「高速」な実装（サイズ $O(n)$ の線形サイズ算術回路によって計算可能と定義）を求めている：

1. 有界独立性（Bounded Independence）： 任意の定数 $t$ に対して $t$-wise 独立であるハッシュ関数。
2. 高速な双対符号（Fast Dual Codes）： 符号とその双対の両方が高速かつ組織的な符号化（systematic encoding）を許容し、かつ距離がギルバート・ヴァルシャム（GV）界に近似する線形符号の族。
3. より強力なランダム特性： 単なる距離を超えて、リスト復号可能性（list-decodability）などの性質、すなわち、局所的な制約下においてもコードがランダム線形符号と同様に振る舞うこと（局所的類似性）を保証すること。

[IKOS08] や [DI14] といった先行研究では、高速なペアワイズ独立ハッシュ関数や、GV界に近似する高速な符号が確立されているが、独立性のパラメータ $t$、動作する体（field）、あるいは符号と双対を同時に最適化できる能力に関して制限がある場合が多い。[BR26] による最近の構成は、高速な双対符号を改善しているものの、バイナリ体（$\mathbb{F}_2$）に限定されており、レートが $1/2$ に固定され、無視できない失敗確率を持ち、組織的な符号化が欠如していた。

手法

著者らは、「IKOS構成」（Ishai, Kushilevitz, Ostrovsky, Sahai）および「DI構成」（Druk, Ishai）に基づき、これらをより高い独立性パラメータへと一般化している。

1. ハッシュ関数の一般化

ハッシュ関数の核となる構成は、以下の3段階のパイプラインに従う：

1. 外部符号化（Outer Encoding）： 入力に対して、大きな（ただし定数サイズの）アルファベット上の高速な線形符号を適用する。
2. 内部ハッシング（Inner Hashing）： 符号化されたベクトルの各座標に対して、定数サイズの $t$-wise 独立なハッシュ関数を適用する。
3. 抽出（Extraction）： 結果に対して、優れた符号の生成行列の転置（抽出器として機能）を適用する。

$t$-wise 独立性を実現するために、著者らは内部ステップにおける定数サイズのペアワイズ独立ハッシュ関数を、定数サイズの $t$-wise 独立ハッシュ関数に置き換えている。もし外部符号の距離が十分に大きい（具体的には $> 1 - 1/t^2$）ならば、$t$ 個の入力の相違性が十分な数の座標にわたって保持されることを証明しており、これにより内部ハッシュ関数が独立で一様な出力を生成し、最終的な抽出ステップがそれを保持できることを示している。

2. 線形一様出力族 (Linear Uniform Output Families: LUOF)

符号を構築するために、著者らは**線形一様出力族（LUOF）**の概念を利用する。ランダムな行列 $A$ が LUOF であるとは、任意の非ゼロ入力 $x$ に対して、出力 $xA$ が一様に分布することを指す。

• 高速 LUOF: 著者らは [DI14] の構成を一般化し、高速 $t$-LUOF を作成している。行列 $A$ が $t$-LUOF であるとは、任意の $t$ 個の線形独立な入力 $x_1, \dots, x_t$ に対して、出力 $x_1A, \dots, x_tA$ が一様かつ統計的に独立であることを指す。
• 構成: この構成もハッシュ関数の構成と同様に、外部符号、ランダムな定数サイズ行列の層（「内部」関数として機能）、および抽出ステップを含む。著者らは、外部符号が十分な距離を持てば、内部のランダム行列が線形独立な入力を独立な一様出力へと写像することを証明している。

3. 高速な双対符号の構築

$t$-LUOF 行列 $A \in \mathbb{F}_q^{k \times r}$ を用いて、著者らは組織的な符号化写像 $x \mapsto (x, xA)$ を持つ符号 $C$ を定義する。

• 双対性: 双対符号 $C^\perp$ は、写像 $y \mapsto (-yA^\top, y)$ によって生成される。
• 転置原理（Transposition Principle）: 転置原理（補題 3.4）を引用し、もし $xA$の計算が高速（線形サイズ）であれば、$yA^\top$ の計算もまた高速であることを論じている。
• 双対の独立性: 重要な技術的貢献は、$A$ が $t$-LUF であるならば、$A^\top$ もまた $t$-LUF であることを証明したこと（補題 3.9）である。これは Vazirani の XOR レマに依拠しており、双対符号が元の符号の強力なランダム特性を継承することを保証している。

主な貢献と結果

1. 高速 $t$-wise 独立ハッシュ関数

• 結果: 任意の定数 $t$ に対して、線形サイズの回路によって計算可能な $t$-wise 独立なハッシュ関数の族を構築する。
• 最適化: バイナリ体（$q=2$）において、代数的次数は $\log_2 t$ に最適化されている。これは、それより低い次数では $t$-wise 独立性をサポートできないため、ほぼ最適である。
• 効率: 回路サイズは $O(k+r)$ である（ここで $k$ は入力長、$r$ は出力長）。隠れた定数は $t$ に依存する（おおよそ $\Theta(t^7)$）が、$t$ が固定されていれば定数である。

2. 高速な双対を持つ高速符号 (GV-Bound)

• 結果: 任意の有限体 $\mathbb{F}_q$ 上で、任意のレート $R \in (0, 1)$ を持つ符号 $C$ およびその双対 $C^\perp$ の族を構築する。
• 特性:
  • $C$ と $C^\perp$ の両方が、高速かつ組織的な符号化（線形サイズ）を許容する。
  • 両者は、確率 $1 - 2q^{-\varepsilon n}$ でギルバート・ヴァルシャム（GV）界に $\varepsilon$ 近い距離を実現する。
  • この構成は、[BR26] とは異なり、無視できる失敗確率を持つ。
  • 符号化のための線形サイズのユニバーサル回路をサポートする。

3. 高速な双対を持つ高速リスト復号可能符号

• 結果: $t$-LUF の性質を利用することで、著者らはこの構成を、ランダム線形符号に $t$-局所的に類似した符号へと拡張している。
• リスト復号: 任意の定数 $t$ に対して、構築された符号（およびその双対）が、リストサイズ $L = O(1/\varepsilon)$ でリスト復号容量まで $(\rho, L)$-リスト復可能であることを証明している。
• 新規性: 著者らの知る限り、高速な符号化、高速な双対符号化、および符号と双対の両方に対する最適なリスト復号可能性を同時に達成した最初の構成である。

重要性と暗号学的応用

本論文は、これらの構成が高効率かつ強力なセキュリティ保証を必要とするシナリオ、特に暗号において強力な構成要素となることを示している。

1. 完全なマルチパーティ計算 (MPC)

著者らは、回路複雑性が参加者数に対して線形（$O(n)$）にスケールする、完全なセキュリティを持つ MPC のための、非自明な最初のプロトコルを提示している。

• 背景: 代数符号（リード・ソロモン符号など）を用いた従来のプロトコルは、しばしば準線形（quasi-linear）のオーバーヘッドを伴っていた。
• 応用: 高速な双対符号を用いることで、オブリービアス線形評価（OLE）プロトコルを構築し、それを一般的な定数サイズの関数へと拡張している。このプロトコルは、パッシブ攻撃者に対してセキュリティ閾値 $t = (1/2 - \varepsilon)n$ を達成する。

2. 暗号化された行列ベクトル積 (EMVP)

複雑性に基づく暗号の文脈において、著者らはこれらの高速な双対符号を暗号化された行列ベクトル積に適用している。

• 改善: 彼らの構成は、[BR26] のアプローチ（$\mathbb{F}_2$ に限定され、無視できない失敗確率を持っていたもの）の限界を克服している。
• 利点: これにより、行列の符号化とクエリの符号化の両方が漸近的に最適な回路複雑性を持つ EMVP プロトコルが可能になる。

3. ランダム線形符号の保守的な代替物

$t$-LUF 構成は、ランダム線形符号（ノイズを伴う線形代数の困難性に依存するもの、例：LPN）の「保守的な」代替物を提供する。

• 利点: 従来の構成は最小距離（1-local similarity）のみに依存していたが、$t$-LUF は $t$-局所的類似性を保証し、リスト復号可能性のような強力な組合せ論的性質を保証する。これは、局所的な構造を悪用する攻撃に対する、より堅牢なセキュリティ仮定を提供する。

4. MPCフレンドリーなハッシング

低代数的次数を持つ高速 $t$-wise 独立ハッシュ関数は、回路サイズと代数的次数の両方が通信量やラウンド複雑性に影響を与える MPC プロトコルに直接適用可能である。この構成は、両方を同時に最適化している。

結論

本論文は、以前の線形サイズ構成を、より高い独立性パラメータとより強力なランダム特性をサポートするように見事に一般化した。高速 $t$-LUF を導入し、その双対の性質を証明することで、著者らは、高速、組織的、かつ統計的に堅牢な、ハッシュ関数と符号を同時に構築するための統一されたフレームワークを提供している。これらの結果は、特に情報理論的な MPC や暗号化計算において、最適な漸近的複雑性を持つ新しい暗号プロトコルを可能にする。