現代の暗号方式の多くは、セキュリティを計算量の複雑さに依存しています。原理上は解読可能ですが、膨大な計算資源を使っても、現実的には途方もない時間がかかります。
しかし、情報理論的安全性という別の安全性の概念があります。これは、計算能力に上限のない攻撃者であっても、暗号化されたメッセージから有用な情報を一切取り出せないことを意味します。情報理論的安全性を保証する暗号方式も考案されていますが、実用化するには複雑すぎます。
Allerton通信・制御・コンピューティング会議で発表された一連の論文で、MITとアイルランドのメイヌース大学の研究者らは、既存の実用的な暗号方式にも独自の情報理論的保証があることを示しました。暗号化されたデータの一部は、計算能力に上限のない攻撃者であっても取り出せません。
研究者らは、任意の暗号方式について最低限の安全性保証を算出する方法を示しました。これにより、情報管理者はデータを保護する方法について、より多くの情報に基づいて判断できるようになります。
「こうした限界を調べ、特徴づけることで、これらの方式の性能や、符号理論など他分野のツールをセキュリティシステムの設計や理解にどう活用できるかについて、多くの知見が得られます」と語るのは、電気工学・コンピューターサイエンスの大学院生で、Allerton会議の3本の論文すべての筆頭著者であるフラビオ・デュ・ピン・カルモン氏です。指導教員である電気工学・コンピューターサイエンスのセシル・E・グリーン教授、ミュリエル・メダール氏も3本すべての論文に参加し、メイヌース大学のケン・ダフィー氏やMITリンカーン研究所のマヤンク・ヴァリア氏らも加わっています。
研究者らの数学的枠組みは、データプライバシーの問題、すなわちインターネット利用者のオンライン履歴に関する集計済みの、いわゆる「匿名化」データから、どれほどの情報を読み取れるかという問題にも応用できます。たとえば、Netflixが利用者の映画の好みに関するデータを公開した場合、政治的な好みに関するデータまで意図せず公開してしまうことはないでしょうか。カルモン氏らの手法を使えば、データ管理者は集計データを変更したり、その提示方法を工夫したりして、プライバシー侵害のリスクを最小限に抑えられます。
近接性を保つ
この手法の仕組みを理解するため、入力、つまり平文が「A」「B」「C」の3種類だけで、出力、つまり暗号文も3種類だけの暗号方式を想像してみましょう。それぞれの暗号文が、3種類の平文のどれを符号化しているかには、一定の確率があります。
暗号文は、3種類の平文を頂点とする三角形の内部の点として表せます。ある暗号文が特定の平文を符号化している確率が高いほど、その点は対応する頂点に近づきます。たとえば、BやCよりもAを符号化している可能性が高い暗号文は、頂点BやCより頂点Aに近くなります。安全な暗号方式では、暗号文を表す点が三角形全体に散らばらず、互いに近くにまとまっています。つまり、どの暗号文からも、攻撃者が方式について得られる情報は他の暗号文と変わりません。
もちろん、ほとんどの暗号化メッセージでは、対応する平文の候補は3つよりはるかに多くあります。9桁の数字のような単純な平文でも10億通りの値があり、暗号化された社会保障番号に対応する確率は、10億次元空間内の点で表されます。しかし、一般原則は同じです。点が互いに近くに集まる暗号方式は優れており、そうでない方式は優れていません。
攻撃者が個々の暗号文に関連する確率を知ることは、実際にはできません。暗号方式の秘密鍵を持つ人でさえ、その確率の算出は困難でしょう。カルモン氏、メダール氏らは分析にあたり、幅広い分布に適用できる安全性指標を開発し、さらに最悪のケース、つまり主な点の集まりの中心から最も遠い点を正確に算出する手法を加えました。確率がどの程度まとまっているかを示す数学的な記述は、原理上、攻撃者が暗号文からどれだけの情報を取り出せるかを直接示します。
対象を絞った保護
2012年に発表した最初のAllerton論文で、研究者らはこの確率的枠組みを使い、暗号文全体としては情報理論的に安全でなくても、その一部のビットは安全であり得ることを示しました。したがって、すべてのデータについて完全な安全性を保証できなくても、たとえば社会保障番号など特定のデータについては保証できる暗号方式を考案できるはずです。
「暗号学者と話すと、いつもこう聞かれました。『すごいですね！何をしても個々の記号を隠せると保証できる。でも、平文の関数についてはどうですか？』と」とカルモン氏は語ります。「標準的な暗号の安全性定義では、そこが重要です。」
つまり、暗号方式によって、攻撃者が符号化された社会保障番号を取り出せないことは保証できても、その番号の下4桁は取り出せるかもしれません。同様に、対象者の年齢を特定できないようにしても、その人がたとえば30歳から40歳の間だと推測することは可能かもしれません。
研究者らが最後の2本のAllerton論文で取り組んだのは、この問題です。カルモン氏、メダール氏、ヴァリア氏は、特定の関数が暗号文から取り出しにくい、あるいは取り出しやすいと判定できれば、相関する多くの関数についても同様に判定できることを示しました。この手法は、平文の関数に関する暗号学者の懸念に応えるだけでなく、極めて高次元の確率空間を分析する必要がないという利点もあります。単一の関数の安全性に関する情報は、比較的簡単な分析で得られることが多く、暗号方式全体の安全性について強力な保証をもたらします。
「完全秘匿性は非常に厳しい要件です。それを保証する唯一の方法は、スパイ小説に出てくるようなワンタイムパッドを使うことだと言ってよいでしょう」と、イリノイ大学アーバナ・シャンペーン校の電気・コンピューター工学助教、マキシム・ラギンスキー氏は述べます。「それよりも、私たちが日々頼りにしている実用的なセキュリティシステムは、完全秘匿性を実現していないという経験的事実を受け入れましょう。保護しようとするデータに関する情報は、いくらか漏れます。カルモン氏、ヴァリア氏、メダール氏の研究は、漏えいした情報から攻撃者が推測できることには限界があると示しています。当然ながら、これはビッグデータの時代に関わる問題です。」
MITの研究者らが用いた数学的手法は「統計分析で使われてきました」とラギンスキー氏は付け加えます。「しかし、情報理論的な含意はすべて新しいものです。間違いなく、多くの興味深い研究につながるでしょう。」
この記事は当初、 MIT News
著者：ラリー・ハーデスティ氏はMIT Newsのゲスト寄稿者です
画像：新しいノートパソコンを使う小学1年生。REUTERS/Jorge Silva
