準同型暗号化されたCRDTs

 (jakelazaroff.com)
15 ポイント 投稿者 GN⁺ 2025-06-20 | 1件のコメント | WhatsAppで共有
  • ローカルファースト・ソフトウェアで共同編集ドキュメントの安全性を保つため、準同型暗号（Homomorphic Encryption）とCRDTsを組み合わせる
  • エンドツーエンド暗号化だけではサーバーがデータをマージできず、同期と更新効率に制約が生じる
  • 準同型暗号は、サーバーが内容を知らないままCRDTの更新をマージできるよう、プログラム実行を可能にする技術
  • しかし、準同型暗号の根本的な限界（性能低下、空間・計算量の増加、コードが最悪ケースで動作する必要）により、実運用には重大な難点がある
  • CRDTsとセキュアな計算の両立に向けたさまざまなアプローチが研究されており、まだ完全な解決策は模索中である

ローカルファーストと安全なコラボレーションの課題

  • リモート共同作業では、ドキュメントをローカルファースト方式でCRDTに保存し、同期によって共同編集体験を提供する構成である
  • ドキュメント内容がアプリ開発者など第三者に絶対に漏れてはならないというセキュリティ要件がある場合、エンドツーエンド暗号化がよく使われる方法である
  • エンドツーエンド暗号化は仕組みが単純だが、同期サーバーがデータをマージできないため、長期間にわたり非同期で作業すると非効率なデータ通信が発生する

準同型暗号とは？

  • 準同型暗号は、暗号化されたデータ上で直接アルゴリズムを実行できる特殊な暗号方式である
  • これを利用すると、同期サーバーはデータ内容を知らないままCRDT更新のマージを実行できる
  • 準同型暗号でサポートされる演算の種類に応じて、部分準同型（加算/乗算のどちらか一方のみ）、制限付き準同型/段階的準同型（両方を一部回数だけ）、**完全準同型（制限なし）**に分類される
  • 演算が増えるほど暗号文にノイズが蓄積し、復号が難しくなるため、Bootstrapping などの高度な技法が必要になる
  • 暗号化されたビット（0/1）レベルでは、XOR や AND のような基本演算ゲートの組み合わせだけで一般的なブール回路を実装できる

実際の準同型暗号CRDT実装例

  • Rustベースのライブラリ TFHE-rs を使い、代表的なCRDTである Last Write Wins Register を準同型暗号で実装している
  • 平文の構造体と暗号化構造体は、フィールドやメソッド（暗号化/復号化）がほぼ同一だが、実際のマージロジックでは重要な違いが生じる
  • if/else や match 構文などの実行経路の分岐は暗号文の復号に関する手がかりを与えうるため、暗号化環境ではすべての分岐・ループを即時評価する方式が必須となる
  • 主な条件比較やマージ演算はすべて、ビット単位の FheBool 演算子や select メソッドなどで処理され、どの条件で値が変わったのかを外部から検知できないようになっている

準同型暗号の根本的な限界

  • 暗号鍵とデータサイズの不均衡: 例では32バイトのデータに123MBのサーバー鍵が必要で（圧縮しても27MB）、空間効率の悪さが深刻である
  • 性能低下: 準同型暗号化されたCRDTの merge は、非暗号化と比べて約20億倍遅い1秒程度と測定された
  • ループや分岐が入力値によって変わると情報漏えいが起こるため、常に最悪ケース基準で演算数とメモリを消費しなければならない
  • たとえば、last-write-wins map のように key-value が疎である場合でも、すべてのキーを固定サイズで埋めたままマージする必要があり、実質的なスケーラビリティが低下する
  • 暗号文の構造や変更履歴から、値が変化したか、どの部分が更新されたかを外部観測者が推測できないように設計しなければならない

結論と展望

  • CRDTsと準同型暗号は理論上は自然に組み合わせられるが、現実には空間/時間効率やプログラム構造の面で致命的な制約が大きい
  • 現時点では完全に実用的なソリューションはまだ出ていないが、CRDTs自体も比較的新しい技術であり、継続的な研究が進められている
  • ローカルファーストのコラボレーションアプリにおいて、安全性と使いやすさのバランスを取る革新的なソリューションの可能性は、なお残されている

関連記事

1件のコメント

 
GN⁺ 2025-06-20
Hacker Newsの意見

  • 完全準同型暗号の分野が本当に遅く非効率なのは事実だが、この分野自体が2009年に登場した比較的新しい領域であることには触れておきたい。過去15年間の進歩は本当に驚異的なレベルだ。最初期の準同型暗号スキームでは数TB〜PB級の鍵が必要で、ブートストラッピング（準同型暗号で乗算演算が増えたときに必須となる処理）には数千時間かかっていた。今では鍵は30MB程度で、ブートストラッピングも0.1秒以内で可能になっている。今後も進歩が続いて、実用的に使える日が来ることを期待したい

    • 初期のCRDT（CRDT: Conflict-free Replicated Data Type）もWOOTのように非常に非実用的だったが、最近の最新CRDTデータベースは一般的なLSMと比べてそこまで性能が劣らない水準になっている。たとえばRDX CRDTはマージソートに似たアルゴリズムで動作するため、すべて O(N) だ。多くの実装でメタデータのオーバーヘッドもうまく抑えられている。WOOT, librdx, go-rdx 参照

    • CRDTはアーキテクチャ上の特性から遅くならざるを得ず、最良のアルゴリズムでさえ構造的にコストが高い。そこに準同型暗号を加えると難易度ははるかに上がる。非常に印象的ではあるが、実際に使い物になるのか気になる。根拠として「サーバーが新しいマップを計算するには、すべてのキーを1つずつマージし、その後でマップ全体を各ピアに送信しなければならない—サーバーから見ると毎回マップ全体が異なるため」という説明を引用する

  • CRDTはConflict-free Replicated Data Typeの略で、衝突なしに分散同期ができる特殊なデータ型だ。CRDTのWikipediaリンク 参照

    • たとえば、複数人が同時に文書を編集する必要があるアプリでは、しばしばCRDTが使われる

  • 記事では性能不足について触れられているが、実際にM4 MacBook Proでlast write winsレジスタを通常どおり動かした場合、マージには0.52ナノ秒しかかからない一方、準同型暗号版では1.06秒かかる。つまり演算速度に20億倍の差がある。本当に衝撃的な数値だ

  • FHE（Full Homomorphic Encryption）は本当に遅いが、2009年以降には驚くべき進歩があった。ブートストラッピング速度だけ見ても数千万倍は高速化している。tfhe-rsを使って、すでに準同型暗号ベースのAES-128も実演されている。AI推論/学習向けにリアルタイムFHEを導入できる可能性は、ますます高まっていると思う。tfhe-aes-128 GitHubリンク 参照

  • サーバーがクライアントの変更内容をもはや理解できない、という話には同意できない。サーバーはユーザーがまだ見ていない差分だけを送ればよく、ユーザーはそれを復号してマージし、文書の最新版を作る仕組みだ。準同型暗号は興味深いが、妥当な性能や帯域幅が必要な場面ではほとんど適していない。以前、（カスタムCPU+RAMを暗号化してエンコードし、各クロック信号ごとに1命令ずつ処理する）準同型暗号ベースの完全秘密計算を扱った論文を見たことがある。実際に動くが、1秒あたり仮想CPU命令1個を処理できる程度だった。そうした速度とコストを許容できるなら、むしろローカルで動かすか、本当に金があるなら自前のハードウェアを買ってローカル処理したほうが賢明だ

    • コンピュータサイエンスや暗号学の論文は、しばしば実用性から遠い、たとえば攻撃複雑度を 2^250 から 2^230 に下げるといった途方もなく非現実的な研究内容が多い。こうした研究は、実際のR&Dや実現可能な領域を広げるうえで意味がある

    • サーバーが内容を直接扱えないなら、CRDT文書をマージできず、毎回CRDTの全状態を受け取ってから送り返す必要がある。友人が同時にオンラインなら、操作結果（operations）を送ってリアルタイムマージできるが、そうでなければ非常に非効率だ

  • 学生たちがFHEで暗号化されたWASMやJSの採点コードを、JupyterLiteとottergraderの組み合わせで自分のChromebook上で直接実行しても信頼できるのか疑問だ。コード署名とSETI@home screensaverの関係も気になる

  • THFE-rsはZama側がプロトタイプ用途以外では商用ライセンスを要求するので、使わないほうがよさそうだ。ライセンス条件が扱いづらい。代わりにopenFHE(C++)、lattigo(golang) ライブラリを勧めたい。どちらも商用利用が自由にできる

  • FHEはここで使うには本質的に不向きな道具だと思う。FHEは中央サーバーが所有または把握しているデータを扱うのに適している。ここでは複数ユーザーが分散したデータを共同で扱う必要があるので、MPC（マルチパーティ計算: 複数の参加者がそれぞれ秘密データを持ち寄って、合算などの共同計算を行う方式）のほうがはるかに効率的だ

    • 私もFHEを使いたくなって、結局もっと良い道具や最適な方法があると気づくことがよくある。そもそもFHEを適用できる場面自体がかなり限られている

  • 記事で提示されている前提がよく理解できない。CRDTと準同型暗号の概念は分かるが、なぜ同期のために双方が同時にオンラインである必要があるのか疑問だ。非同期に更新をやり取りする「store-and-forward」方式なら、転送中のデータも暗号化されたまま送れるはずで、なぜわざわざサーバーが状態を保持しなければならないのか（しかも暗号化された状態で）、提案のように修正する必要があるのか気になる

    • 各ピアごとにレジスタのコピーをサーバーが別々に保存しなければならない問題のためだと思う。サーバーはどれが最新状態か判定できないからだ。FHEを使えばサーバーは1つのコピーだけを維持できる。つまり、すべてのピアが常にオンラインなら（同時接続なら）、サーバーは単に中継するだけで、別途保存する必要はない

  • FHEの遅さと非効率さに、CRDTのストレージ浪費が組み合わさった感じで面白い