Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption

あなたは友人に秘密のメッセージを送ろうとしていますが、中身を覗き見したがるいたずら好きなゴブリンが運営する郵便局を通じて送らなければなりません。昔は、手紙を箱に入れて鍵をかけましたが、一度ゴブリンが箱を開けて中身を読んでしまうと、秘密は消えてしまいます。その後、「準同型暗号（Homomorphic Encryption）」という魔法のような発明が登場しました。これは、特別な鍵付きの箱のようなもので、ゴブリンは中の数字を一度も解読することなく、鍵がかかったままの状態で足し算や掛け算、並べ替えなどの計算を行うことができます。ゴブリンが計算結果を返してきたとき、あなたはそれを解錠して正しい答えを得ることができますが、ゴブリンは中の数字を一度も見ることができなかったのです。

しかし、ここには落とし穴があります。最も普及している「CKKS」と呼ばれるこの魔法のバージョンでは、数学が完璧ではありません。数字があまりに複雑なため、得られる結果は少し「ぼやけて」いたり、近似値であったりします。まるで鮮明な写真ではなく、ぼやけた写真のようです。通常、このぼやけは些細なことであり、単なるわずかなノイズに過ぎません。しかし、ずる賢いゴブリン（攻撃者）が、多くの異なる数学の問題に対して答えを求め、そのぼやけた結果を、彼らが予想する正解と比較することで、あなたの秘密鍵を少しずつ再構築できてしまうことがあります。それは、もしゴブリンが、あなたの鍵付きの箱を振ったときにどれくらい揺れるかを正確に察知でき、その「揺れ」を利用して、組み合わせ（暗証番号）を突き止めるようなものです。これを防ぐために、暗号学者は「ノイズ・フラッディング（Noise Flooding）」という防御策を考案しました。これは、答えを返す前に巨大でランダムな静電気（ノイズ）を加え、ずる賢いゴブリンが秘密を盗むために使おうとする微細な手がかりをかき消してしまう手法です。

ここで大きな疑問が生じます：どれくらいの静電気（ノイズ）を加える必要があるのか？ ノイズが少なすぎると、ゴブリンは依然として秘密を見つけることができます。逆に多すぎると、答えがあまりにぼやけすぎて使い物にならなくなります。非常にトリッキーなのは、ゴブリンは一つひとつの質問を投げ、前の回答に基づいて戦略を変えることができる点です。もし質問ごとに個別にノイズを加えるとしたら、「コスト」は急速に膨れ上がり、最終的な答えを極めて使い物にならないほどぼやけさせてしまいます。しかし、ある巧妙な数学的アイデアは、ゲーム全体を一度に俯瞰して考えれば、コストはもっとゆっくりとしか増えない――例えば、質問の数の「平方根」のように――ということを示唆しました。この論文は、この巧妙なアイデアが実際に機能することを証明し、さらに、間違いがないことを確認するために、コンピュータがすべてのステップをチェックできる方法で証明することについて書かれたものです。

---

この論文の大きな発見：「ピタゴラス」の秘密

「Verified Pythagorean Composition for Adaptive Cryptographic Games（適応的暗号ゲームのための検証済みピタゴラス組成）」と題されたこの論文は、**形式検証（Formal Verification）**における極めて大きな成果です。形式検証とは、基本的には超スマートなコンピュータを使用して、数学の証明に誤りがないかをチェックすることです。著者である研究者チームは、ノイズ・フラッディングに関する有名なセキュリティ論証を、コンピュータが理解できる言語へと翻訳しました。そして、数学的なステップがすべて妥当であることを保証するために、コンピュータにすべての論理的ステップを検証させました。

彼らの研究の核心は、ずる賢い攻撃者が多くの質問を投げかける際に、エラーがどのように蓄積するかについての新しい考え方です。

「ぼやけた写真」の問題

写真を隠すために、写真に少しだけ静電気（ノース）を加えると想像してみてください。ノイズが少なければ、写真はまだ鮮明ですが、鋭い目のゴブリンは秘密を見つけてしまうかもしれません。ノイズが多いと、秘密は安全になりますが、写真はめちゃくちゃになってしまいます。
暗号の世界では、この「静電気」はノイズと呼ばれます。この論文では、攻撃者がメッセージの復号結果を最大 $q$ 回要求するシナリオを検討しています。そのたびに、防御側は秘密を隠すためにノイズを加えます。

• 従来の方法（線形損失）： 各質問を個別のイベントとして扱う場合、あらゆる質問に対して安全であるために、十分な量のノイズを加える必要があります。もし攻撃者が100回の質問をすれば、100倍のノースが必要になり、最終的な結果は完全に使い物にならなくなります。
• 新しい方法（平方根損失）： この論文は、よりスマートな戦略を裏付けています。攻撃者の質問は互いに関連している（「適応的」である）ため、必要なノイズの総量は、質問の数の平方根（$\sqrt{q}$）でしか増えないことを示しています。つまり、100回の質問があったとしても、100倍ではなく、10倍のノイズを加えるだけで済むのです。これは大きな勝利です。なぜなら、答えをるい much に鮮明に保ちながら、安全性を維持できるからです。

「ピタゴラス」のアナロジー

なぜ「ピタゴラス（ピタゴラスの定理）」と呼ぶのでしょうか？ 直角三角形を思い浮かべてください。2つの辺の長さが3と4である場合、一番長い辺（斜辺）は、$3 + 4 = 7$ ではなく、$\sqrt{3^2 + 4^2} = 5$ です。全体の長さは、単に辺を足し合わせたものよりも短くなります。
この論文において、「辺」とは、攻撃者による各質問から生じる微細なリスク（または「コスト」）のことです。

• 間違い： もしリスクを単純に足し合わせる（$3 + 4$）と、巨大で恐ろしい数字になります。
• 現実： 著者たちは、これらのリスクが三角形の辺のように組み合わさることを証明しています。それらは互いに「打ち消し合う」ため、総リスクは、二乗の和の平方根となります。
  論文では、これらのリスクを個別に追跡し（「条件付きカルバック・ライブラー・コスト」として。これは、答えがどれほど異なって見えるかを示す高度な数学的表現です）、最後にまとめて「安全性スコア」に変換できることを証明しています。これにより、数学的な効率性が保たれ、ノイズを低く抑えることが可能になります。

コンピュータの役割：「ロボット弁護士」

「なぜコンピュータを使ってチェックする必要があるのか？ 数学は数学ではないのか？」と思うかもしれません。
問題は、これらの証明が極めて複雑であることです。これらは、確率、乱数、そして考えを変えるずる賢い攻撃者の挙動を扱い、何千ものステップを含んでいます。人間が細部を見落としたり、議論全体を崩壊させるような小さな仮定を誤ったりすることは容易にあります。
著者たちは、Rocq（証明アシスタント）と SSProve というライブラリを使用しました。彼らは単に紙の上に証明を書いたのではなく、この暗号ゲームのデジタルモデルを構築したのです。

1. ロジック： 彼らは、これらの「ピタゴラス的」なリスクの組み合わせをコンピュータに処理させるための、新しい一連のルール（「プログラム・ロジック」）を作成しました。
2. コンパイラ： 彼らは「トレース・コンパイラ」を構築しました。これは、攻撃者のプログラムを監視するロボットのようなものです。それは、秘密を守りつつ、攻撃者を一時停止させたり、次の動きを覗き見たり、あるいは続行させたりすることができます。
3. 検証： コンピュータは、すべてのコードの行とすべての数学的ステップをチェックしました。基礎となる暗号が安全であれば、このノイズ・フラッディング防御を追加することで、これら特定のタイプの攻撃に対しても、この「平方根」の効率性を持って安全であることを確認しました。

これがあなたにとって何を意味するか

この論文は、新しい暗号化手法を発明したり、新しい攻撃法を生み出したりするものではありません。代わりに、既知の防御策（ノイズ・フラッディング）を取り上げ、それが巧妙な「ピタゴラス的」理論が予測した通りに機能することを、絶対的な数学的確実性をもって証明したものです。

• それは、 適応的な攻撃者に対して安全であるために、膨大な量のノイズ（線形成長）を加える必要があるという考えを否定しました。
• それは、 もし基礎となる暗号がすでに安全であれば、「平方根」の成長こそが真実であり安全であることを証明しました。
• それは、 この防御の背後にある複雑な数学に、隠れた欠陥がないことを確認しました。

著者たちは、これは「ロジック」の検証済み証明であり、世界中のすべての特定の暗号ソフトウェアが完璧であるという保証ではない、という点に非常に慎重です。彼らは、もし優れた暗号方式があり、このノイズ・フラッディングを正しく適用すれば、数学的に安全であることを証明しました。また、最も普及している暗号スキームの一つであるCKKS自体の詳細まではチェックしていないことも述べています。しかし、デジタル・プライバシーの守護者にとって、これは大きな前進です。攻撃者がどれほど賢く執拗であっても、私たちの秘密を守る数学を信頼できることを意味するからです。

要するに、この論文は、長年の議論の末に、設計が堅牢であることを確認するためにロボットの検査官チームを呼び寄せた熟練の建築家のようなものです。彼らは、橋を建設するために、当初考えていたよりも倍の鋼鉄を用意する必要はないことを証明しました。設計の巧妙な幾何学（ピタゴラスの法則）があれば、道はクリアに保たれ、秘密は隠され続けるのです。