indistinguishability Obfuscation

ゼロ知識証明から派生した概念らしい(Wikipediaより)
On the (Im)possibility of Obfuscating Programs で提案

ゼロ知識証明とは

ある主張が正しいという事以外の情報が検証者に漏れないプロトコル.

説明は以下が詳しい.

プログラム難読化(Obfuscation)とは

ソースコードの保護を目的として意図的に読みにくいソースコードに変換すること.

Wikipedia

Indistinguishability obfuscation (IO) とは，プログラムの難読化を公式に表現する暗号学上のプリミティブです．形式的には，同じ関数を実装する同じサイズの2つの回路の2つの難読化は，計算上区別できないという性質を満たす．

歴史このアイデアの起源は、1996年にAmit Sahaiが提唱したゼロ知識証明という概念である[3]。2001年、Barakらはブラックボックス難読化が不可能であることを示した上で、識別不可能な難読化器のアイデアを提案し、非効率な難読化器を構築した[3][4][5]。 [3][4][5][2][要検証]この概念は比較的弱いと思われたが、Goldwasser and Rothblum (2007)は、効率的な区別不能難読化装置は最良可能な難読化装置であり、任意の最良可能な難読化装置は区別不能難読化装置であることを示した。 [3][6]（ただし、非効率な難読化装置の場合、多項式の階層が2段目まで崩れない限り、最良の可能性を持つ難読化装置は存在しない[6]）。候補となる構築物 Barakら（2001）は、同じ関数を計算する辞書的に最初の回路である回路に対して、非効率な区別不能難読化装置が存在することを証明した[4]。 [2013年に多線形写像に関する具体的な硬さの仮定の下で安全性が証明できるIOの候補構成が発表されたが[2][7][8]、この仮定は後に無効となった[7][8]（それ以前にGarg, Gentry, and Halevi (2012)がヒューリスティックな仮定に基づいて多線形写像の候補版を構成していた[9]）。 2016年以降，林は多直線写像のより厳密でないバージョンに基づくIOの構築を模索し始め，次数30までの写像に基づく候補を構築し，最終的には次数3までの写像に基づく候補を構築した[8]。最終的に2020年，Jain，Lin，Sahaiは，対称外部Diffie-Helman，learning with errors，learning plus noiseの仮定に基づくIOの構築を提案するとともに[8][10]，関数クラスNC0における超直線伸張疑似乱数生成器の存在を示した。 [10]（NC0における疑似乱数生成器の存在は，（亜線形伸張であっても）2006年まで長年の未解決問題でした[11]）この構成が量子計算によって破られる可能性はありますが，それに対しても安全であるかもしれない代替構成があります（後者はあまり確立されていない安全性の仮定に依存していますが）[8][憶測？] 実用性は？IO候補を実装してベンチマークを行う試みがある[2]。例えば，2017年時点で，セキュリティレベル80ビットの関数{displaystyle x_{1}\ wedge x_{2}\ wedge x_{32}}{\ wedge x_{1}\ wedge x_{32}}の難読化は，生成に23.5分，計測に11. また，Advanced Encryption Standardのハッシュ関数をセキュリティレベル128ビットで難読化すると，測定値は18PB，評価時間は約272年となる[2]． 2015年にはIO候補のオープンソースソフトウェア実装が作成された[12]．

初出論文

On the (Im)possibility of Obfuscating Programs

Abstract

非公式には、難読化装置 $O$ は、プログラム（または回路） $P$ を入力として、 $P$ と同じ機能を持ちながらある意味で「理解できない」新しいプログラム $O (P)$ を生成する（効率的で確率的な）「コンパイラ」である。もし難読化装置が存在するとすれば、ソフトウェアの保護から同型暗号、ライスの定理の複雑さの理論的類推まで、さまざまな暗号や複雑さの理論的応用が可能になります。これらの応用のほとんどは、難読化における「理解不能」という条件を、 $O (P)$ が「仮想ブラックボックス」であることを意味すると解釈することに基づいています。

本研究では、難読化の理論的な検討を開始しました。我々の主な結果は、上記の直観の非常に弱い形式化の下でさえ、難読化は不可能であるということです。すなわち

(a) 関数 $f \in F$ を計算する任意のプログラムが与えられたとき、その値π(f)は効率的に計算できるが

(b)（ランダムに選択された）関数 $f \in F$ へのオラクルアクセスが与えられたとき、ランダムな推測よりもはるかに良い $π (f)$ を計算できる効率的なアルゴリズムは存在しない、という特性

$π : F \to 0, 1$ を構築することにより、このことを証明する。この不可能性の結果を様々な方法で拡張し、

(a)必ずしも多項式時間で計算できない、

(b)機能を近似的にしか維持できない、

(c)非常に限定された計算モデルに対してのみ機能する必要がある

といった難読化装置も含めています(TC0)。また、「難読化できない」署名方式、暗号化方式、疑似乱数関数族を構築することで、難読化装置のいくつかの潜在的な応用を排除します。

Introduction

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

(functionality) $O (P)$ は $P$ と同じ関数を計算する
(“virtual black box” property) $O (P)$ から効率的に計算できるものは、 $P$ へのオラクルアクセスがあれば、効率的に計算できる。

実際には難読化のためのヒューリスティックなアプローチがありますが（図1と[CT00]を参照）、この問題に関する理論的な研究はほとんどありませんでした。難読化が可能であれば、様々な暗号や複雑さの理論的な応用が可能であるにもかかわらず、これは残念なことです。

本研究では、難読化の理論的な検討を開始しました。この概念の様々な形式化を検討し、実現できることとできないことを理解しようとしています。主な結果は否定的なもので、（一般的に理解されているような）難読化は不可能であることを示しています。この結果と他の結果をより詳しく説明する前に、動機付けと概念の明確化のために、難読化装置の潜在的なアプリケーションのいくつかを概説します。

1.2 Our Results

The Basic Impossibility Result

上記の応用例の多くは、難読化されたプログラムは “virtual black box” であるという直観に基づいています。つまり、難読化されたプログラムから効率的に計算できるものは、プログラムへのオラクルアクセスがあれば、効率的に計算できるはずなのです。我々の主な結果は、このような難読化の概念を実現することは不可能であることを示しています。

これを証明するために、(任意の一方向性関数から) “inherently unobfuscatable” (本質的に難読化不可能)な関数族 $F$ を構築します。この関数族は、次のような性質 $π : F \to 0, 1$ を持ちます

関数 $f \in F$ を計算する任意のプログラム（回路）が与えられた場合、値 $π (f)$ は効率的に計算できる
しかし、（ランダムに選択された）関数 $f \in 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: Probabilistic Polynomial-time Turing machine
$A^{M} (x)$ : アルゴリズム $A, M$ と文字列 $x$ として, $M$ をオラクルアクセスとし, $x$ を入力としたアルゴリズム $A$ の出力を表す
Aが確率的チューリングマシンである場合
- $A (x; r)$ とは、入力 $x$ とランダムテープ $r$ に対して $A$ を実行した結果
- $x \leftarrow^{R} D$ : Dにしたがって分布する確率変数
- $x \leftarrow^{R} S$ : 集合Sに一様に分布する確率変数
- $Supp (D)$ : 分布 $D$ の下で0でない確率を持つ点の集合
- $μ : N \to N$ : negligible=任意の正の多項式 $^{\forall} p (\cdot),^{\exists} N \in N,^{\forall} n > N, μ (n) < \frac{1}{p ( n )}$
- negligibleな関数表すのに $neg (\cdot)$ と書く.

Probabilistic polynomial time Turing machine

非決定的チューリングマシンの一つで, 左右の遷移がそれぞれ $\frac{1}{2}$ で決まるTM.

$M = (Q, Σ, Γ, q_{0}, A, δ_{1}, δ_{2})$

状態の集合

入力アルファベット

テープアルファベット( $Σ \in Γ$ )

初期状態

受理状態の集合

遷移関数: $δ_{1}, δ_{2} : Q \times Γ \to Q \times Γ \times {L, R}$

意味: 現在の状態とヘッドが読んでいる文字を入力として次状態とテープを書き換える文字と移動方向を出力とする

確率的チューリングマシン

確率的に遷移するので毎回受理したりしなかったりする.

因みに, 非決定性チューリングマシンで多項式時間で解ける(間違える確率は1/2より小さい)決定問題のクラスを PP という.

Turing Machine

“計算” をモデル化したもの.

左右に無限に伸びる1本の文字が書かれたテープ
テープの文字を読み取るヘッダ
ヘッダを制御する制御部

からなる. 計算が終わったら “受理状態” としてTuring Machineは停止する.

TMは状態遷移図と対応している. 例として 0, 1のみからなる文字列 $\in L$ が回文( $w w^{R}, w \in {0, 1}^{*}$ )かどうかを判定するTMの状態遷移図は以下のようになる.

多項式時間帰着について

2.2 Obfuscators

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

def 2.1 (TM Obfuscator)

確率的アルゴリズム $O$ は以下の性質を満たす時 TM obfuscatorとなる

全てのTM $M$ に対して, プログラム文字列 $O (M)$ は $M$ として同じ関数を計算する (functionality)
(多項式減速) $O (M)$ の記述長と実行時間は、最大でも $M$ のそれよりも多項式的に大きい. すなわち、すべてのTM Mについて、｜O(M)｜≦p(|M|)
(“virtual black box” property) 任意のPPT $A$ に対してPPT $S$ が存在し, negl $α$ は任意のTM $M$ に対して,

$∣ Pr [A (O (M)) = 1] - Pr [S^{M} (1^{∣ M ∣}) = 1] ∣ \leq α (∣ M ∣)$

TMの型が文字列なのはTMを文字列化したということ?

意味: Sが適当な関数 $1^{∣ M ∣}$ で計算する時とAが関数Mの難読化 $O (M)$ で計算する時で受理する確率は無視できる位同じ

def 2.2 (Circuit Obfuscator)

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

prop 2.3

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

3. The Main Impossibility Result

tags	crypto/theory
aliases	iO

Quartz 5

Explorer

indistinguishability Obfuscation

indistinguishability Obfuscation

ゼロ知識証明とは

プログラム難読化(Obfuscation)とは

Wikipedia

初出論文

Abstract

Introduction

1.2 Our Results

The Basic Impossibility Result

近似的難読化装置

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

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

1.3 Discussion

2. Definitions

2.1 Preliminaries

Probabilistic polynomial time Turing machine

Turing Machine

2.2 Obfuscators

def 2.1 (TM Obfuscator)

def 2.2 (Circuit Obfuscator)

prop 2.3

3. The Main Impossibility Result

def. 3.1

Graph View

Table of Contents

Backlinks