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

NTT研究所のインターンであるAayush Jain、アレン・スクールのHuijia (Rachel) Lin教授、UCLAのCenter for Encrypted FunctionalitiesのディレクターであるAmit Sahai教授を含むチームは、理論的なブレークスルーを生み出し、ついにiOを固い地盤の上に置くことに成功した。

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

Read more

アドビ、日本語バリアブルフォント「百千鳥」発表  往年のタイポグラフィー技法をデジタルで再現

アドビ、日本語バリアブルフォント「百千鳥」発表 往年のタイポグラフィー技法をデジタルで再現

アドビは4月10日、日本語のバリアブルフォント「百千鳥」を発表した。レトロ調の手書き風フォントで、太さ(ウェイト)の軸に加えて、字幅(ワイズ)の軸を組み込んだ初の日本語バリアブルフォント。近年のレトロブームを汲み、デザイン現場の様々な要望に応えることが期待されている。

By 吉田拓史
新たなスエズ危機に直面する米海軍[英エコノミスト]

新たなスエズ危機に直面する米海軍[英エコノミスト]

世界が繁栄するためには、船が港に到着しなければならない。マラッカ海峡やパナマ運河のような狭い航路を通過するとき、船舶は最も脆弱になる。そのため、スエズ運河への唯一の南側航路である紅海で最近急増している船舶への攻撃は、世界貿易にとって重大な脅威となっている。イランに支援されたイエメンの過激派フーシ派は、表向きはパレスチナ人を支援するために、35カ国以上につながる船舶に向けて100機以上の無人機やミサイルを発射した。彼らのキャンペーンは、黒海から南シナ海まですでに危険にさらされている航行の自由の原則に対する冒涜である。アメリカとその同盟国は、中東での紛争をエスカレートさせることなく、この問題にしっかりと対処しなければならない。 世界のコンテナ輸送量の20%、海上貿易の10%、海上ガスと石油の8~10%が紅海とスエズルートを通過している。数週間の騒乱の後、世界の5大コンテナ船会社のうち4社が紅海とスエズ航路の航海を停止し、BPは石油の出荷を一時停止した。十分な供給があるため、エネルギー価格への影響は軽微である。しかし、コンテナ会社の株価は、投資家が輸送能力の縮小を予想している

By エコノミスト(英国)
新型ジェットエンジンが超音速飛行を復活させる可能性[英エコノミスト]

新型ジェットエンジンが超音速飛行を復活させる可能性[英エコノミスト]

1960年代以来、世界中のエンジニアが回転デトネーションエンジン(RDE)と呼ばれる新しいタイプのジェット機を研究してきたが、実験段階を超えることはなかった。世界最大のジェットエンジン製造会社のひとつであるジー・エアロスペースは最近、実用版を開発中であると発表した。今年初め、米国の国防高等研究計画局は、同じく大手航空宇宙グループであるRTX傘下のレイセオンに対し、ガンビットと呼ばれるRDEを開発するために2900万ドルの契約を結んだ。 両エンジンはミサイルの推進に使用され、ロケットや既存のジェットエンジンなど、現在の推進システムの航続距離や速度の限界を克服する。しかし、もし両社が実用化に成功すれば、超音速飛行を復活させる可能性も含め、RDEは航空分野でより幅広い役割を果たすことになるかもしれない。 中央フロリダ大学の先端航空宇宙エンジンの専門家であるカリーム・アーメッドは、RDEとは「火を制御された爆発に置き換える」ものだと説明する。専門用語で言えば、ジェットエンジンは酸素と燃料の燃焼に依存しており、これは科学者が消炎と呼ぶ亜音速の反応だからだ。それに比べてデトネーシ

By エコノミスト(英国)