On the (Im)possibility of Obfuscating Programs

難読化を定式化

Abstract

非公式には、難読化装置 $\mathcal{O}$ は、プログラム（または回路）
$P$ を入力として、$P$
と同じ機能を持ちながらある意味で「理解できない」新しいプログラム
$\mathrm{O}(P)$ を生成する（効率的で確率的な）「コンパイラ」である。もし難読化装置が存在するとすれば、ソフトウェアの保護から同型暗号、ライスの定理の複雑さの理論的類推まで、さまざまな暗号や複雑さの理論的応用が可能になります。これらの応用のほとんどは、難読化における「理解不能」という条件を、$\mathcal{O}(P)$
が「仮想ブラックボックス」であることを意味すると解釈することに基づいていま。
本研究では、難読化の理論的な検討を開始しました。我々の主な結果は、上記の直観の非常に弱い形式化の下でさえ、難読化は不可能であるということです。すなわち
(a) 関数
$f\in F$
を計算する任意のプログラムが与えられたとき、その値π(f)は効率的に計算できるが
(b)（ランダムに選択された）関数
$f\in F$
へのオラクルアクセスが与えられたとき、ランダムな推測よりもはるかに良い
$\pi (f)$
を計算できる効率的なアルゴリズムは存在しない、という特性
$\pi :F\to 0,1$
を構築することにより、このことを証明する。この不可能性の結果を様々な方法で拡張し、
(a)必ずしも多項式時間で計算できない、
(b)機能を近似的にしか維持できない、
(c)非常に限定された計算モデルに対してのみ機能する必要がある
といった難読化装置も含めています(TC0)。また、「難読化できない」署名方式、暗号化方式、疑似乱数関数族を構築することで、難読化装置のいくつかの潜在的な応用を排除します。

Introduction

過去数十年の暗号研究では、暗号化、認証、プロトコルなどの古典的な暗号問題のほとんどを複雑性理論の基礎の上に置くことに成功しました。しかし、暗号技術の中には、理論ではほとんど何も言えないような重要な問題がいくつか残っています。その一つが、プログラムの難読化の問題です。大雑把に言えば、（プログラム）難読化の目的は、プログラムの機能を維持したまま、プログラムを「理解できない」ようにすることです。理想的には、難読化されたプログラムは「仮想的なブラックボックス」であり、プログラムから計算できることは、プログラムの入出力動作からも計算できるということです。難読化が可能であるという期待は、十分に豊かな形式で表現されたプログラムを解析することが困難であるという事実から生まれます。実際、完全に理解できないことがコンピュータ・プログラムの自然な状態であることは、プログラマなら誰でも知っている（そして、プログラムがそのような状態にならないようにするためには、努力しなければならない）。理論的には、ライスの定理、ハルティング問題や充足可能性の硬さなどの結果は、プログラムや回路を使ってできる唯一の有用なことは、（自分で選んだ入力に対して）実行することであることを示唆しているように見える。しかし、このような非公式な表現は、もちろん一般化しすぎであり、難読剤の存在については、独自の調査が必要です。もう少し明確に言うと（まだ非公式ですが）、難読化装置Oは、プログラム（または回路）Pを入力として受け取り、以下の2つの条件を満たす新しいプログラムO(P)を生成する、（効率的で確率的な）「コンパイラ」です。
(functionality)
$\mathcal{O}(P)$
は
$P$
と同じ関数を計算する

(“virtual black box” property)
$\mathcal{O}(P)$
から効率的に計算できるものは、
$P$
へのオラクルアクセスがあれば、効率的に計算できる。

実際には難読化のためのヒューリスティックなアプローチがありますが（図1と
CT00
を参照）、この問題に関する理論的な研究はほとんどありませんでした。難読化が可能であれば、様々な暗号や複雑さの理論的な応用が可能であるにもかかわらず、これは残念なことです。
本研究では、難読化の理論的な検討を開始しました。この概念の様々な形式化を検討し、実現できることとできないことを理解しようとしています。主な結果は否定的なもので、（一般的に理解されているような）難読化は不可能であることを示しています。この結果と他の結果をより詳しく説明する前に、動機付けと概念の明確化のために、難読化装置の潜在的なアプリケーションのいくつかを概説します。

1.2 Our Results

The Basic Impossibility Result

上記の応用例の多くは、難読化されたプログラムは “virtual black box” であるという直観に基づいています。つまり、難読化されたプログラムから効率的に計算できるものは、プログラムへのオラクルアクセスがあれば、効率的に計算できるはずなのです。我々の主な結果は、このような難読化の概念を実現することは不可能であることを示しています。
これを証明するために、(任意の一方向性関数から) “inherently unobfuscatable” (本質的に難読化不可能)な関数族
$\mathcal{F}$
を構築します。この関数族は、次のような性質
$\pi :\mathcal{F}\to 0,1$
を持ちます
関数
$f\in \mathcal{F}$
を計算する任意のプログラム（回路）が与えられた場合、値
$\pi (f)$
は効率的に計算できる

しかし、（ランダムに選択された）関数
$f\in \mathcal{F}$
へのオラクルアクセスが与えられた場合、効率的なアルゴリズムは、ランダムな推測よりもはるかに良い方法でπ(f)を計算することはできない

したがって、
難読化が関数に関するたった1ビットの情報(すなわちπ(f))を隠すためのものであり、難読化自身が拘束されない計算時間を持つ場合であっても、これらの関数を計算するプログラムを難読化する方法はありません。

このような関数の存在は、難読化のための「仮想ブラックボックス」というパラダイムに本質的な欠陥があることを示していると考えています。難読化装置のようなものについて肯定的な結果を望むのであれば、この視点を捨てるか、少なくとも上記のような関数の存在と両立させなければなりません。

近似的難読化装置

上述した基本的な不可能性の結果は、難読化されたプログラムO(P)が元のプログラムPと全く同じ関数を計算することを要求する難読化装置Oに適用されます。しかし、いくつかのアプリケーションでは、すべての入力xに対して、O(P)とPが（Oのコイントスよりも）高い確率でxについて合意することで十分な場合があります。我々の不可能性の結果は、いくつかの追加のアイデアを用いて、そのような近似難読化装置にも拡張されます。

アプリケーションの不可能性

私たちの不可能性の結果は、定義上の選択の産物ではなく、「仮想ブラックボックス」の考え方に本質的な欠陥があることをさらに証明するために、難読化装置のいくつかの応用も不可能であることを示します。具体的には、本質的に難読化できない署名方式、暗号化方式、疑似乱数関数を構築します。これらは、標準的なセキュリティの定義を満たすものですが（脚注2に記載されている微妙な点を除く）、Kに対して署名（または暗号化、擬似乱数関数の評価など）を行う任意のプログラムから、秘密鍵Kを効率的に計算することができます。特に、CanettiらのRandom Oracle Methodologyに対する批判
CGH98
を補完しています。彼らは、理想化された（
BR93
の）ランダムオラクルモデルでは安全であるが、ランダムオラクルが任意の（効率的に計算可能な）関数に置き換えられると安全ではない（工夫された）プロトコルが存在することを示している。我々の結果は、ランダムオラクルモデルで安全な自然なプロトコル（例えば、Fiat-Shamir型のスキーム
FS87
）であっても、ランダムオラクルをコントリビュートされた関数を計算する任意のプログラムで置き換えると安全ではなくなるような、（コントリビュートされた）擬似ランダム関数が存在することを意味する。

制限付き複雑性クラスの難読化

一般的なプログラム/回路の難読化が不可能であっても、より限定されたクラスの計算の難読化が可能であると期待することができる。しかし、
NR97
の疑似乱数関数を構成に用いることで、広く信じられている複雑さの仮定（例えば、因数分解の硬さ）の下で、入力プログラムPが一定の深さの閾値回路（すなわち、TC0にある）であっても、不可能という結果が成り立つことを示すことができます。

1.3 Discussion

私たちの研究は、標準的な「仮想ブラックボックス」という難読化装置の概念を、そのいくつかの応用とともに、不可能なものとしています。しかし、プログラムを意味のある正確な意味で「理解できない」ようにする方法が存在しないということではありません。そのような方法は、ソフトウェア保護のために有用であることが証明されています。したがって、ある種の難読化が可能な別の感覚（またはモデル）があるかどうかを理解することは、重要かつ興味深いことであると考えています。この目的のために、本稿では、「仮想ブラックボックス」のパラダイムを回避する（したがって、我々の不可能性証明によって排除されない）難読化装置の2つの弱い定義を提案します。これらの定義は今後の調査の対象となりますが、他の代替案も提案され、検討されることを期待しています。不可能性の結果や下限値の場合と同様に、難読化できない関数アンサンブルという、やや作為的な反例を示すことで、（「仮想ブラックボックス」の意味での）難読化装置が存在しないことを示しています。興味深いのは、ある限られたアルゴリズムのクラスで難読化が可能かどうかということですが、そのクラスには「有用な」アルゴリズムも含まれています。もし、計算量でアルゴリズムを制限しようとすると、難読化にはあまり期待できません。実際、上述したように、我々は（広く信じられている複雑さの仮定の下で）我々の反例がTC0に置けることを示している。一般に、我々の反例の複雑さは、擬似乱数関数の複雑さと本質的に同じであるため、我々の例を含まない複雑さのクラスには、多くの暗号学的に有用なアルゴリズムも含まれないことになる

2. Definitions

2.1 Preliminaries

• TM: Turing machine
• PPT: PPT
  $A^M(x)$
  : アルゴリズム
  $A,M$
  と文字列
  $x$
  として,
  $M$
  をオラクルアクセスとし,
  $x$
  を入力としたアルゴリズム
  $A$
  の出力を表す

Aが確率的チューリングマシンである場合

$A(x;r)$
とは、入力
$x$
とランダムテープ
$r$
に対して
$A$
を実行した結果

$x{\leftarrow }^{R}S$
: 集合Sに一様に分布する確率変数

$\mathrm{Supp}(D)$
: 分布
$D$
の下で0でない確率を持つ点の集合

$\mu :\mathbb{N}\to \mathbb{N}$
: negligible=任意の正の多項式

$${}^{\forall }p(\cdot ),{}^{\exists }N\in \mathbb{N},{}^{\forall }n>N,\mu (n)<\frac{1}{p(n)}$$

negligibleな関数表すのに
$\mathrm{neg}(\cdot )$
と書く.

2.2 Obfuscators

本節では、序論で述べた「仮想ブラックボックス」特性に基づいて、難読化装置の概念を形式化することを目指します。この性質は、“敵対者がプログラムPの難読化O(P)から計算できるものは、Pへの単なるオラクルアクセスが与えられても計算できる “ことを要求していることを思い出してください。この設定において、敵対者が何かをうまく計算するとはどういうことかを定義することになりますが、これにはいくつかの選択肢があります（一般性の高い順に並べてあります）。

def 2.1 (TM Obfuscator)

確率的アルゴリズム
$\mathcal{O}$
は以下の性質を満たす時 TM obfuscatorとなる
全てのTM
$M$
に対して, プログラム文字列
$\mathcal{O}(M)$
は
$M$
として同じ関数を計算する (functionality)

(多項式減速)
$\mathcal{O}(M)$
の記述長と実行時間は、最大でも
$M$
のそれよりも多項式的に大きい. すなわち、すべてのTM Mについて、｜O(M)｜≦p(|M|)

(“virtual black box” property) 任意のPPT
$A$
に対してPPT
$S$
が存在し, negl
$\alpha$
は任意のTM
$M$
に対して,

$$|\mathrm{Pr}[A(\mathcal{O}(M))=1]-{\mathrm{Pr}}^M(1^{|M|})=1|\le \alpha (|M|)$$

TMの型が文字列なのはTMを文字列化したということ?
意味: Sが適当な関数
$1^{|M|}$
で計算する時とAが関数Mの難読化
$\mathcal{O}(M)$
で計算する時で受理する確率は無視できる位同じ

def 2.2 (Circuit Obfuscator)

TM
$M$
が回路
$C$
になった版

prop 2.3

TM ObfuscatorがあるならCircuit Obfuscatorもある.

3. The Main Impossibility Result

watchlater