完全準同型暗号でインターネットが激変！究極のプライバシーが守られる時代へ
引用元：https://news.ycombinator.com/item?id=44601023
FHEと暗号技術を愛する者として言うと、FHEは速くなってるけど、ブートストラップに頼ってる限りplaintextの速度には及ばないだろうね。根本的な理由で、ブートストラップのオーバーヘッドは常に1000倍くらいあるから。ブートストラップの高速化が難しいと分かるとハードウェア加速の話が出たけど、LLMに計算資源が集中してる今、それは難しい。FHEで計算するのにどれくらいのコスト増なら払える？1000倍以上は厳しいよ。プライベートLLM推論とかは、Confidential Computingが現実的。ハードウェアは信頼したくないけど、他に良い手がないんだ。
1000倍高くなっても、証明可能なプライバシーを望む人たちの市場があると思わない？Dropboxみたいに大きくないだろうけど、そういう層はいると思うよ。
え？500ドル相当のクレジットで全部セルフホストできるってマジかよ！
ホントそれ！ほとんどの人が数TB程度のデータなら、NASとか余ってるPCでセルフホストは十分いけるよ。非技術者向けにセットアップできる製品もあるしね。一番の課題は、十分なサービスレベルのISPを契約してるかってとこだね。
ブートストラップ抜きでもFHEはplaintextと同じ速さには絶対ならないよ。暗号文はplaintextデータの約1000倍デカいから、その分メモリ帯域も計算も必要になる。この差は埋められないんだ。
確かにハードウェアは安い。でも、バックアップを3-2-1ルールでやるなら、計算に不動産（保管場所）の費用も入れないとダメだよ。それは安くないからね。
もし1000倍のレイテンシって話なら、それはかなり厳しい売り込みだよね。普段30秒で終わるものが8時間以上かかるってなったら、さすがに無理があるよ。
PythonはC++より400倍遅いけど、みんなそれでも使ってるじゃん。そういうことだよ。
データがたくさんあっても、セルフホストの方が結局安いよ。クラウドプロバイダの利益分がないんだから、そりゃ常に安くなるよね。彼らの利益率はかなり高いからさ。
LLMの話題が盛り上がってるけど、FHEって他に使い道ないのかな？例えば、自分の情報が安全に守られるトレーディングアルゴリズムとか、ランダムなサーバーに置けるようなのってないの？
記事の「Googleがデータ読めない」ってのはありえない話だね。プライバシーは大事だけど、VPNやSSL/TLSで十分な人がほとんどでしょ。やりすぎると逆に怪しまれて、ターゲットになりかねないよ。TorやVPNも完全じゃないし、絶対的なセキュリティなんてありえないから。
それってかなり合理的で、もう普通のことになってる感じだよね？例えば、8MBのウェブページから500語のニュース記事を読むんだけど、動画とか解析ツールとかJavaScriptの無駄なものが自動再生されてる。データの量は3桁、計算の量は4〜5桁も違うんだよ。
コストは高いこともあるけど、必ずしもそうじゃないよ。例えば、Hosthatchの7TBストレージサーバーは2年で190ドル（月7.92ドル、今日のレートだと約5.88ポンド）。これって1日20p以下なんだ。電気代だけでもめっちゃお得だよ。自分でホストするより安いし、ドライブやNASもいらないし、故障の心配もなし！
元トレーディングアルゴリズム開発者として言うと、FHEがあったとしても適当なサーバーにホストはしないね。コードだけじゃなく、1)規制、2)取引所への通信経路の信頼性、3)物理的なセキュリティ（鍵付きケージ）、4)予測可能なレイテンシが超重要だから。ちょっとでも遅延すると、すぐにやられちゃうんだ。
記事に書いてあった「Googleが送受信内容を読めない」って話、本当にその通りなんだよ :-)
Googleのサービスが質問に答えられるってことは、そりゃ内容を読めるってことだろ。Aが暗号化してBが解読できれば、BはAの質問を読めるし、AもBの返事を読めるんだ。セキュリティは魔法じゃないんだからね。
そんなお得なディールってよくあるの？Hosthatchの表示価格は6TBで月24ドルからって書いてあるけど、アカウント登録しないと詳しいこと分かんないんだよね。
自前のサーバーでTrue 3-2-1バックアップしてるよ。Proxmoxで32コア、96GB RAM、5TB SSD。サーバーハードウェアは2年前に1500ドル。月平均30W（約2.50ドル）。クラウドの暗号化バックアップはBackblazeで月15ドル。AWSの同等だと月1050ドルもするんだ。先週SSDが壊れたけど、数時間で復旧したから、ちゃんと機能してるって確信してるよ。
でもさ、ちゃんとFHEを使えば、これらの心配事のほとんどは解決できるはずじゃないの？サーバーに物理的にアクセスされたら終わりってのが、今の追加対策の理由だろ。FHEなら、コードさえ信頼できれば、ハードウェアをいじられてもソフトウェアは安全なはずなんだけど。
実はrate-1の準同型暗号スキームもあるんだけど、あんまり実用的じゃないんだよね。だから君の言ってることは大体合ってるよ。
FHEが任意の計算に使えないのは、暗号化データだと漸近的複雑度がすごく増えるからだよ。例えばDB検索はO(log n)がO(n)になっちゃう。だからFHEでのGoogle検索は根本的に無理だね。DNN推論は違うけど。
FHEって、サーバーのCPUリソースを食い潰して取引アルゴリズムの遅延をどう防ぐの？あと、金融規制当局はシングルテナントを好むんだけど、FHEを説明しても「シングルテナントを強く推奨。FHEが十分かは公式に言えないし、将来問題になるかも」とか「資本準備金増やします」って言われがちだよ。シンガポールだけはテクノロジーに理解がある例外だね。
みんなPythonは重要じゃない時に使って、C++は重要な時に使ったり、Cでバックアップされてるモジュールを暗黙的に呼んだりするけど、FHEだとそれは無理なんだ。全部FHEに”All in”するしかないんだよ。
へー、面白いね。それに関する論文教えてくれる？
実は検索がO(log n)になる理論的なブレークスルー（https://eprint.iacr.org/2022/1703）があったんだけど、それはかなり非実用的だし、それほど速くもなってないよ。
これは良い論文だよ: https://eprint.iacr.org/2019/720.pdf
もしPythonの開発者やユーザーが、CやRustのバインディング、高速言語で書かれたバイナリへのRPCなしに純粋なPythonライブラリだけでやるとしたら、多くの用途、特にML、バイオインフォマティクス、数値解析なんかでは使われなくなるだろうね。
FHEは重要なツールだよ。今、企業は政府に強制されて特定のターゲットのために暗号を破らされることがあるからね。FHEがあれば企業は「私たちは平文を一切見てません」って言えるようになる。E2E暗号ならネットワークやキャリアとしてできるけど、平文を処理する時はできないんだ。プライバシーは人権だと考えてるし、政府は市民の民主的な権利行使に対する報復権限を極めて制限されるべきだ。
FHEは任意の計算を可能にするかもしれないけど、僕がサービスを使うのは彼らが検索インデックスや知識、データベース、銀行取引とか、何か使いたいデータを持ってるからなんだ。だからGoogleが全検索インデックスを暗号化しない限り、彼らは僕のクエリをデータとやり取りする時に見ちゃうだろうし、そうでなきゃ検索できないよね。あとインセンティブの問題も。ごく一部の信用度の高い高リスクなアプリ以外では、企業がわざわざ苦労してFHEサービスを提供する理由がわからないな。
FHEを使った完全プライベートな検索エンジンの実装例があるよ。Wikipediaを検索できるのに、サーバーは君が何読んでるか全然知らないんだって: https://spiralwiki.com/
もっとコメントを表示（1）
Wikipediaのデータベースダンプをダウンロードして、Kiwixでローカルで読む方が断然楽だよ: https://kiwix.org/
僕の理解では、暗号化する必要があるのは機密データ（例えば銀行取引）だけだよ。計算に使う関数は暗号化する必要がないから、公開されてる暗号化されてないデータも使えるはずだよ。
Targetが買い物習慣から女性が妊娠してるのを本人が知る前に見抜いちゃうような世界じゃ、機密データを分ける線引きってかなり曖昧だよね。
ちょっと訂正ね。あの話だと、本人が知る前じゃなくて、父親が知る前だよ。
僕もまさにそう思ったよ。結局、ほとんどの大企業はユーザーのデータやクエリを見たいんだから、FHEでその能力を落とすメリットがないよね。彼らは必要だから見たいんだし、断ればFHEなしでサービスを使うしかない。銀行アプリならいいけど、他で受け入れられるかは議論の余地があると思うな。
インセンティブの話は合ってるけど、前半は違う。平文データベースのプライベート参照は5年以上前から可能だよ。ただ、データベースの前処理が大変だったり、最悪の場合、全体を線形スキャンする必要があるんだ。
平文データベースのプライベート参照は可能って話だけど、それって企業データ全体をプログラムに読み込む必要があるってこと？Googleの検索インデックスみたいに1台のマシンに収まらないデータだと無理じゃん。
Googleは検索は許可してるけど、検索インデックス全体を準同型暗号プログラムに提供するのは全く別の話だよね。
データはクライアントに構造化された検索テーブルだけを共有するように処理できるよ。そのデータ構造はすごく大きいけどね。
ユースケースは”Googleにクエリを知られずに検索する”ことじゃなくて、”自分のデータを彼らに知られずに検索する”ことなんだ。実用的な適用範囲はかなり狭まるよね。
”データ全体をプログラムに読み込む必要がある”って？違うよ。Google検索インデックス全体は無理だけど、できることはたくさんあるんだ。古い論文（2022年）だけど、具体的な数字があるよ。https://eprint.iacr.org/2022/949
DoublePIRってスキームで1GBのDBにクエリするには、クライアントは16MBの”ヒント”をダウンロード。その後、何度でもクエリできて、各クエリは通信量345KB、スループットは7.4GB/秒/コアだよ。
結局、クライアントごとに何ギガバイトもの暗号化データがダウンロードされて、インデックスが更新されるたびに再生成されて再ダウンロードされるってことだよね。
クライアント側がプライバシーのためならお金を払うってのはわかるよ。でも、それがどれだけ高価になるか、だから登録する人がどれだけ少ないかってことを理解してるかな？
例えばプライバシー重視のGoogleの代替サービスを考えよう。年間100ドル（そんなもんじゃないけどね）だとして、どれだけの人が契約する？ごく一部だよ。計算コストを追加するともっと減る。Torみたいな不完全でも無料の選択肢もあるしね。HEが無意味だとは言わないけど、費用がかかる以上、利用者はごくわずかになるだろうね。
今のFHE Googleはめちゃくちゃ高くて遅いから誰も金なんか払わないだろうね。
重要なのは将来どれだけ計算速度が向上するかだ。FHEが1000倍遅くても、ハードウェアも1000倍速くなれば、性能は今の平文と同じになる。
未来の予測は無理だけど、ソフトウェア改善とハードウェアの高速化、そしてFHEのプライバシーというユニークな価値を考えれば、いつか（10年後でなくても50年後には）標準になる可能性はあるよ。50年前と比べたら今のハードウェアは何桁も速いしね。
暗号文サイズが大きいとか、サーバ側でクライアントごとにモデルやインデックス全体を暗号化する必要があるとか、他の問題もあるけどね。FHEはまだ多くのことには実用的じゃないけど、その適用範囲は広がる一方だよ。検索エンジンやLLMも将来カバーすると信じてる。
FHEが1000倍遅くても、ハードウェアが1000倍速くなれば性能は今の平文と同じって話だけど、それって平文なら1000倍多くのことができるってことだよね。
「デフォルトで監視」のネットが「デフォルトでプライバシー」になるのは良いけど、デジタル署名推しの俺から言わせれば、Hacker NewsやFacebookがみんなの身元を決めるのはダメだね。FHEはみんなが欲しがるものではないよ。ほとんどは信頼ベースで動いてて、FHEの複雑なコストを払ってまで使いたいケースはほぼないからさ。
デジタル署名については完全に同意！でも「メールの最後の変なヤツ何？」ってよく聞かれるし、説明しても「はぁ？」って顔されるんだ。君は一般の人をクライアントサイド暗号に巻き込むことできた？どうやったの？
ユーザーが気にしなくてもいいように、全部アプリに組み込むべきだね。メールの署名より、緑のチェックマークが表示される方が分かりやすい。ChromeがTLSをデフォルトにしたみたいに、「URLバーの南京錠が緑か見て」って言うだけでいいんだよ。
FHEとAIは最強の組み合わせかもね。AIが複雑さを肩代わりしてくれるからさ。
これって意味のある組み合わせなの？それとも単にAIって言いたいだけ？
AIは退屈な作業が得意だけど、FHEの障壁もまさに退屈さなんだ。FHEでGoogle検索する時、いちいちクエリを打つのは面倒だけど、LLMにFHEを使ってGoogleとやり取りさせるのは話が違う。AIのテキスト中心のUIはFHEとすごく相性がいいんだよ。
退屈な作業に一番いいのはforループでしょ。
forループで何するの？
計算の1回分の処理だろうね。
Googleの例は誤解を招くと思う。「ウェブ検索」と連想されるからね。FHEは入力全体がキーで暗号化される必要があるけど、Googleの膨大なデータベースはキーkで暗号化できない。この技術は、入力全部を自分でコントロールできて、計算力を借りる場合に使えるってことだね。Googleへの言及は注意が必要だよ。
入力全体を鍵で暗号化する必要があるように見えるけど、検索の例だとクエリとマルチテラバイトのDBを含むよね。AppleのCallerIDの例から理解したこととは違うな。Appleは各ユーザーのためにDB全体を暗号化してるわけじゃないみたいだし。なんで？
URL: https://machinelearning.apple.com/research/homomorphic-encry…
URL: https://machinelearning.apple.com/research/wally-search
彼らは明示してないけど、使ってる同型暗号方式はこう動くんだ。平文と暗号文で操作するには、まず平文を公開鍵で暗号化するんだ。クエリ情報を全く漏らさずにDBとやり取りするなら、常にフルスキャンが必要だよ。もしクエリによって未読部分があるなら、それはクエリじゃなかったことを教えちゃうからね。ブラウザの安全ブラウジングみたいにハッシュの一部を使う方法もあるけどね。
Wallyの論文の投稿で言ってる＞これまでのプライベート検索システムでは、クライアントのクエリごとに、サーバーはデータベースのエントリごとに少なくとも１つの高価な暗号操作を実行しなければならない。って、このこと言ってるのかな？
そうだよ。(同型暗号の投稿しか見てなかったわ、Wallyは見てなかった)。Wallyはこの制限を回避しようとしてて、DBの一部だけ同型暗号を使って、匿名ネットワークで情報漏洩を減らしてる。第三者が運営してるらしいけど、結局はネットワーク運営者がサーバー運営者と共謀しないって信じるしかないよね。プライバシー保証は弱いけど、少なくともめちゃくちゃ遅くはないね。
同型暗号化サービスは、事前に暗号鍵を知る必要がないんだ。それがまさに重要な点だよ。すごく単純な暗号方式で考えてみて。暗号文の足し算ができるんだ、鍵を知らなくてもね。もしもっと複雑な演算ができる代数構造を見つけられたら、それを組み合わせてどんなに複雑な計算でもできるようになるんだよ。
Google検索の場合、E(x)は暗号化されたクエリで、yはGoogleのデータベースだよね。E(y)を計算するのと同じくらいの作業なしにE(x + y)を計算できるの？俺はそう思わないな。むしろ、公開鍵暗号を使って、サーバーがE(y)（そう、データベース全体を暗号化するんだ）を計算できるようにしつつ、D(E(x)) = xを復号できないようにするんじゃないの？
違うよ。検索の場合、データベースは入力クエリを投入する”関数”なんだ。例えば、数字が偶数か奇数かを判定するサービスIsOdd(E(x)) = E(x) mod 2を考えてみて。暗号化された数字を渡したら、暗号化されたビットが返ってきて、それを復号すれば元の数字が偶数か奇数か分かる。サーバーは平文を知らないんだ。同型暗号化DBはIsOdd(x)と似てるけど、もっと複雑なだけ。どんな計算でもBoolean回路にできるから、同型ブロックがあればどんな計算も実装できるんだよ。効率が悪いのはそのためだけど、数学的には機能するんだ。
もっとコメントを表示（2）
もし好意的に見ても、その”データベース”が格納してるのは一つの数字だけだろ。もっと現実的なDB（多くの任意の値を格納できるもの）をBoolean回路に変換したら、一般的に保存された値ごとに少なくとも一つの操作が必要になるよ。暗号化されたデータで回路を評価するときは、それらの操作を毎回すべて評価する必要があるんだ。だから俺は『E(y)を計算するのと同じくらいの作業なしに』って書いたんだよ。
＞IsOdd(E(x)) = E(x) mod 2
これ、分かんないな。IsOdd(E(x)) = x mod 2って意味？でも、そんな関数を誰が提供するのさ？ウェブ検索の場合、その関数は検索エンジンでしょ。Googleが提供するべきで、ユーザーじゃないよ。エンジンの洗練度と完全性がGoogleを選ぶ唯一の理由なんだから。もし俺が関数を提供するなら、彼らからはただ計算能力を買ってるだけになっちゃうよ。
いや、それがまさにポイントだよ。IsOdd()は暗号文E(x)に作用するんだ。平文xは見ない。でもその代数的特性のおかげで、サーバーは復号せずにクエリに答えられるんだよ。例えば、クライアントがx=13をk=45で暗号化してE(x)=32を送る。サーバーはIsOdd(E(x))=32 mod 2 = 0を計算して返す。クライアントはD(IsOdd(E(x)))=D(0)=0 xor TrimLength(45, 1)=1って復号する。サーバーはクライアントが結果を反転させるか知らないから、元の数字が偶数か奇数か分からないってわけ。
なるほど、ありがとう。でも、Google検索みたいにデータがクラウドにある場合、ローカルで計算できないレスポンスをリモートホストがどうやってくれるのか、まだよくわかんないな。
IsOdd()みたいな単純なのじゃなく、もっと複雑な関数でもホモモルフィックに実装できるんだ。AND/OR/NOTゲートみたいに論理回路で表現して、それらをホモモルフィックにすればOK。ただ、データはインライン化とか、ループのアンロールとか、分岐は全部実行しないとダメだけどね。
これって、ワースの法則（Wirth’s Law）を支持する最高のやり方だよね。ソフトウェアがハードウェアよりどんどん遅くなるっていうやつ。
Googleって聞くと、GmailとかGoogle docsとか、個人データ収集してるサービスを思い浮かべちゃうな。お母さんは多分検索のことだと思うだろうけど、HMEの記事は読まないだろうな。
技術が経済を変えるって考え方にいつも疑問なんだよね。「ユーザーデータ収穫ビジネスがオワコンになる」って言うけど、人々は安いサービスのためにデータを喜んで提供してるじゃん。暗号化とかゼロ保持ポリシーのサービスもあるけど、人気ないし。影響は小さいと思うな。
会社が100万倍も計算コストがかかって、デバッグもできず、利用状況の分析もできない準同型暗号サービスに、わざわざ乗り出すわけないよな。
CipherStashの創設者だけど、FHEだけが唯一の選択肢じゃないよ。もっと速い特殊な検索可能暗号化もあるんだ。これらを組み合わせれば、プレーンテキストに近いパフォーマンスの検索システムができる。FHEは汎用計算用だけど、高速な検索可能暗号で絞り込んだ小さいデータセットに使うのがいいと思う。
FHEを一般的なコンピューティングやインターネットに使うのは、まだ先の話。Moore’s Lawが何世代も進んでも難しいかも。FHEが輝くのは、スマートコントラクト、銀行、医療みたいに、高価値で機密性が高いけど、複雑度が低い計算分野だね。Zamaがやってることに注目してみて。https://www.zama.ai/
E2EE Gitが発明されたけど、作者は「悪意あるクライアント」に対して、サーバーがブランチ保護とか強制プッシュを強制する解決策がないって言ってたよ。もしかしたら、これがE2EE Githubにつながるかもね？https://news.ycombinator.com/item?id=44530927
プライベートなインターネットの未来は、完全準同型暗号（FHE）じゃなくて、機密VM（CVMs）だよ。CVMsはメモリ暗号化とか、ホストOSからの分離を使うんだ。ARMのTEE、AMDのSEV、IntelのSGXとかTDXがそう。
鍵と計算がベンダーに預けられている限り、機密計算は”信用して、データは安全に保つから”って言うのに過ぎないよ。
SGXとかは、多層防御の一部としてはまだ使えると思うんだ。NXやASLRみたいなセキュリティ対策は破り方を知ってるけど、だからって役に立たないわけじゃないでしょ。問題は、SGXが“唯一の解決策”みたいに売られてるってことだよ。
NXやASLRは、他人が君のPCのコードを悪用するのを難しくするんだ。SGXは、君がコードやその動作を見ずに、他人が君のPCでコードを実行しやすくしようとするものだよ。これらは同じカテゴリじゃないんだよね。
クライアントデバイス上のSGXはイマイチだけど、サーバー上のSGXはユーザーの利益を守るのに使えるよ。もし機密顧客データをSGX内に入れたら（操作はできるけど抽出はできないように）、国家レベルの敵が”顧客データの令状がある、引き渡せ”って言っても、”無理です”って言えるんだ。コードがSGX内で実行されてるって証明もできるしね（SGXが破られてない前提だから弱いけど、何もないよりマシ）。敵はサーバーに物理アクセスしてSGXを破ろうとするかもだけど、ASLRやNXの迂回みたいに一手間かかるから、本当にそのデータが重要じゃないとやらないでしょ。
サーバー上のSGXが破れるのは、クライアント上のSGXが破れるときだけだよ。他人のPCを所有するか、他人に自分のPCを所有させないか、両方は無理。お尻隠しにはなるかもしれないって言うけど、効果のない技術的解決策でも法的な責任回避になることは多いよね。でもこれが主流になったら、NSAはSGXを破るツールをこっそりインストールしてくるだろうから、バックアッププランは用意しとけよ。あと、IntelはSGXが破られやすくて使われてなかったから、CPUからSGXを削除したことにも注意ね。
SGXは削除されたけど、Intelはサーバー向けCPUでSGXみたいな技術（略語は忘れたけど）をまだ開発してるよ。NSAはもうSGXを破るツールを持ってるだろうけど、その投資を守るため、優先度の低いターゲットには使わないんじゃないかな。NXやASLRと比較したのは、それらが日常的に迂回される対策だけど、それでも普通は良いアイデアだと考えられてるからだよ。
これらが速度面で改善され続けるっていう考えは、平均速度の数学問題を思い出すな。『古い車が丘を上り下りする必要がある。最初の1マイルの上り坂では時速15マイルしか出せない。車はその後1マイル下り坂を進む。全2マイルの旅で平均時速30マイルを出すには、下り坂でどれくらいの速さで行く必要があるか？』過去の改善が未来の可能性を示すとは限らないよ。それぞれの改善が以前と同じ解決策の再適用じゃないんだから。これらはアルゴリズムであって、単純な物理プロセスの縮小じゃないんだ。
下り坂って崖なの？ Googleだと車の終端速度は200-300mphだから、時速300マイルで1マイル落下するには12秒、加速時間考慮して15秒に丸めよう。全2マイルを平均時速30マイルで終えるには4分必要だから、上り坂に225秒残るね。古い車の速度計は不正確だろうし、6%の誤差で時速15マイルと表示して1マイルを225秒で走れるならOK。新品タイヤなら可能だろうし。だから、時速240マイルってことにしよう。それが15秒間の1マイル自由落下の平均速度だ。
時速41マイルだよ。質問者が数字を丸めるのが大好きか、最小限の測定ツールしかなかったと仮定するとね:)))
