Programmable and Non-Programmable Models in Security Proofs

(邦訳:安全性証明におけるプログラム可能およびプログラム不可能なモデル)

 
Mario Larangeira(マリオ・ラランジェラ)
ブラジル銀行 エンジニア

[背景]安全性証明は暗号方式に影響を与える
[問題]安全性証明におけるモデルの性質の理解する
[貢献]2つのモデルにおけるプログラム可能性概念の提案と,それらの安全性証明に対する影響を明らかにした


 安全性証明においてモデルの選択は重要である.理想化されていないモデルは標準モデルと呼ばれ,現実に最も近いので最も弱いとみなされる.このモデルによる安全性証明の構築は多くの場合困難であるだけでなく,いくつかの暗号化方式に対して証明は存在しない可能性も指摘されている.

 研究者はこれまで,ハッシュ関数などの暗号構成要素や,群および環などの代数構造の安全性証明における役割を研究するため,安全性証明モデルを構築してきた.いくつかのモデルにおいて暗号方式の安全性証明に関する数学的帰着はうまく機能するが,標準モデルとの間に矛盾が生じることがある.つまり構築されたモデルでは安全な暗号方式が,標準モデルでは安全でない場合がある.結果として,安全性証明を可能にするモデルの性質および標準モデルとの関連の理解に焦点をあてる研究分野が生まれた.

 たとえば,ランダムオラクルと呼ばれる,ハッシュ関数を理想化したモデルがある.この場合,ハッシュ関数は,“理想的''なハッシュ関数と呼ばれる数学的定義Ο,つまりランダムオラクルに置き換えられる.このモデルにおいては,すべてのアルゴリズム(敵対者Αも含む)は,入力xi のハッシュ値yi はハッシュ関数を理想化したΟから受け取る.

 


図1 帰着による典型的な安全性証明において,
帰着は署名方式を攻撃するアルゴリズムに対してランダムオラクルΟを模倣し,
メッセージm および偽造署名δ*を出力する.
 
 
 本研究では,安全性証明におけるランダムオラクルモデルの性質であるプログラム可能性を調べるため,まず証明の枠組みを再考した.この性質が許されないモデルとしてプログラム不可能なランダムオラクルがある.本研究ではフルドメインハッシュを用いた方式は妥当な仮定のもとで,プログラム不可能なモデルにおいても安全性証明が可能でことを示した.

 次に,抽象群モデルに2つのモデルを提案した.プログラム可能なものとプログラム不可能なものである.これまでの研究で示された通りプログラム不可能なモデルは弱い,つまり安全性証明を構築するのはより難しいということが確認できた.またこれまでの研究において,プログラム不可能なモデルにおいて安全でないと考えられてきたある暗号方式に対して,プログラム可能モデルにおいては安全であることを示した.同じように,より一般的なモデル,抽象環モデルでもプログラム可能なモデルとプログラム不可能なモデルの2~つを提案し,後者のほうがより弱いという,抽象群モデルと同様の結論に達した.

 結論として,ランダムオラクルモデルにおいてのみ考察されていたプログラム可能性および不可能性を,抽象環および抽象群モデルにおいても構築した.そしてこの3つのモデルは以前に考えられていたより多くの類似性をもつということを示した.ここでは,ランダムオラクルモデルは“一般化ハッシュ関数モデル”と呼ばれるにふさわしいということも示している.本研究は安全性証明に使用されるモデルの性質の理解に貢献すると同時に,これらのモデルにおける暗号方式の安全性証明の理解に寄与している.
 (2013年6月14日受付)
取得年月日:2013年3月
学位種別:博士(理学)
大学:東京工業大学



推薦文
:(アルゴリズム研究会)


暗号方式の安全性をどのように示すかについて扱う証明可能安全性についての研究である.具体的には,ランダムオラクルモデル,抽象群モデル,抽象環モデルといった3つのモデルに対して,プログラム可能性が安全性証明中で果たす役割について考察しており,分野に大きく貢献している.


著者からの一言


暗号方式の安全性の研究において,安全性証明に使用されるモデルの選択やその性質は,証明中の議論すべてに影響を与えるので重要である.また同時に,モデルは現実世界の特徴を反映する妥当なモデルでなければならない.本研究では,モデルの性質に基づいた新しい証明技術や新しいモデルを導入した.難しかったのはこのような新しいモデルや安全性証明手法の構築であった.