線形符号の復号問題に基づいた強い意味で安全な公開鍵暗号方式

概要

論文の詳細を見る
暗号技術は,通信内容の秘匿にとどまらず,認証,電子商取引,コンテンツ保護など,様々な用途に利用されている.まさに,現代社会を支える基盤技術の一つであるといって過言ではない.ところが,現在広く使われているRSA,ElGamal,楕円曲線暗号などの公開鍵暗号方式,Diffie-Hellman鍵共有方式,RSA,DSA,Schnorrなどのディジタル署名方式の安全性はすべて素因数分解あるいは離散対数問題を解く難しさに基づいている.つまり,この二つの問題が効率良く解けてしまえばこれらはすべて安全に利用できなくなってしまう.実際,Shorは量子計算機上でこの二つの問題を確率的多項式時間で解く方法を提案しており,量子計算機が実現されれば現在主流の公開鍵暗号,鍵交換,ディジタル署名,及びそれらを用いた各種プロトコルは消えいく運命にある.幸い,現実的なサイズを扱える量子計算機を実現するためには超えなければならないハードルがいくつかあるため,その実現には最低50年あるいは100年以上かかるともいわれている.また,量子計算機以外の方法でこれらの問題を効率良く解く方法に関する研究も進められているが,数年以内に現実的な手法が見つかる可能性は低いと思われる.そのため,現行の方式に対して今すぐ悲観的になる必要はないが,来るべき日に備えておくことが重要であることも事実である.1978年に提案されたMcEliece暗号はこれらとは独立である線形符号の復号問題に基づいた公開鍵暗号方式であり,代替方式になり得る.しかしながら,その方式には現実的な攻撃方法がいくつか提案されており,実用には耐えられない.本論文では,これらの攻撃方法が[35]においてどのように回避され,強い意味での安全性がどのように示されたかについて,その背景にある考え方や最新の動向を交えて解説する.
2004-07-01

線形符号の復号問題に基づいた強い意味で安全な公開鍵暗号方式

スポンサーリンク

概要

著者

関連論文

スポンサーリンク