Dark Pool Research Deep-Dive

2. MPC ダークプールの解剖

2.1 マイルストーン論文 4 本の比較

2.2 MPC Goes Live (FC 2009) — 史上初の MPC 実用化

デンマークの sugar beet root の年次 auction（約 1200 農家）を 3 サーバ（DKS, SCRG, Partisia）で BGW プロトコル＋Shamir secret sharing で執行。 2008 年 1 月 14 日に実運用、当日 1229 入札を 30 分で確定。MPC が 論文の世界から本番取引に渡った瞬間として歴史的価値を持つ。

計算する関数（auction clearing price）

// 入力: 各農家 i の 1 ロット辺り入札ベクトル b_i = (b_i^1, ..., b_i^4000)
// 出力: 市場清算価格 p* と各農家の確定数量 q_i

p* = argmin_p  | Σ_i sell_i(p) − Σ_i buy_i(p) |
q_i = quantity at p*

MPC レベルでの注意点

• 線形演算のみで表現するため、価格は離散グリッド上で step-wise 探索する
• 3 サーバ間の通信は SSL、各サーバは別組織が運用 → honest majority 仮定の現実化
• liveness：1 サーバダウンでも継続可能、ただし 2 サーバが結託すれば leakage

2.3 MPC Dark Side (2019) — Cartlidge & Smart

「市場マイクロストラクチャ屋」と「MPC 研究者」が初めて手を組み、金融現実とプロトコル仮定のギャップ を初めて言語化した論文。 SPDZ 2-party, ~800 orders/sec の volume-match dark pool を PoC 実装。

ダークプール特有の MPC 演算プリミティブ

// 共通入力: encrypted order (side, qty, account)
// 公開入力: ベンチマーク価格 p_mid（lit market から）

// プリミティブ① 線形比較（マッチング）
matched_qty = min(buy_qty, sell_qty)        // 比較は dirty work：bit-decomposition で表現
                                            // → SPDZ では ~log(2^32) = 32 round

// プリミティブ② 残量更新
buy_qty  −= matched_qty
sell_qty −= matched_qty

// プリミティブ③ FIFO キュー操作
queue.dequeue()                             // index は secret → oblivious selection が必要

性能内訳（800 orders/sec）

• 各 order 当たり ~125 ms ラウンドトリップ、内訳は比較 80%・I/O 15%・暗号 5%
• pre-processing（multiplication triple 生成）を offline phase に切り出すことで online を加速
• 線形演算のみに限定したため limit order book 全体はサポートしない（volume-match 限定）

2.4 All-for-One (FC 2022) — n≤100 の壁を AWS < $1/auction で破る

大規模 sealed-bid auction を MPC で執行する場合、n^2 通信 がボトルネック。本論文は SPDZ + LowGear/HighGear pre-processing + GPU 加速 + AWS m5.24xlarge で n=100 でも 1 ドル未満で 1 回 auction を捌く設計を提案。

通信量モデル

n=100, σ=64, R=20 で サーバ間総通信 ~12 GB/auction。GPU 上で SPDZ multiplication を batch 化し、 従来 30 分かかっていた MPC pre-processing を ~90 秒に短縮。

2.5 Prime Match (USENIX 2023) — JPMorgan の本番運用記録

世界初の 銀行本番 MPC dark pool。2021-09 から JP Morgan の機関顧客向けに稼働、 bilateral matching（n=2）+ midpoint pricing という思い切った simplification で本番品質を実現。

simplification の哲学

結果：~10 instr/sec というスループットでも 銀行 - 顧客の bilateral 性 ゆえに業務上は十分。 「academic な multi-party setting に固執せず、2-party で良い実利問題 を切り出した」ことが商用成功の鍵。

2.6 MPC vs FHE 性能比較

3. FHE ダークプールの解剖

3.1 FHE スキーム選択（TFHE / CKKS / BFV）

3.2 Secret Match (ICAIF 2020)

Goldman Sachs のチームによる、FHE のみで完結する dark pool の概念実証。 CKKS を使い volume-match と continuous-time matching を実装。operator が暗号鍵を持たないため、operator は trust 不要。

マッチング回路（擬似コード）

Encrypted match(Enc(order_buy[]), Enc(order_sell[])) {
    for i in 1..N:
        for j in 1..N:
            // すべての (i,j) ペアを舐める（oblivious）
            cond  = Enc.LessEq(order_sell[j].price, order_buy[i].price)
            qty   = Enc.Min(order_buy[i].qty, order_sell[j].qty)
            fill  = Enc.Mul(cond, qty)
            order_buy[i].qty  = Enc.Sub(order_buy[i].qty,  fill)
            order_sell[j].qty = Enc.Sub(order_sell[j].qty, fill)
            output[i][j] = fill
    return output
}

性能（論文値）

• N=10 で 1 マッチング ~5 秒、N=100 で ~5 分（O(N²) 比較ペア）
• CKKS の近似性により 厳密な qty 整合性 は post-decrypt で再確認が必要
• bootstrapping が 各 Mul / LessEq の度に発生するのが律速

3.3 Priority Queue (PETS 2023)

FHE で order book 風の優先度付きキュー を実現する画期的な技法。TFHE の programmable bootstrap を駆使し、 暗号文のまま insert / extract-min / decrease-key をすべて oblivious に実行。

programmable bootstrap とは

従来の TFHE では bootstrap は identity しか適用できなかったが、 programmable 化により 暗号空間で if-then-else・min・max・LUT 全般 が可能になった。

Encrypted Priority Queue の構造

// 各 slot は (Enc(priority), Enc(payload)) のペアを保持
// すべての操作は LUT (Look-Up Table) として 1 PBS で表現

insert(c_p, c_v):
    for i in 1..size:
        cond_i = PBS(c_p − slot[i].priority, sign_LUT)        // 比較
        slot[i] = oblivious_swap(slot[i], (c_p, c_v), cond_i) // 条件付き入替

extract_min():
    min_idx = argmin_PBS(slot[].priority)                     // O(size) PBS
    result  = oblivious_select(slot, min_idx)
    slot[min_idx].priority = Enc(+∞)
    return result

限界

• 1 操作あたり O(size) の PBS が必要 → size=64 で 1 操作 ~10 秒
• FHE のノイズ管理が深刻：insert / extract を交互に大量実行するとノイズ蓄積で再 bootstrap 増加
• operator は trust 不要だが liveness は依存 → operator-DoS 攻撃に弱い

3.4 FHE ダークプールの根本的トレードオフ

4. Bucket / 量子化系：Kicking-the-Bucket 解剖

4.1 量子化数式と幾何学

注文ボリューム v を粒度 Δ でバケット化：

direction (買い/売り) は bucket index の偶奇に埋め込む：

Observer は encoded_id しか見えないので、同じ bucket に落ちた全 user が 区別不能。 ただし bucket 内の 正確な volume や 注文時刻 は別の sub-protocol で隠蔽が必要。

4.2 Δ vs anonymity set の数学的関係

4.3 攻撃モデル

4.4 制約と限界

• tiny order の grouping：retail size の注文は同 bucket に大量に集まりやすい → anonymity 高
• large order の splitting：機関の block trade は単独で 1 bucket を埋める → anonymity 1（裸）
• これを救うため 動的 splitting（block を Δ 単位に分割）が提案されているが、 splitting pattern 自体がフィンガープリントになるという新たな leakage が発生
• bucket 粒度の 事前公開 が必要 → adversary も Δ を知っており、Δ - ε のオーダーで確実に bucket 1 を埋める攻撃が可能

4.5 Kicking-the-Bucket vs 他系統

5. DP ダークプール：Atlas-X と Correlated-Output DP の発見

5.1 古典 DP のおさらい

典型的にはガウス雑音 / ラプラス雑音を出力に加える。 ダークプール文脈では「個別 user の order が含まれているかどうかを観測者が判別できない」を意味する。

5.2 素朴な DP の何が問題か（Atlas-X の発見）

古典 DP は 1 回の releasing に対する保証である。しかしダークプールでは：

1. 同じ user が 複数 day / 複数 venue に注文を分散
2. 各 venue が独立に DP-noise を加える
3. attacker は 複数の DP-noisy outputs を結合 してノイズを平均化 → user 単位で intent が判明

これを Correlated-Output DP (CO-DP) 問題と呼ぶ。Atlas-X は明示的にこの脅威を fomalize し、 standard composition theorem では捕捉できないことを示した。

5.3 Correlated-Output DP の脅威モデル

5.4 Atlas-X の対策：Indifferential Privacy

Atlas-X は Indifferential Privacy という強化定義を提案。

つまり attacker が任意の auxiliary 情報（他 venue の noisy output 含む）を持っていても プライバシー保証が崩れない。 これは Composition theorem ではなく 定義レベル での補強。

5.5 Indifferential Privacy (2025) の追加技法

• noise schedule の coordination：複数 pool が同一 user に対しては 正の相関を持つ noise を意図的に加える → 平均化攻撃を無効化
• bounded queries per user：1 user の合計クエリ数に上限 → privacy budget の漏洩境界を確定
• dummy traffic injection：低ボリューム時間帯に decoy order を注入 → 真の volume の anonymity set 拡大

5.6 Atlas-X と他系統の関係

6. 設計トリレンマ：4 つの構造的バリア深掘り

6.5 4 バリアの相互依存

7. 未解決問題：研究機会 10 マップ

7.11 研究機会ヒートマップ

8. 論文インデックス（23 本詳細カード）