UCLAの暗号学者ら、未解決問題の識別不可能難読化の安全性を証明

過去20年の間に、識別不可能難読化（(iO） は、機能を維持したままコンピュータ・プログラムをハッカーに理解されないようにすることで、コンピュータ・プログラムを安全に保護するための強力な暗号化手法として浮上してきた。このアプローチの数学的基礎は2001年に公式化され、このテーマに関する100以上の論文が生まれたが、その後の研究の多くは、それぞれのアプリケーションに固有の仮定に依存しており、場合によっては、その後の暗号解析で破られた仮定だった。それ以来、研究者たちは、十分に研究された仮定からiOの証明可能なセキュリティ保証を実現しようとする努力を阻まれ、iOセキュリティの概念が揺らいだままになっている。

しかし、最近公開アーカイブに投稿された新しい論文の中で、カリフォルニア大学ロサンゼルス校の大学院生でNTT研究所のインターンであるAayush Jain、アレン・スクールのHuijia (Rachel) Lin教授、UCLAのCenter for Encrypted FunctionalitiesのディレクターであるAmit Sahai教授を含むチームは、理論的なブレークスルーを生み出し、ついにiOを固い地盤の上に置くことに成功した。

彼らの論文『Indistinguishability Obfuscation from Well-Founded Assumptions』では、著者らは初めて、証明可能な安全性を持つiOが、4つの十分に根拠のある仮定の亜指数的な硬さから構築されていることを示しているが、これらはすべて、複雑さ、コーディング、および数論に根ざした長い研究の歴史を持っている。ペアリンググループの対称外部拡散ヘルマン (SXDH)、エラー付き学習 (LWE)、大規模なフィールド上でのノイズ付き学習パリティ (LPN)、そして非常に簡単に計算できるブール疑似乱数発生器 (PRG)だ。

このトピックに関するこれまでの研究では、iOを実現するためには、NC0（すべての出力ビットが一定数の入力ビットに依存する非常に単純な計算モデル）でLWE、SXDH、PRGを仮定し、他に1つのオブジェクトを仮定するだけで十分であることが確立されている。この場合のオブジェクトは、多項式ストレッチと特殊な効率特性を持つ構造化シードPRG（sPRG）であり、シードは公開部分と非公開部分の両方から構成されている。sPRGは、敵対者が公開シードとsPRGの出力を見ることができても、擬似ランダム性を維持するように設計されている。このチームの論文からの重要な貢献の一つは、この目的のためのsPRGを構築するために、NC0でフィールド上のLPNとPRGを活用する新しいシンプルな方法だ。

iOは本当に暗号プロトコルのクラウンジュエル（王冠の宝石）のようなものだ。

一見すると、iOは特に有用な概念ではないように思える。プログラムの秘密が隠されていることを要求するのではなく、同じタスクを実行する2つの異なるプログラムがあっても、どちらの難読化されたバージョンが元のバージョンから来たのかを区別できないように、プログラムが十分に難読化されていることを要求しているだけだからだ。

しかし、iOは思ったよりも強力だ。例えば、銀行口座に関連するタスクを実行するプログラムがあるとするが、そのプログラムには暗号化されていないパスワードが含まれており、そのプログラムを手に入れた人には無防備な状態になっている。そうすると、パスワードを隠したまま同じタスクを実行できるプログラムがある限り、区別がつかない難読化ツールはパスワードを隠すのに十分な強さを持っていることになる。結局のところ、もしそうでなければ、両方のプログラムを難読化装置に通すと、どちらの難読化されたバージョンが元のプログラムから来たものなのかを見分けることができる。

長年にわたり、コンピュータ科学者たちは、iOをベースにして、想像できるほとんどすべての暗号化プロトコル（ブラックボックス難読化を除く）が可能であることを示してきた。これには、公開鍵暗号化（オンライン取引で使用される）のような古典的な暗号化タスクと、完全同型暗号化のような目の覚めるような新参者の両方が含まれており、クラウドコンピュータが暗号化されたデータについて何も学習せずに計算できるようになっている。また、これまで誰も構築方法を知らなかった暗号化プロトコル、例えば否認可能暗号化や機能暗号化なども含まれている。

Linが、最先端の暗号オブジェクトの一つを主流にするために、iOの大幅な進歩に貢献したのは今回が初めてではない。以前の研究では、彼女はiOとPRGの接続を確立し、プログラムを難読化するには高次数のマルチリニアマップではなく、一定次数のマルチリニアマップで十分であることを証明した。彼女はその後、アレン・スクールの同僚であるStefano Tessaroと一緒にこの研究を改良し、iOを構築するのに必要なマルチリニア写像の度数を30以上から3つに減らすことに成功した。

最近では、Jain、Sahai、カリフォルニア大学サンタバーバラ校のPrabhanjan Ananth教授、Christian Matt博士（当時ポスドク）と共同で、特殊な特性を持つ擬似乱数発生器を用いて、マルチリニア写像を使わずにiOを構築する新しい方法を開発した。Linと彼女の共著者は別の論文で、双線形群上のSXDH仮定のみに基づいて、定次多項式や分岐プログラムでさえも部分的に機能暗号化を隠蔽することを紹介した。これらの論文は、、iOを実現するための有用なツールやアイデアを提供し、最近の新構築への道を切り開いてくれた。

Lin、Jain、Sahaiの3人は、この最新のブレイクスルーに基づいて、紙の上だけでなく、実際のアプリケーションでも動作するように、より効率的な解を作ることを目指している。

Photo by Michael Dziedzic on Unsplash