難読化（パートII）：Diamond IO

難読化（パートII）：Diamond IO 特別な謝辞：Sora Suegami氏とJanmajaya Mall氏にフィードバックとレビューの協力に感謝します。 このシリーズの前編では、最も主流で保守的な暗号学的難読化（iO）プロトコルの技術ツリー全体を概観しました。これらのプロトコルは、プログラムを「暗号化」することで、平文の入力に対して暗号化されたプログラムを実行し、平文の出力を得られるようにしますが、プログラムの内部ロジックを見ることはできません。これは、プログラムに内部的な秘密鍵が含まれており、難読化によって秘密鍵を使った特定の操作は許可するものの、それ以外の操作はできないパッケージを提供するといった、様々なユースケースに利用できます。これまでのプロトコルの最大の欠点は、文字通り宇宙的な実行時間でした。実際に実行時間を計算しようとすると、宇宙の寿命よりも長い時間がかかるという結果になります。そのため、最近の実現可能性に関するブレークスルーにもかかわらず、難読化プロトコルはこれまで理論的な curiosities に留まっていました。 本稿では、異なるスタイルの難読化であるdiamond iO（論文、プレゼンテーション）について詳しく説明します。このアプローチは、より「大胆」で、まだあまりテストされていない暗号学的仮定に依存していますが、実行時間を宇宙的ではなく「惑星的」なレベルにまで短縮することに成功しています。これは依然として今日では非現実的ですが、おそらくあと数回の最適化で、少なくとも一部のユースケースでは現実のものとなる可能性があります。 異なる種類の難読化 Diamond IOはどのように機能するのでしょうか？ 大まかに言うと、diamond iOは、前回の記事で説明したBGG+14属性ベース暗号（ABE）スキームを改変して構築されています。続行する前に、そのセクションを再読することを強くお勧めします。また、これはこのAbeではありません。このAbeがどれか知っている人にはボーナスポイントです。前回の記事の4つよりも難しいですよ！ 従来のiOプロトコルと同様に、diamond iOはFHE内で計算を実行し、評価者に、計算が正しく実行された結果である場合にのみ結果を復号する方法を提供します。しかし、diamond iOがこの仕組みを使用する方法は異なります。第一に、条件付きFHE復号を行うために全く異なるメカニズムを使用します。第二に、入力のエンコーディングを生成するために全く異なるメカニズムを使用します。この2つの変更は互いに関連しており、diamond iOがはるかに効率的である真の理由です。これは、FEの上に構築されたはるかに複雑なタワーではなく、「機能的暗号化（FE）と同等の計算負荷」で済みます。 BGG+14は、 s * (B - G * m) + e の形式のエンコーディングを維持することによって機能することを思い出してください。ここで： sは秘密値 Bは公開行列で、回路の各「ワイヤ」ごとに異なるものがあります mはそのワイヤ上の計算中のビット eは「誤差」です（あるいは、減算の代わりにG * mを加算することもできます。どちらも等しく有効で効率的なスキームです） 2つの「入力ワイヤ」への操作（加算、乗算、または否定）を表す2つのB行列から、出力ワイヤを表すB行列を生成できます。操作の2つの有効なエンコーディングから、出力ワイヤを表すB行列に基づいた出力（1 - m、m_a + m_b、またはm_a * m_b）のエンコーディングを得ることができます。 重要なのは、これは完全準同型暗号（FHE）ではないということです。乗算を行うには、m_aまたはm_bのいずれか一方を平文で知る必要があります。 BGG+14では、最後に、特定の「出力」ワイヤ上の計算値が0の場合にのみ、事前に選択された出力を復号できるステップがあります。ここでは、それは行いません。代わりに、エンコーディングから必要なデータだけを抽出します。しかし、どちらの場合も、復号方法は、出力ワイヤを表す特定の行列B_{final}に基づいたエンコーディングに依存します。これが、復号が正しく計算された場合にのみ可能であり、他のコンテキストでは不可能であることを強制する方法です。 Diamond IOの核心は以下の通りです： 入力xを表すBGG+14 B行列とエンコーディング、およびその他のいくつかのものを生成します。 これらのBGG+14エンコーディング上で計算を実行し、xをFHE暗号文FHE.enc(f(x, z))に変換します。ここでfは公開であり、zは難読化者が隠そうとしている内部の隠し入力です。 FHE出力を復号するために、わずかに変更されたBGG+14ステップをさらに実行します。 最後に、「トラップドア」ステップを実行します。これはBGG+14復号に似た仕組みを借用しますが、非常に異なる方法で使用し、実行した回路が「正しい」回路である場合にのみ結果を取得します。 Diamond IOの複雑さは3つの点にあります： 1. 計算された回路がfを表す回路と全く同じである場合にのみこのFHE復号を可能にし、鍵を完全に漏洩させないように、末尾の出力のエンコーディングに対して行うこと。 2. FHE復号の出力が完全に一様でランダムに見えるように、このスキーム全体が安全であるという事実を考慮してf(x, z)を調整し、「f(x, z)をzを隠して難読化する」から「プログラム全体を隠す完全なiO」に変換すること。 3. 評価者が秘密を漏らすことなく、入力のABEエンコーディングを構築できるようにすること。 最初の2つのアイデアは、以前の研究、特にHLL23とAKY24から来ています。3番目の要素、つまり入力のABEエンコーディングを構築するメカニズムは、元々はGGH15から来ています。Diamond IOにおける新しい貢献は、プログラム全体を評価するためにそれを使用するのではなく（これは安全でないことが判明しました）、入力のBGG+エンコーディングを生成するためにそれを使用することです。これらの3つの要素を順番に見ていきます。 復号ステップ 評価者が、以下の4種類のBGG+エンコーディングを何らかの方法で入力として取得したと仮定します： 1（これは後で、これらのエンコーディングを構築するのに役立ちます） fの固定された隠し入力zのFHE暗号文（暗号化されたバージョンをE[z]と表記します） 公開入力ビット：s * (B_{x_1} - x_1 * G) + e_{x_1} ... s * (B_{x_L} - x_L * G) + e_{x_L}、ここでx_1 ... x_Lはfへの入力です FHE復号鍵（低ノルムである必要があり、最後の値は-1である必要があります）。これをtと呼びます。 このアンサンブルを[1, E[z], x, t]とラベル付けします。 評価者はまず、E[z]とxのエンコーディングを使用してBGG+計算を実行します。計算は直接f(x, z)ではなく、FHE.eval(f, x, E[z])であることを思い出してください。BGG+の観点からは、xとE[z]は両方とも平文ビットです。FHEの観点からは、zは隠し入力であり、その暗号化された形式のみが評価者に知られています。 BGG+計算の終了後、評価者はf(x, z)を表すFHE暗号文のビットのBGG+エンコーディングを取得します。 BGG+は完全準同型暗号ではありません。一般に、BGG+エンコーディング上の計算には、基になる平文が必要です。しかし、加算については、既知の値による乗算についても、この規則を回避できます。これは、m_a * m_bのBGG+エンコーディングが次のように計算されるためです： c_{out} = m_b * c_a + c_b * G^{-1}(B_a) （エンコーディングがG * mを減算する代わりに加算していた場合、それはG^{-1}(-B_a)になります） m_aが未知（つまり、エンコーディングのみで与えられる）であっても、m_bが既知である限り、許可できます。これは私たちにとって重要な事実です。 その理由を見るために、GSW復号の構造（このシリーズの前回の記事でも説明されています）を思い出してください。評価者は実際の実行トレースのすべてのビット、最終的なFHE暗号文（Yと呼びます）を含む、すべてのビットを知っているため、FHE復号鍵tをBGG+エンコーディングとしてのみ評価者に提供できます。 復号がどのように機能するかを見てみましょう。t * Yを計算したいのです。tのBGG+エンコーディングのみを持っており、YのBGG+エンコーディングと生のビットの両方を持っています。したがって、原理的には実行できます。しかし、問題があります。Yはビットのシーケンスとして提供されます。つまり、vは得られません。