この方法は、「区別できない難読化」またはIOと呼ばれていました。 著者は、これを暗号化の「コアコア」として宣伝しました。これは、公開鍵や選択的にセキュリティで保護された署名などの有名なツールを再構築する普遍的なフレームワークです。 また、IOの背後にある数学的な装置が作品で実証されました。
これらの研究は多くの注目を集めましたが、2年以上の研究を通じて、専門家はIOの実施を妨げるかなり多くの実際的な困難に直面しました。 たとえば、IOが遅すぎます。 プログラムの難読化の遅延は、現代のコンピューターで何年も測定されています。 さらに、この方法は私たちが望むほど数学的に安全ではないことが判明しました。
しかし、過去数か月にわたって、2013年の最初の発表以来、非常に重要な進歩を示す作品が登場しました。 一部の研究者は、システムの実用バージョンは10年、またはそれ以前に作成できると考えています。 「今では深刻な制限がないかのように見えます」と、カリフォルニア大学のプログラマーであり、両方の科学論文の共著者であるアミット・サハイは言います。 「IOは強力なシステムであり、必要なすべてを実行できます。」 さらに、研究者は、量子コンピューターでさえそれを破ることができないと信じています。
小さな階段の山
IOの説明は、異なる方法で同じ結果を得る2つのプログラムの例から始まります。 たとえば、2つの等価な関数f（x）= x（a + b）およびf（x）= ax + bxを計算します。 3つの変数a、b、xのセットでは、両方のプログラムの結果は同じになります。 IOは、この方法でプログラムを暗号化することが可能であると主張しているため、ユーザーは2つのプログラムのどちらを自由に使用できるかを判断できません。
2013年の作業により、IOが暗号化の範囲を大幅に拡大できると多くの人が確信しました。 しかし、作品では、この可能性をどのように実践できるかの例はありませんでした。 研究者には2つの問題がありました。プロセスを高速化することと、IOが十分に安全であることを確認することです。
「このように難読化してからプログラムを実行するには数百年かかる場合があります」と、IOの仕事に携わるMITの暗号作成者であるVinod Vaikuntanathan氏は言います。 「結果がとてもおかしいときは、具体的な数字に従わない。」
コロンビア大学プログラマーのアリソン・ビショップは、IOを一連の小さな実用的なステップに分割する方法を示しました
プロセスを高速化するためにプログラマが選択するアプローチの1つは、1つの大きなプログラムではなく、それに関連する小さなプログラムを難読化することです。 したがって、難読化は2段階で行う必要があります。
最初は最も難しいです。 既存のIOメソッドは、かなり小さなプログラムのブートストラップから始まります。 このプログラムは、大きな「ターゲット」プログラムと対話します。 ブートストラッププログラムは、ターゲットプログラムの入力と出力のセキュリティシェルのように機能します。入力および終了するすべてを難読化し、その結果、プログラム自体を隠します。
しかし、小さなプログラムであっても難読化する方法はまだ不明です。 「このアーマーの最初のギャップを見つけようとしているようです」とSahai氏は言います。 「私たちはブートストラッププログラムにこだわっています。」
2番目のステップは、研究者に簡単に屈した。 ブートストラッププログラムが実行されている場合、次のタスクは、より長く多様な計算を難読化することです。 毎年の計算理論に関するシンポジウム（STOC）で、3つの研究チームが、1つの輪郭を難読化する方法からあらゆる種類の計算を難読化する方法（チューリングマシン）についての論文を発表しました。
これは大きな一歩です。 アウトラインを隠すために、研究者は入力のサイズと計算の各ステップを事前に知る必要があります。 コンピューターは、入力で任意の量のデータを受け取り、データが到着すると追加の計算を行うように構成されています。 シンポジウムで発表された研究では、「パンクチャドプログラミング」と呼ばれる特別な手法を使用して、互いに接続された一連の離散ステップの形で長いデータセットの計算を難読化する方法を示しました。
「主な技術的成果は、計算のローカルステップで輪郭にIOを適用し、その結果、すべての計算が保護されるようにすべてを結び付けることです」とコロンビア大学のプログラマー、アリソンビショップは言います。
数学的に証明された安全性
IOの有効性を高めることは実用的なタスクであり、メソッドの安全性を証明することが基本です。
オースティンのテキサス大学プログラマーであるSahaiとBrent Watersが2013年にIOの使用を説明したとき、信じられたのはこの方法がプログラム内に秘密を保持するということだけでした。 最初の作業は非常に複雑な結び目を結ぶようなものでした-解くのは難しいように見えますが、その構造を理解しないと、簡単な方法がないことを確信できません。
「その時点では、特定の構造しかありませんでした。その安全性を証明する方法さえ明確ではありませんでした」とヴァイクンタナタンは言います。
ブレントウォーターズ
それ以来、状況は改善されました。 暗号化は、コードをクラックするために攻撃者が解決しなければならないタスクを定義する数学に基づいています。 たとえば、RSA暗号化では、大きな整数の積が使用されます。 電子メールの読み取りを開始するには、攻撃者はこの値を取得して乗算することにより、2つの大きな整数を決定する必要があります。 現在の計算能力を持つこのタスクは不可能と見なされます。
暗号化スキームの基礎となる数学的計算は、強力であり、シンプルで、十分にテストされ、理解可能でなければなりません-そのため、暗号作成者は、タスクが実際に見られるほど複雑であることを確信できます。
「私たちが理解しているのは数学的な問題であるべきです。 さもなければ、経験はハッキングされる可能性があることを示しています」とSahai氏は言います。
2013年には、IOセキュリティに関する実際的な仮定はありませんでした。 翌年、IBMの研究者は、IOが「多重線形マッピング」と呼ばれる数学的オブジェクトに関連するいくつかの仮定に縮小した論文を発表しました。 「ハッカーがIOに侵入すると、これらの問題の1つを解決することを示しました」と、この作品の著者の1人であるビショップは説明しました。
多重線形マッピングは、2013年に暗号に登場しました。 専門家は、信頼性の問題をまだ十分に研究していません。 「これまでのところ、多重線形マッピングから候補にハックしても、一般の人々に衝撃を与えることはありません」とウォーターズは言います。
現時点では、コンピューターサイエンティストは、マルチリニアディスプレイをより理解しやすいものに置き換えようと取り組んでいます。 これまでの最良の候補は、「間違いを伴う学習」の概念です。 彼女は、「格子上の暗号」と呼ばれる領域に共通の「祖先」との多重線形マッピングを持っているため、置換が行われる可能性があります。 しかし、これまでのところ、誰もその方法を知りません。
セキュリティラッシュ
IOのすべての困難にもかかわらず、専門家はそれに基づいた暗号化はすでに近いと信じています。 Sahaiは、暗号化では、アイデアから実装までに30年かかることがあると指摘します。 また、過去2年間の進歩を考えると、IOに必要な時間は短くなる可能性があります。 「私たちは10-15を願っています」と彼は言います。
主なステップは、IOセキュリティのそれほど複雑でない数学的基礎を見つけることです。 今、この分野の最高の頭脳は、仕事は加速されたペースで進むべきだと信じています。 司教は、10年以内に一連の単純な数学的設定が見つかると「議論しない」と述べた。 Vaikuntanatanは一般に、「数年」かかると考えています。
過去2年間に、プロジェクトへの重大な財政的注入がありました。 SahaiはUCLA暗号化センターを運営し、全米科学財団から500万ドルの助成金を受け取りました。 DARPAはSafeWare研究プログラムを確立しました。これは、プログラムを難読化するための効果的で普遍的な方法を作成することを目的としています。
IOを実装しようとする開発者のラッシュは、このトピックの魅力と、新しい暗号化手法を開発する必要性の両方について語っています。 量子コンピューターの開発者も警戒しており、出現後、ほとんどの暗号化スキームが危険にさらされます。 おそらく、IOを除きます。