お知らせ: セキュアシステム研究部門は、2015年4月1日に改組・統合され、情報技術研究部門になりました。
以下のページ内容は、原則として2015年3月31日現在の内容となります。

研究プロジェクト
産総研 > RISEC > 研究プロジェクト > 暗号技術に関する安全性証明の高信頼化

暗号技術に関する安全性証明の高信頼化

研究の概要・背景

暗号技術に関する安全性証明とは、現実的に解くのが困難とみられているある数学的問題を用いて、「暗号技術を攻撃して破ることができたとしたら、その問題が解けてしまう」(つまり、暗号技術を破ることはその非常に難しい問題よりもさらに難しいという意味での安全性を数学的に証明することを指します。近年の実用的暗号技術(暗号化、電子署名、認証など)においては、この証明可能安全性が必須の性質とされています。

しかし、一部の暗号技術においては、証明可能安全性を持つにもかかわらず、そもそもの安全性モデルが現実的な脅威を捉えきれていないためシステム全体として安全でなくなる事例が発見されています。また、近年の高度な暗号技術に対する安全性証明は非常に長く複雑なため、一流の専門家による審査でも証明の誤りを発見できず、暗号方式の公表後に他の専門家から攻撃法を指摘されるといった事態を招いています。

研究内容

これまで捉えきれていなかった現実的脅威の発見と分析

高機能暗号技術の安全性モデルは、時として現実的な攻撃シナリオを捉えきれていない場合があります。下図はグループ署名という高機能暗号技術について、従来のモデルに含まれていないが現実的には対策すべき新しい攻撃シナリオを指摘した例です。当研究グループでは、種々の暗号技術に関する安全性モデルを再検討してより現実に適合した形へ修正する研究と、修正した安全性モデルを満たす暗号技術の開発を行っています。また、ハッシュ関数や擬似乱数生成器といった、高度な暗号技術を構成する部品となる根本的な要素技術についても安全性の検討を行っています。

gs.png

既存の安全性定義間の関係、理論限界の導出

暗号分野では、一つの暗号技術に対して異なる観点から複数の安全性定義が与えられることが多々ありますが、この安全性を満たせばこちらの安全性も自動的に成り立つ、といった安全性定義の相互関係については未知の部分も多く残っています。当研究グループでは、それら安全性定義間の関係を明らかにすることで暗号理論の体系化に努めています。

また、暗号技術の安全性と効率性は一般にトレードオフの関係にありますが、安全性を維持したまま効率を高めようとした際の、実現可能な効率の理論限界を示す研究(下図参照)にも挑戦しています。これによって、暗号理論のさらなる体系化に加えて、実は達成不可能であるような目標へ向かう研究を未然に防止することで社会の研究リソースの効果的な配分への貢献も目指しています。

impossibility.png

安全性・効率性を維持しつつ、より簡潔な安全性証明を作れる方式の提案

近年の安全性証明の長大化・複雑化は、時として一流の専門家ですら検証が困難なレベルに達しており、この傾向がさらに強まると「証明可能安全性」の方法論自体の信頼性と実効性を揺るがしかねません。そこで当研究グループでは、既存の高機能暗号技術について、強い安全性を維持したまま簡潔な安全性証明が可能となるよう構成する研究にチャレンジしています。

担当研究者

近年の主な研究成果

  • K. Nuida, G. Hanaoka, “On the security of pseudorandomized information-theoretically secure schemes”, (IEEE Transactions on Information Theory, to appear)
  • G. Hanaoka, T. Matsuda, J.C.N. Schuldt, “On the Impossibility of Constructing Efficient Key Encapsulation and Programmable Hash Functions in Prime Order Groups”, (CRYPTO2012)
  • T. Matsuda, G. Hanaoka, K. Matsuura, ”Relations between Constrained and Bounded Chosen Ciphertext Security for Key Encapsulation Mechanisms”, (PKC2012)
  • Y. Sakai, J.C.N. Schuldt, K. Emura, G. Hanaoka, K. Ohta, “On the Security of Dynamic Group Signatures”, (PKC2012)
  • K. Nuida, T. Abe, S. Kaji, T. Maeno, Y. Numata, “A Mathematical Problem for Security Analysis of Hash Functions and Pseudorandom Generators”, (IWSEC2011)