難読化(パートII):Diamond IO
Obfuscation (Part II): Diamond IO (vitalik.eth.limo)
要約
本記事は、暗号学的難読化プロトコルに関する前回の記事の続編です。前回の主流な難読化プロトコル(iO)は実行時間が宇宙的(galactic)に長いため理論的なものに留まっていましたが、本稿では「Diamond IO」という新しいアプローチを紹介します。Diamond IOはより大胆な暗号学的仮定に依存しますが、実行時間を惑星的(planetary)なレベルにまで短縮し、実用化に近づけています。
全文翻訳
難読化(パートII):Diamond iO
ダークモードトグル
2026年7月28日 全投稿を見る
難読化(パートII):Diamond iO
*Sora Suegami氏とJanmajaya Mall氏のフィードバックとレビューに多大な感謝を。
このシリーズのパート1では、暗号学的難読化(iO)プロトコルの最も主流で保守的なラインの技術ツリーを網羅しました。これらのプロトコルは、プログラムを「暗号化」し、誰でも平文の入力に対して「暗号化された」プログラムを実行して平文の出力を得られるようにしますが、プログラムの内部ロジックを見ることはできません。これは、プログラムが内部に秘密鍵を含んでいるような状況で、秘密鍵を使って「あること」を「ある状況下」で実行できるパッケージを渡すという目的に役立ちます。
これまでのプロトコルの最大の欠点は、文字通り銀河系的な実行時間でした。実際に実行にかかる時間を計算しようとすると、宇宙の寿命よりも長い時間がかかってしまうでしょう。そのため、実現可能性に関する最近のブレークスルーにもかかわらず、難読化プロトコルはこれまで理論的な好奇心の域を出ませんでした。
この記事では、異なるスタイルの難読化であるDiamond iO(論文、プレゼンテーション)について詳しく説明します。このアプローチは、より「大胆」で、まだ十分に検証されていない暗号学的仮定に依存していますが、実行時間を銀河系スケールではなく、惑星スケールに抑えることを達成しています。これは依然として今日では非現実的ですが、いくつかのユースケースにおいては、わずかな最適化で実現可能になるかもしれません。
[画像: 異なる種類の難読化]
異なる種類の難読化
Diamond iOはどのように機能するか?
大まかに言うと、Diamond iOは、前回の投稿で説明したBGG+14属性ベース暗号(ABE)スキームを改変して構築されています。続行する前に、そのセクションを再読することを強くお勧めします。
[画像: これはアベではない]
これもアベではない。これがどのAbeか知っている人にはボーナスポイント。前回の投稿の4つよりも難しい!
より伝統的なiOプロトコルと同様に、Diamond iOはABE内で計算をFHEで実行し、評価者に、計算が正しく実行された結果である場合にのみ復号できる方法を提供します。しかし、Diamond iOがこの仕組みを「使用」する方法は異なります。第一に、条件付きFHE復号を行うために、全く異なるメカニズムを使用します。第二に、入力のエンコーディングを生成するために、全く異なるメカニズムを使用します。
これら2つの変更は互いに関連しており、Diamond iOがはるかに効率的である真の理由です。それは、FEの上に構築されたはるかに複雑なタワーではなく、「準同型暗号(FE)と同等の計算負荷」であるだけです。
復習として、BGG+14は以下の形式のエンコーディングを維持することで機能します。
(s \cdot (B - G \cdot m) + e)
ここで:
- (s) は秘密値
- (B) は公開行列で、回路の各「ワイヤ」ごとに異なるものが存在します
- (m) はそのワイヤ上のビット値(計算中)
- (e) は「誤差」
(あるいは、減算の代わりに (G \cdot m) を加算することもできます。どちらも同等に有効で効率的なスキームです)
2つの「入力ワイヤ」への操作(加算、乗算、または否定)を表す2つの (B) 行列が与えられた場合、出力ワイヤを表す (B) 行列を生成できます。操作の2つの入力に対する有効なエンコーディングが与えられれば、出力((1 - m)、(m_a + m_b)、または(m_a \cdot m_b))のエンコーディングを得ることができます。これは完全準同型暗号ではありません。乗算を行うには、(m_a) または (m_b) のいずれかを平文で知る必要があります。
BGG+14には、計算のある「出力」ワイヤの値が0である場合にのみ、事前に選択された出力を復号できるステップがあります。ここでは、それを行いません。代わりに、エンコーディングから必要なデータを抽出します。しかし、どちらの場合も、復号方法は、エンコーディングが特定の行列 (B_\text{final}) に基づいているかどうかに依存します。これは、正しく計算した場合にのみ復号が可能であり、それ以外のコンテキストでは不可能であることを保証する方法です。
Diamond iOの核心は以下の通りです。
- 入力 (x) およびその他のいくつかの項のBGG+ (B)-行列とエンコーディングを生成します。
- これらのBGG+エンコーディング上で計算を実行し、(x) を FHE暗号文 (FHE.enc(f(x, z))) に変換します。ここで (f) は公開されており、(z) は難読化者が隠そうとしている内部の隠し入力です。
- わずかに変更されたBGG+ステップを実行して、出力をFHE復号します。
- 最後に、「トラップドア」ステップを実行し、BGG+復号に似た仕組みを利用しますが、非常に異なる方法で使用して結果を取得します。これは、計算された回路が「正しい」ものである場合にのみ可能です。
Diamond iOの複雑さは3つの点にあります。
- 計算された回路が (f) を表す回路と全く同じである場合にのみFHE復号を可能にし、鍵を完全に漏洩させないように、終端で出力のエンコーディングに対して行うこと。
- このスキーム全体が、FHE復号の出力が完全に一様ランダムに見える場合にのみ安全であるという事実を考慮し、「(z)を隠す (f(x, z)) の難読化」から「プログラム全体を難読化する」へ変換するための (f(x, z)) のいくつかの調整。
- 難読化者が秘密を漏らすことなく、入力のABEエンコーディングを評価者が構築できるようにする方法。
最初の2つのアイデアは、以前の研究、特にHLL23とAKY24に由来します。3番目の要素、つまりABEエンコーディングの入力の構築メカニズムは、元々はGGH15に由来します。Diamond iOにおける新しい貢献は、プログラム全体を評価するため(これは安全ではないことが判明しました)ではなく、入力のBGGエンコーディングを生成するためにそれを使用することです。
これらの3つの要素を順に見ていきます。
復号ステップ
評価者が、以下の4種類のBGGエンコーディングを何らかの方法で入力として受け取ると仮定します。
- (1)(これは後でエンコーディングの構築に役立ちます)
- 固定された隠し入力 (z) のFHE暗号文(暗号化されたバージョンを (E[z]) と表記します)
- 公開入力ビット: (s \cdot (B ext{_{x_1}} - x_1 \cdot G) + e ext{_{x_1}} \dots s \cdot (B ext{_{x_L}} - x_L \cdot G) + e ext{_{x_L}})。ここで (x_1 \dots 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 \cdot m_b) のBGG+エンコーディングが次のように計算されるためです。
(c ext{_{out}} = m_b \cdot c ext{_a} + c_b \cdot G ext{`}^{-1}(B ext{_a}))
(エンコーディングが (G \cdot m) を減算する代わりに加算していた場合、(G ext{`}^{-1}(-B ext{_a})) となります)
(m ext{_a}) が不明(つまり、エンコーディングのみで与えられる)であっても、(m_b) が既知であれば、(m ext{_a}) を未知のままで計算を許可できます。
これは私たちにとって重要な事実です。なぜなら、GSW復号の構造(このシリーズの前回の投稿でも説明)を思い出してください。
ciphertext = t * Y
評価者は実際の実行トレースのすべてのビット、最終的なFHE暗号文((Y)と呼びます)を含む、すべてのビットを知っているため、FHE復号鍵 (t) をBGG+エンコーディングとしてのみ提供できます。
復号がどのように機能するかを見てみましょう。
(t \cdot Y) を計算したいとします。(t) のBGG+エンコーディングは持っていますが、(Y) のBGG+エンコーディングと生のビットの両方を持っています。したがって、原理的には実行可能です。
しかし、問題があります。(Y) はビットのシリーズとして提供されます。つまり、([2, 6, 11, \dots]) のようなベクトルは得られません。([0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, \dots]) のようなベクトルが得られます。ここで、各ビットのバケット(この例では4ビット)は、慣例により最下位ビットから順に、数値のバイナリエンコーディングです。したがって、(t ext{_{j}} \cdot Y ext{_{{i,j,b}}}) のようなエンコーディングが出てくるように、ビットを再スケーリングする必要があります。ここで (Y ext{_{{i,j,b}}}) は、バケット (Y ext{_{{i,j}}}) の (2 ext{`}^b) の位のビットです。
便宜上、同じ順序のビットのエンコーディングをグループ化し、最終的に回答の同じ値の内側に入るようにします。つまり、すべての (j) について、特定の (i) と (b) の列 (t ext{_{j}} \cdot Y ext{_{{i,j,b}}}) です。
(\sum ext{_{j}} s \cdot (B ext{_{{out,i,j,b}}} - t ext{_{j}} \cdot Y ext{_{{i,j,b}}} \cdot G) + e ext{_{{out,i,j,b}}})
(= s \cdot (B ext{_{{out,i,b}}} - (tY) ext{_{{i,b}}} \cdot G) + e ext{_{{out,i,b}}})
[画像: Yの1つのエントリと1つの列]
これでパズルにたどり着きました。異なる順序のビットをどのように組み合わせるのでしょうか?
単純な方法としては、再スケーリングして加算することができます。
(\sum ext{_{b=0}}^{\log(q)-1} (s \cdot (B ext{_{{out,i,b}}} - (tY) ext{_{{i,b}}} \cdot G) + e ext{_{{out,i,b}}}) \cdot 2 ext{`}^b)
これの問題は、高位桁の誤差が過度に増幅されてしまうことです。最高位の項の誤差は (2^{\log(q)-1} = \frac{q}{2}) 倍されるため、全体を圧倒してしまいます。
そこで、代わりに次のようにします。
(\sum ext{_{b=0}}^{\log(q)-1} (s \cdot (B ext{_{{out,i,b}}} - (tY) ext{_{{i,b}}} \cdot G) + e ext{_{{out,i,b}}}) \cdot G ext{}^{-1}(2 ext{}^b G))
(G ext{}^{-1}(2 ext{}^b G)) がここで全ての仕事を行います。基本的に、これはバケットごとの左シフト演算子です。各 (log(q))
ビットのバケット (tY) を取り、それらをすべて左にシフトします。
BGG+エンコーディングの形式が (s \cdot (B - G \cdot m) + e) であることを思い出してください。そして (G) がこの形式であることを思い出してください。
[画像: G行列]
これは、BGG+エンコーディングが同時にあらゆるスケールで (m) をエンコードしていることを意味します。そして、私たちがやっていることは、高位ビットを表す各バケットの最初の列に、高位のビットのエンコーディングを移動させているのです。そして、加算とシフトのみを行い、乗算を行わないため、誤差の増加を、加算によって導入されるわずかな量以上に抑えることができます。
(G ext{}^{-1}(2 ext{}^b G)) 行列がこのシフト効果を持つ理由を見るために、(G ext{}^{-1}\) も見てみましょう。単独では、\(G ext{}^{-1}) は (G) の右逆行列であり、ビット分解演算子(行列ではない)です。
したがって、単純な (G ext{`}^{-1}(G)) は単位行列になります。
[画像: G^-1(G)行列]
しかし、(G) を (2) で乗算してから (G ext{`}^{-1}) に挿入すると、各バイナリ分解は1つ上の位置にシフトされ、目的のシフトが得られます。
[画像: G^-1(2bG)行列]
これは、ベクトルと行列の代数に「各バケットを左シフトする」メカニズムを簡単にエンコードできるようにするための、単なる表記上のトリックです。また、(G ext{}^{-1}(2 ext{}^b G)) 行列も非常に低ノルム(1と0のみ)であることがわかります。これは、このステップが誤差を不当に増大させないことを知るもう1つの方法です。
このステップの最終的な結果は、(tY) のBGG+エンコーディングが得られることです。
(s \cdot (B ext{_{final,i}} - G \cdot (tY) ext{_{i}}) + e ext{_{final,i}} )
これらはもはや「通常の」エンコーディングではないことに注意してください。なぜなら、((tY) ext{_{i}})
は (q) を法とする完全な範囲の値であり、評価者は平文の値を知らないからです。評価者はそれ以上のBGG+乗算を実行できません。しかし、それは問題ありません。なぜなら、評価者が残しているのは「(s) でのラップ」を削除することだけで、最終目標である ((tY) ext{_{i}} + e) の抽出に進むことができるからです。
((tY) ext{_{i}} + e) を抽出するために、BGG+ ABEから完全に逸脱します。ABEでは、復号が可能な場合、答え (C(tag)) は0に等しいことを知っています。(G \cdot C(tag)) は消滅し、それがメッセージを抽出できる理由です。(G \cdot C(tag)) はブラインディングファクターの役割を果たします。ここでは、ユースケースが異なります。((tY) ext{_{i}})
が抽出したい全体です。
BGG+エンコーディングを次のように書き直しましょう。
(s \cdot B ext{_{final,i}} - s \cdot G \cdot (tY) ext{_{i}} + e ext{_{final,i}} )
ここで、この式の単一の列を抽出します。つまり、最後のバケットの最下位桁の列です。
[画像: 抽出された列]
最下位桁の列の選択は、「従来のGSW復号」から逸脱しますが、覚えておいてください。バケットごとのシフトトリックのおかげで、この時点では最下位桁の列には、メッセージという最も重要な値の最高位桁から取得された情報が含まれています。
(s) を、その最後の値((s ext{`}_{last}) と表記します)が-1に等しくなるように制約します。また、選択した (G) の列、(g) は、多数のゼロとそれに続く1で構成されていることに注意してください。これにより、単純化された式が得られます。
(s \cdot b ext{_{i}} - s ext{`}_{last} \cdot (tY) ext{_{i}} + e ext{_{i}} )
(= s \cdot b ext{_{i}} + (tY) ext{_{i}} + e ext{_{i}} )
ここで、(s \cdot b ext{_{i}})
を計算して削除するタスクです。
後述のセクションから1つの事実を引用します。評価者は、エンコードされたサンプル (ct = (m \otimes s) P ext{_{L}} + e ext{_{L}})
の形式で (s) に「アクセス」できます。ここで (m) は難読化された計算の完全な入力であり、(\otimes) は「テンソル積」です。つまり、(m \otimes s) は (len(m) \cdot len(s)) の長さのベクトルであり、(s) に (m) の最初の値を掛けたもの、次に (s) に (m) の2番目の値を掛けたものなどが含まれます。都合の良いことに、(m) の最初の値は1に固定されています。
[画像: m ⊗ s]
ここで、トラップドアメカニズム(前回の投稿のABEセクションで説明)を使用して、低ノルムの逆像 (K ext{_{G}})
を生成します。これは以下を満たします。
(P ext{_{L}} \cdot K ext{_{G}} = M)
ここで、(M) はすべての (b ext{_{i}})
を含む行列です。つまり、各 (B ext{_{final,i}})
行列から抽出された列であり、次元を一致させるためにゼロでパディングされています。
これにより、(ct \cdot K ext{_{G}})
は次のように評価されます。
(((m \otimes s) \cdot P ext{_{L}} + e ext{_{L}}) \cdot K ext{_{G}})
(= (m \otimes s) \cdot P ext{_{L}} \cdot K ext{_{G}} + e ext{_{L}} \cdot K ext{_{G}})
(= (m \otimes s) \cdot M + e ext{_{g}})
ここで、(M)
の最初の (len(s)) 行のみが非ゼロであり、(m \otimes s) の最初の (len(s)) 個の値は単に (s) であることに注意してください。したがって、上記は次のように削減されます。
(s \cdot M + e ext{_{g}})
これは、必要なすべての (s \cdot b ext{_{i}} + e ext{_{{i,g}}})
の連結です。
これで、それを減算して、必要な ((tY) ext{_{i}} + e ext{_{i}})
値を得ることができます。これらはFHE復号結果です。そして最後に、評価者は丸めて、(f(x, z)) の最終値を取得します。
ここで、セキュリティがどこから来るのかを再び見ることができます。(K ext{_{G}})
「トラップドア」により、評価者はこれらの (b ext{_{i}})
に対してのみこれを抽出できます。そして、(b ext{_{i}})
は (B ext{_{final,i}})
から来ており、回路の正確な形状にバインドされています。評価者が異なる (b' ext{_{i}})
に対して (s \cdot b' ext{_{i}} + e ext{_{{i,g}}})
を計算した場合、((tY) ext{_{i}} + e ext{_{i}})
をブラインドする (s \cdot (b ext{_{i}} - b' ext{_{i}}))
項が残され、答えを抽出できなくなります。
(f(x, z)) への調整
上記のスキームのセキュリティは、1つの条件の下でのみ証明可能であることが判明しました。それは、出力 ((tY) ext{_{i}} + e ext{_{i}})
が一様ランダムであることです。実際には、すべての (2 ext{`}^L)
入力にわたって共同で擬似ランダムであることです。「共同で擬似ランダム」とは、ここでは、無制限に完全な指数サイズのテーブルにアクセスできたとしても(ただし、計算時間は多項式時間のみ)、ランダムデータと区別できないことを意味します。
これは実際には私たちの作業を困難にします。「通常の」GSW復号では、(t \cdot Y) の最後の項目は (\frac{q}{2} \cdot m + e) に等しくなります。これは2つの問題を引き起こします。
- 誤差はメッセージよりもはるかに小さいことが多いため、出力は (0) と (\frac{q}{2}) の周りで非常に「スパイク状」になります。誤差が常に全範囲をカバーできるとしても(困難:最悪ケースと平均ケースは大きく異なります)、LWE誤差はメッセージと相関しているため、依然として情報が漏洩します。
- 出力 (m) の分布自体が一様ではありません。なぜなら、「自然な」関数 (f) のほとんどはランダムではないからです。
これらを順番に対処できます。
まず、FHEで評価する関数を変更します。(z) に2つの秘密 ((z ext{_1}, z ext{_2}))
を含めるようにします。つまり、関数の秘密入力とランダムなPRF鍵です。次に、(FHE.eval(f', x, E[z])) を実行します。ここで:
(f'(x, z) = \frac{q}{2} \cdot f(x, z ext{_1}) - (\frac{q}{4} - e ext{`}_{max}) + H ext{_1}(x, z ext{_2}))
ここで、(H ext{_1})
は ([0 \dots \frac{q}{2}-2e ext{}_{max})\) の範囲の値を持つハッシュ関数であり、\(e ext{}_{max})
は、私たちの手順全体が導入する可能性のある最大誤差の境界です。形式的には、(H ext{_1})
はPRF(「擬似ランダム関数」)である必要があります。
正しさのためには、単なるハッシュとして考えるだけで十分です。しかし、実際には、このハッシュの計算が評価時間のほぼ全てを占めるため、Diamond iOを実用的にするには、(H ext{_1})
をその特定のニーズに合わせて大幅に最適化し、SHA256のような汎用アルゴリズムを使用しないことがほぼ確実です。
「通常の」GSWでは、(\frac{q}{2})
係数は暗黙的です。メッセージが誤差でぼやけないように、メッセージに (\frac{q}{2}) を掛けるのは当然です。ここでは、(f(x, z ext{_1}))
部分に (\frac{q}{2}) を掛けますが、(H ext{_1}(x, z ext{_2}))
部分には掛けません。そして、その下位ビットの一部が誤差によって破損しても構いません。(H ext{_1}(x, z ext{_2}))
は回復したいデータではなく、「最大範囲」の擬似ランダムノイズであり、FHEおよびABE関連のノイズをぼかすために存在します。(\frac{q}{4} - e ext{}_{max}\) オフセットの目的は、\(H ext{\_1}\) の出力を「中央揃え」にし(つまり、範囲を \(\[-(\frac{q}{4} - e ext{}{max}), \frac{q}{4} - e ext{`}{max}]) にする)、最も近い (\frac{q}{2}) に丸めてから、(f(x, z)) を得るために割ることができるようにすることです。
第二に、ハッシュを (f) 自体にXORすることで、関数を再度変更します。
(f'(x, z) = \frac{q}{2} \cdot xor(f(x, z ext{_1}), H ext{_2}(x)) - (\frac{q}{4} - e ext{`}_{max}) + H ext{_1}(x, z ext{_2}))
(H ext{_2})
からは、ランダムオラクルプロパティを期待します。しかし、(H ext{_2})
は効率のボトルネックではないため、SHA256のような汎用アルゴリズムを使用するのは素晴らしいことです。
最終的な出力を平文で得るために、最終的な (f'(x, z)) の出力から (H ext{_2}(x))
をXORで戻します。
このトリックの結果、((tY) ext{_{i}})
は完全に擬似ランダムになります。
- 各最高位ビットは擬似ランダムです。なぜなら、(H ext{_2}(x))
のビットとXORされるからです。これは擬似ランダム(擬似ランダムオラクルモデルで説明されている形式)であると仮定します。 - すべての下位ビットは (H ext{_1}(x, z ext{_2}))
によって生成されます。これも擬似ランダムであると仮定します。2つの可能なメッセージ値の出力範囲間の (2e ext{`}_{max})
幅の空きスペースは (q) に比べて指数関数的に小さいため、安全に無視できます。
[画像: PROMブートストラップ]
このテクニックは「PROMブートストラップ」と呼ばれることもあり、「擬似ランダムな関数に対する難読化」を、任意の (f) で機能するより一般的な形式の難読化に変換する汎用変換です。ハッシュをランダムオラクルと実装可能な回路の両方として同時に見なすことも、しばしば「怪しい」暗号学的仮定と見なされますが、再帰的STARKなどで広く使用されています。
最後に、「従来の」iO、つまり関数を隠すものを実行したい場合、公開関数 (f) を固定して秘密入力 (z) を隠すのではなく、より保守的な難読化の形式で何度も行ったトリックを実行します。つまり、(f) を「ユニバーサル回路」(VM)
にし、その秘密入力がプログラム (P) であり、(VM(x, P) = P(x))
を満たすようにします。
評価者は入力エンコーディングをどのように学習するか?
これまでのところ、評価者がBGG+エンコーディング (s \cdot (B ext{_{i}} - G \cdot m ext{_{i}}) + e ext{_{i}})
を受け取ると魔法のように仮定してきました。しかし、残念ながら現実はそれほど単純ではありません。難読化者は、(m ext{_{i}} \in {0,1})
に対して (len(m) + L)
個のそのようなエンコーディングを、同じ (s) で構築できます((m) の (x) 部分について、(0) オプションと (1) オプションの両方を提供する必要があるだけです)。しかし、これは安全ではありません。同じ (B ext{_{i}})
と (s) で、異なる (m ext{_{i}})
(バイナリビットを扱う場合、それは (0) と (1) を意味します)を持つ2つのエンコーディングを受け取った場合、それらを減算するだけで (s \cdot G + (e ext{_1} - e ext{_2}))
が得られ、(s) が平文で漏洩します。
したがって、評価者が任意の (m) に対してエンコーディングを生成できるガジェットを提供する必要がありますが、各 (m) に対して異なる (s) を使用します。(m) の1ビットの変化だけでも (s) を完全に変更する必要があります。ここで、Diamond iOのメカニズムの核心があります。
トリックは次のとおりです。まず、(m) の構造を思い出してください:([1, E[z], x, t])。異なる評価間で変化するのは (x) だけです。
「ベース」メッセージ (m ext{_0} = \lbrack1, E[z], 000\dots000, t\rbrack)
と「ベース」秘密 (s ext{_0})
から開始します。
i番目のビットについて、秘密を変換することを目的とした低ノルム行列 (S ext{_{i,0}})
と (S ext{_{i,1}})
も定義します。
したがって、任意の最終的なベクトル (m ext{_L})
は (m ext{_0} \cdot M ext{_{1,b ext{_1}}} \cdot M ext{_{2,b ext{_2}}} \cdot \dots \cdot M ext{_{L,b ext{_L}}})
として表現できます。対応する (s ext{_0} \cdot S ext{_{{1,b ext{_1}}}} \cdot S ext{_{{2,b ext{_2}}}} \cdot \dots \cdot S ext{_{{L,b ext{_L}}}}) は、一意の秘密 (s ext{_L})
を提供します。私たちの目標は、これらの変換を「融合」し、評価者が生成する各特定の (m ext{_L})
に対して、対応する一意の (s ext{_L})
で構築されたBGG+エンコーディングを取得することです。
これらのベクトルと行列をテンソル化し、それらをアンパックできないようにエンコーディングでラップすることで「融合」します。
ミニ例 - ベクトル (m) と (s) をテンソル化することから始めます。
[画像: テンソル化されたmとs]
(m) の左端の値は1に等しく、(s) の右端の値は-1に等しくなるように制約されています。
そして、行列のテンソル化は次のようになります(書かれていないエントリはすべてゼロです)。
[画像: テンソル化された行列]
(M)
が上記の説明と同じ形状であり、(S) が最後の列に触れないように制約されているため、(s) の最後の値を-1に保っていることがわかります。
テンソル化の重要な特性は、(m ext{_1} = m ext{_0} \cdot M ext{_{1,b ext{_1}}})
および (s ext{_1} = s ext{_0} \cdot S ext{_{1,b ext{_1}}})
の場合、((m ext{_1} \otimes s ext{_1}) = (m ext{_0} \otimes s ext{_0}) \cdot (M ext{_{1,b ext{_1}}} \otimes S ext{_{1,b ext{_1}}}))
ということです。便宜上、(Q ext{_{i,b}})
を ((M ext{_{i,b}} \otimes S ext{_{i,b}}))
に等しいと定義します。
これまでのところ、評価者の式は次のようになります。(q ext{_0} = m ext{_0} \otimes s ext{_0})
から開始し、各 (Q ext{_{i,b ext{_i}}} = M ext{_{i,b ext{_i}}} \otimes S ext{_{i,b ext{_i}}})
を順番に掛け、最後に (q ext{_L} = m ext{_L} \otimes s ext{_L})
を得ます。
これで進展がありました。評価者が必要とする可能性のあるエンコーディングの一種を生成する方法が得られました。それは一意の (s ext{_L})
にバインドされています。問題は、これまでのところ、このエンコーディングは (m ext{_L})
(評価者が知るべきではない (t) ビットを含む)と (s ext{_L})
を完全に平文で公開してしまうことです。
次のステップは、各ステップでこれらのエンコーディングを「ブラインド」するために、適切な場所にさらに行列を掛けることです。
難読化者は、評価者にエンコーディング (p ext{_0} = q ext{_0} P ext{_0} + e ext{_0})
を提供します。
難読化者は、以下を満たす低ノルム行列 (K ext{_{i,b}})
を生成します。(P ext{_{i-1}} \cdot K ext{_{i,b}} = Q ext{_{i,b}} \cdot P ext{_{i}} + E ext{_{i,b}})
これは、トラップドアメカニズムのおかげで可能です。
評価者は、可能なエンコーディングの指数サイズのツリーをたどることができます。このツリーがグラフィカルにどのように見えるかを示します。ツリーのサイズは (2 ext{`}^L)
ですが、このツリー全体を生成する実際には異なる「エッジ行列」の数は、最終的な (K ext{_{f}})
(後述)を含めて、わずか (2L+1) です。
[画像: ツリー構造]
そして、これが数学的にどのように機能するかを示します。
(p ext{_1} = p ext{_0} \cdot K ext{_{1,b ext{_1}}})
(= q ext{_0} \cdot P ext{_0} \cdot K ext{_{1,b ext{_1}}} + e ext{_0} \cdot K ext{_{1,b ext{_1}}})
(= q ext{_0} \cdot Q ext{_{1,b ext{_1}}} \cdot P ext{_1} + e ext{_0} \cdot K ext{_{1,b ext{_1}}} + q ext{_0} \cdot E ext{_{1,b ext{_1}}})
(= q ext{_0} \cdot Q ext{_{1,b ext{_1}}} \cdot P ext{_1} + e ext{_1})
そして次に:
(p ext{_2} = p ext{_1} \cdot K ext{_{2,b ext{_2}}})
(= q ext{_0} \cdot Q ext{_{1,b ext{_1}}} \cdot P ext{_1} \cdot K ext{_{2,b ext{_2}}} + e ext{_1} \cdot K ext{_{2,b ext{_2}}})
(= q ext{_0} \cdot Q ext{_{1,b ext{_1}}} \cdot Q ext{_{2,b ext{_2}}} \cdot P ext{_2} + e ext{_1} \cdot K ext{_{2,b ext{_2}}} + q ext{_0} \cdot Q ext{_{1,b ext{_1}}} \cdot E ext{_{2,b ext{_2}}})
(= q ext{_0} \cdot Q ext{_{1,b ext{_1}}} \cdot Q ext{_{2,b ext{_2}}} \cdot P ext{_2} + e ext{_2})
そして、(p ext{_L} = q ext{_0} \cdot Q ext{_{1,b ext{_1}}} \cdot \dots \cdot Q ext{_{L,b ext{_L}}} \cdot P ext{_L} + e ext{_L})
まで続きます。ここで (q ext{_0} \cdot Q ext{_{{1,b ext{_1}}}} \cdot \dots \cdot Q ext{_{{L,b ext{_L}}}}} = q ext{_L})。
(e ext{_{i-1}} \cdot K ext{_{i,b ext{_i}}})
と (q ext{_{i-1}} \cdot E ext{_{{i,b ext{_i}}}})
の両方が (e ext{_i})
に崩壊することに注意してください。これは、(K ext{_{i,b}})
、(Q ext{_{i,b}})
、および (q)
(したがって (m)、(s)、(M ext{_{i,b}})
、(S ext{_{i,b}})
)がすべて低ノルムである必要がある(そしてそうである)ことを意味します。
ここで、実際にはブラインドされた (q ext{_L} = m ext{_L} \otimes s ext{_L})
のエンコーディングが得られました。しかし、まだ適切な形式ではありません。次のようになっています。
((m ext{_L} \otimes s ext{_L}) \cdot P ext{_L} + e ext{_L})
次の形式が必要です。
(s ext{_L} \cdot (B ext{_{i}} - G \cdot m ext{_L}[i]) + e ext{_{i}})
この橋を渡るために、さらに別のトラップドア (K ext{_{f}})
を追加します。これは以下を満たす必要があります。
(P ext{_{L}} \cdot K ext{_{f}} = u ext{_1} \otimes B ext{_{full}} - I \otimes G)
ここで、いくつかの新しい表記法を導入しました。それらを見てみましょう。
- (u ext{_1})
は、最初の位置が1で、それ以外はすべて0のベクトルです。文脈に応じて、「最初の(列/行/バケット/エントリ)を選択する」ことを意味します。 - (B ext{_{full}})
は、入力全体のエンコーディングの (B)
行列の連結です。(s \cdot (B ext{_{i}} - G \cdot m ext{_{i}}) + e ext{_{i}})
の (B ext{_{i}}) - (u ext{_1} \otimes B ext{_{full}})
は、「(B ext{_{full}})
の多数のコピーを垂直に積み重ね、最初のコピーに1を掛け、残りは0を掛ける」ことを意味します。より単純な言葉では、(B ext{_{full}})
の下に多数のゼロを配置します。 - (I \otimes G)
は、対角線に沿って (G)
の多数のコピーのように見えます。これは、「バケットごとに (G)
を掛ける」ことを意味します。
また、ここで((K ext{_{G}})
の場合と同様に、(K ext{_{i,b}})
の場合とは異なり)、右側に誤差がないことにも注意してください。これは問題ありません。なぜなら、最終的な暗号文の誤差は他の場所から来るからです。右側の値は公開式であるため、それをマスクしないことにセキュリティ上のリスクはありません。
(((m ext{_L} \otimes s ext{_L}) \cdot P ext{_{L}} + e ext{_{L}}) \cdot K ext{_{f}})
(= (m ext{_L} \otimes s ext{_L}) \cdot P ext{_{L}} \cdot K ext{_{f}} + e ext{_{L}} \cdot K ext{_{f}})
(= (m ext{_L} \otimes s ext{_L}) \cdot (u ext{_1} \otimes B ext{_{full}} - I \otimes G) + e ext{_{f}})
(= (m ext{_L} \otimes s ext{_L}) \cdot (u ext{_1} \otimes B ext{_{full}}) - (m ext{_L} \otimes s ext{_L}) \cdot (I \otimes G) + e ext{_{f}})
(= s ext{_L} \cdot B ext{_{full}} - (m ext{_L} \otimes s ext{_L}) \cdot (I \otimes G) + e ext{_{f}})
(= s ext{_L} \cdot B ext{_{full}} - m ext{_L} \otimes (s ext{_L} \cdot G) + e ext{_{f}})
最後の2行は最も明白ではありません。何が起こっているかというと、(m ext{_L})
(すべてのメッセージベクトルと同様に)は1で始まるため、(m ext{_L} \otimes s ext{_L})
の最初のバケットは単に (s ext{_L})
です。一方、最初のバケット行の下では、(u ext{_1} \otimes B ext{_{full}})
は単にゼロになります。したがって、((m ext{_L} \otimes s ext{_L}) \cdot (u ext{_1} \otimes B ext{_{full}}))
は単に (s ext{_L} \cdot B ext{_{full}})
に削減されます。そして、(I \otimes G)
は、(m ext{_L})
の各メッセージ値に対して、(s) の多数のコピーに掛けられる (G)
の多数のコピーの役割を果たします。
(論文では、(B ext{_{full}})
を (B ext{_{att}})
(入力の (t) を除く)と (B ext{_{t}})
に分割し、上記の手順をこれらの2つの部分に対して別々に実行しています。これは数学的にはここで説明したことと同等です。概念的な理由は、それらが異なる種類のデータであるためです。([1, E[z], x])
の生の値を評価者に提供しますが、(t) の生の値を公開しません。)
[画像: Bfull行列]
そして、出力は、必要なすべての (s ext{_L} \cdot (B ext{_{i}} - G \cdot m ext{_L}[i]) + e ext{_{{f,i}}})
BGG+エンコーディングの単なる連結です。
Diamond iOの再要約
- 評価者は (p ext{_0})
を受け取ります。これは、(i) 関数入力部分がゼロに設定された (m)
のエンコーディングと、(ii) 初期鍵 (s ext{_0})
をテンソル化したものです。 - メッセージの各ビットについて、評価者は (K ext{_{i,0}})
または (K ext{_{i,1}})
のいずれかを選択できます。これらは、(i) 関数入力部分のi番目のビットに0または1を書き込み、(ii) 新しい係数を鍵に混合する役割を果たします。 - 最後に、最終的な (m)
と (s) をテンソル化したエンコーディング (p ext{_L})
が得られます。トラップドアをさらに掛けて、最終形式:BGG+エンコーディング ([1, E[z], x, t])
にプッシュします。 - 評価者はBGG+計算を実行して、(f'(x, z) = \frac{q}{2} \cdot xor(f(x, z ext{_1}), H ext{_2}(x)) - (\frac{q}{4} - e ext{`}_{max}) + H ext{_1}(x, z ext{_2}))
の暗号文を計算します。 - GSW暗号文の復号は、「単に」ベクトルと行列の乗算 (t \cdot Y) を行い、丸めるだけです。ここでは、(Y)
のビットをBGG+エンコーディングと平文の両方で持ち、(t)
のBGG+エンコーディングのみ(平文なし)を持っています。 - 評価者はこれをBGG+乗算として実行しますが、バケットごとの左シフト演算子を使用して、最高位ビットを表す (t\cdot Y) のエントリを適切にスケーリングします。
- これにより、評価者はエンコーディング (s \cdot B ext{_{final,i}} - s \cdot G \cdot (tY) ext{_{i}} + e ext{_{final,i}})
を得ます。 - 評価者は単一の列を抽出します。つまり、(s) の最後の項目(-1に固定されている)に対応するバケットの最下位桁のエントリです。これにより、(s \cdot b ext{_{i}} + (tY) ext{_{i}} + e ext{_{i}})
に単純化できます。 - 最後に、評価者は「トラップドア行列」を持ち、すべての (s \cdot b ext{_{i}})
を同時に計算できます。ただし、それらの特定の (b ext{_{i}})
に対してのみです。これにより、(s \cdot b ext{_{i}})
を減算し、((tY) ext{_{i}} + e ext{_{i}})
だけを残すことができます。 - 評価者はこれを丸めて除算し、(H ext{_2}(x))
を平文でXORで戻して、目的の結果 (f(x, z)) を取得します。
セキュリティ
このプロトコルの最も「論争の的となる」部分は、BGG+エンコーディングを入力用に生成するメカニズムです。これは、all-product LWE と evasive LWE という、2つのかなり新しい暗号学的仮定に依存しています。Evasive LWEはWee22で導入されました。All-product LWEはDiamond iOに固有のものです。
- Evasive LWE は、秘密を保持するターゲットの逆像を公開しても安全であると述べています。大まかに言うと、2つの行列 (A) と (C) 、およびサンプル (sA + e ext{_1})
と (sC + e ext{_2})
(両方の誤差は独立)があり、これらがランダムから区別できない場合、(A \cdot B = C) を満たす低ノルムの逆像 (B)
を公開しても、(sA + e ext{_1})
サンプルのランダムからの区別可能性が高まることはない、と述べています。特に、(B)
を公開すると、敵対者は (sA + e ext{_1})
サンプルを (sC + e ext{_1}B)
に変換できるようになります。この仮定は、それが安全であると述べています。私たちのケースでは、この仮定は、マスクされた秘密保持ターゲットの逆像である (K ext{_{i,b}})
を公開しても安全であることを意味します。なぜなら、(P ext{_{i-1}} \cdot K ext{_{i,b}} = C)
であり、ここで (C = Q ext{_{i,b}} \cdot P ext{_{i}} + E ext{_{i,b}} = (M ext{_{i,b}} \otimes S ext{_{i,b}}) \cdot P ext{_{i}} + E ext{_{i,b}})
であり、(S ext{_{i,b}})
は秘密の構成要素です。 - All-product LWE は、すべての (2 ext{
}^L\) の \(x\) の値にわたって、上記で説明した*パス積*メカニズムを介して構築された秘密を持つ、すべての \(s ext{\_x} (B - x \otimes G) + e ext{\_x}\) のファミリーが共同で擬似ランダムであることを述べています。つまり、多数の秘密を持つ多数のLWEサンプルを構築する*この特定の方法*は、すべての \(2 ext{}^L)
の秘密が真に独立していた場合と同様に安全であるということです。これは、積に入る初期誤差が擬似ランダムであることを前提としています。Diamond iOのユースケースでは、(K ext{_{i,b}})
行列を公開したため、Evasive LWE仮定を受け入れる場合のみ、これを仮定できます。
これらのLWE仮定は、同時に妥当であり、新しいLWE仮定を作成しようとした10年間の試みから理解されてきた多くの落とし穴を回避しています(それらは「ゼロ化」攻撃によって破られました)。しかし、同時に新規でリスクも伴います。Evasive LWEはNaorの意味で偽造不可能(non-falsifiable)です。形式的には、「Xを区別できるすべてのアルゴリズムに対して、Yを区別できるアルゴリズムが存在する」と述べているため、反例があるかどうかさえ判断が困難です。Evasive LWEが偽となる状況のクラスはすでに知られていますが、Diamond iOは意図的にこの回避策を取るタイプのEvasive LWE仮定を選択しています。
これらの仮定が安全であることを検証するには、さらに多くのセキュリティ分析が必要です。
効率性
BGG+エンコーディングの構築は比較的「簡単」です(ファンアウトが2を超える場合でも使用できるため、例えばファンアウト256は乗算ごとに (x) の8ビットを埋めます)。難しいのはBGG+評価であり、「ABE * FHE」のオーバーヘッドがあります。FHE自体はGSWであり、これは生産環境では誰も使用していません。なぜなら、BFVのようなより主流なアルゴリズムよりもはるかに効率が低いからです。GSWが必要なのは、「良い」代数特性、リニアライゼーションや鍵スイッチングの必要がないこと、そして平文を暗号文の任意のビットサイズに配置できる能力などがあるためです。
これに加えて、非効率性と制限の他の原因があります。
-
難読化のすべての形態と同様に、「証明」内で (2 ext{`}^L)
の可能な入力を「歩き回る」必要があるため、システムは通常のパラメータよりもはるかに大きい「準指数関数的に安全な」パラメータを必要とします。 -
実際的なボトルネックは、ABE * FHE内の (H ext{_1}(x, z))
の計算です。コストの主な貢献者は深さです(深さが増加すると、誤差を処理するために必要な次元が増加します)。計算自体が深い場合、BGG+エンコーディングのノイズを「リフレッシュ」する方法がありますが、これらの方法自体は実行可能な (H ext{_1})
に依存します。したがって、(H ext{_1})
の深さが具体的なボトルネックです。Diamond iOは現在、(H ext{_1})
をインスタンス化するために、Goldreich PRG実行
の「ツリー」を使用しています。これはファンアウトごとに乗算深さ3であり、必要なファンアウトの数は入力長に比例します。
これらの理由から、この記事の冒頭のさまざまな種類の難読化を示すチャートでは、Diamond iOは「非常に攻撃的」で「惑星スケール」のポイントに位置しています。
Diamond iOの具体的な効率を改善したい場合、いくつかの可能な道筋が考えられます。
- Goldreich PRGインスタンス化のツリーを、より効率的なものに置き換える。
- (H ext{_1})
を完全に削除する方法を見つける。これは、ノイズ生成を入力エンコーディングステップに移動させることで可能になるかもしれませんが、そのような構築に対する既知の攻撃があります。 - GSWをより効率的なFHEに置き換える。BGV / CKKS風のもの、またはパッキングされたGSW(私の探求も参照)のいずれかであり、条件付き復号をそこで機能させる方法を見つける。
- ABEとFHEレイヤーを少なくとも部分的に「折りたたむ」方法を見つける。これは、FHEが近似計算で「ネイティブに」動作するという事実を受け入れるようにBGG+を修正することを意味するかもしれません。
- 証明側で「準指数関数的なセキュリティ」要件を削除する方法を見つける。
- 「iO完全プログラム」(正しい回路を有効な入力でFHE評価したことを証明する有効なSTARKを受け取った場合にのみFHE暗号文を復号する)のみを難読化することに特化して、より明示的に設計された最適化を見つける。これにより、他のものを難読化できます。
Diamond iOの主な利点は、その単純さから分析に優しいことです。保守的な難読化バリアントのように、「プロトコル内のプロトコル内のプロトコル」のタワーはありません。唯一のネストはABE内のFHEです。過去20年間に暗号学者が発明した構築物のタワー全体を参照せずに理解できます。準線形乱択エンコーディング、準同型暗号、ガーブルドサーキット、分割FHE、さらには完全なABE(BGG+のコアメカニズムを使用していますが、詳細は十分に異なるため、すでに知っている人にとっての利点ははるかに低いです)を必要としません。これらの理由から、Diamond iOがより多くの注目と分析(セキュリティと最適化の両方)を得て、実際に実行できる難読化プロトコルに到達できることを願っています。