暗号学における大発明がハッキング不可能なソフトウェアを実現するかもしれない

※Cryptography Breakthrough Could Make Software Unhackableの翻訳です。

　1996年、Amit Sahaiは、マサチューセッツ工科大学（MIT）の大学院生として過ごしていた頃、ゼロ知識証明（zero-knowledge proof）という奇妙な概念に魅了された。それは、ある人間にある命題が真であるということをそれが真である理由を詳らかには全く明らかにしないで納得させる数学的な手続きの一種である。Sahaiはこの直感に反する概念について熟考する内に、一層斬新な概念を考えるに至った。もし単に証明の内容を隠すことができるだけではなく、プログラムの内容をも隠すことができるとしたならばどうなるだろうか？　その場合、プログラムがどのようにして動作しているのか解明することのできない状態にしつつも、そのプログラムを使用することができるのではないか？
　プログラムを難読化する（obfuscating）という概念には数十年の歴史があるが、従来、確たる難読化の手法は勿論のこと、厳密な数学的枠組みを開発した者さえいなかった。商用ソフトウェア企業は、長年に亘って、プログラムがより理解のし難いものとなり、その一方で、難読化する前と同一の機能を実行するようにするために、様々な技法を開発してきたが、ハッカーはその全ての試みを打ち破ってきた。現在カリフォルニア大学ロサンゼルス校の計算機科学教授となっているSahaiが言うには、商用の難読化器（obfuscator）は精々プログラム解析の速度を遅らせるだけである。商用の難読化器を使えば、攻撃者はソフトウェアに隠されている秘密を解明するのに数分ではなく数日を要する可能性はある。
　安全確実なプログラムの難読化はソフトウェアパッチの保護、暗号化されたDVDのデータを読み取る半導体素子の機構の難解化、軍の無人機を制御するソフトウェアの暗号化など、多くの応用において有用であると思われる。より未来的なことを言えば、安全確実なプログラムの難読化が実現されれば、ネットワーク上において動作する自律型代行プログラムを作成し、それをクラウドに送信し、人間の代わりに行動させることができると思われる。たとえば、辺鄙な森の中にある山小屋で休暇を過ごす場合には、重要な顧客から電子メールを受け取った際に上司に報告するプログラムや、自分の銀行口座の残高が余りにも少なくなり過ぎた場合に自分の代わりに姉に対して警告を発するプログラムを作成して難読化することができる。プログラムの中に含まれるパスワードその他の秘密は安全が保たれることになる。
　Sahaiが言うには、信用することのできない計算機が存在する計算機の荒野に代行プログラムを送り込むことができる。もしかしたら敵対者に鹵獲され、取り調べられ、分解されるかもしれないが、秘密が明かされることはないだろう。
　しかしながら、Sahaiと何人かの同僚は、プログラムの難読化について熟考して、直ぐに気付いた。その潜在力は如何なる特定の分野への有用性をも凌駕する。もしプログラムの難読化器が作られれば、過去40年に亘って暗号学を活発にしてきた多くの問題、すなわち、安全確実に、たとえば、その正体について知り得なかったり、信用できなかったりするインターネット接続の相手方と意思疎通を行う方法についての問題を解決するかもしれない。
　プログラムの難読化器は想像することのできる殆ど全ての暗号学的な課題に対する妥当な構成を見付け出す際に強力な道具となるだろうとイスラエル工科大学のYuval Ishaiは述べた。
　正に難読化の強力さ故であるのだが、Sahaiとその同僚を含む計算機科学者は、難読化が不可能であると考えている。難読化は実在するには余りにも強力過ぎていると確信しているとSahaiは言う。Sahaiらの最初期の研究成果は全てのプログラムに対する最も自然な形態の難読化が完全に達成不可能であるということを示しており、難読化が不可能であるということを裏付けているように思われる。
　その後、2013年7月20日に、Sahaiと5人の共著者はCryptology ePrint Archiveに論文を投稿し、区別不可能性難読化（indistinguishability obfuscation）と言われる種類の難読化に対応する手続きの候補を明確に示した。2日後、Sahaiとその共著者の1人であるテキサス大学オースティン校のBrent Watersは2本目の論文を投稿し、最初の論文と併せて、この些か難解な形態の難読化が、暗号学者が夢見てきた能力の多くを有するかもしれないということを示唆した。
　マイクロソフトリサーチのBoaz Barakは言うには、これは普遍的な難読化器を発見しようとする試みにおいて、有益な結果としては最初の重大なものである。暗号学会はこの結果を受けて非常に興奮している。Cryptology ePrint Archiveでは本論文が投稿されてから6ヶ月で、本論文が投稿されるまでの17年で投稿されたよりも多くの、表題に難読化という言葉が含まれる論文が投稿された。
　しかしながら、新しい難読化の手法は商用の応用ソフトウェアで利用する段階には程遠い。本手法は短い単純なプログラムを巨大な非常に扱い難いプログラムに変貌させる。また、本手法の安全性は暗号学会によってまだ十分に吟味されていない新しい数学的な方法に基づいている。
　研究者はこの新しい研究成果を暗号学の重大な分岐点として称賛している。多くの暗号学者の話は難読化が可能かどうかということから難読化をどのようにして達成するかということに移った。
　6～7年前には、この問題について考えて、我々がその答えを得られるのか疑わしく思っていた筈なのだが。カリフォルニア工科大学のLeonard Schulmanはそう発言した。現時点で妥当な構成を得られているという事実は大いなる成功である。

実在するには余りにも強力過ぎている
　Sahaiが17年前に難読化について考え始めた時の最初の課題は単にそれを定義することであった。結局のところ、難読化された形態のプログラムであっても、入力を与えて何が出力されるか調べれば、使用者はそのプログラムについて必ず何らかのことを知ることができるのである。
　最も自然で、しかも、最も強くもある難読化器の定義は黒い箱の難読化器（black box obfuscator）という概念であった。この難読化器はプログラムを至極徹底的に攪拌し、最も有効な計算資源を有する者であってもそのプログラムについて入力及び出力から探り出せること以外は全く何も解明することができないようにする。ソフトウェアの内部に隠されているパスワードの内容は、それがプログラムの出力の1つでない限り解明することはできないし、元々計算するよう設計されている以外の、何か意味のあるものを計算するためにプログラムの一部を再構築することもできない。
　もし黒い箱の難読化器が実在するのならば、それは非常に強力であり、解明するのに数十年を要した、あるいは、場合によっては未だに解決されていない多くの暗号学の問題にすぐさま解決策を与える。たとえば、1970年代に創案され、インターネット商取引に道を開いた公開鍵暗号を例に取ると、それが発明される前は、2人の人間が内密に通信したい場合には、その2人は前以て接触し、通信文を符号化及び逆符号化するための暗号化の方法を選択し、その秘密鍵を共有しなければならなかった。公開鍵暗号は全世界に暗号化のための鍵を公開することができ、今までに受信者と接触したことのない人間であっても、受信者しか復号することができない通信文を受信者に対して送信することができる。この新しい概念は暗号学に大変な革命を齎し、次々と賞を授けられ、以て高く評価された。
　しかしながら、もし黒い箱の難読化器があったならば、公開鍵暗号の手続きを作るには、単にお気に入りの秘密鍵暗号方式を選択し、その動作をプログラムとして表現し、そのプログラムを難読化し、難読化された形態のプログラムを広く利用可能にすれば良いだけだということになる。そうすれば、誰でもそのプログラムを用いて、通信文を暗号化してから送信することができ、その一方で、誰も難読化されたソフトウェアから復号鍵を抽出することはできない。
　同様に、黒い箱の難読化器は全ての秘密鍵暗号方式を、インターネット上で見知らぬ人が実行することのできる公開鍵暗号方式へとすぐさま変換する方法を提供する。ある意味、難読化は全ての暗号に対する鍵である。
　Sahaiは言うには、現代的な暗号学というものは殆ど秘密鍵暗号から公開鍵暗号への変遷であったと言って良い。難読化は、数十年に亘って根本的に異なると我々は考えていたこれらの2つの世界の間を移動する、注目に値する能力を提供する。
　普遍的な黒い箱の難読化の強力さは、もしそれが実在するとしたら、話ができ過ぎているように思われる。実際、2001年にSahai、Barak及び後何人かの共著者は黒い箱の難読化を実現することは不可能であることを示した。研究者が実証したように、幾つかのプログラムは、自分の最も私的な時間をTwitterやFacebookで共有すると言って聞かない人々のようなものである。すなわち、それらのプログラムは自身の中に含まれている秘密を断固として公開し、如何なる難読化器でもそれを隠秘することはできない。
　それにも拘らず、Sahaiは難読化の問題について考えるのを止めることはできなかった。研究者集団が考案した、自身の知っていることを全部断固として曝け出すプログラムは、現実世界におけるプログラムとは異なり、人為的で不自然なわざとらしいものであった。もしかしたら黒い箱の難読化より幾らか弱い概念であっても、特に難読化に耐えるように構成されていないプログラムに対してならば、その中に含まれる秘密を保護することができるのではないだろうか？　そして、もしそうであるとしたならば、果たしてそのような概念はどれくらいの強力さを有するのであろうか？

ジグソーパズルプログラム
　Sahai、Barak及びその同僚は2001年の論文において黒い箱の難読化より弱い種類の難読化の定義を提案した。それはかなり難解な、区別不可能性難読化と呼ばれる概念である。プログラムを難読化する手続きが、全く同一の処理を行う2つのプログラムを処理した場合に、必ず、何れの難読化されたプログラムが元のプログラムの何れに由来するのか誰も区別することができないとき、その手続きは区別不可能性難読化器と言われる。
　この概念が特に有用であるに違いないという明確な理由はない。結局のところ、2つの難読化されたプログラムの素を区別することができないのだとしても、依然として復号鍵や秘密の命令など、重要な秘密を収集することは、難読化されたソフトウェアを調べれば可能であるかもしれないのである。
　これは非常に弱い難読化の概念であるとトーマス・J・ワトソン研究所のCraig Gentryは言う。
　しかしながら、2007年に、MITのShafi GoldwasserとマイクロソフトリサーチのGuy Rothblumは区別不可能性難読化器がもし作成できるのだとしたら、それが、可能なものの中では最良の難読化器であるということを示した。その考え方は以下のようである。もし何か別の難読化器が最良であるならば、その難読化器をプログラムを難読化するのに使用してから、更なる変形を施すために元のプログラムと難読化されたプログラムの両方を区別不可能性難読化器に通すことができる。結果として生じる2つのプログラムを調べても何れの難読化されたプログラムが元々の難読化されていないプログラムに由来するのか誰も区別することができない。すなわち、区別不可能性難読化器は少なくともプログラムの秘密を隠秘することに関しては他の最良の難読化器と同様の能力を有しているということである。
　GoldwasserとRothblumの研究成果は区別不可能性難読化器が全ての保護可能なプログラムの秘密を保護することに対する最良の可能性であることを意味した。しかしながら、誰もそのような難読化器を作成する方法を知らなかったし、そうでなくても、プログラムの秘密の内何れが保護可能なのかさえ誰も知らなかった。Sahaiは区別不可能性難読化器が、人々が真に気掛かりである秘密を保護することができるのか知りたいと思った。
　Sahaiの新しい研究成果に至る10年間は手詰まりと漸進的な成果によって特徴付けられた。長期に亘って私は壁にぶつかっており、前途が開けることを望んでいたとSahaiは言う。我々全員が非常に悲観的であった。しかし、その問題は非常に美しかったので、私は完全に虜になっていた。
　2012年秋、Sahaiは関数暗号（functional encryption）と呼ばれる問題に関して、トーマス・J・ワトソン研究所のSanjam Garg及びShai Halevi、SRIインターナショナルのMariana Raykovaに加えて更にGentry及びWatersと協働し始めた。この暗号は、異なる人々に対して、暗号化されたデータへの特定の水準の利用手段を与えるものである。Sahaiが信じられないほどに集中した期間と呼んだ、発想を提案し、それを破棄し、白紙に戻して考え直すという過程を経て、2013年春、研究者集団は問題への解決策を考え付いた。我々が得た結果は乱雑であり、非常に多くの可動部品と下付き文字の下付き文字（訳注：非常に複雑な数式という意味だろうか）を含んでいる。しかしながら、それは我々が解読することのできなかった最初のものであったとSahaiは思い起こした。
　研究者はその構成を単純化しようと試みている内に、それが予期していたより更に前を行っていることに気付いた。それは全てのプログラムに関して区別不可能性難読化を実行する方法を提示した。
　決して忘れることのないだろう瞬間だったとSahaiは言った。
　SahaiとWatersは更に彼らの得た区別不可能性難読化器が黒い箱の難読化器が提供すると思われる完全に包括的な暗号学的な保護の多くを提供すると思われるということを示した。たとえば、それは公開鍵暗号、電子署名（ウェブサイトの訪問者にそのウェブサイトが正真であることを納得させることができる）その他、従来解決されていなかった2つの主たる暗号手続きである関数暗号と否認可能暗号（deniable encryption）を含む多くの基礎的な暗号手続きを作成するのに使用することができる。
　研究者集団が得た難読化器は、与えられたプログラムを多重線型のジグソーパズルとSahaiが呼んでいるものに変換することによって難読化器として機能を果たす。プログラムの断片は1つ1つ、難読化されたプログラムが所定の方法で実行された場合に無作為性が相殺され、正しい出力が計算されるようにプログラムの断片が巧く纏め合わせられるように、注意深く選択された無作為な要素を混ぜ込むことによって難読化される。たとえ難読化されたプログラムに対して何か別のことを行おうと試みても、無作為性が個々のパズルの部品を無意味に見せ掛ける。
　研究者集団は格子に関するある種の新奇な問題を解くのが彼らの考える程に困難であるのならば、彼らが得た難読化方式は解読不可能であることを示した。この前提が正当であるかは時間が経てば明らかになるだろうが、研究者集団が得た難読化方式は既に幾つかの解読の試みに耐性を示している。また、Sahai、Barak及びGargはマイクロソフトリサーチのYael Tauman Kalai及びボストン大学のOmer Panethと共にこの方式に対する最も自然な種類の攻撃が確実に失敗することを証明した。更には、解くのが困難である格子に関する問題は新奇なものではあるものの、試験に耐え、実際の暗号方式の中で使われている解くのが困難である問題の一群に緊密に関係している。
　Sahaiはこの解くのが困難である問題の困難さが時間を掛けて証明されるだけでなく、計算機科学者が難読化方式をより従来型の暗号学的な前提の下で作成する方法を解明することを望んでいる。暗号学者は既に区別不可能性難読化の流行に乗って、この方式をより効率的にし、安全性の前提を強化し、結局のところどのような秘密を保護することができるのかを更に明瞭にする方法を捜し求めている。
　提案された難読化器は既にプログラムの難読化に関する多くの暗号学者の考えに一大転回を齎している。その問題は不可能ではないように思えるとカリフォルニア大学のDaniele Micciancioは言う。
　研究者集団が得た難読化手続きの精緻化という喫緊の課題を越えた先には甚深無量の問いが待ち構えている。難読化の問題が解決されたら、暗号学者には一体全体どのような課題が残されているのか？
　少なくとも原理的には難読化によって解決されない、暗号学における次の主要な未開拓分野は何なのだろうか？　Sahaiが言うには、それは我々の分野にとって最も大きな問いの1つである。