高速な署名方式の安全性に関する研究

概要

論文の詳細を見る
最近, 著者達はon-line上の署名生成において, 高速な署名生成を実現する2つの署名方式[7, 6]を提案した.これらの署名方式の安全性に関しては, ある種の攻撃(possible key attack)を想定した場合の考察[7]等がなされている.しかしながら, この攻撃が攻撃モデルとして妥当であるかという問題が存在する.本論文では, より厳密な安全性が得られると考えられる攻撃(one key attack[10])を想定し, これらの署名方式の安全性について考察する.安全性の証明のため, 本論文は最初に素因数分解問題に帰着する新しい問題(拡張型位探索問題)を定義し, この問題の難しさについて考察する.次にこれらの署名方式に対して, 公開鍵として用いる法nの素因数の数を3以上に増やした場合, 安全性はランダムオラクルの仮定の中で拡張型位探索問題と等価になることを示す.また, これらの手法を用いることによって, 他の署名方式の安全性についても考察する.
社団法人電子情報通信学会の論文
2001-11-02