CRDTを同型暗号化する

341日前原文(jakelazaroff.com)

概要

ローカルファーストソフトウェア での共同編集とセキュリティの課題
エンドツーエンド暗号化 によるプライバシー保護の仕組み
同時非同期編集 とサーバーによるマージの問題点
準同型暗号 による暗号化データ上での計算とその限界
Rust製ライブラリ TFHE-rs を使った実装例と暗号化理論の解説

ローカルファーストソフトウェアとセキュリティ課題

ローカルファーストソフトウェア は、ユーザーの端末上でデータを管理し、同期サーバーを介して他ユーザーとデータを共有する設計
CRDT（Conflict-free Replicated Data Type） の利用により、編集内容のマージや非同期編集が容易
機密性の高いドキュメント を扱う場合、アプリ開発者さえ内容を知れない必要性
エンドツーエンド暗号化 の導入で、編集内容を事前に暗号化し、受信時に復号することでプライバシーを確保
Excalidraw などの事例では、Web Cryptography APIを用いた実装が簡易に可能

エンドツーエンド暗号化の新たな課題

非同期編集 時、同期サーバーは暗号化データの内容を理解できず、マージ処理が不可能
両ユーザーが同時オンライン でなければ、サーバーは単なるリレー役となり、更新データの圧縮も不可
長期間オフライン の場合、復帰時に大量の未圧縮データをダウンロードする必要

準同型暗号による解決案

準同型暗号（Homomorphic Encryption） は、暗号化データ上で直接計算処理を実行可能
同期サーバー が暗号化データ同士のマージ処理を実施でき、内容の秘匿性を維持
Homomorphic CRDT の構築により、ユーザー同士が非同期で安全に共同編集

Homomorphic Encryptionの仕組みとレベル

暗号化されたデータ に対し、加算や乗算などの演算を実行し、復号時に正しい結果を得る仕組み
部分的準同型暗号 は加算または乗算のいずれか一方のみ対応
やや準同型暗号・段階的準同型暗号 は両方対応するが演算回数に制限
完全準同型暗号（FHE） は無制限に加算・乗算が可能
ノイズ蓄積 による復号困難化への対策として、演算回数制限や「ブートストラッピング」技術を利用

TFHE-rsによるRust実装例

TFHE-rs はRust製の準同型暗号ライブラリ
クライアント側 で鍵ペア（クライアントキー・サーバーキー）を生成
データ暗号化後、サーバーキーと共にサーバーへ送信
サーバー側 で暗号化データ同士の計算処理を実施
クライアント側 で計算結果を復号し、正しい値を取得
- 例：2つの数値clear_a, clear_bを暗号化し、サーバーで加算、復号して合計値を得る流れ

準同型暗号の理論的背景

E(a) + E(b) = E(a + b) のような性質を持つ暗号化方式
加算・乗算 のいずれか、または両方をサポート
論理回路（ブール回路） として表現し、XORやANDゲートを組み合わせて任意の計算を実現
暗号化ビット列 を入力・出力として計算し、鍵を持たない者には内容が判明しない

準同型暗号の限界とローカルファーストソフトウェアへの影響

演算コスト が高く、実用化にはパフォーマンスの課題
加算・乗算の回数制限 やノイズ処理の複雑さ
完全な安全性 や安定運用には暗号専門家によるレビューが必須

参考資料・注意事項

CRDT入門 や FHE技術解説 の外部リンクを活用
- An Interactive Intro to CRDTs | jakelazaroff.com
- A High-Level Technical Overview of Fully Homomorphic Encryption | Jeremy Kun
暗号分野は専門性が高く、本番環境での利用前にプロのレビュー推奨

Hackerたちの意見

どこにも書いてないけど、CRDTは「Conflict-free replicated data type」の略だよ。

└

例えば、複数の人がドキュメントを編集する必要があるアプリケーションでよく使われてる。

でも今は、サーバーが送った変更を理解できなくなってる。友達の最新の変更を見たいなら、二人とも同時にオンラインでいる必要があるんだ。え？違うよ、サーバーはまだ見てない変更を送ってくれるから、それを復号化してマージすれば、最新のドキュメントが手に入るんだよね？同型暗号は面白いテーマだけど、合理的なパフォーマンスや帯域幅が必要な場合にはほとんど役に立たないよ。秘密のままで任意のアルゴリズム計算を実装するために同型暗号を巧妙に使った論文を見たことがあるんだけど、（カスタム設計の）CPUとRAMをエンコードして「時計を刻む」アルゴリズムを実行するんだ。それがうまくいくから、AWSの巨大インスタンスを借りて、そこで超重要な計算をすることができる — 1Hzでね。冗談じゃないよ、文字通り1秒に1つの仮想CPU命令なんだから。まあ、そんな速度とコストで大丈夫なら、データがすごく小さいか、めちゃくちゃ金持ちのどっちかだね。小さいならローカルで計算すればいいし、金持ちなら自分のハードウェアを買って、またローカルでやればいいんだ。

└

サーバーがコンテンツを処理できないと、CRDTドキュメントにマージできないんだ。つまり、変更ごとにCRDTの全状態を送受信する必要があるってこと。友達がオンラインなら、送信操作が可能だよ。なぜなら、それを復号化してマージできるから。

└

CSや暗号関連の論文が実用的じゃないことを説明するのはよくあることだよね。君が言ったよりもさらに実用的じゃない例も多いし、例えば攻撃の複雑さが2^250から2^230に減るとか。こういう論文の目的は、何が可能かを明らかにすることで、いつか実際のR&Dに役立つかもしれないってことだね。

ランタイムパフォーマンスも、軽く言っても、全然ダメだよ。M4 MacBook Proで、暗号化されていないバージョンと暗号化されたバージョンの最後の書き込み勝ちレジスタをベンチマークしたんだけど、暗号化されていない方はマージ時間が平均0.52ナノ秒。暗号化された方は？1.06秒だよ。これはタイプミスじゃないよ：同型暗号化されたマージは20億倍遅い。痛いね！

記事にもあるけど、完全同型暗号は信じられないくらい遅くて非効率的だよ。でも、比較的新しい分野だし（最初のFHEスキームは2009年に発見された）、この15年でかなり進展してるんだ。最初のFHEスキームは数TB/PBのキーが必要で、ブートストラッピング（FHEスキームで重要な操作で、計算される乗算が多すぎるときに行う）が数千時間かかってた。今は「たった」30MBのキーで、ブートストラッピングも0.1秒未満でできるようになった。これからも進展が続いて、FHEがもっと実用的になるといいな。

└

CRDTはそのアーキテクチャのせいでめちゃくちゃ遅いよ；どんなに良いアルゴリズムでも、設計上コストがかかるから、同型暗号を追加するのはさらに難しい；でも、本当にすごいと思うし、これが使えるかどうか気になるな；編集して、私の主張の「証拠」を持ってくるね：このページから：新しいマップを計算するには、サーバーがすべてのキーを通過してマージしなければならない。その後、完全なマップを各ピアに転送する必要がある — なぜなら、サーバーが知っている限り、全体のマップが異なるから。

└

学生は、自分のChromebookでFHE暗号化されたWASMやJSの採点コードを信頼して実行してもいいのかな？例えば、JupyterLiteやottergraderを使って。コード署名やSETI@homeのスクリーンセーバーについて。

└

最初のCRDTはかなり実用的じゃなかったよね、例えばWOOT[0]。最近の最先端CRDTデータベースは、パフォーマンス的には普通のLSMとあまり変わらないし。例えば、RDX CRDTs[1,2]は全部マージソートのようなアルゴリズムで実装されてて、純粋にO(N)だよ。メタデータのオーバーヘッドもほとんどの実装で抑えられてる。 [0]: https://github.com/el10savio/woot-crdt [1]: https://github.com/gritzko/librdx [2]: https://github.com/gritzko/go-rdx

FHEは確かに遅いけど、2009年からの進展は本当にすごいよ。ブートストラップの速度だけでも何千万倍も改善されたし、tfhe-rsはもう同種のAES-128を実現してる。AIの推論やトレーニングのためのリアルタイムFHEがますます現実味を帯びてきたね。 > https://github.com/sharkbot1/tfhe-aes-128

└

「現実味がある」って言葉をダブルクリックしてもいい？

脱線しちゃってごめんね。でも、君のブログのUI/UXは素晴らしいよ！いくつか挙げると、いいスタイル（色、フォント、デザイン）、マージンに見える「脚注」、常に目に入る目次、ホバー時のインタラクティブさやリンクプレビュー。いい感じだね。技術スタックは何なの？

いいね！同種暗号の遅さや非効率さが、CRDTのストレージの膨張と上手く補完し合ってる。

THFE-rsは使わない方がいいよ。Zamaはプロトタイピング以外の用途には商業ライセンスが必要だから。ライセンスがひどいんだよね。代わりに、商業利用が無料のopenFHE（C++）やlattigo（golang）ライブラリを使った方がいいよ。

初めて聞く人のために説明すると、「暗号化の文脈で『同種』とは、データを暗号化したままで計算を行える方法を指すんだ。最初に復号する必要がないんだよ。」

ハクソク