難読化: 暗号の最終ボスを構築する (パート I)

ダークモード切り替え 難読化: 暗号の最終ボスを構築する (パート I) 2026年6月29日 全ての投稿を見る 難読化: 暗号の最終ボスを構築する (パート I) フィードバックとレビューをいただいたSora Suegami、Janmajaya Mall、Aayush Jain、Fun Killerに特に感謝します。 暗号学において考案された最も強力なプリミティブは、難読化です。難読化を用いると、プログラム(P)を「暗号化されたプログラム」(Obf(P))に変換できます。これにより、Obf(P)を平文入力で実行すると、Pが与えるものと同じ平文出力を得られますが、Pの内部動作は隠蔽されます。一般的に使用される厳密な形式主義である「区別不能難読化(iO)」では、同じ機能を持つ2つの異なるプログラムの難読化が与えられた場合、どちらがどちらであるかを区別できないとされます。実質的に、データではなくコードを隠蔽するものです。 難読化は、普遍的な「信頼できない信頼できる第三者」という理論的な理想に非常に近いものであるため、強力です。 出典: The God Protocols (Nick Szabo), 1997年 暗号プロトコルはしばしば、全員のメッセージを見て正直に応答する信頼できる第三者に依存するプロトコルをまず想像し、その後、その信頼なしに同じことを行う方法を見つけることで記述されます。暗号化は単純です。「信頼できる第三者」は、実質的に「[受信者]に[メッセージ]を見せたい」という指示を受け入れ、そのメッセージを受信者に渡す郵便システムです。ゼロ知識証明は、データを受け取り、それをチェックし、尋ねる人には誰にでもデータが何らかの意味で正しいことを確認する信頼できる第三者に取って代わります。 難読化（厳密には、難読化とハッシュ）を用いると、基本的にあらゆるプロトコルに対してシミュレートされた信頼できる第三者を作成できるため、上記の両方をはるかに超えるものを置き換えることができます。唯一の大きな例外は、難読化されたプログラムは自分自身のコピーを防ぐことができないため、お金のような「ステートフルな」操作を行うことができないことです。そして、これはまさにブロックチェーンが埋めるのに適したギャップです。したがって、難読化とブロックチェーンがあれば、かなり魔法のようなことができます。例えば、M-of-Nしきい値委員会が不要な、ほとんど信頼仮定のない安全でプライベートな、共謀耐性のある投票システムなどです。または、2014年のこのリストにあるほぼすべてのものを、M-of-Nの信頼仮定なしで実現できます。難読化とブロックチェーンを組み合わせる非常に汎用的な方法で、「信頼できない信頼できる第三者」に非常に近いものを作成します。 では、問題点は何でしょうか？安全な形式の難読化を作成することは、本当に本当に難しいことが判明しています。何十年にもわたって、安全でない難読化の伝統がありました。人々はコンパイルされたプログラムのロジックをシャッフルして、何が起こっているかを見えにくくしていました。確かに、多くの場合、ゲームのようなプロプライエタリなプログラムのユーザーによる改変を防ぐためでした。これは、暗号化におけるシーザー暗号のようなもので、シーザー式の暗号と同様に、定期的に破られています。その結果、数学的に安全であることを証明できる難読化プロトコルを作成しようとする何十年にもわたる伝統もありました。しかし、ほぼ最初から、これは問題に直面しました。2001年には、理想的な形式の難読化（Pを難読化し、Obf(P)の実行が、ユーザーが提供する任意のxに対してP(x)を与えるAPIをクエリすることで学習できる以上のものを何も明らかにしない方法）を作成することは不可能であるという有名な結果が得られました。中心的なアイデアは、Pのコードインスタンスは常に、ユーザーが提供する入力に対する出力以上のものを少なくとも何か明らかにすることです。少なくとも、Pを自分自身のコードに適用することで物事を学ぶことができます。 その時点から、研究者たちは次善の目標、すなわち区別不能難読化（iO）を証明しようとシフトしました。これは20年間にわたるプロジェクトであり、多くの失敗した試み、まだ存在しない要素の上に構築されるプロトコルの多くの構築、その要素を構築しようとする多くの人々、それらの失敗した試みなどがありました。しかし、ここ数年で、ついに朗報が届きました。合理的なセキュリティ仮定の下でiOを達成する方法がわかったのです。しかし、朗報の中には悪いニュースがあります。実行時間が文字通り銀河レベルなのです。技術的には多項式ですが、それは「おおよそ準同型暗号のようなものを一つ取り、その評価のための回路を別のおおよそ準同型暗号のようなものに入れ、その全体を通常の準同型暗号で各ビットごとに一度実行して中間的な数メガバイトの値を作り出し、ああ、その全体を別のおおよそ準同型暗号のようなものに入れ、そして入力の各ビットごとにそのすべてを実行しなければならないと申し上げましたか？」といった多くの層を積み重ねることを含みます。その結果、これらの「ある程度証明可能に安全なiOスキーム」の実行時間は、λ^10をはるかに超えるものになります（ここでλは「セキュリティパラメータ」、つまりスキームを破るのにかかる時間の対数であり、λ = 100または120と仮定するのが一般的です）。 ここには、2つの希望に満ちた話があります。一つは、これが2010年のSNARKsの状態に似ており、可能であることがわかった今、賢い人々（とボット）が各ボトルネックに対して巧妙な回避策を考案し始め、実行時間から次々と桁を削り落とし、最終的には重いGPUで1日かかる「だけ」のものに到達するだろうということです（それでも法外に聞こえるかもしれませんが、多くの興味深いアプリケーションには十分です）。もう一つは、同じ目標に向かって異なる戦略に対するより多くの研究が見られるだろうということです。つまり、新しい暗号学的仮定の開発がはるかに上手になり、どの新しい仮定が実際に安全である可能性が高いかを判断するのが上手になるでしょう。 よりヒューリスティックなアプローチを含めると、これまでに約3つの（まだ死んでいない）難読化プロトコルファミリーがあり、それらを効率とセキュリティ仮定における勇敢さの「トレードオフフロンティア」に配置できます。 この投稿では、これまでのところ最も銀河的ですが、最も厳密なファミリー、つまり上記の図の青色のものを詳しく説明します。警告ですが、多くの数学が登場します。難読化は、ブロックチェーン開発者であればすでに知っているSNARKsやSTARKsのようなプリミティブを除き、暗号学者が過去20年間で発明したほとんどすべてのプリミティブを積み重ねる必要があるため、困難です。根底にある数学も異なります。SNARKsやSTARKsが多くの多項式、ハッシュ、楕円曲線を使用する傾向があるのに対し、難読化は多くの格子、ベクトル、行列を使用します。 表記に関する注意 この投稿の記述は、異なる論文からのアプローチの組み合わせに基づいており、いずれかの単一の論文に完全に従うものではありません。場合によっては、表記や語彙の選択が個々の基礎となる投稿と異なる場合があります。 ベクトルは小文字、行列は大文字で表記されます。 図では、グレー表示されたテキストと点線は、非公式に「XはYに依存するが、Yを実際にXに渡す必要はないため、Xの（サイズ/実行時間）はYの（サイズ/実行時間）よりもはるかに小さい可能性がある」ことを意味します。 「iO」は「indistinguishability obfuscation」の略で、「IO」＝「input/output」とは異なり、さらに、.io TLDが命名されたイギリス領インド洋地域とも異なります。 標準パイプライン 今日構築されている「合理的に証明可能に安全な」難読化プロトコルは、10年前の構築の塔、つまりAJ15 / BV15 / LPST15 / LPST16の系統の上に構築されています。AJ15とBV15は、機能暗号と呼ばれるプリミティブの上に難読化を構築するほぼ同じ方法をそれぞれ発見した、ほぼ同時期の2つの論文です。機能暗号では、「権限者」が関数(F)に紐付けられた鍵を公開し、その鍵が存在すれば、暗号化鍵を持つ誰もがx%を暗号化でき、復号鍵を持つ誰もがF(x)を回復できます。LPST15も同様のものを考案しました。しかし、必要とされる機能暗号は、当時まだ利用できなかった非常に強力な特性を持つ必要がありました。幸いなことに、1年後、LPST16が発見しました。