Archive for February, 2017

サイバーセキュリティ崩壊、量子コンピュータが暗号化されたデータを解読する

Friday, February 17th, 2017

米国政府はセキュリティに関して異例の警戒情報を発表。量子コンピュータが実用化されると現行の暗号化技術が破られると注意を喚起した。政府や企業は機密情報を暗号化して送受信するが、量子コンピュータが悪用されるとセキュリティが担保されなくなる。暗号化技術は全世界で使われており、量子コンピュータの登場でサイバーセキュリティの屋台骨が崩壊する。

出典: VentureClef

米国政府の報告書

サンフランシスコで開催されたセキュリティカンファレンス「RSA Conference」 (上の写真) で量子コンピュータと暗号化技術について議論された。NSA (アメリカ国家安全保障局) はこの危険性に関する報告書「Commercial National Security Suite and Quantum Computing FAQ」を公開し、量子コンピュータが暗号化技術に及ぼす脅威とその対応策について述べている。

量子コンピュータの脅威

米国政府は暗号化技術を標準化し、機密データを安全に扱うためには、これら標準アルゴリズムを使うことを推奨している。このため政府や民間システムで規格化された暗号化技術が幅広く使われている。しかし量子コンピュータの登場で、政府が推奨する暗号化アルゴリズムが破られ、安全にデータを管理することができなくなる。

問題点を指摘するが対策は無い

報告書は問題点を指摘するものの、これに代わるソリューションを示しているわけではない。米国では暗号化アルゴリズムはNIST (アメリカ国立標準技術研究所) が管轄する。NISTは米国の標準技術や規格の制定を通し、産業競争力を育成する任務を担っている。現在使われている暗号化技術はNISTが標準化し、米国だけでなく全世界で使われている。しかし、量子コンピュータに対応できる暗号化技術 (Post-Quantum Cryptographと呼ばれる) については解を示していない。NISTが主導して開発すると述べるに留まっている。

影響を受けるアルゴリズム

NSAが問題としているアルゴリズムはPublic-Key Cryptography (公開鍵暗号) と呼ばれる方式である。Public-Key CryptographyとはPublic Key (公開鍵) とPrivate Key (秘密鍵) のペアを使ってデータを安全に送受信する仕組みを指す。Public Keyでデータを暗号化して送信し、受信者はPrivate Keyでデータを復号化する。実装方式としてはRSA、ECC (Elliptic Curve Cryptography) 、Diffie-Hellmanの三つのアルゴリズムが対象となる。これらのアルゴリズムを搭載したシステムは量子コンピュータの登場で安全性が保障されなくなる。

生活への影響は甚大

Public-Key Cryptographyはインターネットで幅広く使われ、影響の範囲は我々の生活に及ぶ。オンラインバンキングで端末と銀行が交信する際はセキュアなプロトコール「HTTPS」が使われる (下の写真、Bank of Americaとの通信)。ログインIDやパスワードは暗号化プロトコールTransport Layer Security (TLS) で暗号化して送信される。仮に経路上で通信が第三者に盗聴されてもIDやパスワードは解読できない仕組みになっている。量子コンピュータの登場でこの安全性が崩壊し、世界のウェブ通信が危機にさらされることとなる。

出典: Bank of America

なぜ量子コンピュータは暗号化アルゴリズムを敗れるのか

量子コンピュータが暗号化アルゴリズムを破るメカニズムは、量子コンピュータが超高速で処理する能力があるだけでなく、その数学モデルと深い関係がある。量子コンピュータはどんなアプリでも処理できる訳ではなく、特定アルゴリズムだけを超高速で実行する。1994年、Bell Laboratoriesの研究員Peter Shorは、量子コンピュータで整数因数分解 (integer factorization) の問題を解くアルゴリズムを開発した。このアルゴリズムは「Shor’s Algorithm」と呼ばれ、暗号化技法の中心部である数学問題を解くことができるとして早くから課題が指摘されていた。

量子コンピュータの登場

その当時は量子コンピュータの研究開発は進むものの、実際に稼働するモデルについては疑問視されていた。更に、商用モデル登場までには長い年月を要すとみられ、Shor’s Algorithmの危険性は論理の世界に留まっていた。ここにきて、量子コンピュータの開発速度が上がり、危険性が現実のものになってきた。カナダ企業D-Waveは製品を出荷し、IBMはクラウド経由で量子コンピュータを提供している (下の写真)。GoogleやMicrosoftにおける量子コンピュータ研究も進んでいる。Shor’s Algorithmを解く能力を持つ量子コンピュータはまだ存在しないが、Public-Key Cryptographyの安全性が脅かされることが現実の問題となってきた。

出典: IBM Research

Googleが開発するNew Hope

これに対応するためにPost Quantum Cryptographyの開発が始まった。Googleもその一社で、量子コンピュータの登場に備えた暗号化アルゴリズムを発表した。これは「New Hope」と呼ばれ、ブラウザーとサーバ間の通信を安全に行う仕組みを提供する。上述「HTTPS」に代わる方式で、量子コンピュータでも解読できない方式でデータを暗号化する。この暗号化方式は「CECPQ1」と呼ばれ、Transport Layer SecurityにPost-Quantum Cryptographyを実装した構造となっている。これをChrome Canaryに実装し一般に公開された (下の写真、量子コンピュータが登場してもGoogle Playでのオンラインショッピングを安全に実行できる)。

出典: Google

ベンチャー企業の取り組み

RSA Conferenceではカナダのベンチャー企業「ISARA」が量子コンピュータ登場に備えたソリューションを紹介した。同社は既に政府や金融機関向けに製品を提供している。ISARAのAlexander Truskovskyによると、Post Quantum Cryptographyの問題はアルゴリズム開発だけでなく、システムインテグレーションの問題であるとも述べた。暗号化アルゴリズムはシステムの基幹技術でモジュールは様々な部分に散在している。それを確認したうえで古いモジュールを置き換えたり、新しいモジュールを併設するなどの作業が必要となる。2000年問題 (Y2K Problem) が発生したように、Post Quantum Cryptographyでも大規模なシステム改修作業が必要となる。

今から準備を始める必要がある

主要IT企業で量子コンピュータ開発が進んでいるが、実用に耐えるモデルはまだ登場していない。NSAは報告書の中で、なぜこのタイミングで問題点を公開したのかについて述べている。いま現在は公開鍵方式のアルゴリズムを破る能力の量子コンピュータは登場していない。一方、システム構築は数十年単位で設計する必要がある。過去の事例を見るとアルゴリズム導入には20年程度かかっている。このため、Post-Quantum Cryptographyに対応するには、今から準備を始めないと間に合わないと警告する。つまり、量子コンピュータが普及するのはもう少し先であるが、問題を理解してその対応を検討する時期が到来した。

Googleは駐車場の込み具合をAIで予測する技術を開発、センサーは不要でアルゴリズムが正確に推定

Friday, February 3rd, 2017

駐車場管理はInternet of Thingsの得意分野で、設置したセンサーがクルマの有無を捉え混雑状況を把握する。Googleのアプローチはソフトウェアで、クルマの流れをMachine Learningで解析し混雑状況を正確に推定する。駐車場にセンサーを設置することなく、アルゴリズムのパワーで施設を管理する。

出典: VentureClef

駐車場の混雑情報を表示

駐車場の混雑状態を表示するサービスが今月から始まった。Google Mapsで目的地までの道順を検索すると、駐車場の込み具合も表示される (上の写真、最下段の分部)。例えば、Mountain View市街に向かうとき、駐車場の込み具合は「Medium」となっている (上の写真左側)。これは「駐車場を探すのは難しくない」という意味で、時間通りに出発できる。込み具合に応じて出発時間を調整することができる。

駐車場が無ければ電車で移動

一方、サンフランシスコのカンファレンス会場への道順を検索すると、駐車場は「Limited」と表示される (上の写真右側)。これは「駐車場は限られている」という意味で、駐車場を探すために時間がかかると注意を促している。駐車が難しいのであれば電車で行くという選択肢も浮上する。事実、Googleによるとこのサービスを始めると、電車で移動するルートの検索件数が急増したとしている。

混雑状況を把握する仕組み

Googleは新サービスの仕組みを「Using Machine Learning to predict parking difficulty」として公表した。これによると、駐車場空きスペースを把握するために、クラウドソーシングとMachine Learningという技法を使っている。クラウドソーシングとはユーザデータを集約して利用することを示す。このケースではGoogle Mapsユーザの位置情報を集約して利用する。Google Mapsユーザに「駐車場を探すまでどのくらいかかりましたか?」という質問を送り、その回答を集約し、駐車場を探す難易度を算定した。Googleはこの手法で信頼度の高いGround Truth (基準データ) を収集した。

店舗やレストランの混雑状況

Googleは早くから利用を許諾したユーザの位置データを使ったサービスを展開している。その代表がGoogle Mapsで表示されるLive Traffic (渋滞情報) でクルマの流れをリアルタイムで表示する。また店舗やレストランのPopular Time (混雑情報) やVisit Duration (滞在時間) を提供している。便利なツールで生活の一部として利用されている。

クラウドソーシングの限界

しかしこの手法だけでは駐車場の込み具合を正確に推定することはできない。クルマを駐車する場合はパターンの数が多く、これらの要因も考慮する必要がある。例えば、クルマが私有地に駐車すると、アルゴリズムは空きスペースがあると誤認する。また、利用者がタクシーやバスで移動したケースも、アルゴリズムは駐車スペースがあると誤認する。駐車スペースを判定するためにはクラウドソーシングの手法では限界がある。

出典: VentureClef

クルマの移動パターンと駐車場の有無

このためクルマがどんなパターンで移動すると駐車場が無いことを示すのか、その特徴量を見つけることがカギとなる。昼食時間にクルマが街中を周回する動きをすると (下の写真)、これは駐車場が無いためと判断する。一方、利用者が目的地に到着し、そのまま施設に入った場合は駐車場があったと判断する。このような特徴量を把握してアルゴリズムに反映した。

出典: Google

20のモデルを生成

この他に目的地に特有な条件や駐車場の位置に依存した要因も考慮する必要がある。また、駐車する時間や、駐車する日に依存する条件なども取り入れる。更に、過去の統計情報も利用された。最終的には20のモデルが作られ、これを使ってアルゴリズムが教育された。

Logistic Regressionという手法

前述の通り、このモデルの解析ではMachine Learningが使われた。Machine Learningには様々な手法があるが、その中でもLogistic Regressionという技法が使われた。Logistic Regressionとは統計学の代表的な技法で、変数の間の関係を推定する。アルゴリズムを教育することで、ある変数を入力すると、その結果を推定することができる。つまり、Logistic Regressionはある事象に関する結果を予想する。ここではドライバーの運転データを入力すると、駐車場を探すのが容易であったか、困難であったかを推定する。アルゴリズムは容易か困難かの二つの値を出力し、これはBinary Logistic Modelと呼ばれる。

Deep LearningではなくMachine Learningを採用

Deep Learningで世界をリードするGoogleであるが、敢てMachine Learningの技法を使ったことは興味深い。具体的には、Neural Network (人間の脳を模したネットワーク) ではなくLogistic Regression (統計手法) が使われた。Googleはこの理由として、「Logistic Regressionは技術が確立しており、挙動を理解しやすいためと」述べている。このことは、Neural Networkは中身がブラックボックスでその挙動が分かりにくいということを示す。

今年のAI技法のトレンド

Googleや他の企業でMachine Learningを見直す動きが広がっている。Neural Network全盛時代であるが、長年にわたり培われた技法を改良しうまく利用しようとする試みである。同時に、Neural Networkのブラックボックスを開き、仕組みを解明しようという研究も始まった。AIの観点からは、Machine Learningの改良とNeural Networkの解明が今年の大きなテーマになっている。

サンフランシスコ市街の駐車場

この技法でサンフランシスコ市街の駐車場の混雑を予測すると下の写真の通りとなる。市街地を区画ごとに分け駐車場の込み具合を表示している。色の濃い部分が混雑が激しいことを示す。上段は月曜日で下段は土曜日。左側は午前8時で右側は午後9時の標準的な込み具合を表示している。月曜日の朝はFinancial Districtを中心としたビジネス街の駐車場が混むが、土曜日の夜はUnion Squareを中心とした観光スポットの駐車場が込むことが分かる。

出典: Google

サンフランシスコ市の取り組み

駐車場管理や混雑情報の発信は行政の責任でもある。事実、サンフランシスコ市は駐車場にIoTを導入し、混雑度を把握する実証実験「SF Park」を進めている。サンフランシスコ市街地では路上駐車スポットにParking Meterが設置され、コインやカードやアプリで駐車料金を支払う (下の写真)。同時に、Parking Meterがセンサーとなり、クルマの有無を検知する。Parking MeterはIoT専用ネットワークSigfoxで結ばれ、駐車スポットの込み具合を集約する。このIoTシステムが完成すると、駐車場混雑情報がリアルタイムで分かることになる。

出典: San Francisco Municipal Transportation Agency

センサー対アルゴリズム

果たしてサンフランシスコ市によるIoT駐車場管理システムは正しく混雑状態を把握できるのか関心が高まっている。Parking Meterで駐車を正しくセンシングできるかという問題である。Parking Meterのある駐車スポットに違法で駐車したり、また、特別許可証を持ったクルマが駐車した場合は空きと判断される恐れがある。また、駐車時間が残っているのにクルマを出す人もあり、このケースでは駐車中と判断される可能性が高い。

スマートシティー開発のモデルケース

リアルタイムで正確な駐車場空き情報を把握するのは難しい作業となる。これに対し、Googleはセンサーは使わないでアルゴリズムが混雑状況を把握する。センサーとアルゴリズムの戦いが始まり、どちらに軍配が上がるのか地元住民だけでなく全米で関心が高まっている。GoogleやSF Parkの取り組みが米国で展開されているスマートシティー開発のモデルケースとして注目されている。